diff --git a/bench/CmapBench.cpp b/bench/CmapBench.cpp
index 8178477..3b90e35 100644
--- a/bench/CmapBench.cpp
+++ b/bench/CmapBench.cpp
@@ -65,35 +65,25 @@
     }
 }
 
-namespace {
-class UnicharGen {
-    SkUnichar fU;
-    const int fStep;
-public:
-    UnicharGen(int step) : fU(0), fStep(step) {}
-
-    SkUnichar next() {
-        fU += fStep;
-        return fU;
-    }
-};
-}
-
 class CMAPBench : public Benchmark {
     TypefaceProc fProc;
     SkString     fName;
     SkUnichar    fText[NGLYPHS];
     SkFont       fFont;
     SkCharToGlyphCache fCache;
+    int          fCount;
 
 public:
-    CMAPBench(TypefaceProc proc, const char name[]) {
-        fProc = proc;
-        fName.printf("cmap_%s", name);
+    CMAPBench(TypefaceProc proc, const char name[], int count) {
+        SkASSERT(count <= NGLYPHS);
 
-        UnicharGen gen(3);
-        for (int i = 0; i < NGLYPHS; ++i) {
-            fText[i] = gen.next();
+        fProc = proc;
+        fName.printf("%s_%d", name, count);
+        fCount = count;
+
+        SkRandom rand;
+        for (int i = 0; i < count; ++i) {
+            fText[i] = rand.nextU() & 0xFFFF;
             fCache.addCharAndGlyph(fText[i], i);
         }
         fFont.setTypeface(SkTypeface::MakeDefault());
@@ -109,7 +99,7 @@
     }
 
     void onDraw(int loops, SkCanvas* canvas) override {
-        fProc({fCache, loops, fFont, fText, NGLYPHS});
+        fProc({fCache, loops, fFont, fText, fCount});
     }
 
 private:
@@ -119,7 +109,16 @@
 
 //////////////////////////////////////////////////////////////////////////////
 
-DEF_BENCH( return new CMAPBench(textToGlyphs_proc, "font_charToGlyph"); )
-DEF_BENCH( return new CMAPBench(charsToGlyphs_proc, "face_charToGlyph"); )
-DEF_BENCH( return new CMAPBench(addcache_proc, "addcache_charToGlyph"); )
-DEF_BENCH( return new CMAPBench(findcache_proc, "findcache_charToGlyph"); )
+constexpr int SMALL = 10;
+
+DEF_BENCH( return new CMAPBench(textToGlyphs_proc, "font_charToGlyph", SMALL); )
+DEF_BENCH( return new CMAPBench(charsToGlyphs_proc, "face_charToGlyph", SMALL); )
+DEF_BENCH( return new CMAPBench(addcache_proc, "addcache_charToGlyph", SMALL); )
+DEF_BENCH( return new CMAPBench(findcache_proc, "findcache_charToGlyph", SMALL); )
+
+constexpr int BIG = 100;
+
+DEF_BENCH( return new CMAPBench(textToGlyphs_proc, "font_charToGlyph", BIG); )
+DEF_BENCH( return new CMAPBench(charsToGlyphs_proc, "face_charToGlyph", BIG); )
+DEF_BENCH( return new CMAPBench(addcache_proc, "addcache_charToGlyph", BIG); )
+DEF_BENCH( return new CMAPBench(findcache_proc, "findcache_charToGlyph", BIG); )
diff --git a/src/utils/SkCharToGlyphCache.cpp b/src/utils/SkCharToGlyphCache.cpp
index 1ce91a6..f962dea 100644
--- a/src/utils/SkCharToGlyphCache.cpp
+++ b/src/utils/SkCharToGlyphCache.cpp
@@ -8,89 +8,116 @@
 #include "SkCharToGlyphCache.h"
 #include "../private/SkTFitsIn.h"
 
-// TODO: consider faster ways to search big arrays
-//       bsearch
-//       slope-based (since we can compute a slope from first and last values)
+SkCharToGlyphCache::SkCharToGlyphCache() {
+    // Add sentinels so we can always rely on these to stop linear searches (in either direction)
+    // Neither is a legal unichar, so we don't care what glyphID we use.
+    //
+    *fK32.append() = 0x80000000;    *fV16.append() = 0;
+    *fK32.append() = 0x7FFFFFFF;    *fV16.append() = 0;
+
+    fDenom = 0;
+}
+
+SkCharToGlyphCache::~SkCharToGlyphCache() {}
+
+// Determined experimentally. For N much larger, the slope technique is faster.
+// For N much smaller, a simple search is faster.
 //
-//       Also, consider adding sentinels to key arrays so we don't have to check that
-//       index is in rage.
+constexpr int kSmallCountLimit = 16;
+
+// To use slope technique we need at least 2 real entries (+2 sentinels) hence the min of 4
 //
-template <typename T> int find_index(const T* base, int count, T value) {
-    for (int index = 0; index < count; ++index) {
+constexpr int kMinCountForSlope = 4;
+
+static int find_simple(const SkUnichar base[], int count, SkUnichar value) {
+    int index;
+    for (index = 0;; ++index) {
         if (value <= base[index]) {
             if (value < base[index]) {
                 index = ~index; // not found
             }
-            return index;
+            break;
         }
     }
-    return ~count;    // append at the end
+    return index;
 }
 
-SkCharToGlyphCache::SkCharToGlyphCache() {}
+static int find_with_slope(const SkUnichar base[], int count, SkUnichar value, double denom) {
+    SkASSERT(count >= kMinCountForSlope);
 
-SkCharToGlyphCache::~SkCharToGlyphCache() {}
-
-int SkCharToGlyphCache::findGlyphIndex(SkUnichar unichar) const {
     int index;
-    if (SkTFitsIn<uint16_t>(unichar)) {
-        int count = f1616.count() >> 1;
-        index = find_index(f1616.begin(), count, SkToU16(unichar));
-        if (index >= 0) {
-            return f1616[count + index];
+    if (value <= base[1]) {
+        index = 1;
+        if (value < base[index]) {
+            index = ~index;
+        }
+    } else if (value >= base[count - 2]) {
+        index = count - 2;
+        if (value > base[index]) {
+            index = ~(index + 1);
         }
     } else {
-        int count = fKey32.count();
-        index = find_index(fKey32.begin(), count, unichar);
-        if (index >= 0) {
-            return fValue16[index];
+        // make our guess based on the "slope" of the current values
+//        index = 1 + (int64_t)(count - 2) * (value - base[1]) / (base[count - 2] - base[1]);
+        index = 1 + (int)(denom * (count - 2) * (value - base[1]));
+        SkASSERT(index >= 1 && index <= count - 2);
+
+        if (value >= base[index]) {
+            for (;; ++index) {
+                if (value <= base[index]) {
+                    if (value < base[index]) {
+                        index = ~index; // not found
+                    }
+                    break;
+                }
+            }
+        } else {
+            for (--index;; --index) {
+                SkASSERT(index >= 0);
+                if (value >= base[index]) {
+                    if (value > base[index]) {
+                        index = ~(index + 1);
+                    }
+                    break;
+                }
+            }
         }
     }
-    SkASSERT(index < 0);
+    return index;
+}
+
+int SkCharToGlyphCache::findGlyphIndex(SkUnichar unichar) const {
+    const int count = fK32.count();
+    int index;
+    if (count <= kSmallCountLimit) {
+        index = find_simple(fK32.begin(), count, unichar);
+    } else {
+        index = find_with_slope(fK32.begin(), count, unichar, fDenom);
+    }
+    if (index >= 0) {
+        return fV16[index];
+    }
     return index;
 }
 
 void SkCharToGlyphCache::insertCharAndGlyph(int index, SkUnichar unichar, SkGlyphID glyph) {
-    if (SkTFitsIn<uint16_t>(unichar)) {
-        // count is the logical count, since our array is really two arrays back-to-back
-        size_t count = f1616.size() >> 1;
-        SkASSERT((unsigned)index <= count);
+    SkASSERT(fK32.size() == fV16.size());
+    SkASSERT((unsigned)index < fK32.size());
+    SkASSERT(unichar < fK32[index]);
 
-        f1616.setCount(f1616.size() + 2); // make room for key and value
-        uint16_t* base = f1616.begin();
+    *fK32.insert(index) = unichar;
+    *fV16.insert(index) = glyph;
 
-        // now slide twice, to make room for the new key and value
-        uint16_t* src = base + count + index;
-        size_t    amt = count - index;
-        sk_careful_memmove(src + 2, src, amt * sizeof(uint16_t));
-
-        src = base + index;
-        amt = count;
-        sk_careful_memmove(src + 1, src, amt * sizeof(uint16_t));
-
-        // now store the new values
-        base[index] = SkToU16(unichar);
-        base[count + 1 + index] = glyph;
-    } else {
-        SkASSERT(fKey32.size() == fValue16.size());
-        SkASSERT((unsigned)index <= fKey32.size());
-
-        *fKey32.insert(index) = unichar;
-        *fValue16.insert(index) = glyph;
+    // if we've changed the first [1] or last [count-2] entry, recompute our slope
+    const int count = fK32.count();
+    if (count >= kMinCountForSlope && (index == 1 || index == count - 2)) {
+        SkASSERT(index >= 1 && index <= count - 2);
+        fDenom = 1.0 / ((double)fK32[count - 2] - fK32[1]);
     }
-    this->validate();
-}
 
-void SkCharToGlyphCache::validate() const {
 #ifdef SK_DEBUG
-    SkASSERT((f1616.count() & 1) == 0);
-    for (int i = 1; i < f1616.count() >> 1; ++i) {
-        SkASSERT(f1616[i - 1] < f1616[i]);
-    }
-
-    SkASSERT(fKey32.size() == fValue16.size());
-    for (int i = 1; i < fKey32.count(); ++i) {
-        SkASSERT(fKey32[i - 1] < fKey32[i]);
+    for (int i = 1; i < fK32.count(); ++i) {
+        SkASSERT(fK32[i-1] < fK32[i]);
     }
 #endif
 }
diff --git a/src/utils/SkCharToGlyphCache.h b/src/utils/SkCharToGlyphCache.h
index 2eed22e..9e93166 100644
--- a/src/utils/SkCharToGlyphCache.h
+++ b/src/utils/SkCharToGlyphCache.h
@@ -47,15 +47,9 @@
     }
 
 private:
-    // If the unichar is <= 16bits, store keys and values (planar) in the same array
-    // [keys...][values...]
-    SkTDArray<uint16_t> f1616;
-
-    // If the unichar is > 16bits, use these two arrays: 32bit key, 16bit value
-    SkTDArray<int32_t>   fKey32;
-    SkTDArray<uint16_t>  fValue16;
-
-    void validate() const;
+    SkTDArray<int32_t>   fK32;
+    SkTDArray<uint16_t>  fV16;
+    double               fDenom;
 };
 
 #endif
diff --git a/tests/TestUtils.cpp b/tests/TestUtils.cpp
index e0fbc57..16ef403 100644
--- a/tests/TestUtils.cpp
+++ b/tests/TestUtils.cpp
@@ -213,6 +213,9 @@
         SkGlyphID glyph = hash_to_glyph(c);
 
         int index = cache.findGlyphIndex(c);
+        if (index >= 0) {
+            index = cache.findGlyphIndex(c);
+        }
         REPORTER_ASSERT(reporter, index < 0);
         cache.insertCharAndGlyph(~index, c, glyph);
 
@@ -221,6 +224,9 @@
             c = gen2.next();
             glyph = hash_to_glyph(c);
             index = cache.findGlyphIndex(c);
+            if ((unsigned)index != glyph) {
+                index = cache.findGlyphIndex(c);
+            }
             REPORTER_ASSERT(reporter, (unsigned)index == glyph);
         }
     }