RTreeBench.cpp revision f168b86d7fafc5c20c87bebc6fd393cb17e120ca
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: 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 RTreeBuildBench : public Benchmark { 25public: 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 } 46protected: 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 } 61private: 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 70class RTreeQueryBench : public Benchmark { 71public: 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 } 100protected: 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 SkIRect query; 119 switch(fQuery) { 120 case kSmall_QueryType: 121 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 122 query.fTop = rand.nextU() % 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.nextU() % GENERATE_EXTENTS; 128 query.fTop = rand.nextU() % 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.nextU() % GENERATE_EXTENTS; 141 query.fTop = rand.nextU() % GENERATE_EXTENTS; 142 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 143 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 144 break; 145 }; 146 fTree->search(query, &hits); 147 } 148 } 149private: 150 SkBBoxHierarchy* fTree; 151 MakeRectProc fProc; 152 SkString fName; 153 bool fBulkLoad; 154 QueryType fQuery; 155 typedef Benchmark INHERITED; 156}; 157 158static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { 159 SkIRect out = {0, 0, index + 1, index + 1}; 160 return out; 161} 162 163static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 164 SkIRect out; 165 out.fLeft = index % GRID_WIDTH; 166 out.fTop = index / GRID_WIDTH; 167 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 168 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 169 return out; 170} 171static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 172 SkIRect out; 173 out.fLeft = index / GRID_WIDTH; 174 out.fTop = index % GRID_WIDTH; 175 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 176 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 177 return out; 178} 179 180static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) { 181 SkIRect out; 182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; 183 out.fTop = rand.nextS() % GENERATE_EXTENTS; 184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 185 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 186 return out; 187} 188 189/////////////////////////////////////////////////////////////////////////////// 190 191DEF_BENCH( 192 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false, 193 SkRTree::Create(5, 16))); 194) 195DEF_BENCH( 196 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true, 197 SkRTree::Create(5, 16))); 198) 199DEF_BENCH( 200 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 201 SkRTree::Create(5, 16, 1, false))); 202) 203DEF_BENCH( 204 return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true, 205 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 206) 207DEF_BENCH( 208 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 209 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 210) 211 212DEF_BENCH( 213 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false, 214 SkRTree::Create(5, 16))); 215) 216DEF_BENCH( 217 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true, 218 SkRTree::Create(5, 16))); 219) 220DEF_BENCH( 221 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 222 SkRTree::Create(5, 16, 1, false))); 223) 224DEF_BENCH( 225 return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true, 226 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 227) 228DEF_BENCH( 229 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 230 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 231) 232 233DEF_BENCH( 234 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, 235 SkRTree::Create(5, 16))); 236) 237DEF_BENCH( 238 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, 239 SkRTree::Create(5, 16))); 240) 241DEF_BENCH( 242 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true, 243 SkRTree::Create(5, 16, 1, false))); 244) 245DEF_BENCH( 246 return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, 247 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 248) 249DEF_BENCH( 250 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true, 251 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 252) 253 254DEF_BENCH( 255 return SkNEW_ARGS(RTreeBuildBench, ("concentric", 256 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); 257) 258DEF_BENCH( 259 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", 260 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false))); 261) 262DEF_BENCH( 263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true, 264 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 265) 266DEF_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