R-Tree -- Don't sort draw commands unless specified.

bench/RTreeBench.cpp

Index: bench/RTreeBench.cpp
diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index bce1b67513f734d115b174928b6885eca1e41c19..d017f39972f8ed6d87c2360251c4391775bacb22 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/RTreeBench.cpp
@@ -17,6 +17,7 @@ static const int GENERATE_EXTENTS = 1000;
 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 @@ static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index,
     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);

[caryclark, 2013/08/29 19:22:18]

this allows the right and bottom to be less than left and top. Since each is 1
or greater, I expect these are supposed to be width and height?

out.fRight = out.fLeft + 1 + rand.nextU() ...

[sglez, 2013/08/29 20:17:38]

Thanks

+    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 SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect
 ///////////////////////////////////////////////////////////////////////////////
 
 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)));

[caryclark, 2013/08/29 19:22:18]

should the strings for Fact0 and Fact1 be different?

[sglez, 2013/08/29 20:17:38]

They are the same, but the final bench name will be different.
Since the class is BBoxBuildBench, it will append "_build"
The "true" param at the end of this line tells it to use bulk loading.
It will append "_bulk"

So the name will appear as XYordered_build_bulk,
where Fact0 will appear as XYordered_build.

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

[caryclark, 2013/08/29 19:22:18]

should the string passed to Fact2 and Fact4 be different, so one can tell which
gets the BBoxQueryBench::kRandom_QueryType parameter?

[sglez, 2013/08/29 20:17:38]

Same as before, but instead of appending _build it appends _query.

 }
 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,
+    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
+                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+}
+
+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 BenchRegistry gReg0(Fact0);
-static BenchRegistry gReg1(Fact1);
-static BenchRegistry gReg2(Fact2);
-static BenchRegistry gReg3(Fact3);
+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);
+