Implement a persistent uniqueID-based cache for SkImageFilter.

src/core/SkImageFilter.cpp

Index: src/core/SkImageFilter.cpp
diff --git a/src/core/SkImageFilter.cpp b/src/core/SkImageFilter.cpp
index 11a1420dfaf2176973f4ce9cc09706ac63694c8c..c0741a5f5789906259edbc9a9a6a1f31b9051f94 100644
--- a/src/core/SkImageFilter.cpp
+++ b/src/core/SkImageFilter.cpp
@@ -10,6 +10,7 @@
 #include "SkBitmap.h"
 #include "SkChecksum.h"
 #include "SkDevice.h"
+#include "SkLazyPtr.h"
 #include "SkReadBuffer.h"
 #include "SkWriteBuffer.h"
 #include "SkRect.h"
@@ -21,6 +22,30 @@
 #include "SkGr.h"
 #endif
 
+enum { kDefaultCacheSize = 128 * 1024 * 1024 };
+
+static int32_t next_image_filter_generation_id() {
+    static int32_t gImageFilterGenerationID;
+    return sk_atomic_inc(&gImageFilterGenerationID);
+}
+
+struct SkImageFilter::GenIDCache::Key {
+    Key(const uint32_t genID, const SkMatrix& matrix, const SkIRect& clipBounds, uint32_t srcGenID)
+      : fGenID(genID), fMatrix(matrix), fClipBounds(clipBounds), fSrcGenID(srcGenID) {
+        fMatrix.getType();  // force initialization of type, so hashes match
+    }
+    uint32_t fGenID;
+    SkMatrix fMatrix;
+    SkIRect fClipBounds;
+    uint32_t fSrcGenID;
+    bool operator==(const Key& other) const {
+        return fGenID == other.fGenID
+            && fMatrix == other.fMatrix
+            && fClipBounds == other.fClipBounds
+            && fSrcGenID == other.fSrcGenID;
+    }
+};
+
 SkImageFilter::Common::~Common() {
     for (int i = 0; i < fInputs.count(); ++i) {
         SkSafeUnref(fInputs[i]);
@@ -65,6 +90,7 @@ bool SkImageFilter::Common::unflatten(SkReadBuffer& buffer, int expectedCount) {
     
     uint32_t flags = buffer.readUInt();
     fCropRect = CropRect(rect, flags);
+    fGenerationID = buffer.readUInt();
     return buffer.isValid();
 }
 
@@ -75,8 +101,13 @@ SkImageFilter::Cache* gExternalCache;
 SkImageFilter::SkImageFilter(int inputCount, SkImageFilter** inputs, const CropRect* cropRect)
   : fInputCount(inputCount),
     fInputs(new SkImageFilter*[inputCount]),
-    fCropRect(cropRect ? *cropRect : CropRect(SkRect(), 0x0)) {
+    fUsesSrcInput(false),
+    fCropRect(cropRect ? *cropRect : CropRect(SkRect(), 0x0)),
+    fGenerationID(next_image_filter_generation_id()) {
     for (int i = 0; i < inputCount; ++i) {
+        if (NULL == inputs[i] || inputs[i]->usesSrcInput()) {
+            fUsesSrcInput = true;
+        }
         fInputs[i] = inputs[i];
         SkSafeRef(fInputs[i]);
     }
@@ -89,13 +120,21 @@ SkImageFilter::~SkImageFilter() {
     delete[] fInputs;
 }
 
-SkImageFilter::SkImageFilter(int inputCount, SkReadBuffer& buffer) {
+SkImageFilter::SkImageFilter(int inputCount, SkReadBuffer& buffer)
+  : fUsesSrcInput(false) {
     Common common;
     if (common.unflatten(buffer, inputCount)) {
         fCropRect = common.cropRect();
         fInputCount = common.inputCount();
         fInputs = SkNEW_ARRAY(SkImageFilter*, fInputCount);
         common.detachInputs(fInputs);
+        for (int i = 0; i < fInputCount; ++i) {
+            if (NULL == fInputs[i] || fInputs[i]->usesSrcInput()) {
+                fUsesSrcInput = true;
+            }
+        }
+        fGenerationID = buffer.isCrossProcess() ? next_image_filter_generation_id()
+                                                : common.generationID();
     } else {
         fInputCount = 0;
         fInputs = NULL;
@@ -113,17 +152,25 @@ void SkImageFilter::flatten(SkWriteBuffer& buffer) const {
     }
     buffer.writeRect(fCropRect.rect());
     buffer.writeUInt(fCropRect.flags());
+    buffer.writeUInt(fGenerationID);
 }
 
 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;
+    uint32_t srcGenID = fUsesSrcInput ? src.getGenerationID() : 0;
+    Cache* externalCache = GetExternalCache();
+    GenIDCache::Key key(fGenerationID, context.ctm(), context.clipBounds(), srcGenID);
+    if (NULL != externalCache) {
+        if (externalCache->get(this, result, offset)) {
+            return true;
+        }
+    } else if (context.cache()) {
+        if (context.cache()->get(key, result, offset)) {
+            return true;
+        }
     }
     /*
      *  Give the proxy first shot at the filter. If it returns false, ask
@@ -131,7 +178,11 @@ bool SkImageFilter::filterImage(Proxy* proxy, const SkBitmap& src,
      */
     if ((proxy && proxy->filterImage(this, src, context, result, offset)) ||
         this->onFilterImage(proxy, src, context, result, offset)) {
-        cache->set(this, *result, *offset);
+        if (externalCache) {
+            externalCache->set(this, *result, *offset);
+        } else if (context.cache()) {
+            context.cache()->set(key, *result, *offset);
+        }
         return true;
     }
     return false;
@@ -439,3 +490,93 @@ CacheImpl::~CacheImpl() {
         delete v;
     }
 }
+
+namespace {
+
+class GenIDCacheImpl : public SkImageFilter::GenIDCache {

[bsalomon, 2014/07/25 14:11:58]

Curious, why the virtual interface?

[Stephen White, 2014/07/25 17:34:17]

It's just to keep the implementation details out of the .h.
Since the .h is in the public API, I'd rather keep as much
as possible hidden from clients.

+public:
+    GenIDCacheImpl(size_t maxBytes) : fMaxBytes(maxBytes), fCurrentBytes(0) {
+    }
+    virtual ~GenIDCacheImpl() {
+        SkTDynamicHash<Value, Key>::Iter iter(&fLookup);
+
+        while (!iter.done()) {
+            Value* v = &*iter;
+            ++iter;
+            delete v;
+        }
+    }
+    struct Value {
+        Value(const 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(const Key& key) {
+            return SkChecksum::Murmur3(reinterpret_cast<const uint32_t*>(&key), sizeof(Key));
+        }
+        SK_DECLARE_INTERNAL_LLIST_INTERFACE(Value);
+    };
+    virtual bool get(const Key& key, SkBitmap* result, SkIPoint* offset) const {
+        SkAutoMutexAcquire mutex(fMutex);
+        if (Value* v = fLookup.find(key)) {
+            *result = v->fBitmap;
+            *offset = v->fOffset;
+            if (v != fLRU.head()) {
+                fLRU.remove(v);
+                fLRU.addToHead(v);
+            }
+            return true;
+        }
+        return false;
+    }
+    virtual void set(const Key& key, const SkBitmap& result, const SkIPoint& offset) {
+        SkAutoMutexAcquire mutex(fMutex);
+        if (Value* v = fLookup.find(key)) {
+            removeInternal(v);
+        }
+        Value* v = new Value(key, result, offset);
+        fLookup.add(v);
+        fLRU.addToHead(v);
+        fCurrentBytes += result.getSize();
+        while (fCurrentBytes > fMaxBytes) {
+            Value* tail = fLRU.tail();
+            SkASSERT(tail);
+            if (tail == v) {
+                break;
+            }
+            removeInternal(tail);
+        }
+    }
+private:
+    void removeInternal(Value* v) {
+        fCurrentBytes -= v->fBitmap.getSize();
+        fLRU.remove(v);
+        fLookup.remove(v->fKey);
+        delete v;
+    }
+private:
+    SkTDynamicHash<Value, Key>         fLookup;
+    mutable SkTInternalLList<Value>    fLRU;
+    size_t                             fMaxBytes;
+    size_t                             fCurrentBytes;
+    mutable SkMutex                    fMutex;
+};
+
+SkImageFilter::GenIDCache* CreateCache() {
+    return SkImageFilter::GenIDCache::Create(kDefaultCacheSize);
+}
+
+} // namespace
+
+SkImageFilter::GenIDCache* SkImageFilter::GenIDCache::Create(size_t maxBytes) {
+    return SkNEW_ARGS(GenIDCacheImpl, (maxBytes));
+}
+
+SkImageFilter::GenIDCache* SkImageFilter::GenIDCache::Get() {
+    SK_DECLARE_STATIC_LAZY_PTR(SkImageFilter::GenIDCache, cache, CreateCache);
+    return cache.get();
+}