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

bench/RTreeBench.cpp

 
 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkBenchmark.h"
 #include "SkCanvas.h"
 #include "SkRTree.h"
 #include "SkRandom.h"
 #include "SkString.h"
 
 // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
 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);
 
 // Time how long it takes to build an R-Tree either bulk-loaded or not
 class BBoxBuildBench : public SkBenchmark {
 public:
     BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
                     SkBBoxHierarchy* tree)
         : INHERITED(param)
         , fTree(tree)
@@ skipping 126 matching lines @@
 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index, int numRects) {
     SkIRect out = {0, 0, index + 1, index + 1};
     return out;
 }
 
 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index, int numRects) {
     SkIRect out = {0, 0, numRects - index, numRects - 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;
     out.fTop    = rand.nextU() % GENERATE_EXTENTS;
     out.fRight  = out.fLeft + (GENERATE_EXTENTS / 200);
     out.fBottom = out.fTop + (GENERATE_EXTENTS / 200);
     return out;
 }
 
 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRects) {
@@ skipping 10 matching lines @@
     out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
     out.fTop    = rand.nextU() % GENERATE_EXTENTS;
     out.fRight  = out.fLeft + (GENERATE_EXTENTS / 3);
     out.fBottom = out.fTop  + (GENERATE_EXTENTS / 3);
     return out;
 }
 
 ///////////////////////////////////////////////////////////////////////////////
 
 static inline SkBenchmark* Fact0(void* p) {
+    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, "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, "(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, "XYordered", &make_XYordered_rects, true,
+                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+}
+static inline SkBenchmark* Fact4(void* p) {
+    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 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* Fact1(void* p) {
-    return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
-                      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* Fact2(void* p) {
+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* Fact3(void* p) {
-    return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
+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* Fact4(void* p) {
-    return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false,
-                      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);
-static BenchRegistry gReg1(Fact1);
-static BenchRegistry gReg2(Fact2);
-static BenchRegistry gReg3(Fact3);
-static BenchRegistry gReg4(Fact4);
+