Make the glyph array entries inline.

Perf Reports
bin/c --match nytimes --config 8888
desk_nytimes.skp_1_mpd	1.41ms -> 1.38ms	0.98x
desk_nytimes.skp_1	1.94ms -> 1.87ms	0.97x

bin/c --match nytimes --config gpu
desk_nytimes.skp_1_mpd	1.63ms -> 1.59ms	0.97x
desk_nytimes.skp_1	1.56ms ->  1.5ms	0.97x

Here are results from mac instruments:
--match nytimes --config gpu --samples 10000 --skps /Users/herb/src/skia/skps

Inline:
Total Samples	Running Time	Self		Symbol Name
94335	94335.0ms   98.3%	0.0	 	 start
2365	2365.0ms    2.4%	2365.0	 	SkGlyphCache::getGlyphIDMetrics(unsigned short, int, int)
975	975.0ms    1.0%	975.0	 	SkGlyphCache::lookupMetrics(unsigned int, SkGlyphCache::MetricsType)

Clean:
Total Samples	Running Time	Self		Symbol Name
96833	96833.0ms   97.3%	0.0	 	 start
3418	3418.0ms    3.4%	3418.0	 	SkGlyphCache::getGlyphIDMetrics(unsigned short, int, int)
1961	1961.0ms    1.9%	1961.0	 	SkGlyphCache::lookupMetrics(unsigned int, SkGlyphCache::MetricsType)

BUG=skia:

Committed: https://skia.googlesource.com/skia/+/4c08f16b252a55e438a61f26e5581394ed177da1

Committed: https://skia.googlesource.com/skia/+/b4c29ac173e6f8844327338687248b98bc94132d

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

3 files changed, 138 insertions, 137 deletions

diff --git a/src/core/SkGlyph.h b/src/core/SkGlyph.h
index 25aaed77a6..48b9815a03 100644
--- a/src/core/SkGlyph.h
+++ b/src/core/SkGlyph.h
@@ -53,6 +53,10 @@ class SkGlyph {
         this->initCommon(glyph.fID);
     }
 
+    void initGlyphFromCombinedID(uint32_t combined_id) {
+      this->initCommon(combined_id);
+    }
+
     /**
      *  Compute the rowbytes for the specified width and mask-format.
      */
@@ -106,7 +110,6 @@ class SkGlyph {
      */
     void zeroMetrics();
 
-
     void toMask(SkMask* mask) const;
 
  private:
@@ -120,8 +123,9 @@ class SkGlyph {
         fMaskFormat     = MASK_FORMAT_UNKNOWN;
         fForceBW        = 0;
     }
+
     static unsigned ID2Code(uint32_t id) {
-        return (id & kCodeMask);
+        return id & kCodeMask;
     }
 
     static unsigned ID2SubX(uint32_t id) {
@@ -142,6 +146,7 @@ class SkGlyph {
     }
 
     static uint32_t MakeID(unsigned code) {
+        SkASSERT(code <= kCodeMask);
         return code;
     }
 
@@ -150,8 +155,8 @@ class SkGlyph {
         x = FixedToSub(x);
         y = FixedToSub(y);
         return (x << (kSubShift + kSubShiftX)) |
-            (y << (kSubShift + kSubShiftY)) |
-            code;
+               (y << (kSubShift + kSubShiftY)) |
+               code;
     }
 
   // FIXME - This is needed because the Android frame work directly
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index f0fd859385..3fe8f0ae9e 100755
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -66,10 +66,14 @@ SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkSca
 
     fDesc = desc->copy();
     fScalerContext->getFontMetrics(&fFontMetrics);
-
-    // init to 0 so that all of the pointers will be null
-    memset(fGlyphHash, 0, sizeof(fGlyphHash));
             
+    // Create the sentinel SkGlyph.
+    SkGlyph* sentinel = fGlyphArray.insert(kSentinelGlyphIndex);
+    sentinel->initGlyphFromCombinedID(kSentinelGlyphID);
+            
+    // Initialize all index to zero which points to the sentinel SkGlyph.
+    memset(fGlyphHash, 0x00, sizeof(fGlyphHash));
+
     fMemoryUsed = sizeof(*this);
 
     fGlyphArray.setReserve(kMinGlyphCount);
@@ -106,10 +110,10 @@ SkGlyphCache::~SkGlyphCache() {
 
     }
 #endif
-    SkGlyph**   gptr = fGlyphArray.begin();
-    SkGlyph**   stop = fGlyphArray.end();
+    SkGlyph*   gptr = fGlyphArray.begin();
+    SkGlyph*   stop = fGlyphArray.end();
     while (gptr < stop) {
-        SkPath* path = (*gptr)->fPath;
+        SkPath* path = gptr->fPath;
         if (path) {
             SkDELETE(path);
         }
@@ -122,15 +126,31 @@ SkGlyphCache::~SkGlyphCache() {
 
 SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
     if (NULL == fCharToGlyphHash.get()) {
+        // Allocate the array.
         fCharToGlyphHash.reset(kHashCount);
-        // init with 0xFF so that the charCode field will be -1, which is invalid
-        memset(fCharToGlyphHash.get(), 0xFF,
+        // Initialize entries of fCharToGlyphHash to index the sentinel glyph.
+        memset(fCharToGlyphHash.get(), 0x00,
                sizeof(CharGlyphRec) * kHashCount);
     }
     
     return &fCharToGlyphHash[ID2HashIndex(id)];
 }
 
+void SkGlyphCache::adjustCaches(int insertion_index) {
+    for (int i = 0; i < kHashCount; ++i) {
+        if (fGlyphHash[i] >= SkToU16(insertion_index)) {
+            fGlyphHash[i] += 1;
+        }
+    }
+    if (fCharToGlyphHash.get() != NULL) {
+        for (int i = 0; i < kHashCount; ++i) {
+            if (fCharToGlyphHash[i].fGlyphIndex >= SkToU16(insertion_index)) {
+                fCharToGlyphHash[i].fGlyphIndex += 1;
+            }
+        }
+    }
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
@@ -145,7 +165,7 @@ uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
     const CharGlyphRec& rec = *this->getCharGlyphRec(id);
 
     if (rec.fID == id) {
-        return rec.fGlyph->getGlyphID();
+        return fGlyphArray[rec.fGlyphIndex].getGlyphID();
     } else {
         return fScalerContext->charToGlyphID(charCode);
     }
@@ -163,159 +183,119 @@ unsigned SkGlyphCache::getGlyphCount() {
 
 const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    CharGlyphRec* rec = this->getCharGlyphRec(id);
-
-    if (rec->fID != id) {
-        // this ID is based on the UniChar
-        rec->fID = id;
-        // this ID is based on the glyph index
-        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
-        rec->fGlyph = this->lookupMetrics(id, kJustAdvance_MetricsType);
-    }
-    return *rec->fGlyph;
+    return *this->lookupByChar(charCode, kJustAdvance_MetricsType);
 }
 
 const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
     VALIDATE();
     uint32_t id = SkGlyph::MakeID(glyphID);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        glyph = this->lookupMetrics(glyphID, kJustAdvance_MetricsType);
-        fGlyphHash[index] = glyph;
-    }
-    return *glyph;
+    return *this->lookupByCombinedID(id, kJustAdvance_MetricsType);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    CharGlyphRec* rec = this->getCharGlyphRec(id);
-
-    if (rec->fID != id) {
-        RecordHashCollisionIf(rec->fGlyph != NULL);
-        // this ID is based on the UniChar
-        rec->fID = id;
-        // this ID is based on the glyph index
-        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
-        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
-    } else {
-        RecordHashSuccess();
-        if (rec->fGlyph->isJustAdvance()) {
-            fScalerContext->getMetrics(rec->fGlyph);
-        }
-    }
-    SkASSERT(rec->fGlyph->isFullMetrics());
-    return *rec->fGlyph;
+    return *this->lookupByChar(charCode, kFull_MetricsType);
 }
 
 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
                                                SkFixed x, SkFixed y) {
     VALIDATE();
+    return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
+}
+
+const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
+    VALIDATE();
+    uint32_t id = SkGlyph::MakeID(glyphID);
+    return *this->lookupByCombinedID(id, kFull_MetricsType);
+}
+
+const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
+    VALIDATE();
+    uint32_t id = SkGlyph::MakeID(glyphID, x, y);
+    return *this->lookupByCombinedID(id, kFull_MetricsType);
+}
+
+SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
     uint32_t id = SkGlyph::MakeID(charCode, x, y);
     CharGlyphRec* rec = this->getCharGlyphRec(id);
-
+    SkGlyph* glyph;
     if (rec->fID != id) {
-        RecordHashCollisionIf(rec->fGlyph != NULL);
+        RecordHashCollisionIf(glyph_index != kSentinelGlyphIndex);
         // this ID is based on the UniChar
         rec->fID = id;
         // this ID is based on the glyph index
         id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
-        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
+        rec->fGlyphIndex = this->lookupMetrics(id, type);
+        glyph = &fGlyphArray[rec->fGlyphIndex];
     } else {
         RecordHashSuccess();
-        if (rec->fGlyph->isJustAdvance()) {
-            fScalerContext->getMetrics(rec->fGlyph);
-        }
-    }
-    SkASSERT(rec->fGlyph->isFullMetrics());
-    return *rec->fGlyph;
-}
-
-const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
-    VALIDATE();
-    uint32_t id = SkGlyph::MakeID(glyphID);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        RecordHashCollisionIf(glyph != NULL);
-        glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
-        fGlyphHash[index] = glyph;
-    } else {
-        RecordHashSuccess();
-        if (glyph->isJustAdvance()) {
+        glyph = &fGlyphArray[rec->fGlyphIndex];
+        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
             fScalerContext->getMetrics(glyph);
         }
     }
-    SkASSERT(glyph->isFullMetrics());
-    return *glyph;
+    return glyph;
 }
 
-const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
-    VALIDATE();
-    uint32_t id = SkGlyph::MakeID(glyphID, x, y);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        RecordHashCollisionIf(glyph != NULL);
-        glyph = this->lookupMetrics(id, kFull_MetricsType);
-        fGlyphHash[index] = glyph;
+SkGlyph* SkGlyphCache::lookupByCombinedID(uint32_t id, MetricsType type) {
+    uint32_t hash_index = ID2HashIndex(id);
+    uint16_t glyph_index = fGlyphHash[hash_index];
+    SkGlyph* glyph = &fGlyphArray[glyph_index];
+    
+    if (glyph->fID != id) {
+        RecordHashCollisionIf(glyph_index != kSentinelGlyphIndex);
+        glyph_index = this->lookupMetrics(id, type);
+        fGlyphHash[hash_index] = glyph_index;
+        glyph = &fGlyphArray[glyph_index];
     } else {
         RecordHashSuccess();
-        if (glyph->isJustAdvance()) {
-            fScalerContext->getMetrics(glyph);
+        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
+           fScalerContext->getMetrics(glyph);
         }
     }
-    SkASSERT(glyph->isFullMetrics());
-    return *glyph;
+    return glyph;
 }
 
-SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
-    SkGlyph* glyph;
-
-    int     hi = 0;
-    int     count = fGlyphArray.count();
-
-    if (count) {
-        SkGlyph**   gptr = fGlyphArray.begin();
-        int     lo = 0;
-
-        hi = count - 1;
-        while (lo < hi) {
-            int mid = (hi + lo) >> 1;
-            if (gptr[mid]->fID < id) {
-                lo = mid + 1;
-            } else {
-                hi = mid;
-            }
-        }
-        glyph = gptr[hi];
-        if (glyph->fID == id) {
-            if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
-                fScalerContext->getMetrics(glyph);
-            }
-            return glyph;
+uint16_t SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
+    // Count is always greater than 0 because of the sentinel.
+    // The fGlyphArray cache is in descending order, so that the sentinel with a value of ~0 is
+    // always at index 0.
+    SkGlyph* gptr = fGlyphArray.begin();
+    int lo = 0;
+    int hi = fGlyphArray.count() - 1;
+    while (lo < hi) {
+        int mid = (hi + lo) >> 1;
+        if (gptr[mid].fID > id) {
+            lo = mid + 1;
+        } else {
+            hi = mid;
         }
+    }
 
-        // check if we need to bump hi before falling though to the allocator
-        if (glyph->fID < id) {
-            hi += 1;
+    uint16_t glyph_index = hi;
+    SkGlyph* glyph = &gptr[glyph_index];
+    if (glyph->fID == id) {
+        if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
+            fScalerContext->getMetrics(glyph);
         }
+        SkASSERT(glyph_index != kSentinelGlyphIndex);
+        return glyph_index;
     }
 
-    // not found, but hi tells us where to inser the new glyph
+    // check if we need to bump hi before falling though to the allocator
+    if (glyph->fID > id) {
+        glyph_index += 1;
+    }
+  
+    // Not found, but hi contains the index of the insertion point of the new glyph.
     fMemoryUsed += sizeof(SkGlyph);
+  
+    this->adjustCaches(glyph_index);
 
-    glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
-                                        SkChunkAlloc::kThrow_AllocFailType);
-    glyph->initCommon(id);
-    *fGlyphArray.insert(hi) = glyph;
+    glyph = fGlyphArray.insert(glyph_index);
+    glyph->initGlyphFromCombinedID(id);
 
     if (kJustAdvance_MetricsType == mtype) {
         fScalerContext->getAdvance(glyph);
@@ -324,7 +304,8 @@ SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
         fScalerContext->getMetrics(glyph);
     }
 
-    return glyph;
+    SkASSERT(glyph_index != kSentinelGlyphIndex);
+    return glyph_index;
 }
 
 const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
diff --git a/src/core/SkGlyphCache.h b/src/core/SkGlyphCache.h
index b335d29d2d..200655bb41 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -187,32 +187,48 @@ private:
         kFull_MetricsType
     };
 
-    SkGlyph* lookupMetrics(uint32_t id, MetricsType);
+    // Return the SkGlyph* associated with MakeID. The id parameter is the combined glyph/x/y
+    // id generated by MakeID. If it is just a glyph id then x and y are assuemd to be zero.
+    SkGlyph* lookupByCombinedID(uint32_t id, MetricsType type);
+
+    // Return a SkGlyph* associated with unicode id and position x and y.
+    SkGlyph* lookupByChar(SkUnichar id, MetricsType type, SkFixed x = 0, SkFixed y = 0);
+
+    // Return the index of id in the fGlyphArray. If it does
+    // not exist, create a new one using MetricsType.
+    uint16_t lookupMetrics(uint32_t id, MetricsType type);
     static bool DetachProc(const SkGlyphCache*, void*) { return true; }
 
-    SkGlyphCache*       fNext, *fPrev;
-    SkDescriptor*       fDesc;
-    SkScalerContext*    fScalerContext;
+    SkGlyphCache*        fNext, *fPrev;
+    SkDescriptor*        fDesc;
+    SkScalerContext*     fScalerContext;
     SkPaint::FontMetrics fFontMetrics;
 
     enum {
-        kHashBits   = 8,
-        kHashCount  = 1 << kHashBits,
-        kHashMask   = kHashCount - 1
+        kHashBits           = 8,
+        kHashCount          = 1 << kHashBits,
+        kHashMask           = kHashCount - 1,
+        kSentinelGlyphIndex = 0,
+        kSentinelGlyphID    = ~0
     };
-    SkGlyph*            fGlyphHash[kHashCount];
-    SkTDArray<SkGlyph*> fGlyphArray;
-    SkChunkAlloc        fGlyphAlloc;
+    
+    // A quick lookup to avoid the binary search looking for glyphs in fGlyphArray.
+    uint16_t             fGlyphHash[kHashCount];
+    SkTDArray<SkGlyph>   fGlyphArray;
+    SkChunkAlloc         fGlyphAlloc;
 
     struct CharGlyphRec {
         uint32_t    fID;    // unichar + subpixel
-        SkGlyph*    fGlyph;
+        uint16_t    fGlyphIndex;
     };
+
     // no reason to use the same kHashCount as fGlyphHash, but we do for now
     // Dynamically allocated when chars are encountered.
     SkAutoTArray<CharGlyphRec> fCharToGlyphHash;
-    
+
+    // The id arg is a combined id generated by MakeID.
     CharGlyphRec* getCharGlyphRec(uint32_t id);
+    void adjustCaches(int insertion_index);
 
     static inline unsigned ID2HashIndex(uint32_t h) {
         return SkChecksum::CheapMix(h) & kHashMask;
@@ -221,7 +237,6 @@ private:
     // 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;