Improve performance of matrix inversion.

Improve performance of matrix inversion.

The inversion of scale+translate matrices was using 6 division
operations when it could be using 3. Also, general affine
matrices do not need to compute perspective components of the
matrix. This patch updates the matrix inversion with those
optimizations, and includes benchmark code to exercise those
paths.

[shawnsingh, 2013-08-19 05:45:00]

Please take a look.

This improves the 3x4 affine inversion as well as scale+translate matrix
inversions.

Benchmark results on a linux z620 machine:

- Scale+translate matrix inversion is approximately 40% faster (!!)  nice win,
since this is going to be a very common matrix case.

- Affine without perspective inversion is approximately 7-10% faster.

- There is a subtle minor tradeoff, it seemed that the performance of inverting
a perspective matrix may be approximately 1% slower.  But this was very well
within the noise of my benchmarking so I can't be certain.  In any case, I think
it's a good tradeoff since perspective matrices are expected to be the least
common case.

[jvanverth1, 2013-08-19 20:41:44]

Very nice! Some comments below.

https://codereview.chromium.org/23296006/diff/1/bench/Matrix44Bench.cpp
File bench/Matrix44Bench.cpp (right):

https://codereview.chromium.org/23296006/diff/1/bench/Matrix44Bench.cpp#newco...
bench/Matrix44Bench.cpp:109: 
We may want to submit this as a separate change first, just to get the
baselines.

https://codereview.chromium.org/23296006/diff/1/src/utils/SkMatrix44.cpp
File src/utils/SkMatrix44.cpp (right):

https://codereview.chromium.org/23296006/diff/1/src/utils/SkMatrix44.cpp#newc...
src/utils/SkMatrix44.cpp:519: 
Did you try optimizing this and the determinant in the non-perspective case?
For example, b02 would end up being 0, which means the third term in the
determinant is 0 as well.

https://codereview.chromium.org/23296006/diff/1/src/utils/SkMatrix44.cpp#newc...
src/utils/SkMatrix44.cpp:556: 
Looks like there should be some optimization fruit here as well -- in the
non-perspective case, a number of the last terms would be 0, or 1 * element.

[shawnsingh, 2013-08-20 04:13:59]

Thanks for the feedback - it worked out great.

1. Benchmarks and unit tests added in https://codereview.chromium.org/22886010/

2. The new performance numbers are just as good as before, but now the affine
case performs an additional 40% faster!   So basically overall, for
scale/translates and affine without perspective, this patch achieves
approximately a 1.8x -1.9x perf improvement over the existing implementation. 
Great win since those are common cases.

3. To address your comments, I felt it's better to simply create an entirely new
code path for the affine case.   Were you planning to re-land the determinant
check?   If that happens after this patch, there would be two determinant()
checks now that need to be updated instead of just one.

[jvanverth1, 2013-08-20 14:16:54]

LGTM, just one comment below. 

If you approve my updated test for the determinant check, then
it should be going in shortly. Or I could wait until this
change goes in and tweak both locations.

https://codereview.chromium.org/23296006/diff/12001/src/utils/SkMatrix44.cpp
File src/utils/SkMatrix44.cpp (right):

https://codereview.chromium.org/23296006/diff/12001/src/utils/SkMatrix44.cpp#...
src/utils/SkMatrix44.cpp:522: // then its bottom row is (0, 0, 0, 1).
Assuming our indexing is (row, column) this should be right-most column instead
of bottom row.

[reed1, 2013-08-20 15:14:13]

https://codereview.chromium.org/23296006/diff/12001/src/utils/SkMatrix44.cpp
File src/utils/SkMatrix44.cpp (right):

https://codereview.chromium.org/23296006/diff/12001/src/utils/SkMatrix44.cpp#...
src/utils/SkMatrix44.cpp:520: if (!(this->getType() & kPerspective_Mask)) {
At some point we should consider breaking each of the (somewhat long) sections
into helper functions (that get inlined), just to make the code more readable.

e.g.
   invert3x4()
   invertpersp()

Not public functions, just ways to organize our impl

[shawnsingh, 2013-08-21 18:11:20]

I have been waiting for the new perf benchmarks to show up on the skia bots
before landing this, but I'm not seeing them.  Is there something additional I
need to do to make them show up?  Here is an example graph where I'm looking. 
The new benchmarks I would expect to be named matrix44_invertaffine,
matrix44_invertscaletranslate, etc.

Otherwise, yes I updated the determinant check based on what JimVV landed, and I
can submit a follow-up patch that separates things into inlined helper
functions. =)

[jvanverth1, 2013-08-21 19:02:49]

On 2013/08/21 18:11:20, shawnsingh wrote:
> I have been waiting for the new perf benchmarks to show up on the skia bots
> before landing this, but I'm not seeing them.  Is there something additional I
> need to do to make them show up?  Here is an example graph where I'm looking. 
> The new benchmarks I would expect to be named matrix44_invertaffine,
> matrix44_invertscaletranslate, etc.
> 
> Otherwise, yes I updated the determinant check based on what JimVV landed, and
I
> can submit a follow-up patch that separates things into inlined helper
> functions. =)

Not sure what's going on there. My understanding is that DEF_BENCH should add
them
to the graphs. I'd check with Ben Chen.

[shawnsingh, 2013-08-22 20:42:05]

Commited this as https://code.google.com/p/skia/source/detail?r=10883

While committing the gcl script seemed to crash by fluke so I'm closing this
manually.