Use murmur3 finisher to improve font hash efficiency.

Add dump() method to inspect glyphcache strikes.

Murmur addition improves hash efficient roughly 50%

BUG=skia:

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

5 files changed, 103 insertions, 30 deletions

diff --git a/samplecode/SamplePictFile.cpp b/samplecode/SamplePictFile.cpp
index 3fb335fc34..8f827e10aa 100644
--- a/samplecode/SamplePictFile.cpp
+++ b/samplecode/SamplePictFile.cpp
@@ -30,6 +30,8 @@
 #include "SkSurface.h"
 #include "SkXMLParser.h"
 
+#include "SkGlyphCache.h"
+
 class PictFileView : public SampleView {
 public:
     PictFileView(const char name[] = NULL)
@@ -89,12 +91,21 @@ protected:
         SkASSERT(static_cast<int>(fBBox) < kBBoxTypeCount);
         SkPicture** picture = fPictures + fBBox;
 
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+        SkGraphics::PurgeFontCache();
+#endif
+
         if (!*picture) {
             *picture = LoadPicture(fFilename.c_str(), fBBox);
         }
         if (*picture) {
             canvas->drawPicture(*picture);
         }
+
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+        SkGlyphCache::Dump();
+        SkDebugf("\n");
+#endif
     }
 
 private:
diff --git a/src/core/SkChecksum.h b/src/core/SkChecksum.h
index 9f2ebf460a..d9065f5ff3 100644
--- a/src/core/SkChecksum.h
+++ b/src/core/SkChecksum.h
@@ -52,6 +52,19 @@ public:
     }
 
     /**
+     * uint32_t -> uint32_t hash, useful for when you're about to trucate this hash but you
+     * suspect its low bits aren't well mixed.
+     *
+     *  This version is 2-lines cheaper than Mix, but seems to be sufficient for the font cache.
+     */
+    static uint32_t CheapMix(uint32_t hash) {
+        hash ^= hash >> 16;
+        hash *= 0x85ebca6b;
+        hash ^= hash >> 16;
+        return hash;
+    }
+
+    /**
      * Calculate 32-bit Murmur hash (murmur3).
      * This should take 2-3x longer than SkChecksum::Compute, but is a considerably better hash.
      * See en.wikipedia.org/wiki/MurmurHash.
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index 1cbfcd8e6e..a26e9f5cd0 100755
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -1,4 +1,3 @@
-
 /*
  * Copyright 2006 The Android Open Source Project
  *
@@ -6,7 +5,6 @@
  * found in the LICENSE file.
  */
 
-
 #include "SkGlyphCache.h"
 #include "SkGlyphCache_Globals.h"
 #include "SkGraphics.h"
@@ -18,7 +16,6 @@
 #include "SkTypeface.h"
 
 //#define SPEW_PURGE_STATUS
-//#define RECORD_HASH_EFFICIENCY
 
 namespace {
 
@@ -43,26 +40,12 @@ static SkGlyphCache_Globals& getGlobals() {
 
 ///////////////////////////////////////////////////////////////////////////////
 
-#ifdef RECORD_HASH_EFFICIENCY
-    static uint32_t gHashSuccess;
-    static uint32_t gHashCollision;
-
-    static void RecordHashSuccess() {
-        gHashSuccess += 1;
-    }
-
-    static void RecordHashCollisionIf(bool pred) {
-        if (pred) {
-            gHashCollision += 1;
-
-            uint32_t total = gHashSuccess + gHashCollision;
-            SkDebugf("Font Cache Hash success rate: %d%%\n",
-                     100 * gHashSuccess / total);
-        }
-    }
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    #define RecordHashSuccess()             fHashHitCount += 1
+    #define RecordHashCollisionIf(pred)     do { if (pred) fHashMissCount += 1; } while (0)
 #else
-    #define RecordHashSuccess() (void)0
-    #define RecordHashCollisionIf(pred) (void)0
+    #define RecordHashSuccess()             (void)0
+    #define RecordHashCollisionIf(pred)     (void)0
 #endif
 #define RecordHashCollision() RecordHashCollisionIf(true)
 
@@ -94,6 +77,10 @@ SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkSca
     fGlyphArray.setReserve(kMinGlyphCount);
 
     fAuxProcList = NULL;
+
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    fHashHitCount = fHashMissCount = 0;
+#endif
 }
 
 SkGlyphCache::~SkGlyphCache() {
@@ -260,8 +247,7 @@ const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
     return *glyph;
 }
 
-const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID,
-                                               SkFixed x, SkFixed y) {
+const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
     VALIDATE();
     uint32_t id = SkGlyph::MakeID(glyphID, x, y);
     unsigned index = ID2HashIndex(id);
@@ -364,6 +350,29 @@ const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
     return glyph.fPath;
 }
 
+void SkGlyphCache::dump() const {
+    const SkTypeface* face = fScalerContext->getTypeface();
+    const SkScalerContextRec& rec = fScalerContext->getRec();
+    SkMatrix matrix;
+    rec.getSingleMatrix(&matrix);
+    matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize));
+    SkString name;
+    face->getFamilyName(&name);
+
+    SkString msg;
+    msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d",
+               face->uniqueID(), name.c_str(), face->style(), rec.fTextSize,
+               matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
+               matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
+               rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
+               fGlyphArray.count());
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    const int sum = SkTMax(fHashHitCount + fHashMissCount, 1);   // avoid divide-by-zero
+    msg.appendf(" hash:%2d\n", 100 * fHashHitCount / sum);
+#endif
+    SkDebugf("%s\n", msg.c_str());
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 bool SkGlyphCache::getAuxProcData(void (*proc)(void*), void** dataPtr) const {
@@ -520,6 +529,33 @@ void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
     getGlobals().attachCacheToHead(cache);
 }
 
+void SkGlyphCache::Dump() {
+    SkGlyphCache_Globals& globals = getGlobals();
+    SkAutoMutexAcquire    ac(globals.fMutex);
+    SkGlyphCache*         cache;
+
+    globals.validate();
+
+    SkDebugf("SkGlyphCache strikes:%d memory:%d\n",
+             globals.getCacheCountUsed(), (int)globals.getTotalMemoryUsed());
+
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    int hitCount = 0;
+    int missCount = 0;
+#endif
+
+    for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+        hitCount += cache->fHashHitCount;
+        missCount += cache->fHashMissCount;
+#endif
+        cache->dump();
+    }
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    SkDebugf("Hash hit percent:%2d\n", 100 * hitCount / (hitCount + missCount));
+#endif
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
diff --git a/src/core/SkGlyphCache.h b/src/core/SkGlyphCache.h
index bb34a7d977..e11a46025e 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -1,4 +1,3 @@
-
 /*
  * Copyright 2006 The Android Open Source Project
  *
@@ -6,11 +5,11 @@
  * found in the LICENSE file.
  */
 
-
 #ifndef SkGlyphCache_DEFINED
 #define SkGlyphCache_DEFINED
 
 #include "SkBitmap.h"
+#include "SkChecksum.h"
 #include "SkChunkAlloc.h"
 #include "SkDescriptor.h"
 #include "SkGlyph.h"
@@ -23,6 +22,10 @@ class SkPaint;
 
 class SkGlyphCache_Globals;
 
+// Enable this locally to add stats for hash-table hit rates. It also extends the dump()
+// output to show those stats.
+//#define SK_GLYPHCACHE_TRACK_HASH_STATS
+
 /** \class SkGlyphCache
 
     This class represents a strike: a specific combination of typeface, size,
@@ -101,6 +104,8 @@ public:
         return fScalerContext->isSubpixel();
     }
 
+    void dump() const;
+
     /*  AuxProc/Data allow a client to associate data with this cache entry.
         Multiple clients can use this, as their data is keyed with a function
         pointer. In addition to serving as a key, the function pointer is called
@@ -145,6 +150,8 @@ public:
         return VisitCache(typeface, desc, DetachProc, NULL);
     }
 
+    static void Dump();
+
 #ifdef SK_DEBUG
     void validate() const;
 #else
@@ -204,15 +211,19 @@ private:
     // no reason to use the same kHashCount as fGlyphHash, but we do for now
     CharGlyphRec    fCharToGlyphHash[kHashCount];
 
-    static inline unsigned ID2HashIndex(uint32_t id) {
-        id ^= id >> 16;
-        id ^= id >> 8;
-        return id & kHashMask;
+    static inline unsigned ID2HashIndex(uint32_t h) {
+        return SkChecksum::CheapMix(h) & kHashMask;
     }
 
     // used to track (approx) how much ram is tied-up in this cache
     size_t  fMemoryUsed;
 
+
+#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
+    int fHashHitCount;
+    int fHashMissCount;
+#endif
+
     struct AuxProcRec {
         AuxProcRec* fNext;
         void (*fProc)(void*);
diff --git a/src/core/SkScalerContext.h b/src/core/SkScalerContext.h
index 9d3bdc8a8f..4677635d7c 100644
--- a/src/core/SkScalerContext.h
+++ b/src/core/SkScalerContext.h
@@ -243,6 +243,8 @@ public:
 
     static SkMaskGamma::PreBlend GetMaskPreBlend(const Rec& rec);
 
+    const Rec& getRec() const { return fRec; }
+
 protected:
     Rec         fRec;