RTreeBench.cpp revision c289743864e2ab926a95e617a5cd1d29b26d1825
1 2/* 3 * Copyright 2012 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9#include "SkBenchmark.h" 10#include "SkCanvas.h" 11#include "SkRTree.h" 12#include "SkRandom.h" 13#include "SkString.h" 14 15// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs: 16static const int GENERATE_EXTENTS = 1000; 17static const int NUM_BUILD_RECTS = 500; 18static const int NUM_QUERY_RECTS = 5000; 19static const int GRID_WIDTH = 100; 20 21typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); 22 23// Time how long it takes to build an R-Tree either bulk-loaded or not 24class BBoxBuildBench : public SkBenchmark { 25public: 26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad, 27 SkBBoxHierarchy* tree) 28 : INHERITED(param) 29 , fTree(tree) 30 , fProc(proc) 31 , fBulkLoad(bulkLoad) { 32 fName.append("rtree_"); 33 fName.append(name); 34 fName.append("_build"); 35 if (fBulkLoad) { 36 fName.append("_bulk"); 37 } 38 fIsRendering = false; 39 } 40 virtual ~BBoxBuildBench() { 41 fTree->unref(); 42 } 43protected: 44 virtual const char* onGetName() SK_OVERRIDE { 45 return fName.c_str(); 46 } 47 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { 48 SkRandom rand; 49 for (int i = 0; i < this->getLoops(); ++i) { 50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { 51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS), 52 fBulkLoad); 53 } 54 fTree->flushDeferredInserts(); 55 fTree->clear(); 56 } 57 } 58private: 59 SkBBoxHierarchy* fTree; 60 MakeRectProc fProc; 61 SkString fName; 62 bool fBulkLoad; 63 typedef SkBenchmark INHERITED; 64}; 65 66// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not 67class BBoxQueryBench : public SkBenchmark { 68public: 69 enum QueryType { 70 kSmall_QueryType, // small queries 71 kLarge_QueryType, // large queries 72 kRandom_QueryType,// randomly sized queries 73 kFull_QueryType // queries that cover everything 74 }; 75 76 BBoxQueryBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad, 77 QueryType q, SkBBoxHierarchy* tree) 78 : INHERITED(param) 79 , fTree(tree) 80 , fProc(proc) 81 , fBulkLoad(bulkLoad) 82 , fQuery(q) { 83 fName.append("rtree_"); 84 fName.append(name); 85 fName.append("_query"); 86 if (fBulkLoad) { 87 fName.append("_bulk"); 88 } 89 fIsRendering = false; 90 } 91 virtual ~BBoxQueryBench() { 92 fTree->unref(); 93 } 94protected: 95 virtual const char* onGetName() SK_OVERRIDE { 96 return fName.c_str(); 97 } 98 virtual void onPreDraw() SK_OVERRIDE { 99 SkRandom rand; 100 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { 101 fTree->insert(reinterpret_cast<void*>(j), 102 fProc(rand, j, NUM_QUERY_RECTS), 103 fBulkLoad); 104 } 105 fTree->flushDeferredInserts(); 106 } 107 108 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { 109 SkRandom rand; 110 for (int i = 0; i < this->getLoops(); ++i) { 111 SkTDArray<void*> hits; 112 SkIRect query; 113 switch(fQuery) { 114 case kSmall_QueryType: 115 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 116 query.fTop = rand.nextU() % GENERATE_EXTENTS; 117 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); 118 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); 119 break; 120 case kLarge_QueryType: 121 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 122 query.fTop = rand.nextU() % GENERATE_EXTENTS; 123 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); 124 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); 125 break; 126 case kFull_QueryType: 127 query.fLeft = -GENERATE_EXTENTS; 128 query.fTop = -GENERATE_EXTENTS; 129 query.fRight = 2 * GENERATE_EXTENTS; 130 query.fBottom = 2 * GENERATE_EXTENTS; 131 break; 132 default: // fallthrough 133 case kRandom_QueryType: 134 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 135 query.fTop = rand.nextU() % GENERATE_EXTENTS; 136 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 137 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 138 break; 139 }; 140 fTree->search(query, &hits); 141 } 142 } 143private: 144 SkBBoxHierarchy* fTree; 145 MakeRectProc fProc; 146 SkString fName; 147 bool fBulkLoad; 148 QueryType fQuery; 149 typedef SkBenchmark INHERITED; 150}; 151 152static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) { 153 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; 154 return out; 155} 156 157static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { 158 SkIRect out = {0, 0, index + 1, index + 1}; 159 return out; 160} 161 162static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) { 163 SkIRect out = {0, 0, numRects - index, numRects - index}; 164 return out; 165} 166 167static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 168 SkIRect out; 169 out.fLeft = index % GRID_WIDTH; 170 out.fTop = index / GRID_WIDTH; 171 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 172 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 173 return out; 174} 175static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 176 SkIRect out; 177 out.fLeft = index / GRID_WIDTH; 178 out.fTop = index % GRID_WIDTH; 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 181 return out; 182} 183 184static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects) { 185 SkIRect out; 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); 190 return out; 191} 192 193static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) { 194 SkIRect out; 195 out.fLeft = rand.nextS() % GENERATE_EXTENTS; 196 out.fTop = rand.nextS() % GENERATE_EXTENTS; 197 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 198 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 199 return out; 200} 201 202static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects) { 203 SkIRect out; 204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; 205 out.fTop = rand.nextU() % GENERATE_EXTENTS; 206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); 207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); 208 return out; 209} 210 211/////////////////////////////////////////////////////////////////////////////// 212 213static inline SkBenchmark* Fact0(void* p) { 214 return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, false, 215 SkRTree::Create(5, 16))); 216} 217static inline SkBenchmark* Fact1(void* p) { 218 return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, true, 219 SkRTree::Create(5, 16))); 220} 221static inline SkBenchmark* Fact2(void* p) { 222 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true, 223 SkRTree::Create(5, 16, 1, false))); 224} 225static inline SkBenchmark* Fact3(void* p) { 226 return SkNEW_ARGS(BBoxQueryBench, (p, "XYordered", &make_XYordered_rects, true, 227 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 228} 229static inline SkBenchmark* Fact4(void* p) { 230 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true, 231 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 232} 233 234static inline SkBenchmark* Fact5(void* p) { 235 return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, false, 236 SkRTree::Create(5, 16))); 237} 238static inline SkBenchmark* Fact6(void* p) { 239 return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, true, 240 SkRTree::Create(5, 16))); 241} 242static inline SkBenchmark* Fact7(void* p) { 243 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true, 244 SkRTree::Create(5, 16, 1, false))); 245} 246static inline SkBenchmark* Fact8(void* p) { 247 return SkNEW_ARGS(BBoxQueryBench, (p, "YXordered", &make_YXordered_rects, true, 248 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 249} 250static inline SkBenchmark* Fact9(void* p) { 251 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true, 252 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 253} 254 255static inline SkBenchmark* Fact10(void* p) { 256 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false, 257 SkRTree::Create(5, 16))); 258} 259static inline SkBenchmark* Fact11(void* p) { 260 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true, 261 SkRTree::Create(5, 16))); 262} 263static inline SkBenchmark* Fact12(void* p) { 264 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)random", &make_random_rects, true, 265 SkRTree::Create(5, 16, 1, false))); 266} 267static inline SkBenchmark* Fact13(void* p) { 268 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true, 269 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 270} 271static inline SkBenchmark* Fact14(void* p) { 272 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)random", &make_random_rects, true, 273 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 274} 275 276static inline SkBenchmark* Fact15(void* p) { 277 return SkNEW_ARGS(BBoxBuildBench, (p, "concentric", 278 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); 279} 280static inline SkBenchmark* Fact16(void* p) { 281 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)concentric", 282 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false))); 283} 284static inline SkBenchmark* Fact17(void* p) { 285 return SkNEW_ARGS(BBoxQueryBench, (p, "concentric", &make_concentric_rects_increasing, true, 286 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 287} 288static inline SkBenchmark* Fact18(void* p) { 289 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)concentric", &make_concentric_rects_increasing, true, 290 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 291} 292 293static BenchRegistry gReg18(Fact18); 294static BenchRegistry gReg17(Fact17); 295static BenchRegistry gReg16(Fact16); 296static BenchRegistry gReg15(Fact15); 297static BenchRegistry gReg14(Fact14); 298static BenchRegistry gReg13(Fact13); 299static BenchRegistry gReg12(Fact12); 300static BenchRegistry gReg11(Fact11); 301static BenchRegistry gReg10(Fact10); 302static BenchRegistry gReg9(Fact9); 303static BenchRegistry gReg8(Fact8); 304static BenchRegistry gReg7(Fact7); 305static BenchRegistry gReg6(Fact6); 306static BenchRegistry gReg5(Fact5); 307static BenchRegistry gReg4(Fact4); 308static BenchRegistry gReg3(Fact3); 309static BenchRegistry gReg2(Fact2); 310static BenchRegistry gReg1(Fact1); 311static BenchRegistry gReg0(Fact0); 312