use murmur3 finisher to improve font hash efficiency

src/core/SkGlyphCache.h

 
 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #ifndef SkGlyphCache_DEFINED
 #define SkGlyphCache_DEFINED
 
 #include "SkBitmap.h"
 #include "SkChunkAlloc.h"
 #include "SkDescriptor.h"
 #include "SkGlyph.h"
 #include "SkScalerContext.h"
 #include "SkTemplates.h"
 #include "SkTDArray.h"
 
 struct SkDeviceProperties;
 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,
     matrix, etc., and holds the glyphs for that strike. Calling any of the
     getUnichar.../getGlyphID... methods will return the requested glyph,
     either instantly if it is already cached, or by first generating it and then
     adding it to the strike.
 
     The strikes are held in a global list, available to all threads. To interact
     with one, call either VisitCache() or DetachCache().
@@ skipping 58 matching lines @@
     const SkDescriptor& getDescriptor() const { return *fDesc; }
 
     SkMask::Format getMaskFormat() const {
         return fScalerContext->getMaskFormat();
     }
 
     bool isSubpixel() const {
         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
         with the data when the glyphcache object is deleted, so the client can
         cleanup their data as well. NOTE: the auxProc must not try to access
         this glyphcache in any way, since it may be in the process of being
         deleted.
     */
 
     //! If the proc is found, return true and set *dataPtr to its data
@@ skipping 24 matching lines @@
         a different strike will be generated. This is fine. It does mean we
         can have more than 1 strike for the same descriptor, but that will
         eventually get purged, and the win is that different thread will never
         block each other while a strike is being used.
     */
     static SkGlyphCache* DetachCache(SkTypeface* typeface,
                                      const SkDescriptor* desc) {
         return VisitCache(typeface, desc, DetachProc, NULL);
     }
 
+    static void Dump();
+
 #ifdef SK_DEBUG
     void validate() const;
 #else
     void validate() const {}
 #endif
 
     class AutoValidate : SkNoncopyable {
     public:
         AutoValidate(const SkGlyphCache* cache) : fCache(cache) {
             if (fCache) {
@@ skipping 39 matching lines @@
     SkTDArray<SkGlyph*> fGlyphArray;
     SkChunkAlloc        fGlyphAlloc;
 
     struct CharGlyphRec {
         uint32_t    fID;    // unichar + subpixel
         SkGlyph*    fGlyph;
     };
     // 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) {

[mtklein, 2015/01/27 22:28:22]

SkChecksum::MixLess?

[reed1, 2015/01/28 21:22:39]

Done.

+        // apply (partial) Murmur3 finisher
+        h ^= h >> 16;
+        h *= 0x85ebca6b;
+#if 0
+        // This part of the Murmur3 finisher does not seems necessary, i.e. it does not seem
+        // to measurably improve our hash-hit efficiency, so we leave it out.
+        h ^= h >> 13;
+        h *= 0xc2b2ae35;
+#endif
+        h ^= h >> 16;
+        return 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*);
         void* fData;
     };
     AuxProcRec* fAuxProcList;
     void invokeAndRemoveAuxProcs();
 
     inline static SkGlyphCache* FindTail(SkGlyphCache* head);
 
@@ skipping 64 matching lines @@
                             const SkMatrix* matrix) {
         fCache = paint.detachCache(deviceProperties, matrix, true);
     }
 
 private:
     SkAutoGlyphCacheNoGamma() : SkAutoGlyphCacheBase() {}
 };
 #define SkAutoGlyphCacheNoGamma(...) SK_REQUIRE_LOCAL_VAR(SkAutoGlyphCacheNoGamma)
 
 #endif