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"
 
 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/12/03 19:02:02]

Let's put this guy back.  This will never be expensive.

     }
 
     ~SkTDynamicHash() {
         sk_free(fArray);
     }
 
     int count() const { return fCount; }
 
     // Return the entry with this key if we have it, otherwise NULL.
     T* find(const Key& key) 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)) {
                 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.
     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());
         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

[mtklein, 2013/12/03 19:02:02]

This is a little nit, but let's just move the #ifdef inside validate and have
one declaration instead of two.

+    void validate() const {
+        #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return

[mtklein, 2013/12/03 19:02:02]

If we're guarding by SK_DEBUG, we can just use SkASSERT directly instead of
SKTDYNAMICHASH_CHECK.  The "if (!(x)) return" should never run if the assert
fails.

 
         // 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 26 matching lines @@
             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.

[mtklein, 2013/12/03 19:02:02]

Can we now pull validate() down here too?

+
+    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);
     }
 
     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--;
@@ skipping 66 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