Implement intra-frame cacheing in image filters.

src/core/SkImageFilter.cpp

Index: src/core/SkImageFilter.cpp
diff --git a/src/core/SkImageFilter.cpp b/src/core/SkImageFilter.cpp
index 2be66e787c5c6efba9148de9884c3e26a85b012f..8d0c22de285a51ac5de63483233507d8533725a1 100644
--- a/src/core/SkImageFilter.cpp
+++ b/src/core/SkImageFilter.cpp
@@ -12,6 +12,7 @@
 #include "SkReadBuffer.h"
 #include "SkWriteBuffer.h"
 #include "SkRect.h"
+#include "SkTDynamicHash.h"
 #include "SkValidationUtils.h"
 #if SK_SUPPORT_GPU
 #include "GrContext.h"
@@ -96,14 +97,23 @@ void SkImageFilter::flatten(SkWriteBuffer& buffer) const {
 bool SkImageFilter::filterImage(Proxy* proxy, const SkBitmap& src,
                                 const Context& context,
                                 SkBitmap* result, SkIPoint* offset) const {
+    Cache* cache = context.cache();
     SkASSERT(result);
     SkASSERT(offset);
+    SkASSERT(cache);
+    if (cache->get(this, result, offset)) {
+        return true;
+    }
     /*
      *  Give the proxy first shot at the filter. If it returns false, ask
      *  the filter to do it.
      */
-    return (proxy && proxy->filterImage(this, src, context, result, offset)) ||
-           this->onFilterImage(proxy, src, context, result, offset);
+    if ((proxy && proxy->filterImage(this, src, context, result, offset)) ||
+        this->onFilterImage(proxy, src, context, result, offset)) {
+        cache->set(this, *result, *offset);
+        return true;
+    }
+    return false;
 }
 
 bool SkImageFilter::filterBounds(const SkIRect& src, const SkMatrix& ctm,
@@ -321,3 +331,83 @@ bool SkImageFilter::getInputResultGPU(SkImageFilter::Proxy* proxy,
     }
 }
 #endif
+
+static uint32_t compute_hash(const uint32_t* data, int count) {
+    uint32_t hash = 0;
+
+    for (int i = 0; i < count; ++i) {
+        uint32_t k = data[i];
+        k *= 0xcc9e2d51;
+        k = (k << 15) | (k >> 17);
+        k *= 0x1b873593;
+
+        hash ^= k;
+        hash = (hash << 13) | (hash >> 19);
+        hash *= 5;
+        hash += 0xe6546b64;
+    }
+
+    //    hash ^= size;
+    hash ^= hash >> 16;
+    hash *= 0x85ebca6b;
+    hash ^= hash >> 13;
+    hash *= 0xc2b2ae35;
+    hash ^= hash >> 16;
+
+    return hash;
+}
+
+class CacheImpl : public SkImageFilter::Cache {
+public:
+    explicit CacheImpl(int minChildren) : fMinChildren(minChildren) {}
+    virtual ~CacheImpl();
+    bool get(const SkImageFilter* key, SkBitmap* result, SkIPoint* offset) SK_OVERRIDE;
+    void set(const SkImageFilter* key, const SkBitmap& result, const SkIPoint& offset) SK_OVERRIDE;
+private:
+    typedef const SkImageFilter* Key;
+    struct Value {
+        Value(Key key, const SkBitmap& bitmap, const SkIPoint& offset)
+            : fKey(key), fBitmap(bitmap), fOffset(offset) {}
+        Key fKey;
+        SkBitmap fBitmap;
+        SkIPoint fOffset;
+        static const Key& GetKey(const Value& v) {
+            return v.fKey;
+        }
+        static uint32_t Hash(Key key) {
+            return compute_hash(reinterpret_cast<const uint32_t*>(&key), sizeof(Key) / sizeof(uint32_t));

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

You do realize that this is computing a hash which includes the ref count right?
Having keys which are modifiable is rather frightening. 

[Stephen White, 2014/04/14 17:24:45]

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 *).
Agreed.

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

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*).

+        }
+    };
+    SkTDynamicHash<Value, Key> fData;
+    int fMinChildren;
+};
+
+bool CacheImpl::get(const SkImageFilter* key, SkBitmap* result, SkIPoint* offset) {
+    Value* v = fData.find(key);
+    if (v) {
+        *result = v->fBitmap;
+        *offset = v->fOffset;
+        return true;
+    }
+    return false;
+}
+
+void CacheImpl::set(const SkImageFilter* key, const SkBitmap& result, const SkIPoint& offset) {
+    if (key->getRefCnt() >= fMinChildren) {

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

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:45]

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]

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.

+        fData.add(new Value(key, result, offset));
+    }
+}
+
+SkImageFilter::Cache* SkImageFilter::Cache::Create(int minChildren) {
+    return new CacheImpl(minChildren);
+}
+
+CacheImpl::~CacheImpl() {
+    SkTDynamicHash<Value, Key>::Iter iter(&fData);
+
+    while (!iter.done()) {
+        Value* v = &*iter;
+        ++iter;
+        delete v;
+    }
+}