| OLD | NEW |
|---|
| (Empty) |
| 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, an
d 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_EXT
ENTS); | |
| 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* tre
e) | |
| 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_BUI
LD_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_EX
TENTS / 2); | |
| 133 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EX
TENTS / 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 numRec
ts) { | |
| 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 numRec
ts) { | |
| 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 ) | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 500373005:
Remove SkQuadTree. (Closed)
Base URL: https://skia.googlesource.com/skia.git@master