Optimizing matrix inversion and determinant.

Optimizing matrix inversion and determinant.
Reduce matrix inversion from 351 fops to 139 fops.
Added a benchmark for matrix inverse.  The rest of the patch reduces
the benchmark time from 8.3 cmsecs to 5.7 cmsecs.

[whunt, 2012-12-07 01:09:16]

Updated matrix inversion and determinant code to use a version that factors the
math in such a way to minimize number of fops.  (reduction is from 351 to 139
ops).  Here's a link to an implementation that is close (but still slightly less
optimized) to what I have added.

https://github.com/toji/gl-matrix/blob/2.0-dev/src/gl-matrix/mat4.js

[reed1, 2012-12-07 14:33:46]

adding other heads.

Do we already have a bench for these routines? If not, lets create one as part
of this CL, so we can measure the diff.

Do you think the existing unittests (in tests/) cover these two routines
adequately? If not, lets augment those as part of this CL.

[bsalomon, 2012-12-07 14:45:14]

https://codereview.appspot.com/6901046/diff/1/src/utils/SkMatrix44.cpp
File src/utils/SkMatrix44.cpp (right):

https://codereview.appspot.com/6901046/diff/1/src/utils/SkMatrix44.cpp#newcod...
src/utils/SkMatrix44.cpp:498: double a00 = fMat[0][0];
If you really want this inlined perhaps we should have a inline function rather
than two copies of this math.

[TomH, 2012-12-07 14:47:39]

+1 for inline function rather than cut-and-paste.

Otherwise LGTM, but do we need somebody hardcore like Cary to cast a critical
eye looking for overflow/stability float issues?

[whunt, 2012-12-07 18:21:46]

I would be considered hardcore in this respect =).

On 2012/12/07 14:47:39, TomH wrote:
> +1 for inline function rather than cut-and-paste.
> 
> Otherwise LGTM, but do we need somebody hardcore like Cary to cast a critical
> eye looking for overflow/stability float issues?

[whunt, 2012-12-07 18:21:52]

https://codereview.appspot.com/6901046/diff/1/src/utils/SkMatrix44.cpp
File src/utils/SkMatrix44.cpp (right):

https://codereview.appspot.com/6901046/diff/1/src/utils/SkMatrix44.cpp#newcod...
src/utils/SkMatrix44.cpp:498: double a00 = fMat[0][0];
I think you guys are assuming that this is just a call to det.  It's not, Notice
that we use the values b00-b11 in the rest of the invert.  If we were to write
an inline function that serves both det and invert it would have to return *12*
arguments or an array of 12 arguments (which would add a bunch of copying).

On 2012/12/07 14:45:14, bsalomon wrote:
> If you really want this inlined perhaps we should have a inline function
rather
> than two copies of this math.

[jamesr, 2012-12-12 03:17:00]

On 2012/12/07 14:47:39, TomH wrote:
> +1 for inline function rather than cut-and-paste.
> 
> Otherwise LGTM, but do we need somebody hardcore like Cary to cast a critical
> eye looking for overflow/stability float issues?

Can we get a decision on this from someone on the skia team, or is this ready to
land now?

[shawnsingh, 2012-12-12 06:54:37]

+1  I'm also interested in seeing this land very soon.  For what it's worth, I
think whunt's patch is effective and appropriate. =)

[TomH, 2012-12-12 10:01:44]

I don't like the code duplication, but can live with it.

Mike specifically requested a benchmark & unit tests.

[whunt, 2012-12-12 18:43:58]

On 2012/12/12 10:01:44, TomH wrote:
> I don't like the code duplication, but can live with it.
> 
> Mike specifically requested a benchmark & unit tests.

The unit tests use invert in many places.  A bad implementation would almost
certainly cause them to fail.  There is no performance test for invert.  I don't
know if I can add one with this patch (I modified it in a Chrome checkout that
doesn't include either /test or /bench from skia.)

Code duplication isn't an inherently bad thing and in this case seems like a
better option that either a function with 12 return values or a macro.  Would
you prefer one of those alternatives?

[reed1, 2012-12-12 18:45:29]

Questions around code-duplication are usually (perceived) maintenance -vs-
measure performance. Adding (or using existing) benchmarks for inverse and
determinant will help answer this.

[whunt, 2012-12-12 22:40:41]

Added a benchmark for matrix inverse.  The rest of the patch reduces
the benchmark time from 8.3 cmsecs to 5.7 cmsecs.

[whunt, 2012-12-12 23:05:07]

Optimizing matrix inversion and determinant.
Reduce matrix inversion from 351 fops to 139 fops.
Added a benchmark for matrix inverse.  The rest of the patch reduces
the benchmark time from 8.3 cmsecs to 5.7 cmsecs.

[TomH, 2012-12-13 09:55:57]

Thanks, that'll do. LGTM.
On Linux, I see a benchmark improvement of 6.66 -> 4.66.
Assuming you aren't a Skia contributor, I took the liberty of committing this as
r6775 (so that it would have a chance of rolling into Chrome today and Clank
tomorrow); please check go/skia-buildbot when you have a chance, and if it's
passed everything, close this issue.

[reed1, 2012-12-13 13:27:41]

Thanks. Do we also want a bench for determinant()?

[whunt, 2012-12-14 21:55:05]

On 2012/12/13 13:27:41, reed1 wrote:
> Thanks. Do we also want a bench for determinant()?

We don't need one now.  Invert showed up as pretty hot on the profile but det
did not.  I just went ahead and changed det because it was so trivial to do. 
We're trying to get all of this done by the branch point that's coming up soon.

[whunt, 2012-12-18 01:06:23]

Is this patch going to get committed?

On 2012/12/14 21:55:05, whunt wrote:
> On 2012/12/13 13:27:41, reed1 wrote:
> > Thanks. Do we also want a bench for determinant()?
> 
> We don't need one now.  Invert showed up as pretty hot on the profile but det
> did not.  I just went ahead and changed det because it was so trivial to do. 
> We're trying to get all of this done by the branch point that's coming up
soon.

[jamesr, 2012-12-18 01:55:50]

It did:

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


On Mon, Dec 17, 2012 at 5:06 PM, <whunt@chromium.org> wrote:

> Is this patch going to get committed?
>
>
> On 2012/12/14 21:55:05, whunt wrote:
>
>> On 2012/12/13 13:27:41, reed1 wrote:
>> > Thanks. Do we also want a bench for determinant()?
>>
>
>  We don't need one now.  Invert showed up as pretty hot on the profile
>>
> but det
>
>> did not.  I just went ahead and changed det because it was so trivial
>>
> to do.
>
>> We're trying to get all of this done by the branch point that's coming
>>
> up soon.
>
>
>
>
https://codereview.appspot.**com/6901046/<https://codereview.appspot.com/6901...
>

[whunt, 2012-12-18 02:04:12]

On 2012/12/18 01:55:50, jamesr wrote:
> It did:
> 
> http://code.google.com/p/skia/source/detail?r=6775
> 
> 
> On Mon, Dec 17, 2012 at 5:06 PM, <mailto:whunt@chromium.org> wrote:
> 
> > Is this patch going to get committed?
> >
> >
> > On 2012/12/14 21:55:05, whunt wrote:
> >
> >> On 2012/12/13 13:27:41, reed1 wrote:
> >> > Thanks. Do we also want a bench for determinant()?
> >>
> >
> >  We don't need one now.  Invert showed up as pretty hot on the profile
> >>
> > but det
> >
> >> did not.  I just went ahead and changed det because it was so trivial
> >>
> > to do.
> >
> >> We're trying to get all of this done by the branch point that's coming
> >>
> > up soon.
> >
> >
> >
> >
>
https://codereview.appspot.**com/6901046/%3Chttps://codereview.appspot.com/69...>
> >

Interesting, does the skia system not rename issues to (closed) afterwards?

[TomH, 2012-12-18 09:52:10]

On 2012/12/18 02:04:12, whunt wrote:
> 
> Interesting, does the skia system not rename issues to (closed) afterwards?

It's not just renaming, it's changing the state in the system.
That's why I asked you to do it when I committed it, because only the owner can
close an issue.

The fast way is to look at the top of the page next to the issue number and
click on the little x-in-circle.

[brian2, 2012-12-18 12:39:21]

On 2012/12/18 09:52:10, TomH wrote:
> On 2012/12/18 02:04:12, whunt wrote:
> > 
> > Interesting, does the skia system not rename issues to (closed) afterwards?
> 
> It's not just renaming, it's changing the state in the system.
> That's why I asked you to do it when I committed it, because only the owner
can
> close an issue.
> 
> The fast way is to look at the top of the page next to the issue number and
> click on the little x-in-circle.

It only closes automatically on commit if the issue owner uses gcl commit to
check in the change. Otherwise it must be closed manually.