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: 16 static const int GENERATE_EXTENTS = 1000; 17 static const int NUM_BUILD_RECTS = 500; 18 static const int NUM_QUERY_RECTS = 5000; 19 static const int NUM_QUERIES = 1000; 20 21 typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int); 22 23 // Time how long it takes to build an R-Tree either bulk-loaded or not 24 class BBoxBuildBench : public SkBenchmark { 25 public: 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 } 43 protected: 44 virtual const char* onGetName() SK_OVERRIDE { 45 return fName.c_str(); 46 } 47 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { 48 SkMWCRandom rand; 49 for (int i = 0; i < SkBENCHLOOP(100); ++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 } 58 private: 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 67 class BBoxQueryBench : public SkBenchmark { 68 public: 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 } 94 protected: 95 virtual const char* onGetName() SK_OVERRIDE { 96 return fName.c_str(); 97 } 98 virtual void onPreDraw() SK_OVERRIDE { 99 SkMWCRandom rand; 100 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { 101 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, 102 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); 103 } 104 fTree->flushDeferredInserts(); 105 } 106 107 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { 108 SkMWCRandom rand; 109 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { 110 SkTDArray<void*> hits; 111 SkIRect query; 112 switch(fQuery) { 113 case kSmall_QueryType: 114 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 115 query.fTop = rand.nextU() % GENERATE_EXTENTS; 116 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); 117 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); 118 break; 119 case kLarge_QueryType: 120 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 121 query.fTop = rand.nextU() % GENERATE_EXTENTS; 122 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); 123 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); 124 break; 125 case kFull_QueryType: 126 query.fLeft = -GENERATE_EXTENTS; 127 query.fTop = -GENERATE_EXTENTS; 128 query.fRight = 2 * GENERATE_EXTENTS; 129 query.fBottom = 2 * GENERATE_EXTENTS; 130 break; 131 default: // fallthrough 132 case kRandom_QueryType: 133 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 134 query.fTop = rand.nextU() % GENERATE_EXTENTS; 135 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 136 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 137 break; 138 }; 139 fTree->search(query, &hits); 140 } 141 } 142 private: 143 SkBBoxHierarchy* fTree; 144 MakeRectProc fProc; 145 SkString fName; 146 bool fBulkLoad; 147 QueryType fQuery; 148 typedef SkBenchmark INHERITED; 149 }; 150 151 static inline SkIRect make_simple_rect(SkMWCRandom&, int index, int numRects) { 152 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; 153 return out; 154 } 155 156 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index, int numRects) { 157 SkIRect out = {0, 0, index + 1, index + 1}; 158 return out; 159 } 160 161 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index, int numRects) { 162 SkIRect out = {0, 0, numRects - index, numRects - index}; 163 return out; 164 } 165 166 static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRects) { 167 SkIRect out; 168 out.fLeft = rand.nextU() % GENERATE_EXTENTS; 169 out.fTop = rand.nextU() % GENERATE_EXTENTS; 170 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); 171 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); 172 return out; 173 } 174 175 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRects) { 176 SkIRect out; 177 out.fLeft = rand.nextS() % GENERATE_EXTENTS; 178 out.fTop = rand.nextS() % GENERATE_EXTENTS; 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 181 return out; 182 } 183 184 static inline SkIRect make_large_rects(SkMWCRandom& 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 / 3); 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); 190 return out; 191 } 192 193 /////////////////////////////////////////////////////////////////////////////// 194 195 static inline SkBenchmark* Fact0(void* p) { 196 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true, 197 SkRTree::Create(5, 16))); 198 } 199 static inline SkBenchmark* Fact1(void* p) { 200 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false, 201 SkRTree::Create(5, 16))); 202 } 203 static inline SkBenchmark* Fact2(void* p) { 204 return SkNEW_ARGS(BBoxBuildBench, (p, "concentric", 205 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); 206 } 207 static inline SkBenchmark* Fact3(void* p) { 208 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true, 209 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 210 } 211 static inline SkBenchmark* Fact4(void* p) { 212 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, 213 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 214 } 215 216 static BenchRegistry gReg0(Fact0); 217 static BenchRegistry gReg1(Fact1); 218 static BenchRegistry gReg2(Fact2); 219 static BenchRegistry gReg3(Fact3); 220 static BenchRegistry gReg4(Fact4); 221
