Optimize interactions with glyph cache

There are two fixes here:
- precaching: instead of caching-then-drawing whenever there is a new
glyph, we cache at DisplayList record time. Then when we finally draw that
DisplayList, we just upload the affected texture(s) once, instead of once
per change. This is a huge savings in upload time, especially when there are
larger glyphs being used by the app.
- packing: Previously, glyphs would line up horizontally on each cache line, leaving
potentially tons of space vertically, especially when smaller glyphs got put into cache
lines intended for large glyphs (which can happen when an app uses lots of unique
glyphs, a common case with, for example, chinese/japanese/korean languages). The new
approach packs glyphs vertically as well as horizontally to use the space more efficiently
and provide space for more glyphs in these situations.

Change-Id: I84338aa25db208c7bf13f3f92b4d05ed40c33527

4 files changed, 319 insertions, 77 deletions

diff --git a/libs/hwui/DisplayListRenderer.cpp b/libs/hwui/DisplayListRenderer.cpp
index 95fc2c5..2de70d4 100644
--- a/libs/hwui/DisplayListRenderer.cpp
+++ b/libs/hwui/DisplayListRenderer.cpp
@@ -1699,7 +1699,9 @@ status_t DisplayListRenderer::drawTextOnPath(const char* text, int bytesCount, i
     addFloat(hOffset);
     addFloat(vOffset);
     paint->setAntiAlias(true);
-    addPaint(paint);
+    SkPaint* addedPaint = addPaint(paint);
+    FontRenderer& fontRenderer = mCaches.fontRenderer->getFontRenderer(addedPaint);
+    fontRenderer.precache(addedPaint, text, count);
     return DrawGlInfo::kStatusDone;
 }
 
@@ -1711,7 +1713,9 @@ status_t DisplayListRenderer::drawPosText(const char* text, int bytesCount, int
     addInt(count);
     addFloats(positions, count * 2);
     paint->setAntiAlias(true);
-    addPaint(paint);
+    SkPaint* addedPaint = addPaint(paint);
+    FontRenderer& fontRenderer = mCaches.fontRenderer->getFontRenderer(addedPaint);
+    fontRenderer.precache(addedPaint, text, count);
     return DrawGlInfo::kStatusDone;
 }
 
@@ -1742,7 +1746,11 @@ status_t DisplayListRenderer::drawText(const char* text, int bytesCount, int cou
     addFloat(x);
     addFloat(y);
     addFloats(positions, count * 2);
-    addPaint(paint);
+    SkPaint* addedPaint = addPaint(paint);
+    if (!reject) {
+        FontRenderer& fontRenderer = mCaches.fontRenderer->getFontRenderer(addedPaint);
+        fontRenderer.precache(addedPaint, text, count);
+    }
     addFloat(length);
     addSkip(location);
     return DrawGlInfo::kStatusDone;
diff --git a/libs/hwui/DisplayListRenderer.h b/libs/hwui/DisplayListRenderer.h
index 60a40c6..c8b3e47 100644
--- a/libs/hwui/DisplayListRenderer.h
+++ b/libs/hwui/DisplayListRenderer.h
@@ -770,10 +770,10 @@ private:
         addInt((int) pathCopy);
     }
 
-    inline void addPaint(SkPaint* paint) {
+    inline SkPaint* addPaint(SkPaint* paint) {
         if (!paint) {
             addInt((int) NULL);
-            return;
+            return paint;
         }
 
         SkPaint* paintCopy = mPaintMap.valueFor(paint);
@@ -785,6 +785,8 @@ private:
         }
 
         addInt((int) paintCopy);
+
+        return paintCopy;
     }
 
     inline void addDisplayList(DisplayList* displayList) {
diff --git a/libs/hwui/FontRenderer.cpp b/libs/hwui/FontRenderer.cpp
index ccddd91..a596fa9 100644
--- a/libs/hwui/FontRenderer.cpp
+++ b/libs/hwui/FontRenderer.cpp
@@ -37,11 +37,78 @@ namespace uirenderer {
 #define DEFAULT_TEXT_CACHE_WIDTH 1024
 #define DEFAULT_TEXT_CACHE_HEIGHT 256
 #define MAX_TEXT_CACHE_WIDTH 2048
-#define TEXTURE_BORDER_SIZE 1
+#define CACHE_BLOCK_ROUNDING_SIZE 4
 
 #define AUTO_KERN(prev, next) (((next) - (prev) + 32) >> 6 << 16)
 
 ///////////////////////////////////////////////////////////////////////////////
+// CacheBlock
+///////////////////////////////////////////////////////////////////////////////
+
+/**
+ * Insert new block into existing linked list of blocks. Blocks are sorted in increasing-width
+ * order, except for the final block (the remainder space at the right, since we fill from the
+ * left).
+ */
+CacheBlock* CacheBlock::insertBlock(CacheBlock* head, CacheBlock *newBlock) {
+#if DEBUG_FONT_RENDERER
+    ALOGD("insertBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
+            newBlock, newBlock->mX, newBlock->mY,
+            newBlock->mWidth, newBlock->mHeight);
+#endif
+    CacheBlock *currBlock = head;
+    CacheBlock *prevBlock = NULL;
+    while (currBlock && currBlock->mY != TEXTURE_BORDER_SIZE) {
+        if (newBlock->mWidth < currBlock->mWidth) {
+            newBlock->mNext = currBlock;
+            newBlock->mPrev = prevBlock;
+            currBlock->mPrev = newBlock;
+            if (prevBlock) {
+                prevBlock->mNext = newBlock;
+                return head;
+            } else {
+                return newBlock;
+            }
+        }
+        prevBlock = currBlock;
+        currBlock = currBlock->mNext;
+    }
+    // new block larger than all others - insert at end (but before the remainder space, if there)
+    newBlock->mNext = currBlock;
+    newBlock->mPrev = prevBlock;
+    if (currBlock) {
+        currBlock->mPrev = newBlock;
+    }
+    if (prevBlock) {
+        prevBlock->mNext = newBlock;
+        return head;
+    } else {
+        return newBlock;
+    }
+}
+
+CacheBlock* CacheBlock::removeBlock(CacheBlock* head, CacheBlock *blockToRemove) {
+#if DEBUG_FONT_RENDERER
+    ALOGD("removeBlock: this, x, y, w, h = %p, %d, %d, %d, %d",
+            blockToRemove, blockToRemove->mX, blockToRemove->mY,
+            blockToRemove->mWidth, blockToRemove->mHeight);
+#endif
+    CacheBlock* newHead = head;
+    CacheBlock* nextBlock = blockToRemove->mNext;
+    CacheBlock* prevBlock = blockToRemove->mPrev;
+    if (prevBlock) {
+        prevBlock->mNext = nextBlock;
+    } else {
+        newHead = nextBlock;
+    }
+    if (nextBlock) {
+        nextBlock->mPrev = prevBlock;
+    }
+    delete blockToRemove;
+    return newHead;
+}
+
+///////////////////////////////////////////////////////////////////////////////
 // CacheTextureLine
 ///////////////////////////////////////////////////////////////////////////////
 
@@ -50,14 +117,73 @@ bool CacheTextureLine::fitBitmap(const SkGlyph& glyph, uint32_t *retOriginX, uin
         return false;
     }
 
-    if (mCurrentCol + glyph.fWidth + TEXTURE_BORDER_SIZE * 2 < mMaxWidth) {
-        *retOriginX = mCurrentCol + TEXTURE_BORDER_SIZE;
-        *retOriginY = mCurrentRow + TEXTURE_BORDER_SIZE;
-        mCurrentCol += glyph.fWidth + TEXTURE_BORDER_SIZE * 2;
-        mDirty = true;
-        return true;
+    uint16_t glyphW = glyph.fWidth + TEXTURE_BORDER_SIZE;
+    uint16_t glyphH = glyph.fHeight + TEXTURE_BORDER_SIZE;
+    // roundedUpW equals glyphW to the next multiple of CACHE_BLOCK_ROUNDING_SIZE.
+    // This columns for glyphs that are close but not necessarily exactly the same size. It trades
+    // off the loss of a few pixels for some glyphs against the ability to store more glyphs
+    // of varying sizes in one block.
+    uint16_t roundedUpW =
+            (glyphW + CACHE_BLOCK_ROUNDING_SIZE - 1) & -CACHE_BLOCK_ROUNDING_SIZE;
+    CacheBlock *cacheBlock = mCacheBlocks;
+    while (cacheBlock) {
+        // Store glyph in this block iff: it fits the block's remaining space and:
+        // it's the remainder space (mY == 0) or there's only enough height for this one glyph
+        // or it's within ROUNDING_SIZE of the block width
+        if (roundedUpW <= cacheBlock->mWidth && glyphH <= cacheBlock->mHeight &&
+                (cacheBlock->mY == TEXTURE_BORDER_SIZE ||
+                        (cacheBlock->mWidth - roundedUpW < CACHE_BLOCK_ROUNDING_SIZE))) {
+            if (cacheBlock->mHeight - glyphH < glyphH) {
+                // Only enough space for this glyph - don't bother rounding up the width
+                roundedUpW = glyphW;
+            }
+            *retOriginX = cacheBlock->mX;
+            *retOriginY = mCurrentRow + cacheBlock->mY;
+            // If this is the remainder space, create a new cache block for this column. Otherwise,
+            // adjust the info about this column.
+            if (cacheBlock->mY == TEXTURE_BORDER_SIZE) {
+                uint16_t oldX = cacheBlock->mX;
+                // Adjust remainder space dimensions
+                cacheBlock->mWidth -= roundedUpW;
+                cacheBlock->mX += roundedUpW;
+                if (mMaxHeight - glyphH >= glyphH) {
+                    // There's enough height left over to create a new CacheBlock
+                    CacheBlock *newBlock = new CacheBlock(oldX, glyphH, roundedUpW,
+                            mMaxHeight - glyphH);
+#if DEBUG_FONT_RENDERER
+                    ALOGD("fitBitmap: Created new block: this, x, y, w, h = %p, %d, %d, %d, %d",
+                            newBlock, newBlock->mX, newBlock->mY,
+                            newBlock->mWidth, newBlock->mHeight);
+#endif
+                    mCacheBlocks = CacheBlock::insertBlock(mCacheBlocks, newBlock);
+                }
+            } else {
+                // Insert into current column and adjust column dimensions
+                cacheBlock->mY += glyphH;
+                cacheBlock->mHeight -= glyphH;
+#if DEBUG_FONT_RENDERER
+                ALOGD("fitBitmap: Added to existing block: this, x, y, w, h = %p, %d, %d, %d, %d",
+                        cacheBlock, cacheBlock->mX, cacheBlock->mY,
+                        cacheBlock->mWidth, cacheBlock->mHeight);
+#endif
+            }
+            if (cacheBlock->mHeight < fmin(glyphH, glyphW)) {
+                // If remaining space in this block is too small to be useful, remove it
+                mCacheBlocks = CacheBlock::removeBlock(mCacheBlocks, cacheBlock);
+            }
+            mDirty = true;
+#if DEBUG_FONT_RENDERER
+            ALOGD("fitBitmap: current block list:");
+            mCacheBlocks->output();
+#endif
+            ++mNumGlyphs;
+            return true;
+        }
+        cacheBlock = cacheBlock->mNext;
     }
-
+#if DEBUG_FONT_RENDERER
+    ALOGD("fitBitmap: returning false for glyph of size %d, %d", glyphW, glyphH);
+#endif
     return false;
 }
 
@@ -297,6 +423,27 @@ void Font::measure(SkPaint* paint, const char* text, uint32_t start, uint32_t le
     render(paint, text, start, len, numGlyphs, 0, 0, MEASURE, NULL, 0, 0, bounds, positions);
 }
 
+void Font::precache(SkPaint* paint, const char* text, int numGlyphs) {
+
+    if (numGlyphs == 0 || text == NULL) {
+        return;
+    }
+    int glyphsCount = 0;
+
+    while (glyphsCount < numGlyphs) {
+        glyph_t glyph = GET_GLYPH(text);
+
+        // Reached the end of the string
+        if (IS_END_OF_STRING(glyph)) {
+            break;
+        }
+
+        CachedGlyphInfo* cachedGlyph = getCachedGlyph(paint, glyph);
+
+        glyphsCount++;
+    }
+}
+
 void Font::render(SkPaint* paint, const char* text, uint32_t start, uint32_t len,
         int numGlyphs, int x, int y, RenderMode mode, uint8_t *bitmap,
         uint32_t bitmapW, uint32_t bitmapH, Rect* bounds, const float* positions) {
@@ -545,9 +692,33 @@ void FontRenderer::flushAllAndInvalidate() {
         mActiveFonts[i]->invalidateTextureCache();
     }
 
+    uint16_t totalGlyphs = 0;
     for (uint32_t i = 0; i < mCacheLines.size(); i++) {
-        mCacheLines[i]->mCurrentCol = 0;
+        totalGlyphs += mCacheLines[i]->mNumGlyphs;
+        mCacheLines[i]->init();
+    }
+
+#if DEBUG_FONT_RENDERER
+    ALOGD("FontRenderer: flushAllAndInvalidatel");
+    // Erase caches, just as a debugging facility
+    if (mCacheTextureSmall && mCacheTextureSmall->mTexture) {
+        memset(mCacheTextureSmall->mTexture, 0,
+                mCacheTextureSmall->mWidth * mCacheTextureSmall->mHeight);
+    }
+    if (mCacheTexture128 && mCacheTexture128->mTexture) {
+        memset(mCacheTexture128->mTexture, 0,
+                mCacheTexture128->mWidth * mCacheTexture128->mHeight);
     }
+    if (mCacheTexture256 && mCacheTexture256->mTexture) {
+        memset(mCacheTexture256->mTexture, 0,
+                mCacheTexture256->mWidth * mCacheTexture256->mHeight);
+    }
+    if (mCacheTexture512 && mCacheTexture512->mTexture) {
+        memset(mCacheTexture512->mTexture, 0,
+                mCacheTexture512->mWidth * mCacheTexture512->mHeight);
+    }
+    ALOGD("Flushing caches: glyphs cached = %d", totalGlyphs);
+#endif
 }
 
 void FontRenderer::deallocateTextureMemory(CacheTexture *cacheTexture) {
@@ -573,7 +744,16 @@ void FontRenderer::flushLargeCaches() {
                 cacheLine->mCacheTexture == mCacheTexture256 ||
                 cacheLine->mCacheTexture == mCacheTexture512) &&
                 cacheLine->mCacheTexture->mTexture != NULL) {
-            cacheLine->mCurrentCol = 0;
+#if DEBUG_FONT_RENDERER
+            if (cacheLine->mCacheTexture == mCacheTexture128) {
+                ALOGD("flushing cacheTexture128");
+            } else if (cacheLine->mCacheTexture == mCacheTexture256) {
+                ALOGD("flushing cacheTexture256");
+            } else {
+                ALOGD("flushing cacheTexture512");
+            }
+#endif
+            cacheLine->init();
             for (uint32_t i = 0; i < mActiveFonts.size(); i++) {
                 mActiveFonts[i]->invalidateTextureCache(cacheLine);
             }
@@ -614,9 +794,12 @@ void FontRenderer::cacheBitmap(const SkGlyph& glyph, CachedGlyphInfo* cachedGlyp
         uint32_t* retOriginX, uint32_t* retOriginY) {
     cachedGlyph->mIsValid = false;
     // If the glyph is too tall, don't cache it
-    if (glyph.fHeight + TEXTURE_BORDER_SIZE * 2 > mCacheLines[mCacheLines.size() - 1]->mMaxHeight) {
-        ALOGE("Font size to large to fit in cache. width, height = %i, %i",
-                (int) glyph.fWidth, (int) glyph.fHeight);
+    if (mCacheLines.size() == 0 ||
+        glyph.fHeight + TEXTURE_BORDER_SIZE * 2 > mCacheLines[mCacheLines.size() - 1]->mMaxHeight) {
+        if (mCacheLines.size() != 0) {
+            ALOGE("Font size too large to fit in cache. width, height = %i, %i",
+                    (int) glyph.fWidth, (int) glyph.fHeight);
+        }
         return;
     }
 
@@ -747,26 +930,26 @@ void FontRenderer::initTextTexture() {
     mUploadTexture = false;
     // Split up our default cache texture into lines of certain widths
     int nextLine = 0;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 18, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 18, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 26, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 26, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 26, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 26, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 34, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 34, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 34, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 34, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
-    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 42, nextLine, 0, mCacheTextureSmall));
+    mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, 42, nextLine, mCacheTextureSmall));
     nextLine += mCacheLines.top()->mMaxHeight;
     mCacheLines.push(new CacheTextureLine(mSmallCacheWidth, mSmallCacheHeight - nextLine,
-            nextLine, 0, mCacheTextureSmall));
+            nextLine, mCacheTextureSmall));
 
     //  The first cache is split into 2 lines of height 128, the rest have just one cache line.
-    mCacheLines.push(new CacheTextureLine(maxWidth, 128, 0, 0, mCacheTexture128));
-    mCacheLines.push(new CacheTextureLine(maxWidth, 128, 128, 0, mCacheTexture128));
-    mCacheLines.push(new CacheTextureLine(maxWidth, 256, 0, 0, mCacheTexture256));
-    mCacheLines.push(new CacheTextureLine(maxWidth, 512, 0, 0, mCacheTexture512));
+    mCacheLines.push(new CacheTextureLine(maxWidth, 128, 0, mCacheTexture128));
+    mCacheLines.push(new CacheTextureLine(maxWidth, 128, 128, mCacheTexture128));
+    mCacheLines.push(new CacheTextureLine(maxWidth, 256, 0, mCacheTexture256));
+    mCacheLines.push(new CacheTextureLine(maxWidth, 512, 0, mCacheTexture512));
 }
 
 // Avoid having to reallocate memory and render quad by quad
@@ -837,6 +1020,10 @@ void FontRenderer::checkTextureUpdate() {
                 glBindTexture(GL_TEXTURE_2D, cacheTexture->mTextureId);
                 lastTextureId = cacheTexture->mTextureId;
             }
+#if DEBUG_FONT_RENDERER
+            ALOGD("glTextSubimage for cacheLine %d: xOff, yOff, width height = %d, %d, %d, %d", i,
+                    xOffset, yOffset, width, height);
+#endif
             glTexSubImage2D(GL_TEXTURE_2D, 0, xOffset, yOffset, width, height,
                     GL_ALPHA, GL_UNSIGNED_BYTE, textureData);
 
@@ -960,43 +1147,7 @@ void FontRenderer::appendRotatedMeshQuad(float x1, float y1, float u1, float v1,
     }
 }
 
-uint32_t FontRenderer::getRemainingCacheCapacity() {
-    uint32_t remainingCapacity = 0;
-    float totalPixels = 0;
-
-    //avoid divide by zero if the size is 0
-    if (mCacheLines.size() == 0) {
-        return 0;
-    }
-    for(uint32_t i = 0; i < mCacheLines.size(); i ++) {
-         remainingCapacity += (mCacheLines[i]->mMaxWidth - mCacheLines[i]->mCurrentCol);
-         totalPixels += mCacheLines[i]->mMaxWidth;
-    }
-    remainingCapacity = (remainingCapacity * 100) / totalPixels;
-    return remainingCapacity;
-}
-
-void FontRenderer::precacheLatin(SkPaint* paint) {
-    // Remaining capacity is measured in %
-    uint32_t remainingCapacity = getRemainingCacheCapacity();
-    uint32_t precacheIndex = 0;
-
-    // We store a string with letters in a rough frequency of occurrence
-    String16 l("eisarntolcdugpmhbyfvkwzxjq EISARNTOLCDUGPMHBYFVKWZXJQ,.?!()-+@;:'0123456789");
-
-    size_t size = l.size();
-    uint16_t latin[size];
-    paint->utfToGlyphs(l.string(), SkPaint::kUTF16_TextEncoding, size * sizeof(char16_t), latin);
-
-    while (remainingCapacity > 25 && precacheIndex < size) {
-        mCurrentFont->getCachedGlyph(paint, TO_GLYPH(latin[precacheIndex]));
-        remainingCapacity = getRemainingCacheCapacity();
-        precacheIndex++;
-    }
-}
-
 void FontRenderer::setFont(SkPaint* paint, uint32_t fontId, float fontSize) {
-    uint32_t currentNumFonts = mActiveFonts.size();
     int flags = 0;
     if (paint->isFakeBoldText()) {
         flags |= Font::kFakeBold;
@@ -1012,12 +1163,6 @@ void FontRenderer::setFont(SkPaint* paint, uint32_t fontId, float fontSize) {
     mCurrentFont = Font::create(this, fontId, fontSize, flags, italicStyle,
             scaleX, style, strokeWidth);
 
-    const float maxPrecacheFontSize = 40.0f;
-    bool isNewFont = currentNumFonts != mActiveFonts.size();
-
-    if (isNewFont && fontSize <= maxPrecacheFontSize) {
-        precacheLatin(paint);
-    }
 }
 
 FontRenderer::DropShadow FontRenderer::renderDropShadow(SkPaint* paint, const char *text,
@@ -1084,6 +1229,25 @@ void FontRenderer::finishRender() {
     }
 }
 
+void FontRenderer::precache(SkPaint* paint, const char* text, int numGlyphs) {
+    int flags = 0;
+    if (paint->isFakeBoldText()) {
+        flags |= Font::kFakeBold;
+    }
+    const float skewX = paint->getTextSkewX();
+    uint32_t italicStyle = *(uint32_t*) &skewX;
+    const float scaleXFloat = paint->getTextScaleX();
+    uint32_t scaleX = *(uint32_t*) &scaleXFloat;
+    SkPaint::Style style = paint->getStyle();
+    const float strokeWidthFloat = paint->getStrokeWidth();
+    uint32_t strokeWidth = *(uint32_t*) &strokeWidthFloat;
+    float fontSize = paint->getTextSize();
+    Font* font = Font::create(this, SkTypeface::UniqueID(paint->getTypeface()),
+            fontSize, flags, italicStyle, scaleX, style, strokeWidth);
+
+    font->precache(paint, text, numGlyphs);
+}
+
 bool FontRenderer::renderText(SkPaint* paint, const Rect* clip, const char *text,
         uint32_t startIndex, uint32_t len, int numGlyphs, int x, int y, Rect* bounds) {
     if (!mCurrentFont) {
diff --git a/libs/hwui/FontRenderer.h b/libs/hwui/FontRenderer.h
index 9ed6932..8b1d10c 100644
--- a/libs/hwui/FontRenderer.h
+++ b/libs/hwui/FontRenderer.h
@@ -53,6 +53,8 @@ namespace uirenderer {
     #define IS_END_OF_STRING(glyph) glyph < 0
 #endif
 
+#define TEXTURE_BORDER_SIZE 1
+
 ///////////////////////////////////////////////////////////////////////////////
 // Declarations
 ///////////////////////////////////////////////////////////////////////////////
@@ -80,16 +82,79 @@ public:
     bool mLinearFiltering;
 };
 
+/**
+ * CacheBlock is a noce in a linked list of current free space areas in a CacheTextureLine.
+ * Using CacheBlocks enables us to pack the cache line from top to bottom as well as left to right.
+ * When we add a glyph to the cache, we see if it fits within one of the existing columns that
+ * have already been started (this is the case if the glyph fits vertically as well as
+ * horizontally, and if its width is sufficiently close to the column width to avoid
+ * sub-optimal packing of small glyphs into wide columns). If there is no column in which the
+ * glyph fits, we check the final node, which is the remaining space in the cache line, creating
+ * a new column as appropriate.
+ *
+ * As columns fill up, we remove their CacheBlock from the list to avoid having to check
+ * small blocks in the future.
+ */
+struct CacheBlock {
+    uint16_t mX;
+    uint16_t mY;
+    uint16_t mWidth;
+    uint16_t mHeight;
+    CacheBlock* mNext;
+    CacheBlock* mPrev;
+
+    CacheBlock(uint16_t x, uint16_t y, uint16_t width, uint16_t height, bool empty = false):
+        mX(x), mY(y), mWidth(width), mHeight(height), mNext(NULL), mPrev(NULL)
+    {
+    }
+
+    static CacheBlock* insertBlock(CacheBlock* head, CacheBlock *newBlock);
+
+    static CacheBlock* removeBlock(CacheBlock* head, CacheBlock *blockToRemove);
+
+    void output() {
+        CacheBlock *currBlock = this;
+        while (currBlock) {
+            ALOGD("Block: this, x, y, w, h = %p, %d, %d, %d, %d",
+                    currBlock, currBlock->mX, currBlock->mY, currBlock->mWidth, currBlock->mHeight);
+            currBlock = currBlock->mNext;
+        }
+    }
+};
+
 class CacheTextureLine {
 public:
     CacheTextureLine(uint16_t maxWidth, uint16_t maxHeight, uint32_t currentRow,
-            uint32_t currentCol, CacheTexture* cacheTexture):
+            CacheTexture* cacheTexture):
                 mMaxHeight(maxHeight),
                 mMaxWidth(maxWidth),
                 mCurrentRow(currentRow),
-                mCurrentCol(currentCol),
                 mDirty(false),
+                mNumGlyphs(0),
                 mCacheTexture(cacheTexture) {
+        mCacheBlocks = new CacheBlock(TEXTURE_BORDER_SIZE, TEXTURE_BORDER_SIZE,
+                maxWidth - TEXTURE_BORDER_SIZE, maxHeight - TEXTURE_BORDER_SIZE, true);
+    }
+
+    ~CacheTextureLine() {
+        reset();
+    }
+
+    void reset() {
+        // Delete existing cache blocks
+        while (mCacheBlocks != NULL) {
+            CacheBlock* tmpBlock = mCacheBlocks;
+            mCacheBlocks = mCacheBlocks->mNext;
+            delete tmpBlock;
+        }
+        mNumGlyphs = 0;
+    }
+
+    void init() {
+        // reset, then create a new remainder space to start again
+        reset();
+        mCacheBlocks = new CacheBlock(TEXTURE_BORDER_SIZE, TEXTURE_BORDER_SIZE,
+                mMaxWidth - TEXTURE_BORDER_SIZE, mMaxHeight - TEXTURE_BORDER_SIZE, true);
     }
 
     bool fitBitmap(const SkGlyph& glyph, uint32_t *retOriginX, uint32_t *retOriginY);
@@ -97,9 +162,10 @@ public:
     uint16_t mMaxHeight;
     uint16_t mMaxWidth;
     uint32_t mCurrentRow;
-    uint32_t mCurrentCol;
     bool mDirty;
+    uint16_t mNumGlyphs;
     CacheTexture* mCacheTexture;
+    CacheBlock* mCacheBlocks;
 };
 
 struct CachedGlyphInfo {
@@ -179,6 +245,8 @@ protected:
         MEASURE,
     };
 
+    void precache(SkPaint* paint, const char* text, int numGlyphs);
+
     void render(SkPaint* paint, const char *text, uint32_t start, uint32_t len,
             int numGlyphs, int x, int y, RenderMode mode, uint8_t *bitmap,
             uint32_t bitmapW, uint32_t bitmapH, Rect *bounds, const float* positions);
@@ -244,6 +312,9 @@ public:
     }
 
     void setFont(SkPaint* paint, uint32_t fontId, float fontSize);
+
+    void precache(SkPaint* paint, const char* text, int numGlyphs);
+
     // bounds is an out parameter
     bool renderText(SkPaint* paint, const Rect* clip, const char *text, uint32_t startIndex,
             uint32_t len, int numGlyphs, int x, int y, Rect* bounds);
@@ -327,8 +398,6 @@ protected:
     void initRender(const Rect* clip, Rect* bounds);
     void finishRender();
 
-    void precacheLatin(SkPaint* paint);
-
     void issueDrawCommand();
     void appendMeshQuadNoClip(float x1, float y1, float u1, float v1,
             float x2, float y2, float u2, float v2,
@@ -347,7 +416,6 @@ protected:
     uint32_t mSmallCacheHeight;
 
     Vector<CacheTextureLine*> mCacheLines;
-    uint32_t getRemainingCacheCapacity();
 
     Font* mCurrentFont;
     Vector<Font*> mActiveFonts;