Prune SkRTree

  - Propagate a bunch of constant parameters through.
  - Delete code that's not used when bulk loading.
  - Allocate all Nodes together.
  - Stay in SkRect.

Doing a single malloc for the nodes can't not have improved memory usage.

Looks like this might improve record performance ~5%, probably mostly from
staying in SkRects.  This finally dethrones building the BBH as the hot spot.
(Now it's mapping user bounds back to device bounds and adjusting for paints.)

Recording time changes from my MBP:
    desk_rectangletransition.skp	11.5us -> 11.7us	1x
             desk_forecastio.skp	 115us ->  114us	0.98x
                desk_booking.skp	 550us ->  541us	0.98x
            tabl_mercurynews.skp	 176us ->  173us	0.98x
                   tabl_hsfi.skp	 294us ->  287us	0.98x
              desk_wordpress.skp	 351us ->  343us	0.98x
           tabl_worldjournal.skp	 439us ->  426us	0.97x
                  tabl_gmail.skp	20.3us -> 19.7us	0.97x
         desk_youtubetvvideo.skp	10.8us -> 10.4us	0.97x
             desk_googleplus.skp	 1.1ms -> 1.07ms	0.97x
               tabl_slashdot.skp	 106us ->  103us	0.97x
         desk_jsfiddlebigcar.skp	26.7us -> 25.7us	0.96x
               tabl_techmeme.skp	95.4us -> 91.7us	0.96x
             tabl_deviantart.skp	 133us ->  127us	0.96x
              desk_pinterest.skp	40.6us -> 38.9us	0.96x
                 desk_carsvg.skp	 195us ->  187us	0.96x
               tabl_engadget.skp	 376us ->  359us	0.96x
                tabl_sahadan.skp	60.5us -> 57.5us	0.95x
      tabl_culturalsolutions.skp	 255us ->  242us	0.95x
                  tabl_gspro.skp	58.3us -> 55.5us	0.95x
               desk_linkedin.skp	 146us ->  138us	0.94x
                   desk_ebay.skp	 192us ->  181us	0.94x
                    tabl_cnn.skp	 467us ->  440us	0.94x
     desk_jsfiddlehumperclip.skp	29.9us -> 28.1us	0.94x
               desk_tigersvg.skp	43.2us -> 40.5us	0.94x
           desk_yahooanswers.skp	 131us ->  123us	0.94x
desk_googlespreadsheetdashed.skp	1.18ms -> 1.11ms	0.94x
                desk_blogger.skp	 193us ->  181us	0.94x
                tabl_mozilla.skp	1.82ms ->  1.7ms	0.94x
                    tabl_mlb.skp	 145us ->  136us	0.93x
              mobi_wikipedia.skp	 577us ->  539us	0.93x
               tabl_frantzen.skp	54.1us -> 50.4us	0.93x
                  desk_baidu.skp	87.9us -> 81.9us	0.93x
             desk_techcrunch.skp	 224us ->  209us	0.93x
                 desk_sfgate.skp	 206us ->  192us	0.93x
                  tabl_ukwsj.skp	 269us ->  250us	0.93x
               desk_facebook.skp	 316us ->  293us	0.93x
            desk_gmailthread.skp	 205us ->  190us	0.93x
         tabl_googlecalendar.skp	 158us ->  147us	0.93x
                   tabl_digg.skp	 382us ->  354us	0.93x
                 desk_amazon.skp	 106us -> 98.5us	0.93x
          tabl_androidpolice.skp	 693us ->  642us	0.93x
                tabl_nytimes.skp	 206us ->  191us	0.92x
                    desk_gws.skp	 124us ->  114us	0.92x
                desk_youtube.skp	 255us ->  235us	0.92x
           tabl_cuteoverload.skp	 583us ->  537us	0.92x
            desk_oldinboxapp.skp	  18us -> 16.6us	0.92x
             desk_mobilenews.skp	 297us ->  273us	0.92x
                 tabl_pravda.skp	 168us ->  154us	0.92x
              tabl_vnexpress.skp	 236us ->  217us	0.92x
          desk_css3gradients.skp	 202us ->  185us	0.92x
            tabl_gamedeksiam.skp	 508us ->  464us	0.91x
                desk_wowwiki.skp	1.02ms ->  929us	0.91x
                   desk_espn.skp	 209us ->  191us	0.91x
             desk_chalkboard.skp	 315us ->  284us	0.9x
                 desk_mapsvg.skp	 607us ->  543us	0.89x
            desk_pokemonwiki.skp	5.18ms -> 4.62ms	0.89x
               desk_samoasvg.skp	 335us ->  298us	0.89x
        desk_youtubetvbrowse.skp	10.1us -> 8.59us	0.85x
BUG=skia:3085, skia:2834

Review URL: https://codereview.chromium.org/734723002

3 files changed, 142 insertions, 509 deletions

diff --git a/src/core/SkBBHFactory.cpp b/src/core/SkBBHFactory.cpp
index c895ff60fb..22f816c4d9 100644
--- a/src/core/SkBBHFactory.cpp
+++ b/src/core/SkBBHFactory.cpp
@@ -11,17 +11,8 @@
 
 
 SkBBoxHierarchy* SkRTreeFactory::operator()(int width, int height) const {
-    // These values were empirically determined to produce reasonable
-    // performance in most cases.
-    static const int kRTreeMinChildren = 6;
-    static const int kRTreeMaxChildren = 11;
-
-    SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(width),
-                                       SkIntToScalar(height));
-    bool sortDraws = false;  // Do not sort draw calls when bulk loading.
-
-    return SkRTree::Create(kRTreeMinChildren, kRTreeMaxChildren,
-                           aspectRatio, sortDraws);
+    SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(width), SkIntToScalar(height));
+    return SkNEW_ARGS(SkRTree, (aspectRatio));
 }
 
 SkBBoxHierarchy* SkTileGridFactory::operator()(int width, int height) const {
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index 93f914276f..6c7803119d 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -6,445 +6,167 @@
  */
 
 #include "SkRTree.h"
-#include "SkTSort.h"
 
-static inline uint32_t get_area(const SkIRect& rect);
-static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
-static inline uint32_t get_margin(const SkIRect& rect);
-static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
-static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
-
-///////////////////////////////////////////////////////////////////////////////////////////////////
-
-SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
-            bool sortWhenBulkLoading) {
-    if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
-        minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
-        return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
-    }
-    return NULL;
-}
-
-SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
-        bool sortWhenBulkLoading)
-    : fMinChildren(minChildren)
-    , fMaxChildren(maxChildren)
-    , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
-    , fCount(0)
-    , fNodes(fNodeSize * 256)
-    , fAspectRatio(aspectRatio)
-    , fSortWhenBulkLoading(sortWhenBulkLoading) {
-    SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
-             static_cast<int>(SK_MaxU16));
-    SkASSERT((maxChildren + 1) / 2 >= minChildren);
-    this->validate();
-}
-
-SkRTree::~SkRTree() {
-    this->clear();
-}
+SkRTree::SkRTree(SkScalar aspectRatio) : fCount(0), fAspectRatio(aspectRatio) {}
 
 void SkRTree::insert(SkAutoTMalloc<SkRect>* boundsArray, int N) {
-    SkASSERT(this->isEmpty());
-    this->validate();
+    SkASSERT(0 == fCount);
 
-    SkTDArray<Branch> deferred;
-    deferred.setReserve(N);
+    SkTDArray<Branch> branches;
+    branches.setReserve(N);
 
     for (int i = 0; i < N; i++) {
-        SkIRect bounds;
-        (*boundsArray)[i].roundOut(&bounds);
+        const SkRect& bounds = (*boundsArray)[i];
         if (bounds.isEmpty()) {
             continue;
         }
 
-        Branch newBranch;
-        newBranch.fBounds = bounds;
-        newBranch.fChild.opIndex = i;
-
-        deferred.push(newBranch);
+        Branch* b = branches.push();
+        b->fBounds = bounds;
+        b->fOpIndex = i;
     }
 
-    fCount = deferred.count();
+    fCount = branches.count();
     if (fCount) {
         if (1 == fCount) {
-            fRoot.fChild.subtree = this->allocateNode(0);
-            fRoot.fChild.subtree->fNumChildren = 0;
-            this->insert(fRoot.fChild.subtree, &deferred[0]);
-            fRoot.fBounds = deferred[0].fBounds;
+            fNodes.setReserve(1);
+            Node* n = this->allocateNodeAtLevel(0);
+            n->fNumChildren = 1;
+            n->fChildren[0] = branches[0];
+            fRoot.fSubtree = n;
+            fRoot.fBounds  = branches[0].fBounds;
         } else {
-            fRoot = this->bulkLoad(&deferred);
+            fNodes.setReserve(CountNodes(fCount, fAspectRatio));
+            fRoot = this->bulkLoad(&branches);
         }
     }
-
-    this->validate();
 }
 
-void SkRTree::search(const SkRect& fquery, SkTDArray<unsigned>* results) const {
-    SkIRect query;
-    fquery.roundOut(&query);
-    this->validate();
-    if (!this->isEmpty() && SkIRect::IntersectsNoEmptyCheck(fRoot.fBounds, query)) {
-        this->search(fRoot.fChild.subtree, query, results);
-    }
-    this->validate();
-}
-
-void SkRTree::clear() {
-    this->validate();
-    fNodes.reset();
-    fCount = 0;
-    this->validate();
-}
-
-SkRTree::Node* SkRTree::allocateNode(uint16_t level) {
-    Node* out = static_cast<Node*>(fNodes.allocThrow(fNodeSize));
+SkRTree::Node* SkRTree::allocateNodeAtLevel(uint16_t level) {
+    SkDEBUGCODE(Node* p = fNodes.begin());
+    Node* out = fNodes.push();
+    SkASSERT(fNodes.begin() == p);  // If this fails, we didn't setReserve() enough.
     out->fNumChildren = 0;
     out->fLevel = level;
     return out;
 }
 
-SkRTree::Branch* SkRTree::insert(Node* root, Branch* branch, uint16_t level) {
-    Branch* toInsert = branch;
-    if (root->fLevel != level) {
-        int childIndex = this->chooseSubtree(root, branch);
-        toInsert = this->insert(root->child(childIndex)->fChild.subtree, branch, level);
-        root->child(childIndex)->fBounds = this->computeBounds(
-            root->child(childIndex)->fChild.subtree);
+// This function parallels bulkLoad, but just counts how many nodes bulkLoad would allocate.
+int SkRTree::CountNodes(int branches, SkScalar aspectRatio) {
+    if (branches == 1) {
+        return 1;
     }
-    if (toInsert) {
-        if (root->fNumChildren == fMaxChildren) {
-            // handle overflow by splitting. TODO: opportunistic reinsertion
-
-            // decide on a distribution to divide with
-            Node* newSibling = this->allocateNode(root->fLevel);
-            Branch* toDivide = SkNEW_ARRAY(Branch, fMaxChildren + 1);
-            for (int i = 0; i < fMaxChildren; ++i) {
-                toDivide[i] = *root->child(i);
-            }
-            toDivide[fMaxChildren] = *toInsert;
-            int splitIndex = this->distributeChildren(toDivide);
-
-            // divide up the branches
-            root->fNumChildren = splitIndex;
-            newSibling->fNumChildren = fMaxChildren + 1 - splitIndex;
-            for (int i = 0; i < splitIndex; ++i) {
-                *root->child(i) = toDivide[i];
-            }
-            for (int i = splitIndex; i < fMaxChildren + 1; ++i) {
-                *newSibling->child(i - splitIndex) = toDivide[i];
-            }
-            SkDELETE_ARRAY(toDivide);
-
-            // pass the new sibling branch up to the parent
-            branch->fChild.subtree = newSibling;
-            branch->fBounds = this->computeBounds(newSibling);
-            return branch;
+    int numBranches = branches / kMaxChildren;
+    int remainder   = branches % kMaxChildren;
+    if (remainder > 0) {
+        numBranches++;
+        if (remainder >= kMinChildren) {
+            remainder = 0;
         } else {
-            *root->child(root->fNumChildren) = *toInsert;
-            ++root->fNumChildren;
-            return NULL;
+            remainder = kMinChildren - remainder;
         }
     }
-    return NULL;
-}
-
-int SkRTree::chooseSubtree(Node* root, Branch* branch) {
-    SkASSERT(!root->isLeaf());
-    if (1 < root->fLevel) {
-        // root's child pointers do not point to leaves, so minimize area increase
-        int32_t minAreaIncrease = SK_MaxS32;
-        int32_t minArea         = SK_MaxS32;
-        int32_t bestSubtree     = -1;
-        for (int i = 0; i < root->fNumChildren; ++i) {
-            const SkIRect& subtreeBounds = root->child(i)->fBounds;
-            int32_t areaIncrease = get_area_increase(subtreeBounds, branch->fBounds);
-            // break ties in favor of subtree with smallest area
-            if (areaIncrease < minAreaIncrease || (areaIncrease == minAreaIncrease &&
-                static_cast<int32_t>(get_area(subtreeBounds)) < minArea)) {
-                minAreaIncrease = areaIncrease;
-                minArea = get_area(subtreeBounds);
-                bestSubtree = i;
-            }
-        }
-        SkASSERT(-1 != bestSubtree);
-        return bestSubtree;
-    } else if (1 == root->fLevel) {
-        // root's child pointers do point to leaves, so minimize overlap increase
-        int32_t minOverlapIncrease = SK_MaxS32;
-        int32_t minAreaIncrease    = SK_MaxS32;
-        int32_t bestSubtree = -1;
-        for (int32_t i = 0; i < root->fNumChildren; ++i) {
-            const SkIRect& subtreeBounds = root->child(i)->fBounds;
-            SkIRect expandedBounds = subtreeBounds;
-            join_no_empty_check(branch->fBounds, &expandedBounds);
-            int32_t overlap = 0;
-            for (int32_t j = 0; j < root->fNumChildren; ++j) {
-                if (j == i) continue;
-                // Note: this would be more correct if we subtracted the original pre-expanded
-                // overlap, but computing overlaps is expensive and omitting it doesn't seem to
-                // hurt query performance. See get_overlap_increase()
-                overlap += get_overlap(expandedBounds, root->child(j)->fBounds);
-            }
-            // break ties with lowest area increase
-            if (overlap < minOverlapIncrease || (overlap == minOverlapIncrease &&
-                static_cast<int32_t>(get_area_increase(branch->fBounds, subtreeBounds)) <
-                minAreaIncrease)) {
-                minOverlapIncrease = overlap;
-                minAreaIncrease = get_area_increase(branch->fBounds, subtreeBounds);
-                bestSubtree = i;
-            }
-        }
-        return bestSubtree;
-    } else {
-        SkASSERT(false);
-        return 0;
-    }
-}
-
-SkIRect SkRTree::computeBounds(Node* n) {
-    SkIRect r = n->child(0)->fBounds;
-    for (int i = 1; i < n->fNumChildren; ++i) {
-        join_no_empty_check(n->child(i)->fBounds, &r);
-    }
-    return r;
-}
-
-int SkRTree::distributeChildren(Branch* children) {
-    // We have two sides to sort by on each of two axes:
-    const static SortSide sorts[2][2] = {
-        {&SkIRect::fLeft, &SkIRect::fRight},
-        {&SkIRect::fTop, &SkIRect::fBottom}
-    };
-
-    // We want to choose an axis to split on, then a distribution along that axis; we'll need
-    // three pieces of info: the split axis, the side to sort by on that axis, and the index
-    // to split the sorted array on.
-    int32_t sortSide = -1;
-    int32_t k        = -1;
-    int32_t axis     = -1;
-    int32_t bestS    = SK_MaxS32;
-
-    // Evaluate each axis, we want the min summed margin-value (s) over all distributions
-    for (int i = 0; i < 2; ++i) {
-        int32_t minOverlap   = SK_MaxS32;
-        int32_t minArea      = SK_MaxS32;
-        int32_t axisBestK    = 0;
-        int32_t axisBestSide = 0;
-        int32_t s = 0;
-
-        // Evaluate each sort
-        for (int j = 0; j < 2; ++j) {
-            SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[i][j]));
-
-            // Evaluate each split index
-            for (int32_t k = 1; k <= fMaxChildren - 2 * fMinChildren + 2; ++k) {
-                SkIRect r1 = children[0].fBounds;
-                SkIRect r2 = children[fMinChildren + k - 1].fBounds;
-                for (int32_t l = 1; l < fMinChildren - 1 + k; ++l) {
-                    join_no_empty_check(children[l].fBounds, &r1);
-                }
-                for (int32_t l = fMinChildren + k; l < fMaxChildren + 1; ++l) {
-                    join_no_empty_check(children[l].fBounds, &r2);
-                }
-
-                int32_t area = get_area(r1) + get_area(r2);
-                int32_t overlap = get_overlap(r1, r2);
-                s += get_margin(r1) + get_margin(r2);
-
-                if (overlap < minOverlap || (overlap == minOverlap && area < minArea)) {
-                    minOverlap = overlap;
-                    minArea = area;
-                    axisBestSide = j;
-                    axisBestK = k;
+    int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / aspectRatio));
+    int numTiles  = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
+    int currentBranch = 0;
+    int nodes = 0;
+    for (int i = 0; i < numStrips; ++i) {
+        for (int j = 0; j < numTiles && currentBranch < branches; ++j) {
+            int incrementBy = kMaxChildren;
+            if (remainder != 0) {
+                if (remainder <= kMaxChildren - kMinChildren) {
+                    incrementBy -= remainder;
+                    remainder = 0;
+                } else {
+                    incrementBy = kMinChildren;
+                    remainder -= kMaxChildren - kMinChildren;
                 }
             }
-        }
-
-        if (s < bestS) {
-            bestS = s;
-            axis = i;
-            sortSide = axisBestSide;
-            k = axisBestK;
-        }
-    }
-
-    // replicate the sort of the winning distribution, (we can skip this if the last
-    // sort ended up being best)
-    if (!(axis == 1 && sortSide == 1)) {
-        SkTQSort(children, children + fMaxChildren, RectLessThan(sorts[axis][sortSide]));
-    }
-
-    return fMinChildren - 1 + k;
-}
-
-void SkRTree::search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const {
-    for (int i = 0; i < root->fNumChildren; ++i) {
-        if (SkIRect::IntersectsNoEmptyCheck(root->child(i)->fBounds, query)) {
-            if (root->isLeaf()) {
-                results->push(root->child(i)->fChild.opIndex);
-            } else {
-                this->search(root->child(i)->fChild.subtree, query, results);
+            nodes++;
+            currentBranch++;
+            for (int k = 1; k < incrementBy && currentBranch < branches; ++k) {
+                currentBranch++;
             }
         }
     }
+    return nodes + CountNodes(nodes, aspectRatio);
 }
 
 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
-    if (branches->count() == 1) {
-        // Only one branch: it will be the root
-        Branch out = (*branches)[0];
-        branches->rewind();
-        return out;
-    } else {
-        // We sort the whole list by y coordinates, if we are told to do so.
-        //
-        // We expect Webkit / Blink to give us a reasonable x,y order.
-        // Avoiding this call resulted in a 17% win for recording with
-        // negligible difference in playback speed.
-        if (fSortWhenBulkLoading) {
-            SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
-        }
-
-        int numBranches = branches->count() / fMaxChildren;
-        int remainder = branches->count() % fMaxChildren;
-        int newBranches = 0;
-
-        if (0 != remainder) {
-            ++numBranches;
-            // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
-            // some other branches to make up for it
-            if (remainder >= fMinChildren) {
-                remainder = 0;
-            } else {
-                remainder = fMinChildren - remainder;
-            }
+    if (branches->count() == 1) { // Only one branch.  It will be the root.
+        return (*branches)[0];
+    }
+
+    // We might sort our branches here, but we expect Blink gives us a reasonable x,y order.
+    // Skipping a call to sort (in Y) here resulted in a 17% win for recording with negligible
+    // difference in playback speed.
+    int numBranches = branches->count() / kMaxChildren;
+    int remainder   = branches->count() % kMaxChildren;
+    int newBranches = 0;
+
+    if (remainder > 0) {
+        ++numBranches;
+        // If the remainder isn't enough to fill a node, we'll add fewer nodes to other branches.
+        if (remainder >= kMinChildren) {
+            remainder = 0;
+        } else {
+            remainder = kMinChildren - remainder;
         }
+    }
 
-        int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) *
-                                     SkScalarInvert(fAspectRatio)));
-        int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) /
-                                    SkIntToScalar(numStrips));
-        int currentBranch = 0;
-
-        for (int i = 0; i < numStrips; ++i) {
-            // Once again, if we are told to do so, we sort by x.
-            if (fSortWhenBulkLoading) {
-                int begin = currentBranch;
-                int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
-                        (fMaxChildren - fMinChildren) * numTiles);
-                if (end > branches->count()) {
-                    end = branches->count();
+    int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
+    int numTiles  = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
+    int currentBranch = 0;
+
+    for (int i = 0; i < numStrips; ++i) {
+        // Might be worth sorting by X here too.
+        for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
+            int incrementBy = kMaxChildren;
+            if (remainder != 0) {
+                // if need be, omit some nodes to make up for remainder
+                if (remainder <= kMaxChildren - kMinChildren) {
+                    incrementBy -= remainder;
+                    remainder = 0;
+                } else {
+                    incrementBy = kMinChildren;
+                    remainder -= kMaxChildren - kMinChildren;
                 }
-
-                // Now we sort horizontal strips of rectangles by their x coords
-                SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
             }
-
-            for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
-                int incrementBy = fMaxChildren;
-                if (remainder != 0) {
-                    // if need be, omit some nodes to make up for remainder
-                    if (remainder <= fMaxChildren - fMinChildren) {
-                        incrementBy -= remainder;
-                        remainder = 0;
-                    } else {
-                        incrementBy = fMinChildren;
-                        remainder -= fMaxChildren - fMinChildren;
-                    }
-                }
-                Node* n = allocateNode(level);
-                n->fNumChildren = 1;
-                *n->child(0) = (*branches)[currentBranch];
-                Branch b;
-                b.fBounds = (*branches)[currentBranch].fBounds;
-                b.fChild.subtree = n;
+            Node* n = allocateNodeAtLevel(level);
+            n->fNumChildren = 1;
+            n->fChildren[0] = (*branches)[currentBranch];
+            Branch b;
+            b.fBounds = (*branches)[currentBranch].fBounds;
+            b.fSubtree = n;
+            ++currentBranch;
+            for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
+                b.fBounds.join((*branches)[currentBranch].fBounds);
+                n->fChildren[k] = (*branches)[currentBranch];
+                ++n->fNumChildren;
                 ++currentBranch;
-                for (int k = 1; k < incrementBy && currentBranch < branches->count(); ++k) {
-                    b.fBounds.join((*branches)[currentBranch].fBounds);
-                    *n->child(k) = (*branches)[currentBranch];
-                    ++n->fNumChildren;
-                    ++currentBranch;
-                }
-                (*branches)[newBranches] = b;
-                ++newBranches;
             }
+            (*branches)[newBranches] = b;
+            ++newBranches;
         }
-        branches->setCount(newBranches);
-        return this->bulkLoad(branches, level + 1);
     }
+    branches->setCount(newBranches);
+    return this->bulkLoad(branches, level + 1);
 }
 
-void SkRTree::validate() const {
-#ifdef SK_DEBUG
-    if (this->isEmpty()) {
-        return;
+void SkRTree::search(const SkRect& query, SkTDArray<unsigned>* results) const {
+    if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
+        this->search(fRoot.fSubtree, query, results);
     }
-    SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
-#endif
 }
 
-int SkRTree::validateSubtree(Node* root, SkIRect bounds, bool isRoot) const {
-    // make sure the pointer is pointing to a valid place
-    SkASSERT(fNodes.contains(static_cast<void*>(root)));
-
-    if (isRoot) {
-        // If the root of this subtree is the overall root, we have looser standards:
-        if (root->isLeaf()) {
-            SkASSERT(root->fNumChildren >= 1 && root->fNumChildren <= fMaxChildren);
-        } else {
-            SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
-        }
-    } else {
-        SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
-    }
-
-    for (int i = 0; i < root->fNumChildren; ++i) {
-        SkASSERT(bounds.contains(root->child(i)->fBounds));
-    }
-
-    if (root->isLeaf()) {
-        SkASSERT(0 == root->fLevel);
-        return root->fNumChildren;
-    } else {
-        int childCount = 0;
-        for (int i = 0; i < root->fNumChildren; ++i) {
-            SkASSERT(root->child(i)->fChild.subtree->fLevel == root->fLevel - 1);
-            childCount += this->validateSubtree(root->child(i)->fChild.subtree,
-                                                root->child(i)->fBounds);
+void SkRTree::search(Node* node, const SkRect& query, SkTDArray<unsigned>* results) const {
+    for (int i = 0; i < node->fNumChildren; ++i) {
+        if (SkRect::Intersects(node->fChildren[i].fBounds, query)) {
+            if (0 == node->fLevel) {
+                results->push(node->fChildren[i].fOpIndex);
+            } else {
+                this->search(node->fChildren[i].fSubtree, query, results);
+            }
         }
-        return childCount;
     }
 }
-
-///////////////////////////////////////////////////////////////////////////////////////////////////
-
-static inline uint32_t get_area(const SkIRect& rect) {
-    return rect.width() * rect.height();
-}
-
-static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2) {
-    // I suspect there's a more efficient way of computing this...
-    return SkMax32(0, SkMin32(rect1.fRight, rect2.fRight) - SkMax32(rect1.fLeft, rect2.fLeft)) *
-           SkMax32(0, SkMin32(rect1.fBottom, rect2.fBottom) - SkMax32(rect1.fTop, rect2.fTop));
-}
-
-// Get the margin (aka perimeter)
-static inline uint32_t get_margin(const SkIRect& rect) {
-    return 2 * (rect.width() + rect.height());
-}
-
-static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2) {
-    join_no_empty_check(rect1, &rect2);
-    return get_area(rect2) - get_area(rect1);
-}
-
-// Expand 'out' to include 'joinWith'
-static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
-    // since we check for empty bounds on insert, we know we'll never have empty rects
-    // and we can save the empty check that SkIRect::join requires
-    if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
-    if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
-    if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
-    if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
-}
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 00c6c8941d..440411d9b0 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -9,163 +9,83 @@
 #ifndef SkRTree_DEFINED
 #define SkRTree_DEFINED
 
+#include "SkBBoxHierarchy.h"
 #include "SkRect.h"
 #include "SkTDArray.h"
-#include "SkChunkAlloc.h"
-#include "SkBBoxHierarchy.h"
 
 /**
  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
  * bounding rectangles.
  *
- * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
- * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
- * there isn't a canonical ordering to use when choosing insertion locations and splitting
- * distributions. A variety of heuristics have been proposed for these problems; here, we're using
- * something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
- * and aims to minimize a combination of margin, overlap, and area when splitting.
+ * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
+ * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
  *
- * One detail that is thus far unimplemented that may improve tree quality is attempting to remove
- * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
- * been placed well early on may hurt the tree later when more nodes have been added; removing
- * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
- * is also unimplemented.
+ * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
+ * which groups rects by position on the Hilbert curve, is probably worth a look). There also
+ * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
  *
  * For more details see:
  *
  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
  *      an efficient and robust access method for points and rectangles"
- *
- * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
- * to be usable in its intermediate states while it is being constructed, this is significantly
- * quicker than individual insertions and produces more consistent trees.
  */
 class SkRTree : public SkBBoxHierarchy {
 public:
     SK_DECLARE_INST_COUNT(SkRTree)
 
     /**
-     * Create a new R-Tree with specified min/max child counts.
-     * The child counts are valid iff:
-     * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
-     * - min < max
-     * - min > 0
-     * - max < SK_MaxU16
      * If you have some prior information about the distribution of bounds you're expecting, you
-     * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
-     * better proportioned tiles of rectangles.
+     * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
+     * create better proportioned tiles of rectangles.
      */
-    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
-            bool orderWhenBulkLoading = true);
-    virtual ~SkRTree();
+    explicit SkRTree(SkScalar aspectRatio = 1);
+    virtual ~SkRTree() {}
 
     virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
-    void clear();
+    // Methods and constants below here are only public for tests.
+
     // Return the depth of the tree structure.
-    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+    int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
     // Insertion count (not overall node count, which may be greater).
     int getCount() const { return fCount; }
 
+    // These values were empirically determined to produce reasonable performance in most cases.
+    static const int kMinChildren = 6,
+                     kMaxChildren = 11;
 private:
-    bool isEmpty() const { return 0 == this->getCount(); }
-
     struct Node;
 
-    /**
-     * A branch of the tree, this may contain a pointer to another interior node, or a data value
-     */
     struct Branch {
         union {
-            Node* subtree;
-            unsigned opIndex;
-        } fChild;
-        SkIRect fBounds;
+            Node* fSubtree;
+            unsigned fOpIndex;
+        };
+        SkRect fBounds;
     };
 
-    /**
-     * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
-     */
     struct Node {
         uint16_t fNumChildren;
         uint16_t fLevel;
-        bool isLeaf() { return 0 == fLevel; }
-        // Since we want to be able to pick min/max child counts at runtime, we assume the creator
-        // has allocated sufficient space directly after us in memory, and index into that space
-        Branch* child(size_t index) {
-            return reinterpret_cast<Branch*>(this + 1) + index;
-        }
-    };
-
-    typedef int32_t SkIRect::*SortSide;
-
-    // Helper for sorting our children arrays by sides of their rects
-    struct RectLessThan {
-        RectLessThan(SkRTree::SortSide side) : fSide(side) { }
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
-            return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
-        }
-    private:
-        const SkRTree::SortSide fSide;
-    };
-
-    struct RectLessX {
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
-            return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
-                   ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
-        }
-    };
-
-    struct RectLessY {
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
-            return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
-                   ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
-        }
+        Branch fChildren[kMaxChildren];
     };
 
-    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
-
-    /**
-     * Recursively descend the tree to find an insertion position for 'branch', updates
-     * bounding boxes on the way up.
-     */
-    Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
-
-    int chooseSubtree(Node* root, Branch* branch);
-    SkIRect computeBounds(Node* n);
-    int distributeChildren(Branch* children);
-    void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const;
+    void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const;
 
-    /**
-     * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
-     * seems to generally produce better, more consistent trees at significantly lower cost than
-     * repeated insertions.
-     *
-     * This consumes the input array.
-     *
-     * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
-     * which groups rects by position on the Hilbert curve, is probably worth a look). There also
-     * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
-     */
+    // Consumes the input array.
     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
 
-    void validate() const;
-    int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false) const;
+    // How many times will bulkLoad() call allocateNodeAtLevel()?
+    static int CountNodes(int branches, SkScalar aspectRatio);
 
-    const int fMinChildren;
-    const int fMaxChildren;
-    const size_t fNodeSize;
+    Node* allocateNodeAtLevel(uint16_t level);
 
     // This is the count of data elements (rather than total nodes in the tree)
     int fCount;
-
-    Branch fRoot;
-    SkChunkAlloc fNodes;
     SkScalar fAspectRatio;
-    bool fSortWhenBulkLoading;
-
-    Node* allocateNode(uint16_t level);
+    Branch fRoot;
+    SkTDArray<Node> fNodes;
 
     typedef SkBBoxHierarchy INHERITED;
 };