diff --git a/bench/CmapBench.cpp b/bench/CmapBench.cpp
index 3fcda85..8178477 100644
--- a/bench/CmapBench.cpp
+++ b/bench/CmapBench.cpp
@@ -7,70 +7,109 @@
 
 #include "Benchmark.h"
 #include "SkCanvas.h"
+#include "SkCharToGlyphCache.h"
 #include "SkFont.h"
+#include "SkRandom.h"
 #include "SkTypeface.h"
+#include "SkUTF.h"
 
 enum {
     NGLYPHS = 100
 };
 
-typedef void (*TypefaceProc)(int loops, const SkFont&, const void* text, size_t len,
-                             int glyphCount);
+namespace {
+struct Rec {
+    const SkCharToGlyphCache&   fCache;
+    int                         fLoops;
+    const SkFont&               fFont;
+    const SkUnichar*            fText;
+    int                         fCount;
+};
+}
 
-static void textToGlyphs_proc(int loops, const SkFont& font, const void* text, size_t len,
-                              int glyphCount) {
+typedef void (*TypefaceProc)(const Rec& r);
+
+static void textToGlyphs_proc(const Rec& r) {
     uint16_t glyphs[NGLYPHS];
-    SkASSERT(glyphCount <= NGLYPHS);
+    SkASSERT(r.fCount <= NGLYPHS);
 
-    for (int i = 0; i < loops; ++i) {
-        font.textToGlyphs(text, len, kUTF8_SkTextEncoding, glyphs, NGLYPHS);
+    for (int i = 0; i < r.fLoops; ++i) {
+        r.fFont.textToGlyphs(r.fText, r.fCount*4, kUTF32_SkTextEncoding, glyphs, NGLYPHS);
     }
 }
 
-static void charsToGlyphs_proc(int loops, const SkFont& font, const void* text,
-                               size_t len, int glyphCount) {
+static void charsToGlyphs_proc(const Rec& r) {
     uint16_t glyphs[NGLYPHS];
-    SkASSERT(glyphCount <= NGLYPHS);
+    SkASSERT(r.fCount <= NGLYPHS);
 
-    SkTypeface* face = font.getTypefaceOrDefault();
-    for (int i = 0; i < loops; ++i) {
-        face->charsToGlyphs(text, SkTypeface::kUTF8_Encoding, glyphs, glyphCount);
+    SkTypeface* face = r.fFont.getTypefaceOrDefault();
+    for (int i = 0; i < r.fLoops; ++i) {
+        face->charsToGlyphs(r.fText, SkTypeface::kUTF32_Encoding, glyphs, r.fCount);
     }
 }
 
-static void charsToGlyphsNull_proc(int loops, const SkFont& font, const void* text,
-                                   size_t len, int glyphCount) {
-    SkTypeface* face = font.getTypefaceOrDefault();
-    for (int i = 0; i < loops; ++i) {
-        face->charsToGlyphs(text, SkTypeface::kUTF8_Encoding, nullptr, glyphCount);
+static void addcache_proc(const Rec& r) {
+    for (int i = 0; i < r.fLoops; ++i) {
+        SkCharToGlyphCache cache;
+        for (int i = 0; i < r.fCount; ++i) {
+            cache.addCharAndGlyph(r.fText[i], i);
+        }
     }
 }
 
+static void findcache_proc(const Rec& r) {
+    for (int i = 0; i < r.fLoops; ++i) {
+        for (int i = 0; i < r.fCount; ++i) {
+            r.fCache.findGlyphIndex(r.fText[i]);
+        }
+    }
+}
+
+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;
-    char         fText[NGLYPHS];
+    SkUnichar    fText[NGLYPHS];
     SkFont       fFont;
+    SkCharToGlyphCache fCache;
 
 public:
     CMAPBench(TypefaceProc proc, const char name[]) {
         fProc = proc;
         fName.printf("cmap_%s", name);
 
+        UnicharGen gen(3);
         for (int i = 0; i < NGLYPHS; ++i) {
-            // we're jamming values into utf8, so we must keep it legal utf8
-            fText[i] = 'A' + (i & 31);
+            fText[i] = gen.next();
+            fCache.addCharAndGlyph(fText[i], i);
         }
         fFont.setTypeface(SkTypeface::MakeDefault());
     }
 
+    bool isSuitableFor(Backend backend) override {
+        return backend == kNonRendering_Backend;
+    }
+
 protected:
     const char* onGetName() override {
         return fName.c_str();
     }
 
     void onDraw(int loops, SkCanvas* canvas) override {
-        fProc(loops, fFont, fText, sizeof(fText), NGLYPHS);
+        fProc({fCache, loops, fFont, fText, NGLYPHS});
     }
 
 private:
@@ -80,6 +119,7 @@
 
 //////////////////////////////////////////////////////////////////////////////
 
-DEF_BENCH( return new CMAPBench(textToGlyphs_proc, "paint_textToGlyphs"); )
-DEF_BENCH( return new CMAPBench(charsToGlyphs_proc, "face_charsToGlyphs"); )
-DEF_BENCH( return new CMAPBench(charsToGlyphsNull_proc, "face_charsToGlyphs_null"); )
+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"); )
diff --git a/gn/utils.gni b/gn/utils.gni
index 74d890c..4a44408 100644
--- a/gn/utils.gni
+++ b/gn/utils.gni
@@ -22,7 +22,7 @@
   "$_include/utils/SkParsePath.h",
   "$_include/utils/SkRandom.h",
   "$_include/utils/SkShadowUtils.h",
-  
+
   #mac
   "$_include/utils/mac/SkCGUtils.h",
 ]
@@ -38,6 +38,8 @@
   "$_src/utils/SkCanvasStack.h",
   "$_src/utils/SkCanvasStack.cpp",
   "$_src/utils/SkCanvasStateUtils.cpp",
+  "$_src/utils/SkCharToGlyphCache.cpp",
+  "$_src/utils/SkCharToGlyphCache.h",
   "$_src/utils/SkDashPath.cpp",
   "$_src/utils/SkDashPathPriv.h",
   "$_src/utils/SkEventTracer.cpp",
diff --git a/include/private/SkMalloc.h b/include/private/SkMalloc.h
index 0e41073..9c899b3 100644
--- a/include/private/SkMalloc.h
+++ b/include/private/SkMalloc.h
@@ -124,4 +124,13 @@
     return dst;
 }
 
+static inline void* sk_careful_memmove(void* dst, const void* src, size_t len) {
+    // When we pass >0 len we had better already be passing valid pointers.
+    // So we just need to skip calling memcpy when len == 0.
+    if (len) {
+        memmove(dst,src,len);
+    }
+    return dst;
+}
+
 #endif  // SkMalloc_DEFINED
diff --git a/src/utils/SkCharToGlyphCache.cpp b/src/utils/SkCharToGlyphCache.cpp
new file mode 100644
index 0000000..1ce91a6
--- /dev/null
+++ b/src/utils/SkCharToGlyphCache.cpp
@@ -0,0 +1,96 @@
+/*
+ * Copyright 2019 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#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)
+//
+//       Also, consider adding sentinels to key arrays so we don't have to check that
+//       index is in rage.
+//
+template <typename T> int find_index(const T* base, int count, T value) {
+    for (int index = 0; index < count; ++index) {
+        if (value <= base[index]) {
+            if (value < base[index]) {
+                index = ~index; // not found
+            }
+            return index;
+        }
+    }
+    return ~count;    // append at the end
+}
+
+SkCharToGlyphCache::SkCharToGlyphCache() {}
+
+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];
+        }
+    } else {
+        int count = fKey32.count();
+        index = find_index(fKey32.begin(), count, unichar);
+        if (index >= 0) {
+            return fValue16[index];
+        }
+    }
+    SkASSERT(index < 0);
+    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);
+
+        f1616.setCount(f1616.size() + 2); // make room for key and value
+        uint16_t* base = f1616.begin();
+
+        // 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;
+    }
+    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]);
+    }
+#endif
+}
diff --git a/src/utils/SkCharToGlyphCache.h b/src/utils/SkCharToGlyphCache.h
new file mode 100644
index 0000000..2eed22e
--- /dev/null
+++ b/src/utils/SkCharToGlyphCache.h
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2019 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkCharToGlyphCache_DEFINED
+#define SkCharToGlyphCache_DEFINED
+
+#include "SkTypes.h"
+#include "../private/SkTDArray.h"
+
+class SkCharToGlyphCache {
+public:
+    SkCharToGlyphCache();
+    ~SkCharToGlyphCache();
+
+    /**
+     *  Given a unichar, return its glyphID (if the return value is positive), else return
+     *  ~index of where to insert the computed glyphID.
+     *
+     *  int result = cache.charToGlyph(unichar);
+     *  if (result >= 0) {
+     *      glyphID = result;
+     *  } else {
+     *      glyphID = compute_glyph_using_typeface(unichar);
+     *      cache.insertCharAndGlyph(~result, unichar, glyphID);
+     *  }
+     */
+    int findGlyphIndex(SkUnichar c) const;
+
+    /**
+     *  Insert a new char/glyph pair into the cache at the specified index.
+     *  See charToGlyph() for how to compute the bit-not of the index.
+     */
+    void insertCharAndGlyph(int index, SkUnichar, SkGlyphID);
+
+    // helper to pre-seed an entry in the cache
+    void addCharAndGlyph(SkUnichar unichar, SkGlyphID glyph) {
+        int index = this->findGlyphIndex(unichar);
+        if (index >= 0) {
+            SkASSERT(SkToU16(index) == glyph);
+        } else {
+            this->insertCharAndGlyph(~index, unichar, glyph);
+        }
+    }
+
+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;
+};
+
+#endif
diff --git a/tests/TestUtils.cpp b/tests/TestUtils.cpp
index 560894f..e0fbc57 100644
--- a/tests/TestUtils.cpp
+++ b/tests/TestUtils.cpp
@@ -182,3 +182,46 @@
     dst->prepend("data:image/png;base64,");
     return true;
 }
+
+#include "SkCharToGlyphCache.h"
+
+static SkGlyphID hash_to_glyph(uint32_t value) {
+    return SkToU16(((value >> 16) ^ value) & 0xFFFF);
+}
+
+namespace {
+class UnicharGen {
+    SkUnichar fU;
+    const int fStep;
+public:
+    UnicharGen(int step) : fU(0), fStep(step) {}
+
+    SkUnichar next() {
+        fU += fStep;
+        return fU;
+    }
+};
+}
+
+DEF_TEST(chartoglyph_cache, reporter) {
+    SkCharToGlyphCache cache;
+    const int step = 3;
+
+    UnicharGen gen(step);
+    for (int i = 0; i < 500; ++i) {
+        SkUnichar c = gen.next();
+        SkGlyphID glyph = hash_to_glyph(c);
+
+        int index = cache.findGlyphIndex(c);
+        REPORTER_ASSERT(reporter, index < 0);
+        cache.insertCharAndGlyph(~index, c, glyph);
+
+        UnicharGen gen2(step);
+        for (int j = 0; j <= i; ++j) {
+            c = gen2.next();
+            glyph = hash_to_glyph(c);
+            index = cache.findGlyphIndex(c);
+            REPORTER_ASSERT(reporter, (unsigned)index == glyph);
+        }
+    }
+}