Change SkBlurImageFilter to use fixed-point division. Yields ~1.8X speedup on

Change SkBlurImageFilter to use fixed-point division. Yields ~1.8X speedup on
MacBookPro.

Note: this will require defining SK_DISABLE_BLUR_DIVISION_OPTIMIZATION in
Chrome, a la https://codereview.chromium.org/49973005.

R=mtklein@google.com

Committed: https://code.google.com/p/skia/source/detail?r=12113

[Stephen White, 2013-11-04 01:23:20]

reed@: PTAL. Thanks!

[Tom Hudson, 2013-11-04 11:34:02]

If you're getting rid of integer division here, this could be a huge win for
blurs on Android, too. Did you just get that 1.8x number from skia/bench/?

[Stephen White, 2013-11-04 13:05:39]

On 2013/11/04 11:34:02, Tom Hudson wrote:
> If you're getting rid of integer division here, this could be a huge win for
> blurs on Android, too. Did you just get that 1.8x number from skia/bench/?

Yeah, that's from the bench. Note that these are the RGBA blurs used for
-webkit-filter: blur(), not the mask blurs used for shadows, which already have
this optimization.

I'll try to get some Android numbers when I'm in the office.

[mtklein, 2013-11-04 15:19:45]

On 2013/11/04 13:09:20, reed1 wrote:

lgtm

I see this as 1.5-1.9x faster on both my desktop and 1.5-1.8x on the Nexus 4.

Mike added me here because I've been incidentally looking at this code for a
little while.  Bottlenecks were definitely division, well fixed here, and then
memory loads on the leading pixel, particularly in Y.  Looks like that
expression (sptr + (bottomOffset + 1) * srcStride) is too tricky for the
processor to prefetch.  If we add a manual prefetch of the leading pixels, we
can make this a solid 2.0-2.1x faster on my desktop, but that pixel load still
takes up ~30% of the runtime.  Been struggling to figure out why prefetch
doesn't help or hurt the Nexus 4 (it does show up in the disassembly).

My next step here is to write up a CL for prefetch.  Will send it out to you
all.  After that, any interest in getting this SIMD'd?  I've got a somewhat
unconventional new approach to SSE and NEON that's just begging for a place to
prove its worth.

[Tom Hudson, 2013-11-04 15:24:50]

Tangent: Sami pointed out that the performance of infinite impulse response
blurs shouldn't be dependent on kernel size. Have we experimented with those?
Would it be worth changing to an IIR implementation when the kernel is large and
so we get slow? Or are large kernels so rare or obviously bad programming by web
devs that we needn't worry about them?

[Stephen White, 2013-11-04 15:32:16]

On 2013/11/04 15:19:45, mtklein wrote:
> On 2013/11/04 13:09:20, reed1 wrote:
> 
> lgtm
> 
> I see this as 1.5-1.9x faster on both my desktop and 1.5-1.8x on the Nexus 4.
> 
> Mike added me here because I've been incidentally looking at this code for a
> little while.  Bottlenecks were definitely division, well fixed here, and then
> memory loads on the leading pixel, particularly in Y.  Looks like that
> expression (sptr + (bottomOffset + 1) * srcStride) is too tricky for the
> processor to prefetch.  If we add a manual prefetch of the leading pixels, we
> can make this a solid 2.0-2.1x faster on my desktop, but that pixel load still
> takes up ~30% of the runtime.  Been struggling to figure out why prefetch
> doesn't help or hurt the Nexus 4 (it does show up in the disassembly).

What I've done in the mask blur is to add an option to transpose in Y on write.
Then all passes become reads in X: blurX, blurX, blurXTranspose, blurX, blurX,
blurXTranspose.
This plays much better with cache. I'll probably give that a shot here.

> My next step here is to write up a CL for prefetch.  Will send it out to you
> all.  After that, any interest in getting this SIMD'd?  I've got a somewhat
> unconventional new approach to SSE and NEON that's just begging for a place to
> prove its worth.

I'm working on a SSE2 impl now. It might be worth trying two different
approaches and seeing which is faster, 
though, since there are so many ways to skin a cat in SSE2.

[mtklein, 2013-11-04 15:41:29]

On 2013/11/04 15:32:16, Stephen White wrote:
> On 2013/11/04 15:19:45, mtklein wrote:
> > On 2013/11/04 13:09:20, reed1 wrote:
> > 
> > lgtm
> > 
> > I see this as 1.5-1.9x faster on both my desktop and 1.5-1.8x on the Nexus
4.
> > 
> > Mike added me here because I've been incidentally looking at this code for a
> > little while.  Bottlenecks were definitely division, well fixed here, and
then
> > memory loads on the leading pixel, particularly in Y.  Looks like that
> > expression (sptr + (bottomOffset + 1) * srcStride) is too tricky for the
> > processor to prefetch.  If we add a manual prefetch of the leading pixels,
we
> > can make this a solid 2.0-2.1x faster on my desktop, but that pixel load
still
> > takes up ~30% of the runtime.  Been struggling to figure out why prefetch
> > doesn't help or hurt the Nexus 4 (it does show up in the disassembly).
> 
> What I've done in the mask blur is to add an option to transpose in Y on
write.
> Then all passes become reads in X: blurX, blurX, blurXTranspose, blurX, blurX,
> blurXTranspose.
> This plays much better with cache. I'll probably give that a shot here.
> 
> > My next step here is to write up a CL for prefetch.  Will send it out to you
> > all.  After that, any interest in getting this SIMD'd?  I've got a somewhat
> > unconventional new approach to SSE and NEON that's just begging for a place
to
> > prove its worth.
> 
> I'm working on a SSE2 impl now. It might be worth trying two different
> approaches and seeing which is faster, 
> though, since there are so many ways to skin a cat in SSE2.

Both SGTM.  The transposition I figure is going to be a bigger win than
prefetch.  Will send that out anyway as FYI.

[Stephen White, 2013-11-04 15:42:50]

On 2013/11/04 15:24:50, Tom Hudson wrote:
> Tangent: Sami pointed out that the performance of infinite impulse response
> blurs shouldn't be dependent on kernel size. Have we experimented with those?
> Would it be worth changing to an IIR implementation when the kernel is large
and
> so we get slow? Or are large kernels so rare or obviously bad programming by
web
> devs that we needn't worry about them?

The sliding-window box blur here is (or should be) independent of kernel size in
terms of big-O complexity. It might still a bit sensitive to it once the kernel
is bigger than cache size, but I haven't noticed 
yet. We use 3 box blurs to approximate the Gaussian (thanks to central limit
theorem), and ignore values beyond 3 sigma.

[Stephen White, 2013-11-04 16:07:45]

Committed patchset #2 manually as r12113 (presubmit successful).