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

1 files changed, 102 insertions, 10 deletions

diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp
index bce1b67513..d017f39972 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);
+    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)));
 }
 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,
+    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);
+