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
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index 030d376..93576a7 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -19,12 +19,10 @@
typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
-// Time how long it takes to build an R-Tree either bulk-loaded or not
+// Time how long it takes to build an R-Tree.
class RTreeBuildBench : public Benchmark {
public:
- RTreeBuildBench(const char* name, MakeRectProc proc, SkRTree* tree)
- : fTree(tree)
- , fProc(proc) {
+ RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
fName.printf("rtree_%s_build", name);
}
@@ -32,9 +30,6 @@
return backend == kNonRendering_Backend;
}
- virtual ~RTreeBuildBench() {
- fTree->unref();
- }
protected:
virtual const char* onGetName() SK_OVERRIDE {
return fName.c_str();
@@ -47,34 +42,27 @@
}
for (int i = 0; i < loops; ++i) {
- fTree->insert(&rects, NUM_BUILD_RECTS);
+ SkRTree tree;
+ tree.insert(&rects, NUM_BUILD_RECTS);
SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects.
- fTree->clear();
}
}
private:
- SkRTree* fTree;
MakeRectProc fProc;
SkString fName;
typedef Benchmark INHERITED;
};
-// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
+// Time how long it takes to perform queries on an R-Tree.
class RTreeQueryBench : public Benchmark {
public:
- RTreeQueryBench(const char* name, MakeRectProc proc, SkRTree* tree)
- : fTree(tree)
- , fProc(proc) {
+ RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
fName.printf("rtree_%s_query", name);
}
virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
return backend == kNonRendering_Backend;
}
-
- virtual ~RTreeQueryBench() {
- fTree->unref();
- }
protected:
virtual const char* onGetName() SK_OVERRIDE {
return fName.c_str();
@@ -85,7 +73,7 @@
for (int i = 0; i < NUM_QUERY_RECTS; ++i) {
rects[i] = fProc(rand, i, NUM_QUERY_RECTS);
}
- fTree->insert(&rects, NUM_QUERY_RECTS);
+ fTree.insert(&rects, NUM_QUERY_RECTS);
}
virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
@@ -97,21 +85,16 @@
query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
- fTree->search(query, &hits);
+ fTree.search(query, &hits);
}
}
private:
- SkBBoxHierarchy* fTree;
+ SkRTree fTree;
MakeRectProc fProc;
SkString fName;
typedef Benchmark INHERITED;
};
-static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
- SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
- return out;
-}
-
static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
SkRect out;
out.fLeft = SkIntToScalar(index % GRID_WIDTH);
@@ -138,42 +121,18 @@
return out;
}
+static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
+ return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
+}
+
///////////////////////////////////////////////////////////////////////////////
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench,
- ("concentric_unsorted",
- &make_concentric_rects_increasing,
- SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY", &make_XYordered_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX", &make_YXordered_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects)));
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));)
-DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench,
- ("concentric_unsorted",
- &make_concentric_rects_increasing,
- SkRTree::Create(5, 16, 1, false)));)
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY", &make_XYordered_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX", &make_YXordered_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects)));
+DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects)));
diff --git a/src/core/SkBBHFactory.cpp b/src/core/SkBBHFactory.cpp
index c895ff6..22f816c 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 93f9142..6c78031 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;
- }
- }
-
- 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();
- }
-
- // 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;
- ++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->setCount(newBranches);
- return this->bulkLoad(branches, level + 1);
+ if (branches->count() == 1) { // Only one branch. It will be the root.
+ return (*branches)[0];
}
-}
-void SkRTree::validate() const {
-#ifdef SK_DEBUG
- if (this->isEmpty()) {
- return;
- }
- SkASSERT(fCount == this->validateSubtree(fRoot.fChild.subtree, fRoot.fBounds, true));
-#endif
-}
+ // 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;
-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);
+ 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 {
- SkASSERT(root->fNumChildren >= 2 && root->fNumChildren <= fMaxChildren);
+ remainder = kMinChildren - remainder;
}
- } else {
- SkASSERT(root->fNumChildren >= fMinChildren && root->fNumChildren <= fMaxChildren);
}
- for (int i = 0; i < root->fNumChildren; ++i) {
- SkASSERT(bounds.contains(root->child(i)->fBounds));
- }
+ int numStrips = SkScalarCeilToInt(SkScalarSqrt(SkIntToScalar(numBranches) / fAspectRatio));
+ int numTiles = SkScalarCeilToInt(SkIntToScalar(numBranches) / SkIntToScalar(numStrips));
+ int currentBranch = 0;
- 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);
+ 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;
+ }
+ }
+ 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;
+ }
+ (*branches)[newBranches] = b;
+ ++newBranches;
}
- return childCount;
+ }
+ branches->setCount(newBranches);
+ return this->bulkLoad(branches, level + 1);
+}
+
+void SkRTree::search(const SkRect& query, SkTDArray<unsigned>* results) const {
+ if (fCount > 0 && SkRect::Intersects(fRoot.fBounds, query)) {
+ this->search(fRoot.fSubtree, query, results);
}
}
-///////////////////////////////////////////////////////////////////////////////////////////////////
-
-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; }
+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);
+ }
+ }
+ }
}
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 00c6c89..440411d 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;
- }
+ Branch fChildren[kMaxChildren];
};
- typedef int32_t SkIRect::*SortSide;
+ void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const;
- // 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);
- }
- };
-
- 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;
-
- /**
- * 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;
};
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 5d5c1cb..50eaacb 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -7,12 +7,8 @@
#include "SkRTree.h"
#include "SkRandom.h"
-#include "SkTSort.h"
#include "Test.h"
-static const size_t MIN_CHILDREN = 6;
-static const size_t MAX_CHILDREN = 11;
-
static const int NUM_RECTS = 200;
static const size_t NUM_ITERATIONS = 100;
static const size_t NUM_QUERIES = 50;
@@ -30,11 +26,7 @@
}
static bool verify_query(SkRect query, SkRect rects[], SkTDArray<unsigned>& found) {
- // TODO(mtklein): no need to do this after everything's SkRects
- query.roundOut();
-
SkTDArray<unsigned> expected;
-
// manually intersect with every rectangle
for (int i = 0; i < NUM_RECTS; ++i) {
if (SkRect::Intersects(query, rects[i])) {
@@ -45,19 +37,14 @@
if (expected.count() != found.count()) {
return false;
}
-
if (0 == expected.count()) {
return true;
}
-
- // skia:2834. RTree doesn't always return results in order.
- SkTQSort(expected.begin(), expected.end() -1);
- SkTQSort(found.begin(), found.end() -1);
return found == expected;
}
static void run_queries(skiatest::Reporter* reporter, SkRandom& rand, SkRect rects[],
- SkRTree& tree) {
+ const SkRTree& tree) {
for (size_t i = 0; i < NUM_QUERIES; ++i) {
SkTDArray<unsigned> hits;
SkRect query = random_rect(rand);
@@ -66,53 +53,39 @@
}
}
-static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
- SkASSERT(rtree);
-
+DEF_TEST(RTree, reporter) {
int expectedDepthMin = -1;
- int expectedDepthMax = -1;
-
int tmp = NUM_RECTS;
while (tmp > 0) {
- tmp -= static_cast<int>(pow(static_cast<double>(MAX_CHILDREN),
- static_cast<double>(expectedDepthMin + 1)));
+ tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMaxChildren),
+ static_cast<double>(expectedDepthMin + 1)));
++expectedDepthMin;
}
+ int expectedDepthMax = -1;
tmp = NUM_RECTS;
while (tmp > 0) {
- tmp -= static_cast<int>(pow(static_cast<double>(MIN_CHILDREN),
- static_cast<double>(expectedDepthMax + 1)));
+ tmp -= static_cast<int>(pow(static_cast<double>(SkRTree::kMinChildren),
+ static_cast<double>(expectedDepthMax + 1)));
++expectedDepthMax;
}
SkRandom rand;
SkAutoTMalloc<SkRect> rects(NUM_RECTS);
for (size_t i = 0; i < NUM_ITERATIONS; ++i) {
- rtree->clear();
- REPORTER_ASSERT(reporter, 0 == rtree->getCount());
+ SkRTree rtree;
+ REPORTER_ASSERT(reporter, 0 == rtree.getCount());
for (int j = 0; j < NUM_RECTS; j++) {
rects[j] = random_rect(rand);
}
- rtree->insert(&rects, NUM_RECTS);
+ rtree.insert(&rects, NUM_RECTS);
SkASSERT(rects); // SkRTree doesn't take ownership of rects.
- run_queries(reporter, rand, rects, *rtree);
- REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
- REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
- expectedDepthMax >= rtree->getDepth());
+ run_queries(reporter, rand, rects, rtree);
+ REPORTER_ASSERT(reporter, NUM_RECTS == rtree.getCount());
+ REPORTER_ASSERT(reporter, expectedDepthMin <= rtree.getDepth() &&
+ expectedDepthMax >= rtree.getDepth());
}
}
-
-DEF_TEST(RTree, reporter) {
- SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
- SkAutoUnref au(rtree);
- rtree_test_main(rtree, reporter);
-
- // Rtree that orders input rectangles on deferred insert.
- SkRTree* unsortedRtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN, 1, false);
- SkAutoUnref auo(unsortedRtree);
- rtree_test_main(unsortedRtree, reporter);
-}