Speed up GrResourceCache add and lookup by using TDynamicHash

src/core/SkTDynamicHash.h

 /*
  * Copyright 2013 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef SkTDynamicHash_DEFINED
 #define SkTDynamicHash_DEFINED
 
 #include "SkTypes.h"
 #include "SkMath.h"
 
+/** SkTDynamicHash is a set of pointers of T. The elements can be looked up from the set by
+ * key Key. Duplicate keys are allowed.
+ */
 template <typename T,
           typename Key,
           const Key& (GetKey)(const T&),
           uint32_t (Hash)(const Key&),
           bool (Equal)(const T&, const Key&),
           int kGrowPercent   = 75,  // Larger -> more memory efficient, but slower.
           int kShrinkPercent = 25>
 class SkTDynamicHash {
     static const int kMinCapacity = 4;  // Smallest capacity we allow.
 public:
     SkTDynamicHash(int initialCapacity=64/sizeof(T*)) {
         this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity));
-        SkASSERT(this->validate());

[mtklein, 2013/11/27 14:21:54]

Please put validate back to how it was.  SkASSERT compiles away to a no-op when
NDEBUG is defined.  SkASSERT(this->validate()); costs nothing.

[Kimmo Kinnunen, 2013/11/28 06:40:08]

The commit msg actually said that when it is *run*, it is too costly.

In other words: if validating after every operation, debug build runs of "tests"
never finish.

I don't think DynamicHash has been used with any substantial amount of items
before.

     }
 
     ~SkTDynamicHash() {
         sk_free(fArray);
     }
 
     int count() const { return fCount; }
 
-    // Return the entry with this key if we have it, otherwise NULL.
+    struct Any {
+        // Return the first entry that matches the key.
+        bool operator()(const T*) const { return true; }

[mtklein, 2013/11/27 14:21:54]

I'm not a fan of this API.  I know it's replicating the existing GrResourceCache
API, but it's not something that's done any more efficiently here than in the
GrResourceCache itself.

Allowing multiple values with the same key is going to open up a bag of worms. 
There's more than one way you might want add(), remove(), find(), etc. to work
in the presence of duplicate keys, which makes me think it shouldn't be handled
here.  In contrast, if you require unique keys, there's really only one way
these things can work.

Here's what I propose:
  - GrResourceCache makes an SkTDynamicHash mapping from its key to a list
(SkTDArray, SkTArray, SkTLList, ...) of its entries.
  - Filtered lookups in GrResourceCache first call find() here then manually
iterate over the entries in the list until the filter is satisfied.

[Kimmo Kinnunen, 2013/11/28 06:40:08]

Yeah.. Though, in this stage of this usage, I don't think it would  *in
practice* open any.

I see what I can do, but it is not that pretty.

+    };
+
+    // Return an entry with passed key if the collection has it, otherwise NULL.
     T* find(const Key& key) const {
+        return this->find(key, Any());
+    }
+
+    // Return an entry with the passed key if the collection has it and if filter returns true for
+    // the entry. Otherwise return NULL.
+    template <typename Filter>
+    T* find(const Key& key, Filter filter) const {
         int index = this->firstIndex(key);
         for (int round = 0; round < fCapacity; round++) {
             T* candidate = fArray[index];
             if (Empty() == candidate) {
                 return NULL;
             }
-            if (Deleted() != candidate && Equal(*candidate, key)) {
+            if (Deleted() != candidate && Equal(*candidate, key) && filter(fArray[index])) {
                 return candidate;
             }
             index = this->nextIndex(index, round);
         }
-        SkASSERT(0); //  find: should be unreachable
         return NULL;
     }
 
-    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
+    // Add an entry with this key.
     void add(T* newEntry) {
-        SkASSERT(NULL == this->find(GetKey(*newEntry)));
         this->maybeGrow();
-        SkASSERT(this->validate());
         this->innerAdd(newEntry);
-        SkASSERT(this->validate());
     }
 
-    // Remove the entry with this key.  We reqire that an entry with this key is present.
-    void remove(const Key& key) {
-        SkASSERT(NULL != this->find(key));
-        this->innerRemove(key);
-        SkASSERT(this->validate());
+    // Remove the entry with this key.  We require that the entry has been added before.
+    void remove(const T* entry) {

[mtklein, 2013/11/27 14:21:54]

Generally, these should be const T&.  It's neither optional nor are we
NULL-checking it.

[Kimmo Kinnunen, 2013/11/28 06:40:08]

A) This is set that stores pointers
B) Pointers are stored by adding a pointer
C) Pointers are removed by removing a reference

Does this summarize your suggestion?

[bsalomon, 2013/12/02 14:18:16]

If the function (or something it calls) will retain a pointer to the passed
object then I *think* our convention is to pass by pointer not reference, though
our style guide makes no mention of this at present.

[reed1, 2013/12/02 16:20:40]

agreed -- passing a ptr is clearer (to me) that the caller *could* take
ownership. Passing a reference signifies to me that we're just trying to be more
efficient than passing by value, but with the same constness/ownership contract.

+        SkASSERT(NULL != this->find(GetKey(*entry)));
+        this->innerRemove(entry);
         this->maybeShrink();
-        SkASSERT(this->validate());
     }
 
-protected:
-    // These methods are used by tests only.
-
-    int capacity() const { return fCapacity; }
-
-    // How many collisions do we go through before finding where this entry should be inserted?
-    int countCollisions(const Key& key) const {
-        int index = this->firstIndex(key);
-        for (int round = 0; round < fCapacity; round++) {
-            const T* candidate = fArray[index];
-            if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
-                return round;
-            }
-            index = this->nextIndex(index, round);
-        }
-        SkASSERT(0); // countCollisions: should be unreachable
-        return -1;
-    }
-
-private:
-    // We have two special values to indicate an empty or deleted entry.
-    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
-    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
-
-    static T** AllocArray(int capacity) {
-        return (T**)sk_calloc_throw(sizeof(T*) * capacity);  // All cells == Empty().
-    }
-
-    void reset(int capacity) {
-        fCount = 0;
-        fDeleted = 0;
-        fCapacity = capacity;
-        fArray = AllocArray(fCapacity);
-    }
-
-    bool validate() const {
-        #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
+#ifdef SK_DEBUG
+    void validate() const {
+        #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return;
 
         // Is capacity sane?
         SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
         SKTDYNAMICHASH_CHECK(fCapacity >= kMinCapacity);
 
         // Is fCount correct?
         int count = 0;
         for (int i = 0; i < fCapacity; i++) {
             if (Empty() != fArray[i] && Deleted() != fArray[i]) {
                 count++;
@@ skipping 21 matching lines @@
         // Are all entries unique?
         for (int i = 0; i < fCapacity; i++) {
             if (Empty() == fArray[i] || Deleted() == fArray[i]) {
                 continue;
             }
             for (int j = i+1; j < fCapacity; j++) {
                 if (Empty() == fArray[j] || Deleted() == fArray[j]) {
                     continue;
                 }
                 SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
-                SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
-                SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
             }
         }
         #undef SKTDYNAMICHASH_CHECK
-        return true;
+    }
+#else
+    void validate() const { }
+#endif
+
+protected:
+    // These methods are used by tests only.
+
+    int capacity() const { return fCapacity; }
+
+    // How many collisions do we go through before finding where this entry should be inseretd?
+    int countCollisions(const Key& key) const {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
+                return round;
+            }
+            index = this->nextIndex(index, round);
+        }
+        SkASSERT(0); // countCollisions: should be unreachable
+        return -1;
+    }
+
+private:
+    // We have two special values to indicate an empty or deleted entry.
+    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
+    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
+
+    static T** AllocArray(int capacity) {
+        return (T**)sk_calloc_throw(sizeof(T*) * capacity);  // All cells == Empty().
+    }
+
+    void reset(int capacity) {
+        fCount = 0;
+        fDeleted = 0;
+        fCapacity = capacity;
+        fArray = AllocArray(fCapacity);
     }
 
     void innerAdd(T* newEntry) {
         const Key& key = GetKey(*newEntry);
         int index = this->firstIndex(key);
         for (int round = 0; round < fCapacity; round++) {
             const T* candidate = fArray[index];
             if (Empty() == candidate || Deleted() == candidate) {
                 if (Deleted() == candidate) {
                     fDeleted--;
                 }
                 fCount++;
                 fArray[index] = newEntry;
                 return;
             }
             index = this->nextIndex(index, round);
         }
         SkASSERT(0); // add: should be unreachable
     }
 
-    void innerRemove(const Key& key) {
+    void innerRemove(const T* entry) {
+        const Key& key = GetKey(*entry);
         const int firstIndex = this->firstIndex(key);
         int index = firstIndex;
         for (int round = 0; round < fCapacity; round++) {
             const T* candidate = fArray[index];
-            if (Deleted() != candidate && Equal(*candidate, key)) {
+            if (Deleted() != candidate && Equal(*candidate, key) && fArray[index] == entry) {
                 fDeleted++;
                 fCount--;
                 fArray[index] = Deleted();
                 return;
             }
             index = this->nextIndex(index, round);
         }
         SkASSERT(0); // innerRemove: should be unreachable
     }
 
@@ skipping 40 matching lines @@
         return (index + round + 1) & this->hashMask();
     }
 
     int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
     int fDeleted;   // Number of Deleted() entries in fArray.
     int fCapacity;  // Number of entries in fArray.  Always a power of 2.
     T** fArray;
 };
 
 #endif