Use BBH reserve hook to preallocate space for tiles.
Before getting too far into changing how SkTileGrid stores its tiles, I figured I'd
better see how much I can tweak out the existing format. Cleverly, that way
any improvements I make by changing the format will look that much less
impressive.
This CL looks like it will be a 5-15% win in time spent recording, with no effect
on playback.
This CL also shrinks the tiles to fit exactly when we're done inserting,
using newly added SkTDArray::shrinkToFit(). It's quite cheap to run (maybe
taking back 1-2% from those 5-15% wins), and means we'll lug around about 15%
fewer bytes in the tile grids. Note though this strategy temporarily uses up to
30% more memory while building the tile grid. For our largest SKPs, that's
maybe 75-100K extra.
BUG=skia:
Review URL: https://codereview.chromium.org/639823005
diff --git a/include/core/SkTDArray.h b/include/core/SkTDArray.h
index 92f297c..8e8b492 100644
--- a/include/core/SkTDArray.h
+++ b/include/core/SkTDArray.h
@@ -347,6 +347,11 @@
}
#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 8b96b73..2a3eac9 100644
--- a/src/core/SkTileGrid.cpp
+++ b/src/core/SkTileGrid.cpp
@@ -17,12 +17,37 @@
, 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 e8a0d96..fd7584f 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -39,6 +39,9 @@
// 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;