use dynamic hash to speed up scaledimagecache

BUG=

Review URL: https://codereview.chromium.org/20344002

git-svn-id: http://skia.googlecode.com/svn/trunk@10362 2bbb7eff-a529-9590-31e7-b0007b416f81

2 files changed, 54 insertions, 20 deletions

diff --git a/src/core/SkScaledImageCache.cpp b/src/core/SkScaledImageCache.cpp
index 8d34dfbcc3..e901abdf14 100644
--- a/src/core/SkScaledImageCache.cpp
+++ b/src/core/SkScaledImageCache.cpp
@@ -149,6 +149,7 @@ class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec,
 
 ///////////////////////////////////////////////////////////////////////////////
 
+// experimental hash to speed things up
 //#define USE_HASH
 
 SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
@@ -298,8 +299,6 @@ void SkScaledImageCache::unlock(SkScaledImageCache::ID* id) {
     SkASSERT(rec->fLockCount > 0);
     rec->fLockCount -= 1;
 
-//    SkDebugf("Unlock: [%d %d] %d\n", rec->fBitmap.width(), rec->fBitmap.height(), rec->fLockCount);
-
     // we may have been over-budget, but now have released something, so check
     // if we should purge.
     if (0 == rec->fLockCount) {
@@ -318,7 +317,6 @@ void SkScaledImageCache::purgeAsNeeded() {
         }
         Rec* prev = rec->fPrev;
         if (0 == rec->fLockCount) {
-//            SkDebugf("Purge: [%d %d] %d\n", rec->fBitmap.width(), rec->fBitmap.height(), fCount);
             size_t used = rec->bytesUsed();
             SkASSERT(used <= bytesUsed);
             bytesUsed -= used;
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index 665028abaa..b4787fb89e 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -14,19 +14,22 @@ template <typename T, typename KEY, const KEY& (KEY_FROM_T)(const T&),
 uint32_t (HASH_FROM_KEY)(const Key&), bool (EQ_T_KEY)(const T&, const Key&)>
 class SkTDynamicHash {
 private:
-    T* fStorage[1];
+    T* fStorage[4];
     T** fArray;
     int fCapacity;
     int fCountUsed;
     int fCountDeleted;
     
-    unsigned hashMask() const { return fCapacity - 1; }
     const T* deletedValue() const { return reinterpret_cast<const T*>(-1); }
-    
+    uint32_t hashMask() const { return fCapacity - 1; }
+    int hashToIndex(uint32_t hash) const {
+        return ((hash >> 16) ^ hash) & (fCapacity - 1);
+    }
 public:
     SkTDynamicHash() {
+        sk_bzero(fStorage, sizeof(fStorage));
         fArray = fStorage;
-        fCapacity = 1;
+        fCapacity = SK_ARRAY_COUNT(fStorage);
         fCountUsed = fCountDeleted = 0;
     }
     ~SkTDynamicHash() {
@@ -38,8 +41,7 @@ public:
     T* find(const KEY& key) {
         const T* const deleted = this->deletedValue();
         const unsigned mask = this->hashMask();
-        int index = HASH_FROM_KEY(key) & mask;
-        const int origIndex = index;
+        int index = this->hashToIndex(HASH_FROM_KEY(key));
         int delta = 1;
         
         do {
@@ -52,7 +54,7 @@ public:
             }
             index = (index + delta) & mask;
             delta <<= 1;
-        } while (index != origIndex);
+        } while (delta <= fCapacity);
         return NULL;
     }
     
@@ -60,8 +62,7 @@ public:
         const T* const deleted = this->deletedValue();
         for (;;) {
             const unsigned mask = this->hashMask();
-            int index = HASH_FROM_KEY(key) & mask;
-            const int origIndex = index;
+            int index = this->hashToIndex(HASH_FROM_KEY(key));
             int delta = 1;
             
             do {
@@ -77,7 +78,7 @@ public:
                 }
                 index = (index + delta) & mask;
                 delta <<= 1;
-            } while (index != origIndex);
+            } while (delta <= fCapacity);
             if (autoGrow) {
                 this->grow();
             } else {
@@ -91,9 +92,7 @@ public:
     void remove(const KEY& key) {
         const T* const deleted = this->deletedValue();
         const unsigned mask = this->hashMask();
-        const uint32_t hash = HASH_FROM_KEY(key);
-        int index = hash & mask;
-        SkDEBUGCODE(const int origIndex = index;)
+        int index = this->hashToIndex(HASH_FROM_KEY(key));
         int delta = 1;
         
         for (;;) {
@@ -101,20 +100,51 @@ public:
             SkASSERT(candidate);
             if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
                 fArray[index] = const_cast<T*>(deleted);
+                fCountUsed -= 1;
                 fCountDeleted += 1;
                 break;
             }
             index = (index + delta) & mask;
             delta <<= 1;
-            SkASSERT(index != origIndex);
+            SkASSERT(delta <= fCapacity);
         }
         this->checkStrink();
     }
     
 private:
+    int countCollisions(const Key& key) const {
+        const T* const deleted = this->deletedValue();
+        const unsigned mask = this->hashMask();
+        int index = this->hashToIndex(HASH_FROM_KEY(key));
+        int delta = 1;
+        int collisionCount = 0;
+
+        for (;;) {
+            const T* candidate = fArray[index];
+            SkASSERT(candidate);
+            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+                break;
+            }
+            index = (index + delta) & mask;
+            delta <<= 1;
+            collisionCount += 1;
+            SkASSERT(delta <= fCapacity);
+        }
+        return collisionCount;
+    }
+
     void grow() {
         const T* const deleted = this->deletedValue();
-        
+#if 0
+        SkDebugf("growing from %d: used=%d\n", fCapacity, fCountUsed);
+        for (int i = 0; i < fCapacity; ++i) {
+            T* elem = fArray[i];
+            if (NULL == elem || deleted == elem) {
+                continue;
+            }
+            SkDebugf("    entry[%d] had %d collisions\n", i, countCollisions(KEY_FROM_T(*elem)));
+        }
+#endif
         int oldCapacity = fCapacity;
         T** oldArray = fArray;
         
@@ -137,10 +167,16 @@ private:
             SkASSERT(success);
         }
         SkASSERT(oldCountUsed == fCountUsed);
-        sk_free(oldArray);
+
+        if (oldArray != fStorage) {
+            sk_free(oldArray);
+        }
     }
     
-    void checkStrink() {}
+    void checkStrink() {
+        // todo: based on density and deadspace (fCountDeleted), consider
+        // shrinking fArray and repopulating it.
+    }
 };
 
 #endif