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 "Benchmark.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 SkScalar GENERATE_EXTENTS = 1000.0f; 17 static const int NUM_BUILD_RECTS = 500; 18 static const int NUM_QUERY_RECTS = 5000; 19 static const int GRID_WIDTH = 100; 20 21 typedef SkRect (*MakeRectProc)(SkRandom&, int, int); 22 23 // Time how long it takes to build an R-Tree either bulk-loaded or not 24 class RTreeBuildBench : public Benchmark { 25 public: 26 RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, 27 SkBBoxHierarchy* tree) 28 : fTree(tree) 29 , fProc(proc) 30 , fBulkLoad(bulkLoad) { 31 fName.append("rtree_"); 32 fName.append(name); 33 fName.append("_build"); 34 if (fBulkLoad) { 35 fName.append("_bulk"); 36 } 37 } 38 39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 40 return backend == kNonRendering_Backend; 41 } 42 43 virtual ~RTreeBuildBench() { 44 fTree->unref(); 45 } 46 protected: 47 virtual const char* onGetName() SK_OVERRIDE { 48 return fName.c_str(); 49 } 50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 51 SkRandom rand; 52 for (int i = 0; i < loops; ++i) { 53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { 54 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS), 55 fBulkLoad); 56 } 57 fTree->flushDeferredInserts(); 58 fTree->clear(); 59 } 60 } 61 private: 62 SkBBoxHierarchy* fTree; 63 MakeRectProc fProc; 64 SkString fName; 65 bool fBulkLoad; 66 typedef Benchmark INHERITED; 67 }; 68 69 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not 70 class RTreeQueryBench : public Benchmark { 71 public: 72 enum QueryType { 73 kSmall_QueryType, // small queries 74 kLarge_QueryType, // large queries 75 kRandom_QueryType,// randomly sized queries 76 kFull_QueryType // queries that cover everything 77 }; 78 79 RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, 80 QueryType q, SkBBoxHierarchy* tree) 81 : fTree(tree) 82 , fProc(proc) 83 , fBulkLoad(bulkLoad) 84 , fQuery(q) { 85 fName.append("rtree_"); 86 fName.append(name); 87 fName.append("_query"); 88 if (fBulkLoad) { 89 fName.append("_bulk"); 90 } 91 } 92 93 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 94 return backend == kNonRendering_Backend; 95 } 96 97 virtual ~RTreeQueryBench() { 98 fTree->unref(); 99 } 100 protected: 101 virtual const char* onGetName() SK_OVERRIDE { 102 return fName.c_str(); 103 } 104 virtual void onPreDraw() SK_OVERRIDE { 105 SkRandom rand; 106 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { 107 fTree->insert(reinterpret_cast<void*>(j), 108 fProc(rand, j, NUM_QUERY_RECTS), 109 fBulkLoad); 110 } 111 fTree->flushDeferredInserts(); 112 } 113 114 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 115 SkRandom rand; 116 for (int i = 0; i < loops; ++i) { 117 SkTDArray<void*> hits; 118 SkRect query; 119 switch(fQuery) { 120 case kSmall_QueryType: 121 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 122 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 123 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); 124 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); 125 break; 126 case kLarge_QueryType: 127 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 128 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 129 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); 130 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); 131 break; 132 case kFull_QueryType: 133 query.fLeft = -GENERATE_EXTENTS; 134 query.fTop = -GENERATE_EXTENTS; 135 query.fRight = 2 * GENERATE_EXTENTS; 136 query.fBottom = 2 * GENERATE_EXTENTS; 137 break; 138 default: // fallthrough 139 case kRandom_QueryType: 140 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 141 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 142 query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); 143 query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); 144 break; 145 }; 146 fTree->search(query, &hits); 147 } 148 } 149 private: 150 SkBBoxHierarchy* fTree; 151 MakeRectProc fProc; 152 SkString fName; 153 bool fBulkLoad; 154 QueryType fQuery; 155 typedef Benchmark INHERITED; 156 }; 157 158 static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { 159 SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); 160 return out; 161 } 162 163 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 164 SkRect out; 165 out.fLeft = SkIntToScalar(index % GRID_WIDTH); 166 out.fTop = SkIntToScalar(index / GRID_WIDTH); 167 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 168 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 169 return out; 170 } 171 static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 172 SkRect out; 173 out.fLeft = SkIntToScalar(index / GRID_WIDTH); 174 out.fTop = SkIntToScalar(index % GRID_WIDTH); 175 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 176 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 177 return out; 178 } 179 180 static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) { 181 SkRect out; 182 out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 183 out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 184 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); 185 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); 186 return out; 187 } 188 189 /////////////////////////////////////////////////////////////////////////////// 190 191 DEF_BENCH( 192 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false, 193 SkRTree::Create(5, 16))); 194 ) 195 DEF_BENCH( 196 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true, 197 SkRTree::Create(5, 16))); 198 ) 199 DEF_BENCH( 200 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 201 SkRTree::Create(5, 16, 1, false))); 202 ) 203 DEF_BENCH( 204 return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true, 205 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 206 ) 207 DEF_BENCH( 208 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 209 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 210 ) 211 212 DEF_BENCH( 213 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false, 214 SkRTree::Create(5, 16))); 215 ) 216 DEF_BENCH( 217 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true, 218 SkRTree::Create(5, 16))); 219 ) 220 DEF_BENCH( 221 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 222 SkRTree::Create(5, 16, 1, false))); 223 ) 224 DEF_BENCH( 225 return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true, 226 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 227 ) 228 DEF_BENCH( 229 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 230 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 231 ) 232 233 DEF_BENCH( 234 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, 235 SkRTree::Create(5, 16))); 236 ) 237 DEF_BENCH( 238 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, 239 SkRTree::Create(5, 16))); 240 ) 241 DEF_BENCH( 242 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true, 243 SkRTree::Create(5, 16, 1, false))); 244 ) 245 DEF_BENCH( 246 return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, 247 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 248 ) 249 DEF_BENCH( 250 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true, 251 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 252 ) 253 254 DEF_BENCH( 255 return SkNEW_ARGS(RTreeBuildBench, ("concentric", 256 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); 257 ) 258 DEF_BENCH( 259 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", 260 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false))); 261 ) 262 DEF_BENCH( 263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true, 264 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 265 ) 266 DEF_BENCH( 267 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true, 268 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 269 ) 270
