Rewriting MatrixConvolution image filter with SSE and AVX2

Rewriting MatrixConvolution image filter with SSE and AVX2

1. Hottest part of SkMatrixConvolutionImageFilter was moved
  to opts/ folder.
2. Create SSE implementation for MatrixConvolution.
  Perf.gain ~ 2x over plain implementation.
3. Create AVX2 implementation for MatrixConvolution.
  Perf.gain ~ 2.5x over plain implementation.
4. Add runtime check for AVX2 availability (AVX2 implementation
  will be uses only if AVX2 is supported by HW).

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1881903004
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot

[Sergey M, 2016-04-12 19:39:42]

Description was changed from

==========
Rewriting MatrixConvolution image filter with SSE and AVX2

1. Hottest part of SkMatrixConvolutionImageFilter was moved
  to opts/ folder.
2. Create SSE implementation for MatrixConvolution.
  Perf.gain ~ 2x over plain implementation.
3. Create AVX2 implementation for MatrixConvolution.
  Perf.gain ~ 2.5x over plain implementation.
4. Add runtime check for AVX2 availability (AVX2 implementation
  will be uses only if AVX2 is supported by HW).

BUG=skia:
==========

to

==========
Rewriting MatrixConvolution image filter with SSE and AVX2

1. Hottest part of SkMatrixConvolutionImageFilter was moved
  to opts/ folder.
2. Create SSE implementation for MatrixConvolution.
  Perf.gain ~ 2x over plain implementation.
3. Create AVX2 implementation for MatrixConvolution.
  Perf.gain ~ 2.5x over plain implementation.
4. Add runtime check for AVX2 availability (AVX2 implementation
  will be uses only if AVX2 is supported by HW).

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

[Sergey M, 2016-04-12 19:41:44]

Description was changed from

==========
Rewriting MatrixConvolution image filter with SSE and AVX2

1. Hottest part of SkMatrixConvolutionImageFilter was moved
  to opts/ folder.
2. Create SSE implementation for MatrixConvolution.
  Perf.gain ~ 2x over plain implementation.
3. Create AVX2 implementation for MatrixConvolution.
  Perf.gain ~ 2.5x over plain implementation.
4. Add runtime check for AVX2 availability (AVX2 implementation
  will be uses only if AVX2 is supported by HW).

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

to

==========
Rewriting MatrixConvolution image filter with SSE and AVX2

1. Hottest part of SkMatrixConvolutionImageFilter was moved
  to opts/ folder.
2. Create SSE implementation for MatrixConvolution.
  Perf.gain ~ 2x over plain implementation.
3. Create AVX2 implementation for MatrixConvolution.
  Perf.gain ~ 2.5x over plain implementation.
4. Add runtime check for AVX2 availability (AVX2 implementation
  will be uses only if AVX2 is supported by HW).

BUG=skia:
GOLD_TRYBOT_URL=
https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&is...
CQ_EXTRA_TRYBOTS=client.skia:Test-Ubuntu-GCC-GCE-CPU-AVX2-x86_64-Release-SKNX_NO_SIMD-Trybot
==========

[Sergey M, 2016-04-12 19:41:44]

melnikov.sergey.v@gmail.com changed reviewers:
+ mtklein@google.com, senorblanco@google.com

[Sergey M, 2016-04-12 19:46:05]

Could you take a look at my changes: I implemented MatrixConvolution image
filter with SSE and AVX.

https://codereview.chromium.org/1881903004/diff/1/gyp/opts.gyp
File gyp/opts.gyp (right):

https://codereview.chromium.org/1881903004/diff/1/gyp/opts.gyp#newcode172
gyp/opts.gyp:172: [ 'not skia_android_framework', { 'cflags': [ '-mavx2',
'-mtune=core-avx2' ] }],
Add additional tuning parameter. This flag enable low-level tuning for
micro-architecture besides just enabling instruction set.

[Stephen White, 2016-04-12 20:01:58]

senorblanco@chromium.org changed reviewers:
+ senorblanco@chromium.org

[Stephen White, 2016-04-12 20:01:59]

Thanks for the patch! This is promising stuff.

mtklein@ should definitely take a look as well.

https://codereview.chromium.org/1881903004/diff/1/gyp/opts.gypi
File gyp/opts.gypi (right):

https://codereview.chromium.org/1881903004/diff/1/gyp/opts.gypi#newcode46
gyp/opts.gypi:46: '<(skia_src_path)/opts/SkOpts_sse_sse2.cpp',
It seems strange to add a file just for this one function. Mike would know
better than I the current way to do these integrations, in Skia, but perhaps the
SSE path should just be integrated directly into
SkMatrixConvolutionImageFilter.cpp (protected by a compile-time flag), and we
just switch between the SSE-or-not version and the AVX2 version at runtime?

https://codereview.chromium.org/1881903004/diff/1/src/effects/SkMatrixConvolu...
File src/effects/SkMatrixConvolutionImageFilter.cpp (right):

https://codereview.chromium.org/1881903004/diff/1/src/effects/SkMatrixConvolu...
src/effects/SkMatrixConvolutionImageFilter.cpp:176: if (fConvolveAlpha) {
IIRC, this did actually have a measurable impact when I original wrote it
(hence, the template param). Is that no longer the case?

https://codereview.chromium.org/1881903004/diff/1/src/effects/SkMatrixConvolu...
src/effects/SkMatrixConvolutionImageFilter.cpp:206: src,
Please use spaces instead of tabs.

https://codereview.chromium.org/1881903004/diff/1/src/opts/SkMatrixConvolutio...
File src/opts/SkMatrixConvolutionImageFilter_opts.h (right):

https://codereview.chromium.org/1881903004/diff/1/src/opts/SkMatrixConvolutio...
src/opts/SkMatrixConvolutionImageFilter_opts.h:40: SkPMColor s =
*src.getAddr32(x + cx - kernelOffset.fX,
Rather than maintain a no-opts and SSE2 flavour, another way to do this might be
to use the Sk4f classes, which give SSE2 and NEON automatically. The Sk4f
version could be done directly in SkMatrixConvolutionImageFilter, and the AVX2
version could be switched at runtime.

https://codereview.chromium.org/1881903004/diff/1/src/opts/SkMatrixConvolutio...
File src/opts/SkMatrixConvolutionImageFilter_opts_SSE.cpp (right):

https://codereview.chromium.org/1881903004/diff/1/src/opts/SkMatrixConvolutio...
src/opts/SkMatrixConvolutionImageFilter_opts_SSE.cpp:61: ?
SkClampMax(SkScalarFloorToInt(SkScalarMul(sumA, gain) + bias), 255)
Using Sk4/Sk4f might also allow us to benefit from SSE2 integer ops here,
instead of resorting to scalar.

[mtklein, 2016-04-12 20:07:19]

I too would rather start with an Sk4f version inline in
SkMatrixConvolutionImageFilter.cpp.
After that lands I'd be happy to see if the extra speedup from AVX2 merits the
extra complexity.

But the first question to answer is, do we care that
SkMatrixConvolutionImageFilter is slow?

[Sergey M, 2016-04-12 20:28:19]

On 2016/04/12 20:07:19, mtklein wrote:
> I too would rather start with an Sk4f version inline in
> SkMatrixConvolutionImageFilter.cpp.
> After that lands I'd be happy to see if the extra speedup from AVX2 merits the
> extra complexity.
> 
> But the first question to answer is, do we care that
> SkMatrixConvolutionImageFilter is slow?

Initially (without my fix), Nanobench get about 24ms for matrixconvolution test.
First, I implemented it with SkNx. I discovered slow down. Nanobench time was
about 30ms for matrixconvolution. I profiled this code and found out plenty
issues. The most significant was very slow byte -> float converting (but it's
not the only reason of slow down, there are more reasons). Just for comparison:
SSE implementation takes about 12ms, AVX2 - 10ms on my Intel HASWELL PC
(according to nanobench).

Regarding SkMatrixConvolutionImageFilter speed. This function was among the TOP
hottest functions in nanobench and the most easy to improve (I took a look at
the code and found out a hot loop was easy-to-vectorize).

[mtklein, 2016-04-12 20:41:52]

Hmm, that's odd.  Why don't you post up your SkNx version so I can take a look? 
I did a quick hack up of just the inner loop here, and it seems pretty
promising, dropping from ~12ms to ~8ms. 
https://codereview.chromium.org/1886553002

Are you working towards some particular goal here or just looking through Skia
for slow code to speed up?  You don't care particularly about
SkMatrixConvolutionImageFilter, do you?  If so, that's okay, but if not I might
be able to point you toward code that has more impact.  I'm not yet convinced
that this particular image filter is important enough to merit any extra code.

[Sergey M, 2016-04-12 21:10:30]

On 2016/04/12 20:41:52, mtklein wrote:
> Hmm, that's odd.  Why don't you post up your SkNx version so I can take a
look? 
> I did a quick hack up of just the inner loop here, and it seems pretty
> promising, dropping from ~12ms to ~8ms. 
> https://codereview.chromium.org/1886553002
> 
> Are you working towards some particular goal here or just looking through Skia
> for slow code to speed up?  You don't care particularly about
> SkMatrixConvolutionImageFilter, do you?  If so, that's okay, but if not I
might
> be able to point you toward code that has more impact.  I'm not yet convinced
> that this particular image filter is important enough to merit any extra code.

Thanks! I'll take a look at your implementation, compare with my one and will
try to find out why my implementation is worse.
Yes, I'm looking for a slow code to speed up.

[mtklein, 2016-04-12 21:11:47]

On 2016/04/12 at 21:10:30, Melnikov.Sergey.V wrote:
> On 2016/04/12 20:41:52, mtklein wrote:
> > Hmm, that's odd.  Why don't you post up your SkNx version so I can take a
look? 
> > I did a quick hack up of just the inner loop here, and it seems pretty
> > promising, dropping from ~12ms to ~8ms. 
> > https://codereview.chromium.org/1886553002
> > 
> > Are you working towards some particular goal here or just looking through
Skia
> > for slow code to speed up?  You don't care particularly about
> > SkMatrixConvolutionImageFilter, do you?  If so, that's okay, but if not I
might
> > be able to point you toward code that has more impact.  I'm not yet
convinced
> > that this particular image filter is important enough to merit any extra
code.
> 
> Thanks! I'll take a look at your implementation, compare with my one and will
try to find out why my implementation is worse.
> Yes, I'm looking for a slow code to speed up.

Patchset 2 on that same code review link now vectorizes the per-pixel tail too. 
Looks like a ~2x speedup on the matrixconvolution benches.

[Sergey M, 2016-04-13 22:47:30]

On 2016/04/12 21:11:47, mtklein wrote:
> On 2016/04/12 at 21:10:30, Melnikov.Sergey.V wrote:
> > On 2016/04/12 20:41:52, mtklein wrote:
> > > Hmm, that's odd.  Why don't you post up your SkNx version so I can take a
> look? 
> > > I did a quick hack up of just the inner loop here, and it seems pretty
> > > promising, dropping from ~12ms to ~8ms. 
> > > https://codereview.chromium.org/1886553002
> > > 
> > > Are you working towards some particular goal here or just looking through
> Skia
> > > for slow code to speed up?  You don't care particularly about
> > > SkMatrixConvolutionImageFilter, do you?  If so, that's okay, but if not I
> might
> > > be able to point you toward code that has more impact.  I'm not yet
> convinced
> > > that this particular image filter is important enough to merit any extra
> code.
> > 
> > Thanks! I'll take a look at your implementation, compare with my one and
will
> try to find out why my implementation is worse.
> > Yes, I'm looking for a slow code to speed up.
> 
> Patchset 2 on that same code review link now vectorizes the per-pixel tail
too. 
> Looks like a ~2x speedup on the matrixconvolution benches.

As I see you've already committed a version with SkNx implementation.
So, I think my review is obsolete except AVX2 implementation. How should I
rewrite it with SkNx? If I just add SkNx specializations for AVX2 types, I
should guard my code with #ifdef/#endif (but I believe no one will specify AVX2
as target platform, therefore my AVX2 version will never be used). So, I think
it's better to use runtime check. Is it possible to have few algorithm
specializations and switch between them at run-time using SkNx? Or I should use
SkOpts for runtime check/switching?

BTW, Mike, could you advise any performance-critical place in SKIA to take a
look?

[mtklein, 2016-04-14 00:05:55]

> As I see you've already committed a version with SkNx implementation.

It's not been committed.  I wanted to give you the chance to comment or work on
it if you think it should be done differently.  If it looks like what you'd
write, we can certainly land it!

I'm a little skeptical about advancing this particular code beyond a simple
inline SkNx implementation.  The simpler we can keep our code the easier it is
to refactor and implement new features... adding SkOpts implementations of code
makes that rather more difficult.  This particular routine is not a very
commonly used part of code, so it'd have to speed up massively to really warrant
extra code complexity.  (You'll notice the SkNx version is simpler than the
original portable code...)

Let me ask around and see if I can find a place that'd benefit from AVX2 and is
quiet enough to let you hack away at without fear of someone tromping in and
moving the code out from under you.  Maybe we can start with some of the things
that are already in SkOpts.  Want to take a look at blit_row_color32()?  That
routine blends a constant color over a destination array.  It should be pretty
straightforward to take the approach in src/opts/SkOpts_sse41.cpp and double the
vector width?

I took quick look today and I think that as far as usage goes, about 25% of our
users on x86 have AVX2, about 65% have AVX, and 85% have SSE 4.1.  So of course
the more we stick to older instruction sets, the more people we affect, but 25%
is a pretty big chunk of users already.  It's probably a good time to start
looking at AVX2 seriously.

[Sergey M, 2016-04-14 23:53:12]

On 2016/04/14 00:05:55, mtklein wrote:
> > As I see you've already committed a version with SkNx implementation.
> 
> It's not been committed.  I wanted to give you the chance to comment or work
on
> it if you think it should be done differently.  If it looks like what you'd
> write, we can certainly land it!
> 
> I'm a little skeptical about advancing this particular code beyond a simple
> inline SkNx implementation.  The simpler we can keep our code the easier it is
> to refactor and implement new features... adding SkOpts implementations of
code
> makes that rather more difficult.  This particular routine is not a very
> commonly used part of code, so it'd have to speed up massively to really
warrant
> extra code complexity.  (You'll notice the SkNx version is simpler than the
> original portable code...)
> 
> Let me ask around and see if I can find a place that'd benefit from AVX2 and
is
> quiet enough to let you hack away at without fear of someone tromping in and
> moving the code out from under you.  Maybe we can start with some of the
things
> that are already in SkOpts.  Want to take a look at blit_row_color32()?  That
> routine blends a constant color over a destination array.  It should be pretty
> straightforward to take the approach in src/opts/SkOpts_sse41.cpp and double
the
> vector width?
> 
> I took quick look today and I think that as far as usage goes, about 25% of
our
> users on x86 have AVX2, about 65% have AVX, and 85% have SSE 4.1.  So of
course
> the more we stick to older instruction sets, the more people we affect, but
25%
> is a pretty big chunk of users already.  It's probably a good time to start
> looking at AVX2 seriously.

I believe it doesn't worth to rewrite your code. As you told, It doesn't involve
platform-specific SIMD implementation directly and is portable across all
platforms. It defenetly helps to maintain, refactor and support this code in
future. I believe your implementation is really good! Generated assembly
instructions are very nice, without anything exactly redundant. I believe it
will be difficult to rewrite this code significantly more optimal way without
'hacks'.

I believe the only value for my code is AVX2 implementation now. But it will be
wrong to use here SkOpts for AVX2 implementation only. Moreover, AVX2 doesn't
bring as significant boost as SSE implementation. 
I'll think how to enable AVX2 in SkNx with 'proper' way. I believe, first, I'll
think how to avoid a concrete vector length in algorithms with SkNx (I mean, for
example, you wrote particular vector length in your code: SkNx<4, float>. It
inhibited moving forward to AVX/AVX2 and so).
I'm going to abandon this review. If I find the right way to implement it with
AVX2, I'll send one more patch set.

Thank you for advice, I'll take a look at this function on this weekends!

About looking at AVX2. What do you think, what is the preferable way to enable
AVX/AVX2? Guard AVX/AVX2 code with #ifdef/#endif or implement a runtime check
with SkOpts or make in-place runtime check?

[mtklein, 2016-04-15 14:03:41]

> I'll think how to enable AVX2 in SkNx with 'proper' way. I believe, first,
I'll think how to avoid a concrete vector length in algorithms with SkNx (I
mean, for example, you wrote particular vector length in your code: SkNx<4,
float>. It inhibited moving forward to AVX/AVX2 and so).

I agree that it'd be nicer to not have to know the register length.  But for
now, we could always just rewrite this in terms Sk8f.  SkNx<N,T> falls back
transparently to 2 SkNx<N/2,T> if it has no native support for N T's.

> About looking at AVX2. What do you think, what is the preferable way to enable
AVX/AVX2? Guard AVX/AVX2 code with #ifdef/#endif or implement a runtime check
with SkOpts or make in-place runtime check?

For AVX2, definitely a runtime check.  There are no clients of Skia that I'm
aware of building with -mavx2 globally, or -mavx, for that matter.  There are a
few up to -msse4.1.  But it's best to think SSE2 and NEON are nearly guaranteed
at compile time, SSE3 and SSSE3 are very likely at compile time, and anything
beyond that is unlikely.

I've just reorganized how to do these runtime checks.  Hopefully that change
sticks.
   #include "SkCpu.h"
   ...
   if (SkCpu::Supports(SkCpu::AVX2)) { 
       ...
   }