SkMatrix::invert propagate typeMask flags for some simple cases

[junov1, 2012-07-09 17:55:26]

PTAL.

SkMatrix::computeTypeMask was showing up as a hotspot in a lot of 2D canvas
benchmarks in Chrome. The problem is that the type mask has to be computed from
scratch on inverse matrices generated in SkCanvas::getClipBounds, which is
called on every primitive draw (via quickReject).

This small change gives a 10-15% perf boost on several benchmarks in Chrome 22.

[reed1, 2012-07-09 18:09:33]

1. add comment in the code describing why we can only do this for
rectstaysrect()
2. do we have an existing bench that sees a perf-win?

[TomH, 2012-07-09 18:29:53]

This has been a hotspot before; we'd addressed the worst of it then, but there
are ideas for further optimizations scattered around the skia bug tracker.
Sounds like yours is even better than those.

Which 2D canvas benchmarks?

[junov1, 2012-07-09 18:38:55]

On 2012/07/09 18:29:53, TomH wrote:

> Which 2D canvas benchmarks?

In particular, I did a lot of profiling of several of the sub benchmarks from
this benchmark suite:
https://github.com/sibblingz/PerfMarks 

The Canvas 2D full clear tests get a significant speedup from this change.

[reed1, 2012-07-09 18:40:19]

lets write a bench (if we don't already have one) to test this (and be sure the
change doesn't slow down previous benches)

[junov1, 2012-07-09 21:01:33]

On 2012/07/09 18:40:19, reed1 wrote:
> lets write a bench (if we don't already have one) to test this (and be sure
the
> change doesn't slow down previous benches)

Argh! Turns out this change significantly harms cases where false ==
rectStaysRect(), as well as cases where the typeMask of the matrix to be
inverted is not previously computed.

I'll try to see if there's a better way to implement this. If not, I will at
least submit the shiny new benchmarks I wrote this afternoon...

[TomH, 2012-07-09 21:09:58]

If you're seeing any hotspot contribution from computePerspectiveTypeMask(), I
can't help noticing that I didn't copy the #ifdef'd optimization there from
computeTypeMask(). :(

[TomH, 2012-07-09 21:11:15]

Also, I think you could break lines 112-129 into a separate
computeRectStaysRectMask() function, given that you know whether you aren't
perspective.

[junov1, 2012-07-10 13:57:17]

On 2012/07/09 21:11:15, TomH wrote:
> Also, I think you could break lines 112-129 into a separate
> computeRectStaysRectMask() function, given that you know whether you aren't
> perspective.

I found a way to not regress the performance of invert() in any case: it
consists in checking fTypeMask directly without calling rectStaysRect() that
way, I am never unnecessarily calling computeTypeMask on the original matrix. 
If the original matrix has an unknown typemask, then we'll just be computing the
type mask on the inverted matrix.

That being said, your suggestion of breaking out computeRectStaysRectMask()
would be a good complement to that.

Interesting fact: when profiling in a syzigized Chrome official build, I am
getting a disproportionate hotspot on the first instruction of computeTypeMask,
which is probably due to some kind of pathological situation on the CPU,
probably a code cache miss.  I am not seeing the same hotspot in bench.exe.
Therefore, the speedup I am getting in Chrome with this fix is way more awesome
than what skia benchmarks suggests.

Also, my local build of bench.exe is generating SSE assembly for sections of
code that is not SSE2-specific (not within cpuid checks), so it looks like we
are turning on SSE2 code generation by default at least on win32.  This is not
representative of a Chrome build.

[junov1, 2012-07-10 14:46:12]

New patch fixes perf, adds bench tests.

[TomH, 2012-07-10 14:53:32]

http://codereview.appspot.com/6380043/diff/8001/src/core/SkMatrix.cpp
File src/core/SkMatrix.cpp (right):

http://codereview.appspot.com/6380043/diff/8001/src/core/SkMatrix.cpp#newcode918
src/core/SkMatrix.cpp:918: // simple to derive algebraically from the
expressions above.
The last sentence here does not contribute to the comment? However, the
expression below is still complex enough that I'd like to see it broken into
parts.

[reed1, 2012-07-10 15:39:26]

Conceding the SSE code, what are the bench results (old and new) with this CL?

[junov1, 2012-07-10 17:48:34]

On 2012/07/10 15:39:26, reed1 wrote:
> Conceding the SSE code, what are the bench results (old and new) with this CL?

matrix_invert_maprect_rectstaysrect and matrix_invert_maprect_identity go from
7.0ms (before fix) to 5.7 ms (with fix)
All other matrix_invert_maprect_* benchmarks are unchanged.

[junov1, 2012-07-10 17:53:54]

On 2012/07/10 14:53:32, TomH wrote:
> The last sentence here does not contribute to the comment? However, the
> expression below is still complex enough that I'd like to see it broken into
> parts.

Done in Patch Set 3.

[reed1, 2012-07-10 18:20:07]

http://codereview.appspot.com/6380043/diff/13001/src/core/SkMatrix.cpp
File src/core/SkMatrix.cpp (right):

http://codereview.appspot.com/6380043/diff/13001/src/core/SkMatrix.cpp#newcod...
src/core/SkMatrix.cpp:916: // In those cases, the inverse has a translation if
*this has a
Is it algebraically true that rotates and skews don't have this same symmetry?

http://codereview.appspot.com/6380043/diff/13001/src/core/SkMatrix.cpp#newcod...
src/core/SkMatrix.cpp:917: // translation.  Same thing for scale.
Wow, I found this much harder to parse than

if (rect_mask == (...)) {
    setTypeMask(fTypeMask);
} else {
    setTypeMask(unknown);
}

[junov1, 2012-07-10 18:26:05]

http://codereview.appspot.com/6380043/diff/13001/src/core/SkMatrix.cpp
File src/core/SkMatrix.cpp (right):

http://codereview.appspot.com/6380043/diff/13001/src/core/SkMatrix.cpp#newcod...
src/core/SkMatrix.cpp:916: // In those cases, the inverse has a translation if
*this has a
On 2012/07/10 18:20:07, reed1 wrote:
> Is it algebraically true that rotates and skews don't have this same symmetry?
A skew can affect the scale of the inverse, and the test to differentiate
between a rotation and a skew is expensive

[junov1, 2012-07-10 21:04:04]

After chatting with Mike, found a way to make so that the type mask of the
inverse is always the same as the type mask of the original matrix. While I was
at it, I rehashed computeTypeMask to make it more efficient.  With this change,
I am improving perf for all matrix_invert_maprect_* bench tests.

[reed1, 2012-07-10 21:10:59]

lgtm

do we need more (or different) unittests, to ensure that our new invariant is
always true (e.g. affine implies scale)?

[TomH, 2012-07-10 21:13:36]

http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp
File src/core/SkMatrix.cpp (right):

http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode66
src/core/SkMatrix.cpp:66: return SkToU8(kORableMasks);
You've changed the semantics here! You're setting all the other bits to true.

http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode77
src/core/SkMatrix.cpp:77: // subsequent calls to computeTypeMask.
I don't understand this comment.

[junov1, 2012-07-11 14:17:39]

On 2012/07/10 21:13:36, TomH wrote:
> 
>
http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode66
> src/core/SkMatrix.cpp:66: return SkToU8(kORableMasks);
> You've changed the semantics here! You're setting all the other bits to true.

Yes the thinking is that it is OK to have false positives in the type mask, but
not OK to have false negatives.  Currently there are no (and ther probably never
will be) optimizations that care about the Translate, Scale and Skew bits if the
Perpective bit is set.  Therefore there is no penalty to having these false
positives on those bits when we have a perspective matrix. So we have an early
out opportunity.

> 
>
http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode77
> src/core/SkMatrix.cpp:77: // subsequent calls to computeTypeMask.
> I don't understand this comment.

Because the Unknown bit is not set, the type mask is considered fully computed.

[TomH, 2012-07-11 14:29:14]

On 2012/07/11 14:17:39, junov1 wrote:
> On 2012/07/10 21:13:36, TomH wrote:
> > 
> >
>
http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode66
> > src/core/SkMatrix.cpp:66: return SkToU8(kORableMasks);
> > You've changed the semantics here! You're setting all the other bits to
true.
> 
> Yes the thinking is that it is OK to have false positives in the type mask,
but
> not OK to have false negatives.  Currently there are no (and ther probably
never
> will be) optimizations that care about the Translate, Scale and Skew bits if
the
> Perpective bit is set.  Therefore there is no penalty to having these false
> positives on those bits when we have a perspective matrix. So we have an early
> out opportunity.

I really dislike this. It needs to be clearly documented in the header.

>
http://codereview.appspot.com/6380043/diff/15002/src/core/SkMatrix.cpp#newcode77
> > src/core/SkMatrix.cpp:77: // subsequent calls to computeTypeMask.
> > I don't understand this comment.
> 
> Because the Unknown bit is not set, the type mask is considered fully
computed.

I still don't understand. The comment needs to be a lot clearer. I think you're
trying to say the same thing as you said up above, but even that isn't explained
well enough. And since WE'RE LYING in the type mask now, it needs to be really,
really clear, and in the header so users understand the contract we're offering
them.

[junov1, 2012-07-11 15:15:20]

New patch has improved comments, for clarity.  I also removed two conditional
branches "if ((mask & kPerspective_Mask) == 0)", which were pointless because
the early exit in the perspective case.

[TomH, 2012-07-11 15:38:42]

http://codereview.appspot.com/6380043/diff/16002/include/core/SkMatrix.h
File include/core/SkMatrix.h (right):

http://codereview.appspot.com/6380043/diff/16002/include/core/SkMatrix.h#newc...
include/core/SkMatrix.h:50: arithmetic as is necessary. When a bit is turned
off, it is garanteed
Multiple spelling errors, and still not happy with the diction or the clarity.
Also, the comments on TypeMask are also lying, and making them truthful would
make them too long.

strawman:
/**
Returns a bitfield describing the types of transformations the matrix performs.
If kPerspective_Mask is true, all other bits may be set to true.
*/

http://codereview.appspot.com/6380043/diff/16002/src/core/SkMatrix.cpp
File src/core/SkMatrix.cpp (right):

http://codereview.appspot.com/6380043/diff/16002/src/core/SkMatrix.cpp#newcode79
src/core/SkMatrix.cpp:79: // may prevent a subsequent call to computeTypeMask.
strawman:
/*
If this is a perspective transform, we return true for all other flags - this
does not disable any optimizations, and significantly speeds up type mask
computation.
*/

http://codereview.appspot.com/6380043/diff/16002/src/core/SkMatrix.cpp#newcod...
src/core/SkMatrix.cpp:146: 
GrAssert(0 == (mask & kPerspective_Mask)), please.

[junov1, 2012-07-11 15:51:47]

On 2012/07/11 15:38:42, TomH wrote:

> Also, the comments on TypeMask are also lying, and making them truthful would
> make them too long.

How are they lying?

> 
> strawman:
> /**
> Returns a bitfield describing the types of transformations the matrix
performs.
> If kPerspective_Mask is true, all other bits may be set to true.
> */
That is just one false positive case out of plenty that are possible, many of
which existed even before this change.  Why would we only call out this one?

[TomH, 2012-07-11 15:56:44]

On 2012/07/11 15:51:47, junov1 wrote:
> On 2012/07/11 15:38:42, TomH wrote:
> 
> > Also, the comments on TypeMask are also lying, and making them truthful
would
> > make them too long.
> 
> How are they lying?

"set if the matrix has translation" OR it's perspective

> > strawman:
> > /**
> > Returns a bitfield describing the types of transformations the matrix
> performs.
> > If kPerspective_Mask is true, all other bits may be set to true.
> > */
> That is just one false positive case out of plenty that are possible, many of
> which existed even before this change.  Why would we only call out this one?

I didn't know that. Are you certain? Are any of them anywhere near as common?
Revised strawman:

/**
Returns a bitfield describing the transformations the matrix may perform; can
include false positives.
For example, when kPerspective_Mask is true, all other bits may be set to true.
*/

[junov1, 2012-07-11 17:38:58]

On 2012/07/11 15:56:44, TomH wrote:
> 
> "set if the matrix has translation" OR it's perspective

Technically, "set if the matrix has translation" on its own is correct.  "if" !=
"if and only if"

But now I'm just being a smartass. I get your point.  I will find a way to make
it clearer.

> > That is just one false positive case out of plenty that are possible, many
of
> > which existed even before this change.  Why would we only call out this one?
> 
> I didn't know that. Are you certain? Are any of them anywhere near as common?

Most of the cases I can think of are edge cases, but there is one really common
one: a pure rotation matrix will set the scale bit .  This was true even before
my change (because of non-one values on the diagonal).

[junov1, 2012-07-11 17:52:36]

Patch uploaded. I ended pasting almost exactly what you suggested, I like that
it's concise.

[TomH, 2012-07-11 17:57:06]

LGTM

[junov1, 2012-07-16 19:05:13]

Fixed with r4562