Implement intra-frame cacheing in image filters.

Implement intra-frame cacheing in image filters.

When image filters are processed within Skia, they simply do
a blind recursion. This has the side-effect of turning the
DAG into a tree. I.e., nodes visited more than once during
the traversal will be processed more than once.

This change implements a very simple cacheing scheme: a
cache is created before traversing the DAG, and handed
into the processing traversal. Before recursing into a child
in SkImageFilter::filterImage(), the cache is checked for a
hit, and early-out is performed. Otherwise, the node is
processed, and its result bitmap and location (offset) are
cached, but only if it contains two or more children and
thus will be visited again during the traversal.

Currently, the child count is approximated with the
refcount. This is good enough in most cases (and exactly
correct for the Chrome use case). We could add an exact
child count to the image filter, but this will require
violating the immutability of image filters slightly in
order to bump the child count as nodes are connected. I
leave it up to the reviewer to decide which is better.

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

[Stephen White, 2014-04-10 20:58:06]

reed@: PTAL. This is a version with the cache as a non-const-accessible member
of the Context.

[reed1, 2014-04-10 21:23:26]

lgtm w/ request for documenting the call-site of '2'

https://codereview.chromium.org/230653005/diff/10001/src/core/SkCanvas.cpp
File src/core/SkCanvas.cpp (right):

https://codereview.chromium.org/230653005/diff/10001/src/core/SkCanvas.cpp#ne...
src/core/SkCanvas.cpp:1261: SkImageFilter::Cache* cache =
SkImageFilter::Cache::Create(2);
That '2' is mysterious to the new reviewer...

1. Why is 2 a good answer?

2. How about...

const int minChildren = 2; // answer to #1
cache = SkImageFilter::Cache::Create(minChildren);

[Stephen White, 2014-04-10 21:26:36]

https://codereview.chromium.org/230653005/diff/10001/src/core/SkCanvas.cpp
File src/core/SkCanvas.cpp (right):

https://codereview.chromium.org/230653005/diff/10001/src/core/SkCanvas.cpp#ne...
src/core/SkCanvas.cpp:1261: SkImageFilter::Cache* cache =
SkImageFilter::Cache::Create(2);
On 2014/04/10 21:23:26, reed1 wrote:
> That '2' is mysterious to the new reviewer...
> 
> 1. Why is 2 a good answer?

2 means "cache only image filters with 2 or more children".

(In an upcoming change, I'm going to reuse this class externally with a value
other than 2.)

> 2. How about...
> 
> const int minChildren = 2; // answer to #1
> cache = SkImageFilter::Cache::Create(minChildren);

How about I make it the default param?

[Stephen White, 2014-04-10 21:30:00]

New patch: give minChildren a default, and document it.

[Stephen White, 2014-04-11 17:58:54]

The CQ bit was checked by senorblanco@chromium.org

[commit-bot: I haz the power, 2014-04-11 17:59:05]

CQ is trying da patch. Follow status at
https://skia-tree-status.appspot.com/cq/senorblanco@chromium.org/230653005/30001

[commit-bot: I haz the power, 2014-04-11 18:57:19]

Change committed as 14160

[bungeman-skia, 2014-04-14 16:47:47]

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.cpp
File src/core/SkImageFilter.cpp (right):

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:378: return compute_hash(reinterpret_cast<const
uint32_t*>(&key), sizeof(Key) / sizeof(uint32_t));
You do realize that this is computing a hash which includes the ref count right?
Having keys which are modifiable is rather frightening.

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:396: if (key->getRefCnt() >= fMinChildren) {
This is somewhat crazy. 'getRefCnt' is marked 'Use only for debugging.' for a
reason. I see why you think you can get away with this here, but it's really
iffy.

[Stephen White, 2014-04-14 17:24:44]

Thanks for the drive-by review; I appreciate it! :)

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.cpp
File src/core/SkImageFilter.cpp (right):

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:378: return compute_hash(reinterpret_cast<const
uint32_t*>(&key), sizeof(Key) / sizeof(uint32_t));
On 2014/04/14 16:47:48, bungeman1 wrote:
> You do realize that this is computing a hash which includes the ref count
right?

Unless I've messed up totally, this should just be a hash of the SkImageFilter
pointer value, not its contents. (Key is a const SkImageFilter*, sizeof(Key)
should be the size of a pointer, so 1 or 2 uint32_t's. We never deref the
pointer; just use it as an opaque key (could probably be a void *).

> Having keys which are modifiable is rather frightening. 

Agreed.

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:396: if (key->getRefCnt() >= fMinChildren) {
On 2014/04/14 16:47:48, bungeman1 wrote:
> This is somewhat crazy. 'getRefCnt' is marked 'Use only for debugging.' for a
> reason. I see why you think you can get away with this here, but it's really
> iffy.

I think it would probably be better long-term to keep an actual child count. I
just didn't like the idea of making SkImageFilter partly-mutable (see patch
description).

[bungeman-skia, 2014-04-14 18:05:10]

I'm Skia sheriff this week, and I took a quick look at what I was rolling due to
other changes in Chromium. I just saw these changes and though I should comment.

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.cpp
File src/core/SkImageFilter.cpp (right):

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:378: return compute_hash(reinterpret_cast<const
uint32_t*>(&key), sizeof(Key) / sizeof(uint32_t));
On 2014/04/14 17:24:45, Stephen White wrote:
> On 2014/04/14 16:47:48, bungeman1 wrote:
> > You do realize that this is computing a hash which includes the ref count
> right?
> 
> Unless I've messed up totally, this should just be a hash of the SkImageFilter
> pointer value, not its contents. (Key is a const SkImageFilter*, sizeof(Key)
> should be the size of a pointer, so 1 or 2 uint32_t's. We never deref the
> pointer; just use it as an opaque key (could probably be a void *).
> 

Ah, I see, the Key here is SkImageFilter*, so this is casting SkImageFilter** to
'const uint32_t*'. Changing the number of indirections in this cast is probably
what threw me off here (why it looks like you're hashing the SkImageFilter data
vs the SkImageFilter*).

> > Having keys which are modifiable is rather frightening. 
> 
> Agreed.

https://codereview.chromium.org/230653005/diff/30001/src/core/SkImageFilter.c...
src/core/SkImageFilter.cpp:396: if (key->getRefCnt() >= fMinChildren) {
On 2014/04/14 17:24:45, Stephen White wrote:
> On 2014/04/14 16:47:48, bungeman1 wrote:
> > This is somewhat crazy. 'getRefCnt' is marked 'Use only for debugging.' for
a
> > reason. I see why you think you can get away with this here, but it's really
> > iffy.
> 
> I think it would probably be better long-term to keep an actual child count. I
> just didn't like the idea of making SkImageFilter partly-mutable (see patch
> description).

Sure, although SkImageFilter, being SkRefCnt, is already partly mutable. I
understand why one would prefer to avoid that though. I just saw a non-debug use
of getRefCnt and alarm bells went off.