3 files changed, 34 insertions, 1 deletions
diff --git a/include/core/SkTDArray.h b/include/core/SkTDArray.h
index 92f297c31a..8e8b4923e3 100644
--- a/include/core/SkTDArray.h
+++ b/include/core/SkTDArray.h
@@ -347,6 +347,11 @@ public:
     }
 #endif
 
+    void shrinkToFit() {
+        fReserve = fCount;
+        fArray = (T*)sk_realloc_throw(fArray, fReserve * sizeof(T));
+    }
+
 private:
 #ifdef SK_DEBUG
     enum {
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp
index 8b96b73fa1..2a3eac9ec1 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -17,12 +17,37 @@ SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGrid
     , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY))
     , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(),
                                  yTiles * info.fTileInterval.height()))
-    , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {}
+    , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {
+    SkASSERT(fXTiles * fYTiles != 0);
+}
 
 SkTileGrid::~SkTileGrid() {
     SkDELETE_ARRAY(fTiles);
 }
 
+void SkTileGrid::reserve(unsigned opCount) {
+    // If we assume every op we're about to try to insert() falls within our grid bounds,
+    // then every op has to hit at least one tile.  In fact, a quick scan over our small
+    // SKP set shows that in the average SKP, each op hits two 256x256 tiles.
+
+    // If we take those observations and further assume the ops are distributed evenly
+    // across the picture, we get this guess for number of ops per tile:
+    const int opsPerTileGuess = (2 * opCount) / (fXTiles * fYTiles);
+
+    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) {
+        tile->setReserve(opsPerTileGuess);
+    }
+
+    // In practice, this heuristic means we'll temporarily allocate about 30% more bytes
+    // than if we made no setReserve() calls, but time spent in insert() drops by about 50%.
+}
+
+void SkTileGrid::flushDeferredInserts() {
+    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) {
+        tile->shrinkToFit();
+    }
+}
+
 // Adjustments to user-provided bounds common to both insert() and search().
 // Call this after making insert- or search- specific adjustments.
 void SkTileGrid::commonAdjust(SkRect* rect) const {
diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index e8a0d96a65..fd7584fd9c 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -39,6 +39,9 @@ public:
     // For testing.
     int tileCount(int x, int y) { return fTiles[y * fXTiles + x].count(); }
 
+    virtual void reserve(unsigned opCount) SK_OVERRIDE;
+    virtual void flushDeferredInserts() SK_OVERRIDE;
+
 private:
     void commonAdjust(SkRect*) const;
     void userToGrid(const SkRect&, SkIRect* grid) const;