R-Tree -- Don't sort draw commands unless specified.
We expect Webkit and Bink to give us draw commands in a reasonable x,y order.
We can maintain correctness and get a 17% recording speedup for the R-Tree by
not sorting in x and y when bulk-loading.
R=caryclark@google.com, reed@google.com
Review URL: https://codereview.chromium.org/23480002
git-svn-id: http://skia.googlecode.com/svn/trunk@11037 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index bce1b67..d017f39 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -17,6 +17,7 @@
static const int NUM_BUILD_RECTS = 500;
static const int NUM_QUERY_RECTS = 5000;
static const int NUM_QUERIES = 1000;
+static const int GRID_WIDTH = 100;
typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int);
@@ -163,6 +164,23 @@
return out;
}
+static inline SkIRect make_XYordered_rects(SkMWCRandom& rand, int index, int numRects) {
+ SkIRect out;
+ out.fLeft = index % GRID_WIDTH;
+ out.fTop = index / GRID_WIDTH;
+ out.fRight = 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ return out;
+}
+static inline SkIRect make_YXordered_rects(SkMWCRandom& rand, int index, int numRects) {
+ SkIRect out;
+ out.fLeft = index / GRID_WIDTH;
+ out.fTop = index % GRID_WIDTH;
+ out.fRight = 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
+ return out;
+}
+
static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRects) {
SkIRect out;
out.fLeft = rand.nextU() % GENERATE_EXTENTS;
@@ -193,28 +211,102 @@
///////////////////////////////////////////////////////////////////////////////
static inline SkBenchmark* Fact0(void* p) {
- return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
+ return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, false,
SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact1(void* p) {
- return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
+ return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, true,
SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact2(void* p) {
- return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
- &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
+ SkRTree::Create(5, 16, 1, false)));
}
static inline SkBenchmark* Fact3(void* p) {
- return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
+ return SkNEW_ARGS(BBoxQueryBench, (p, "XYordered", &make_XYordered_rects, true,
BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact4(void* p) {
- return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
}
-static BenchRegistry gReg0(Fact0);
-static BenchRegistry gReg1(Fact1);
-static BenchRegistry gReg2(Fact2);
-static BenchRegistry gReg3(Fact3);
+static inline SkBenchmark* Fact5(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, false,
+ SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact6(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, true,
+ SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact7(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
+ SkRTree::Create(5, 16, 1, false)));
+}
+static inline SkBenchmark* Fact8(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "YXordered", &make_YXordered_rects, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact9(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+}
+
+static inline SkBenchmark* Fact10(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
+ SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact11(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
+ SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact12(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)random", &make_random_rects, true,
+ SkRTree::Create(5, 16, 1, false)));
+}
+static inline SkBenchmark* Fact13(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact14(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)random", &make_random_rects, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+}
+
+static inline SkBenchmark* Fact15(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
+ &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact16(void* p) {
+ return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)concentric",
+ &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
+}
+static inline SkBenchmark* Fact17(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "concentric", &make_concentric_rects_increasing, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact18(void* p) {
+ return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)concentric", &make_concentric_rects_increasing, true,
+ BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+}
+
+static BenchRegistry gReg18(Fact18);
+static BenchRegistry gReg17(Fact17);
+static BenchRegistry gReg16(Fact16);
+static BenchRegistry gReg15(Fact15);
+static BenchRegistry gReg14(Fact14);
+static BenchRegistry gReg13(Fact13);
+static BenchRegistry gReg12(Fact12);
+static BenchRegistry gReg11(Fact11);
+static BenchRegistry gReg10(Fact10);
+static BenchRegistry gReg9(Fact9);
+static BenchRegistry gReg8(Fact8);
+static BenchRegistry gReg7(Fact7);
+static BenchRegistry gReg6(Fact6);
+static BenchRegistry gReg5(Fact5);
static BenchRegistry gReg4(Fact4);
+static BenchRegistry gReg3(Fact3);
+static BenchRegistry gReg2(Fact2);
+static BenchRegistry gReg1(Fact1);
+static BenchRegistry gReg0(Fact0);
+
diff --git a/src/core/SkPicture.cpp b/src/core/SkPicture.cpp
index 1aa4528..f70f16e 100644
--- a/src/core/SkPicture.cpp
+++ b/src/core/SkPicture.cpp
@@ -232,8 +232,10 @@
SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(fWidth),
SkIntToScalar(fHeight));
+ bool sortDraws = false; // Do not sort draw calls when bulk loading.
+
return SkRTree::Create(kRTreeMinChildren, kRTreeMaxChildren,
- aspectRatio);
+ aspectRatio, sortDraws);
}
SkCanvas* SkPicture::getRecordingCanvas() const {
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index d7a15d5..95e4336 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -21,21 +21,24 @@
SK_DEFINE_INST_COUNT(SkRTree)
-SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio) {
+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);
+ return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
}
return NULL;
}
-SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio)
+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) {
+ , fAspectRatio(aspectRatio)
+ , fSortWhenBulkLoading(sortWhenBulkLoading) {
SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
static_cast<int>(SK_MaxU16));
SkASSERT((maxChildren + 1) / 2 >= minChildren);
@@ -323,8 +326,14 @@
branches->rewind();
return out;
} else {
- // First we sort the whole list by y coordinates
- SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
+ // 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;
@@ -348,15 +357,18 @@
int currentBranch = 0;
for (int i = 0; i < numStrips; ++i) {
- int begin = currentBranch;
- int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
- (fMaxChildren - fMinChildren) * numTiles);
- if (end > branches->count()) {
- end = branches->count();
- }
+ // 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());
+ // 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;
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 2d11f28..54421de 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -55,7 +55,8 @@
* 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);
+ static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
+ bool orderWhenBulkLoading = true);
virtual ~SkRTree();
/**
@@ -144,7 +145,7 @@
}
};
- SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio);
+ SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
/**
* Recursively descend the tree to find an insertion position for 'branch', updates
@@ -184,6 +185,7 @@
SkChunkAlloc fNodes;
SkTDArray<Branch> fDeferredInserts;
SkScalar fAspectRatio;
+ bool fSortWhenBulkLoading;
Node* allocateNode(uint16_t level);
diff --git a/tests/RTreeTest.cpp b/tests/RTreeTest.cpp
index 6296c4e..655336c 100644
--- a/tests/RTreeTest.cpp
+++ b/tests/RTreeTest.cpp
@@ -68,7 +68,7 @@
return found == expected;
}
-static void runQueries(skiatest::Reporter* reporter, SkMWCRandom& rand, DataRect rects[],
+static void run_queries(skiatest::Reporter* reporter, SkMWCRandom& rand, DataRect rects[],
SkRTree& tree) {
for (size_t i = 0; i < NUM_QUERIES; ++i) {
SkTDArray<void*> hits;
@@ -78,11 +78,9 @@
}
}
-static void TestRTree(skiatest::Reporter* reporter) {
+static void rtree_test_main(SkRTree* rtree, skiatest::Reporter* reporter) {
DataRect rects[NUM_RECTS];
SkMWCRandom rand;
- SkRTree* rtree = SkRTree::Create(MIN_CHILDREN, MAX_CHILDREN);
- SkAutoUnref au(rtree);
REPORTER_ASSERT(reporter, NULL != rtree);
int expectedDepthMin = -1;
@@ -110,7 +108,7 @@
rtree->insert(rects[i].data, rects[i].rect, true);
}
rtree->flushDeferredInserts();
- runQueries(reporter, rand, rects, *rtree);
+ run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
expectedDepthMax >= rtree->getDepth());
@@ -121,7 +119,7 @@
for (int i = 0; i < NUM_RECTS; ++i) {
rtree->insert(rects[i].data, rects[i].rect);
}
- runQueries(reporter, rand, rects, *rtree);
+ run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
expectedDepthMax >= rtree->getDepth());
@@ -132,7 +130,7 @@
for (int i = NUM_RECTS - 1; i >= 0; --i) {
rtree->insert(rects[i].data, rects[i].rect);
}
- runQueries(reporter, rand, rects, *rtree);
+ run_queries(reporter, rand, rects, *rtree);
REPORTER_ASSERT(reporter, NUM_RECTS == rtree->getCount());
REPORTER_ASSERT(reporter, expectedDepthMin <= rtree->getDepth() &&
expectedDepthMax >= rtree->getDepth());
@@ -141,5 +139,17 @@
}
}
+static void test_rtree(skiatest::Reporter* 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, false);
+ SkAutoUnref auo(orderedRtree);
+ rtree_test_main(orderedRtree, reporter);
+}
+
+
#include "TestClassDef.h"
-DEFINE_TESTCLASS("RTree", RTreeTestClass, TestRTree)
+DEFINE_TESTCLASS("RTree", RTreeTestClass, test_rtree)
diff --git a/tools/PictureRenderer.cpp b/tools/PictureRenderer.cpp
index 2730a23..c53bd08 100644
--- a/tools/PictureRenderer.cpp
+++ b/tools/PictureRenderer.cpp
@@ -790,8 +790,9 @@
static const int kRTreeMaxChildren = 11;
SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(fWidth),
SkIntToScalar(fHeight));
+ bool sortDraws = false;
return SkRTree::Create(kRTreeMinChildren, kRTreeMaxChildren,
- aspectRatio);
+ aspectRatio, sortDraws);
}
};