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: 15static const int GENERATE_EXTENTS = 1000; 16static const int NUM_BUILD_RECTS = 500; 17static const int NUM_QUERY_RECTS = 5000; 18static const int GRID_WIDTH = 100; 19static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( 20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS); 21 22typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); 23 24// Time how long it takes to build an QuadTree 25class QuadTreeBuildBench : public Benchmark { 26public: 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 } 42protected: 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 } 56private: 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 64class QuadTreeQueryBench : public Benchmark { 65public: 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 } 90protected: 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 } 139private: 140 SkBBoxHierarchy* fTree; 141 MakeRectProc fProc; 142 SkString fName; 143 QueryType fQuery; 144 typedef Benchmark INHERITED; 145}; 146 147static 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 152static 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 161static 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 170static 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 181DEF_BENCH( 182 return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects, 183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 184) 185DEF_BENCH( 186 return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects, 187 QuadTreeQueryBench::kRandom_QueryType, 188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 189) 190DEF_BENCH( 191 return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects, 192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 193) 194DEF_BENCH( 195 return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects, 196 QuadTreeQueryBench::kRandom_QueryType, 197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 198) 199DEF_BENCH( 200 return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects, 201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 202) 203DEF_BENCH( 204 return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects, 205 QuadTreeQueryBench::kRandom_QueryType, 206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 207) 208DEF_BENCH( 209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing, 210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 211) 212DEF_BENCH( 213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing, 214 QuadTreeQueryBench::kRandom_QueryType, 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); 216) 217