1 /* 2 * Copyright 2014 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #include "Benchmark.h" 9 #include "SkCanvas.h" 10 #include "SkQuadTree.h" 11 #include "SkRandom.h" 12 #include "SkString.h" 13 14 // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs: 15 static const int GENERATE_EXTENTS = 1000; 16 static const int NUM_BUILD_RECTS = 500; 17 static const int NUM_QUERY_RECTS = 5000; 18 static const int GRID_WIDTH = 100; 19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( 20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS); 21 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); 23 24 // Time how long it takes to build an QuadTree 25 class QuadTreeBuildBench : public Benchmark { 26 public: 27 QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree) 28 : fTree(tree) 29 , fProc(proc) { 30 fName.append("quadtree_"); 31 fName.append(name); 32 fName.append("_build"); 33 } 34 35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 36 return backend == kNonRendering_Backend; 37 } 38 39 virtual ~QuadTreeBuildBench() { 40 fTree->unref(); 41 } 42 protected: 43 virtual const char* onGetName() SK_OVERRIDE { 44 return fName.c_str(); 45 } 46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 47 SkRandom rand; 48 for (int i = 0; i < loops; ++i) { 49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { 50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS), 51 false); 52 } 53 fTree->clear(); 54 } 55 } 56 private: 57 SkBBoxHierarchy* fTree; 58 MakeRectProc fProc; 59 SkString fName; 60 typedef Benchmark INHERITED; 61 }; 62 63 // Time how long it takes to perform queries on an QuadTree 64 class QuadTreeQueryBench : public Benchmark { 65 public: 66 enum QueryType { 67 kSmall_QueryType, // small queries 68 kLarge_QueryType, // large queries 69 kRandom_QueryType,// randomly sized queries 70 kFull_QueryType // queries that cover everything 71 }; 72 73 QuadTreeQueryBench(const char* name, MakeRectProc proc, 74 QueryType q, SkBBoxHierarchy* tree) 75 : fTree(tree) 76 , fProc(proc) 77 , fQuery(q) { 78 fName.append("quadtree_"); 79 fName.append(name); 80 fName.append("_query"); 81 } 82 83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 84 return backend == kNonRendering_Backend; 85 } 86 87 virtual ~QuadTreeQueryBench() { 88 fTree->unref(); 89 } 90 protected: 91 virtual const char* onGetName() SK_OVERRIDE { 92 return fName.c_str(); 93 } 94 virtual void onPreDraw() SK_OVERRIDE { 95 SkRandom rand; 96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { 97 fTree->insert(reinterpret_cast<void*>(j), 98 fProc(rand, j, NUM_QUERY_RECTS), 99 false); 100 } 101 fTree->flushDeferredInserts(); 102 } 103 104 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 105 SkRandom rand; 106 for (int i = 0; i < loops; ++i) { 107 SkTDArray<void*> hits; 108 SkIRect query; 109 switch(fQuery) { 110 case kSmall_QueryType: 111 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 112 query.fTop = rand.nextU() % GENERATE_EXTENTS; 113 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); 114 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); 115 break; 116 case kLarge_QueryType: 117 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 118 query.fTop = rand.nextU() % GENERATE_EXTENTS; 119 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); 120 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); 121 break; 122 case kFull_QueryType: 123 query.fLeft = -GENERATE_EXTENTS; 124 query.fTop = -GENERATE_EXTENTS; 125 query.fRight = 2 * GENERATE_EXTENTS; 126 query.fBottom = 2 * GENERATE_EXTENTS; 127 break; 128 default: // fallthrough 129 case kRandom_QueryType: 130 query.fLeft = rand.nextU() % GENERATE_EXTENTS; 131 query.fTop = rand.nextU() % GENERATE_EXTENTS; 132 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 133 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 134 break; 135 }; 136 fTree->search(query, &hits); 137 } 138 } 139 private: 140 SkBBoxHierarchy* fTree; 141 MakeRectProc fProc; 142 SkString fName; 143 QueryType fQuery; 144 typedef Benchmark INHERITED; 145 }; 146 147 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { 148 SkIRect out = {0, 0, index + 1, index + 1}; 149 return out; 150 } 151 152 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 153 SkIRect out; 154 out.fLeft = index % GRID_WIDTH; 155 out.fTop = index / GRID_WIDTH; 156 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 157 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 158 return out; 159 } 160 161 static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 162 SkIRect out; 163 out.fLeft = index / GRID_WIDTH; 164 out.fTop = index % GRID_WIDTH; 165 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 166 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 167 return out; 168 } 169 170 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) { 171 SkIRect out; 172 out.fLeft = rand.nextS() % GENERATE_EXTENTS; 173 out.fTop = rand.nextS() % GENERATE_EXTENTS; 174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 176 return out; 177 } 178 179 /////////////////////////////////////////////////////////////////////////////// 180 181 DEF_BENCH( 182 return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects, 183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 184 ) 185 DEF_BENCH( 186 return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects, 187 QuadTreeQueryBench::kRandom_QueryType, 188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 189 ) 190 DEF_BENCH( 191 return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects, 192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 193 ) 194 DEF_BENCH( 195 return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects, 196 QuadTreeQueryBench::kRandom_QueryType, 197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 198 ) 199 DEF_BENCH( 200 return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects, 201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 202 ) 203 DEF_BENCH( 204 return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects, 205 QuadTreeQueryBench::kRandom_QueryType, 206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 207 ) 208 DEF_BENCH( 209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing, 210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 211 ) 212 DEF_BENCH( 213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing, 214 QuadTreeQueryBench::kRandom_QueryType, 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 216 ) 217
