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);
+