diff --git a/libs/hwui/OpenGLRenderer.cpp b/libs/hwui/OpenGLRenderer.cpp
index 62c590d..5b226b4 100644
--- a/libs/hwui/OpenGLRenderer.cpp
+++ b/libs/hwui/OpenGLRenderer.cpp
@@ -692,9 +692,8 @@
     SkXfermode::Mode mode;
     getAlphaAndMode(paint, &alpha, &mode);
 
-    Patch* mesh = mCaches.patchCache.get(width, height);
-    mesh->updateVertices(bitmap->width(), bitmap->height(),left, top, right, bottom,
-            xDivs, yDivs, width, height);
+    const Patch* mesh = mCaches.patchCache.get(bitmap->width(), bitmap->height(),
+            right - left, bottom - top, xDivs, yDivs, width, height);
 
     // Specify right and bottom as +1.0f from left/top to prevent scaling since the
     // patch mesh already defines the final size
diff --git a/libs/hwui/Patch.h b/libs/hwui/Patch.h
index 1d08c64..a9109cd 100644
--- a/libs/hwui/Patch.h
+++ b/libs/hwui/Patch.h
@@ -18,6 +18,7 @@
 #define ANDROID_UI_PATCH_H
 
 #include <sys/types.h>
+#include <cstring>
 
 #include "Vertex.h"
 
@@ -28,24 +29,28 @@
  * Description of a patch.
  */
 struct PatchDescription {
-    PatchDescription(): xCount(0), yCount(0) { }
-    PatchDescription(const uint32_t xCount, const uint32_t yCount):
+    PatchDescription(): bitmapWidth(0), bitmapHeight(0),
+            pixelWidth(0), pixelHeight(0), xCount(0), yCount(0) { }
+    PatchDescription(const float bitmapWidth, const float bitmapHeight,
+            const float pixelWidth, const float pixelHeight,
+            const uint32_t xCount, const uint32_t yCount):
+            bitmapWidth(bitmapWidth), bitmapHeight(bitmapHeight),
+            pixelWidth(pixelWidth), pixelHeight(pixelHeight),
             xCount(xCount), yCount(yCount) { }
     PatchDescription(const PatchDescription& description):
+            bitmapWidth(description.bitmapWidth), bitmapHeight(description.bitmapHeight),
+            pixelWidth(description.pixelWidth), pixelHeight(description.pixelHeight),
             xCount(description.xCount), yCount(description.yCount) { }
 
+    float bitmapWidth;
+    float bitmapHeight;
+    float pixelWidth;
+    float pixelHeight;
     uint32_t xCount;
     uint32_t yCount;
 
     bool operator<(const PatchDescription& rhs) const {
-        if (xCount == rhs.xCount) {
-            return yCount < rhs.yCount;
-        }
-        return xCount < rhs.xCount;
-    }
-
-    bool operator==(const PatchDescription& rhs) const {
-        return xCount == rhs.xCount && yCount == rhs.yCount;
+        return memcmp(this, &rhs, sizeof(PatchDescription)) < 0;
     }
 }; // struct PatchDescription
 
diff --git a/libs/hwui/PatchCache.cpp b/libs/hwui/PatchCache.cpp
index f2cf548..4dc1a4d 100644
--- a/libs/hwui/PatchCache.cpp
+++ b/libs/hwui/PatchCache.cpp
@@ -29,10 +29,10 @@
 // Constructors/destructor
 ///////////////////////////////////////////////////////////////////////////////
 
-PatchCache::PatchCache(): mCache(DEFAULT_PATCH_CACHE_SIZE) {
+PatchCache::PatchCache(): mMaxEntries(DEFAULT_PATCH_CACHE_SIZE) {
 }
 
-PatchCache::PatchCache(uint32_t maxEntries): mCache(maxEntries) {
+PatchCache::PatchCache(uint32_t maxEntries): mMaxEntries(maxEntries) {
 }
 
 PatchCache::~PatchCache() {
@@ -40,31 +40,44 @@
 }
 
 ///////////////////////////////////////////////////////////////////////////////
-// Callbacks
-///////////////////////////////////////////////////////////////////////////////
-
-void PatchCache::operator()(PatchDescription& description, Patch*& mesh) {
-    if (mesh) delete mesh;
-}
-
-///////////////////////////////////////////////////////////////////////////////
 // Caching
 ///////////////////////////////////////////////////////////////////////////////
 
 void PatchCache::clear() {
-    mCache.setOnEntryRemovedListener(this);
+    size_t count = mCache.size();
+    for (int i = 0; i < count; i++) {
+        delete mCache.valueAt(i);
+    }
     mCache.clear();
-    mCache.setOnEntryRemovedListener(NULL);
 }
 
-Patch* PatchCache::get(uint32_t width, uint32_t height) {
-    const PatchDescription description(width, height);
+Patch* PatchCache::get(const float bitmapWidth, const float bitmapHeight,
+        const float pixelWidth, const float pixelHeight,
+        const int32_t* xDivs, const int32_t* yDivs,
+        const uint32_t width, const uint32_t height) {
 
-    Patch* mesh = mCache.get(description);
+    const PatchDescription description(bitmapWidth, bitmapHeight,
+            pixelWidth, pixelHeight, width, height);
+
+    ssize_t index = mCache.indexOfKey(description);
+    Patch* mesh = NULL;
+    if (index >= 0) {
+        mesh = mCache.valueAt(index);
+    }
+
     if (!mesh) {
         PATCH_LOGD("Creating new patch mesh, w=%d h=%d", width, height);
+
         mesh = new Patch(width, height);
-        mCache.put(description, mesh);
+        mesh->updateVertices(bitmapWidth, bitmapHeight, 0.0f, 0.0f,
+                pixelWidth, pixelHeight, xDivs, yDivs, width, height);
+
+        if (mCache.size() >= mMaxEntries) {
+            delete mCache.valueAt(0);
+            mCache.removeItemsAt(0, 1);
+        }
+
+        mCache.add(description, mesh);
     }
 
     return mesh;
diff --git a/libs/hwui/PatchCache.h b/libs/hwui/PatchCache.h
index b077469..08f78a3 100644
--- a/libs/hwui/PatchCache.h
+++ b/libs/hwui/PatchCache.h
@@ -17,8 +17,9 @@
 #ifndef ANDROID_UI_PATCH_CACHE_H
 #define ANDROID_UI_PATCH_CACHE_H
 
+#include <utils/KeyedVector.h>
+
 #include "Patch.h"
-#include "GenerationCache.h"
 
 namespace android {
 namespace uirenderer {
@@ -41,23 +42,21 @@
 // Cache
 ///////////////////////////////////////////////////////////////////////////////
 
-class PatchCache: public OnEntryRemoved<PatchDescription, Patch*> {
+class PatchCache {
 public:
     PatchCache();
     PatchCache(uint32_t maxCapacity);
     ~PatchCache();
 
-    /**
-     * Used as a callback when an entry is removed from the cache.
-     * Do not invoke directly.
-     */
-    void operator()(PatchDescription& description, Patch*& mesh);
-
-    Patch* get(uint32_t width, uint32_t height);
+    Patch* get(const float bitmapWidth, const float bitmapHeight,
+            const float pixelWidth, const float pixelHeight,
+            const int32_t* xDivs, const int32_t* yDivs,
+            const uint32_t width, const uint32_t height);
     void clear();
 
 private:
-    GenerationCache<PatchDescription, Patch*> mCache;
+    uint32_t mMaxEntries;
+    KeyedVector<PatchDescription, Patch*> mCache;
 }; // class PatchCache
 
 }; // namespace uirenderer
diff --git a/libs/hwui/Properties.h b/libs/hwui/Properties.h
index 277aacc..2c1a82b 100644
--- a/libs/hwui/Properties.h
+++ b/libs/hwui/Properties.h
@@ -47,7 +47,7 @@
 #define DEFAULT_TEXTURE_CACHE_SIZE 22.0f
 #define DEFAULT_LAYER_CACHE_SIZE 4.0f
 #define DEFAULT_PATH_CACHE_SIZE 4.0f
-#define DEFAULT_PATCH_CACHE_SIZE 100
+#define DEFAULT_PATCH_CACHE_SIZE 512
 #define DEFAULT_GRADIENT_CACHE_SIZE 0.5f
 #define DEFAULT_DROP_SHADOW_CACHE_SIZE 2.0f
 #define DEFAULT_FBO_CACHE_SIZE 25