Start to vectorize SkTileGrid.

src/core/SkTileGrid.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkTileGrid.h"
+#include "Sk4x.h"
 
 SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info)
     : fXTiles(xTiles)
-    , fYTiles(yTiles)
-    , fInvWidth( SkScalarInvert(info.fTileInterval.width()))
-    , fInvHeight(SkScalarInvert(info.fTileInterval.height()))
-    , fMarginWidth (info.fMargin.fWidth +1)  // Margin is offset by 1 as a provision for AA and
-    , fMarginHeight(info.fMargin.fHeight+1)  // to cancel the outset applied by getClipDeviceBounds.
-    , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY))
-    , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(),
-                                 yTiles * info.fTileInterval.height()))
+    , fNumTiles(xTiles * yTiles)
+    , fGridBounds(0, 0, xTiles * info.fTileInterval.width(), yTiles * info.fTileInterval.height())
+    , fMargin(-info.fMargin.fWidth  - 1,  // Margin is increased by 1 as a provision for AA
+              -info.fMargin.fHeight - 1,  // and to cancel the outset applied by
+              +info.fMargin.fWidth  + 1,  // getClipDeviceBounds().
+              +info.fMargin.fHeight + 1)
+    , fOffset(info.fOffset.fX,
+              info.fOffset.fY,
+              info.fOffset.fX - SK_ScalarNearlyZero,  // We scrunch user-provided bounds in a little
+              info.fOffset.fY - SK_ScalarNearlyZero)  // to make right and bottom edges exclusive.
+    , fUserToGrid(SkScalarInvert(info.fTileInterval.width()),
+                  SkScalarInvert(info.fTileInterval.height()),
+                  SkScalarInvert(info.fTileInterval.width()),
+                  SkScalarInvert(info.fTileInterval.height()))
+    , fGridHigh(fXTiles - 1, yTiles - 1, fXTiles - 1, yTiles - 1)
     , fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {}
 
 SkTileGrid::~SkTileGrid() {
     SkDELETE_ARRAY(fTiles);
 }
 
 void SkTileGrid::reserve(unsigned opCount) {
-    if (fXTiles * fYTiles == 0) {
+    if (fNumTiles == 0) {
         return;  // A tileless tile grid is nonsensical, but happens in at least cc_unittests.
     }
 
     // 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);
+    const int opsPerTileGuess = (2 * opCount) / fNumTiles;
 
-    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) {
+    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; 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++) {
+    for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; 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 {
-    // Apply our offset.
-    rect->offset(fOffset);
+// Convert user-space bounds to grid tiles they cover (LT+RB both inclusive).
+// Out of bounds queries are clamped to the single nearest tile.
+void SkTileGrid::userToGrid(const Sk4f& user, SkIRect* out) const {
+    // Map from user coordinates to grid tile coordinates.
+    Sk4f grid = user.multiply(fUserToGrid);
 
-    // Scrunch the bounds in just a little to make the right and bottom edges
-    // exclusive.  We want bounds of exactly one tile to hit exactly one tile.
-    rect->fRight  -= SK_ScalarNearlyZero;
-    rect->fBottom -= SK_ScalarNearlyZero;
+    // Now that we're in grid coordinates, clamp to the grid bounds.
+    grid = Sk4f::Max(grid, Sk4f(0,0,0,0));
+    grid = Sk4f::Min(grid, fGridHigh);
+
+    // Truncate to integers.
+    grid.cast<Sk4i>().store(&out->fLeft);
 }
 
-// Convert user-space bounds to grid tiles they cover (LT inclusive, RB exclusive).
-void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const {
-    grid->fLeft   = SkPin32(user.left()   * fInvWidth , 0, fXTiles - 1);
-    grid->fTop    = SkPin32(user.top()    * fInvHeight, 0, fYTiles - 1);
-    grid->fRight  = SkPin32(user.right()  * fInvWidth , 0, fXTiles - 1) + 1;
-    grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1) + 1;
+// If the rect is inverted, sort it.
+static Sk4f sorted(const Sk4f& ltrb) {
+    // To sort:
+    //   left, right = minmax(left, right)
+    //   top, bottom = minmax(top, bottom)
+    Sk4f rblt = ltrb.zwxy(),
+         ltlt = Sk4f::Min(ltrb, rblt),  // Holds (2 copies of) new left and top.
+         rbrb = Sk4f::Max(ltrb, rblt),  // Holds (2 copies of) new right and bottom.
+         sort = Sk4f::XYAB(ltlt, rbrb);
+    return sort;
+}
+
+// Do these two LTRB rectangles intersect?
+static bool intersects(const Sk4f& r1, const Sk4f& r2) {
+    // Two rects intersect if lefts are less than the
+    // opposite rights and tops less than opposite bottoms.
+    Sk4f lt = Sk4f::XYAB(r1, r2),  // r1.L r1.T r2.L r2.T <
+         rb = Sk4f::ZWCD(r2, r1);  // r2.R r2.B r1.R r1.B ?
+    return lt.lessThan(rb).allTrue();
 }
 
 void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) {
-    SkRect bounds = originalBounds;
-    bounds.outset(fMarginWidth, fMarginHeight);
-    this->commonAdjust(&bounds);
+    Sk4f bounds = Sk4f(&originalBounds.fLeft).add(fMargin).add(fOffset);
+    SkASSERT(sorted(bounds).equal(bounds).allTrue());
 
-    // TODO(mtklein): can we assert this instead to save an intersection in Release mode,
-    // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)?
-    if (!SkRect::Intersects(bounds, fGridBounds)) {
+    // TODO(mtklein): skip this check and just let out-of-bounds rects insert into nearest tile?
+    if (!intersects(bounds, fGridBounds)) {
         return;
     }
 
     SkIRect grid;
     this->userToGrid(bounds, &grid);
 
-    for (int y = grid.fTop; y < grid.fBottom; y++) {
-        for (int x = grid.fLeft; x < grid.fRight; x++) {
-            fTiles[y * fXTiles + x].push(opIndex);
+    // This is just a loop over y then x.  This compiles to a slightly faster and
+    // more compact loop than if we just did fTiles[y * fXTiles + x].push(opIndex).
+    SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft];
+    for (int y = 0; y <= grid.fBottom - grid.fTop; y++) {
+        SkTDArray<unsigned>* tile = row;
+        for (int x = 0; x <= grid.fRight - grid.fLeft; x++) {
+            (tile++)->push(opIndex);
         }
+        row += fXTiles;
     }
 }
 
 // Number of tiles for which data is allocated on the stack in
 // SkTileGrid::search. If malloc becomes a bottleneck, we may consider
 // increasing this number. Typical large web page, say 2k x 16k, would
 // require 512 tiles of size 256 x 256 pixels.
 static const int kStackAllocationTileCount = 1024;
 
+
 void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* results) const {
-    // The inset counteracts the outset that applied in 'insert', which optimizes
-    // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile grid).
-    SkRect query = originalQuery;
-    query.inset(fMarginWidth, fMarginHeight);
-    this->commonAdjust(&query);
+    // The .subtract(fMargin) counteracts the .add(fMargin) applied in insert(),
+    // which optimizes for lookups of size tileInterval + 2 * margin (aligned with the tile grid).
+    Sk4f query = sorted(Sk4f(&originalQuery.fLeft).subtract(fMargin).add(fOffset));
 
-    // The inset may have inverted the rectangle, so sort().
-    // TODO(mtklein): It looks like we only end up with inverted bounds in unit tests
-    // that make explicitly inverted queries, not from insetting.  If we can drop support for
-    // unsorted bounds (i.e. we don't see them outside unit tests), I think we can drop this.
-    query.sort();
-
-    // No intersection check.  We optimize for queries that are in bounds.
-    // We're safe anyway: userToGrid() will clamp out-of-bounds queries to nearest tile.
     SkIRect grid;
     this->userToGrid(query, &grid);
 
-    const int tilesHit = (grid.fRight - grid.fLeft) * (grid.fBottom - grid.fTop);
+    const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.fTop + 1);

[reed1, 2014/10/15 20:48:11]

I see a +1 here, and a change from < to <= down below.

Not trying to pick on this CL per-se, but I see this change as well as just
scalers -> 4f.

1. I'm sure I don't understand either of the two (i.e. I don't understand the
trickiness of this logic either way)?
2. Is this change an integral part of the Sk4x change?

I'm kind of ok either way, but I do think that switching to Sk4x makes the code
faster, but definitely harder to understand.

[mtklein, 2014/10/15 20:55:28]

Ah, yeah, you're watching work in progress.  That +1/<= change is going to spin
off into a prequel CL.

     SkASSERT(tilesHit > 0);
 
     if (tilesHit == 1) {
         // A performance shortcut.  The merging code below would work fine here too.
         *results = fTiles[grid.fTop * fXTiles + grid.fLeft];
         return;
     }
 
     // We've got to merge the data in many tiles into a single sorted and deduplicated stream.
     // We do a simple k-way merge based on the value of opIndex.
 
     // Gather pointers to the starts and ends of the tiles to merge.
     SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit);
     int i = 0;
-    for (int y = grid.fTop; y < grid.fBottom; y++) {
-        for (int x = grid.fLeft; x < grid.fRight; x++) {
+    for (int y = grid.fTop; y <= grid.fBottom; y++) {
+        for (int x = grid.fLeft; x <= grid.fRight; x++) {
             starts[i] = fTiles[y * fXTiles + x].begin();
             ends[i]   = fTiles[y * fXTiles + x].end();
             i++;
         }
     }
 
     // Merge tiles into results until they're fully consumed.
     results->reset();
     while (true) {
         // The tiles themselves are already ordered, so the earliest op is at the front of some
@@ skipping 13 matching lines @@
         // We did find an earliest op. Output it, and step forward every tile that contains it.
         results->push(earliest);
         for (int i = 0; i < starts.count(); i++) {
             if (starts[i] < ends[i] && *starts[i] == earliest) {
                 starts[i]++;
             }
         }
     }
 }