From 83ca337348c74dede813b2022943c25a337f32eb Mon Sep 17 00:00:00 2001
From: "reed@google.com" <reed@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Thu, 12 Jul 2012 15:27:54 +0000
Subject: [PATCH] check a hashtable before using a bsearch Review URL:
 https://codereview.appspot.com/6345097

git-svn-id: http://skia.googlecode.com/svn/trunk@4572 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkPictureFlat.h     | 52 +++++++++++++++++++++++++++++++-----
 src/core/SkPictureRecord.cpp |  8 +++---
 2 files changed, 50 insertions(+), 10 deletions(-)

diff --git a/src/core/SkPictureFlat.h b/src/core/SkPictureFlat.h
index e2026dee8a..b8f0b083f8 100644
--- a/src/core/SkPictureFlat.h
+++ b/src/core/SkPictureFlat.h
@@ -200,6 +200,8 @@ public:
         this->setSentinel(kCandidate_Sentinel);
     }
 
+    uint32_t checksum() const { return fChecksum; }
+
 #ifdef SK_DEBUG_SIZE
     // returns the logical size of our data. Does not return any sentinel or
     // padding we might have.
@@ -261,6 +263,7 @@ public:
         fHeap = heap;
         // set to 1 since returning a zero from find() indicates failure
         fNextIndex = 1;
+        sk_bzero(fHash, sizeof(fHash));
     }
 
     int count() const { return fData.count(); }
@@ -274,8 +277,12 @@ public:
      * Clears the dictionary of all entries. However, it does NOT free the
      * memory that was allocated for each entry.
      */
-    void reset() { fData.reset(); fNextIndex = 1; }
-
+    void reset() {
+        fData.reset();
+        fNextIndex = 1;
+        sk_bzero(fHash, sizeof(fHash));
+    }
+    
     /**
      * Given an element of type T it returns its index in the dictionary. If
      * the element wasn't previously in the dictionary it is automatically added
@@ -287,23 +294,31 @@ public:
      *  This trick allows Compare to always loop until failure. If it fails on
      *  the sentinal value, we know the blocks are equal.
      */
-    int find(const T* element, SkRefCntSet* refCntRecorder = NULL,
+    int find(const T& element, SkRefCntSet* refCntRecorder = NULL,
              SkRefCntSet* faceRecorder = NULL, uint32_t writeBufferflags = 0) {
-        if (element == NULL)
-            return 0;
-        SkFlatData* flat = SkFlatData::Create(fHeap, element, fNextIndex,
+
+        SkFlatData* flat = SkFlatData::Create(fHeap, &element, fNextIndex,
                 fFlattenProc, refCntRecorder, faceRecorder, writeBufferflags);
 
+        int hashIndex = ChecksumToHashIndex(flat->checksum());
+        const SkFlatData* candidate = fHash[hashIndex];
+        if (candidate && !SkFlatData::Compare(flat, candidate)) {
+            (void)fHeap->unalloc(flat);
+            return candidate->index();
+        }
+        
         int index = SkTSearch<SkFlatData>((const SkFlatData**) fData.begin(),
                 fData.count(), flat, sizeof(flat), &SkFlatData::Compare);
         if (index >= 0) {
             (void)fHeap->unalloc(flat);
+            fHash[hashIndex] = fData[index];
             return fData[index]->index();
         }
 
         index = ~index;
         *fData.insert(index) = flat;
         flat->setSentinelInCache();
+        fHash[hashIndex] = flat;
         SkASSERT(fData.count() == fNextIndex);
         return fNextIndex++;
     }
@@ -337,6 +352,31 @@ private:
     SkChunkAlloc* fHeap;
     int fNextIndex;
     SkTDArray<const SkFlatData*> fData;
+
+    enum {
+        // Determined by trying diff values on picture-recording benchmarks
+        // (e.g. PictureRecordBench.cpp), choosing the smallest value that
+        // showed a big improvement. Even better would be to benchmark diff
+        // values on recording representative web-pages or other "real" content.
+        HASH_BITS   = 7,
+        HASH_MASK   = (1 << HASH_BITS) - 1,
+        HASH_COUNT  = 1 << HASH_BITS
+    };
+    const SkFlatData* fHash[HASH_COUNT];
+    
+    static int ChecksumToHashIndex(uint32_t checksum) {
+        int n = checksum;
+        if (HASH_BITS < 32) {
+            n ^= n >> 16;
+        }
+        if (HASH_BITS < 16) {
+            n ^= n >> 8;
+        }
+        if (HASH_BITS < 8) {
+            n ^= n >> 4;
+        }
+        return n & HASH_MASK;
+    }        
 };
 
 ///////////////////////////////////////////////////////////////////////////////
diff --git a/src/core/SkPictureRecord.cpp b/src/core/SkPictureRecord.cpp
index a55c9afe9a..f961bc4c62 100644
--- a/src/core/SkPictureRecord.cpp
+++ b/src/core/SkPictureRecord.cpp
@@ -521,7 +521,7 @@ void SkPictureRecord::addMatrix(const SkMatrix& matrix) {
 }
 
 void SkPictureRecord::addMatrixPtr(const SkMatrix* matrix) {
-    addInt(fMatrices.find(matrix));
+    this->addInt(matrix ? fMatrices.find(*matrix) : 0);
 }
 
 void SkPictureRecord::addPaint(const SkPaint& paint) {
@@ -529,7 +529,7 @@ void SkPictureRecord::addPaint(const SkPaint& paint) {
 }
 
 void SkPictureRecord::addPaintPtr(const SkPaint* paint) {
-    addInt(fPaints.find(paint, &fRCSet, &fTFSet));
+    this->addInt(paint ? fPaints.find(*paint, &fRCSet, &fTFSet) : 0);
 }
 
 void SkPictureRecord::addPath(const SkPath& path) {
@@ -597,7 +597,7 @@ void SkPictureRecord::addIRectPtr(const SkIRect* rect) {
 }
 
 void SkPictureRecord::addRegion(const SkRegion& region) {
-    addInt(fRegions.find(&region));
+    addInt(fRegions.find(region));
 }
 
 void SkPictureRecord::addText(const void* text, size_t byteLength) {
@@ -640,7 +640,7 @@ int SkPictureRecord::find(const SkBitmap& bitmap) {
     
     uint32_t writeFlags = flattenPixels ?
         SkFlattenableWriteBuffer::kForceFlattenBitmapPixels_Flag : 0;
-    int index = fBitmaps.find(&bitmap, &fRCSet, NULL, writeFlags);
+    int index = fBitmaps.find(bitmap, &fRCSet, NULL, writeFlags);
 
     if (flattenPixels) {
         entry.fIndex = index;
-- 
2.34.1