Manually set fFilterValues in SkConvolutionFilter1D.

Manually set fFilterValues in SkConvolutionFilter1D.

Using fFilterValues.reset() or a loop of fFilterValues.push_back() is about 5x slower than calling fFilterValues.resize_back() and then looping using primitive [] and =.

This is only going to show up if you apply https://codereview.chromium.org/183763047/, where it yields about 2.5% speedup in the bitmap resize microbenchmarks on a Linux desktop. Ceteris paribus, it should actually improve rasterization time of drawBitmapRectToRect() with a resize by about 5% in Chromium.


BUG=skia:2258
R=humper@google.com

Committed: http://code.google.com/p/skia/source/detail?r=13681

[tomhudson, 2014-03-06 12:23:31]

PTAL

[humper, 2014-03-06 14:42:11]

On 2014/03/06 12:23:31, tomhudson wrote:
> PTAL

LGTM, nice find.

[tomhudson, 2014-03-06 14:42:54]

The CQ bit was checked by tomhudson@google.com

[commit-bot: I haz the power, 2014-03-06 14:43:02]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/tomhudson@chromium.org/184323003/1

[commit-bot: I haz the power, 2014-03-06 14:56:59]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2014-03-06 14:57:00]

Commit queue rejected this change because the description was changed
between the time the change entered the commit queue and the time it
was ready to commit. You can safely check the commit box again.

[tomhudson, 2014-03-06 14:57:23]

The CQ bit was checked by tomhudson@google.com

[commit-bot: I haz the power, 2014-03-06 14:57:32]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/tomhudson@chromium.org/184323003/1

[commit-bot: I haz the power, 2014-03-06 14:57:49]

Change committed as 13681

[rmistry, 2014-03-06 15:40:27]

On 2014/03/06 14:57:49, I haz the power (commit-bot) wrote:
> Change committed as 13681

This CL has been reverted in
https://code.google.com/p/skia/source/detail?r=13683

[tomhudson, 2014-03-06 17:01:14]

Understand my error now. fFilterValues[] is a single array, not a separate array
for each filter. Easy to fix, but no longer obvious we can get as much of a
performance boost here. Will time it tomorrow.

[tomhudson, 2014-03-06 18:01:08]

Patch set two is correct (as far as gm on Linux is concerned), but yields closer
to 1% speedup. I think we could probably eke out a bit more, but this approach
doesn't have as much potential as I'd hoped; perhaps waiting for Ian and Mike to
agree about rewriting SkTArray is the right course here.

(From the assembly I'm guessing that the bottleneck is in checkRealloc() calling
SkTArrayExt::copyAndDelete<T>().)

[mtklein, 2014-03-06 18:21:08]

On 2014/03/06 18:01:08, tomhudson wrote:
> Patch set two is correct (as far as gm on Linux is concerned), but yields
closer
> to 1% speedup. I think we could probably eke out a bit more, but this approach
> doesn't have as much potential as I'd hoped; perhaps waiting for Ian and Mike
to
> agree about rewriting SkTArray is the right course here.
> 
> (From the assembly I'm guessing that the bottleneck is in checkRealloc()
calling
> SkTArrayExt::copyAndDelete<T>().)

Ah, good to know we've got a place where speeding up SkTArray matters.  I'd been
treating "figure out SkTArray SkTDArray etc" as low priority refactoring, but I
think this bumps it up to medium. :)

[mtklein, 2014-03-06 18:24:38]

On 2014/03/06 18:21:08, mtklein wrote:
> On 2014/03/06 18:01:08, tomhudson wrote:
> > Patch set two is correct (as far as gm on Linux is concerned), but yields
> closer
> > to 1% speedup. I think we could probably eke out a bit more, but this
approach
> > doesn't have as much potential as I'd hoped; perhaps waiting for Ian and
Mike
> to
> > agree about rewriting SkTArray is the right course here.
> > 
> > (From the assembly I'm guessing that the bottleneck is in checkRealloc()
> calling
> > SkTArrayExt::copyAndDelete<T>().)
> 
> Ah, good to know we've got a place where speeding up SkTArray matters.  I'd
been
> treating "figure out SkTArray SkTDArray etc" as low priority refactoring, but
I
> think this bumps it up to medium. :)

Actually, have I got it right that fFilterValues is just an SkTArray<short>?  If
that's the case, you can probably get a big, dare I say bigass, speedup just by
switching to SkTDArray.

[tomhudson, 2014-03-07 11:18:03]

On 2014/03/06 18:24:38, mtklein wrote:
> Actually, have I got it right that fFilterValues is just an SkTArray<short>? 
If
> that's the case, you can probably get a big, dare I say bigass, speedup just
by
> switching to SkTDArray.

Naive change in code produces zero change in performance (within noise):

+#include "SkTDArray.h"

+        //fFilterValues.push_back( val );
+        fFilterValues.append( val );

+    //SkTArray<ConvolutionFixed> fFilterValues;
+    SkTDArray<ConvolutionFixed> fFilterValues;

+        //fFilterValues.resize_back(initialOffset + filterLength);
+        fFilterValues.setCount(initialOffset + filterLength);

Patch set 4 is a bit more aggressive: if we assume that we have a square filter,
when we see the first bit of length L (including padding zeroes), allocate L^2.
This gets rid of all the incremental allocations for the square-filter special
case, which I believe is by far the most common. But since we landed
https://codereview.chromium.org/188743002 for a 2x speedup in that special case
anyway, it's only offering to trim 1-2% off the microbenchmarks. We're getting
closer to a (Linux) profile dominated by convolution, as you might hope for:

+  44.52%  [.] void convolveVertically_SSE2<false>(short const*, int, unsigned
char* const*, int,
+  26.82%  [.] convolve4RowsHorizontally_SSE2(unsigned char const**,
SkConvolutionFilter1D const&,
+   6.29%  [.] __memcpy_ssse3_back
+   5.04%  [.]
_ZN14SkResizeFilter14computeFiltersEiiifP21SkConvolutionFilter1DRK18SkConvolutionPr
+   3.33%  [.] SkMitchellFilter::evaluate(float) const
+   2.69%  [.] BGRAConvolve2D(unsigned char const*, int, bool,
SkConvolutionFilter1D const&, SkCon
+   1.31%  [.] convolveHorizontally_SSE2(unsigned char const*,
SkConvolutionFilter1D const&, unsig
+   0.84%  [.] SkConvolutionFilter1D::AddFilter(int, short const*, int)
+   0.71%  [.] _int_malloc

The surprising-to-me memcpy is supposedly because we're calling
SkMatrix::mapRect() with an identity matrix an AWFUL LOT. In one of the two
forms this ends up copying a rect over itself?

Patch set 4 is not for commit because it breaks non-square filters; but is the
modest over-allocation worth pursuing? (If filters are circular, we're
allocating 4r^2 instead of pi*r^2, but it's a single allocation that gets avoids
fragmentation or realloc copying.