OLD | NEW |
1 /* | 1 /* |
2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 Google Inc. |
3 * | 3 * |
4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
6 */ | 6 */ |
7 | 7 |
8 #include "SkBenchmark.h" | 8 #include "SkBenchmark.h" |
9 #include "SkCanvas.h" | 9 #include "SkCanvas.h" |
10 #include "SkQuadTree.h" | 10 #include "SkQuadTree.h" |
11 #include "SkRandom.h" | 11 #include "SkRandom.h" |
12 #include "SkString.h" | 12 #include "SkString.h" |
13 | 13 |
14 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: | 14 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: |
15 static const int GENERATE_EXTENTS = 1000; | 15 static const int GENERATE_EXTENTS = 1000; |
16 static const int NUM_BUILD_RECTS = 500; | 16 static const int NUM_BUILD_RECTS = 500; |
17 static const int NUM_QUERY_RECTS = 5000; | 17 static const int NUM_QUERY_RECTS = 5000; |
18 static const int GRID_WIDTH = 100; | 18 static const int GRID_WIDTH = 100; |
19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( | 19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( |
20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXT
ENTS); | 20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXT
ENTS); |
21 | 21 |
22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
23 | 23 |
24 // Time how long it takes to build an QuadTree | 24 // Time how long it takes to build an QuadTree |
25 class BBoxBuildBench : public SkBenchmark { | 25 class QuadTreeBuildBench : public SkBenchmark { |
26 public: | 26 public: |
27 BBoxBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree) | 27 QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tre
e) |
28 : fTree(tree) | 28 : fTree(tree) |
29 , fProc(proc) { | 29 , fProc(proc) { |
30 fName.append("quadtree_"); | 30 fName.append("quadtree_"); |
31 fName.append(name); | 31 fName.append(name); |
32 fName.append("_build"); | 32 fName.append("_build"); |
33 } | 33 } |
34 | 34 |
35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
36 return backend == kNonRendering_Backend; | 36 return backend == kNonRendering_Backend; |
37 } | 37 } |
38 | 38 |
39 virtual ~BBoxBuildBench() { | 39 virtual ~QuadTreeBuildBench() { |
40 fTree->unref(); | 40 fTree->unref(); |
41 } | 41 } |
42 protected: | 42 protected: |
43 virtual const char* onGetName() SK_OVERRIDE { | 43 virtual const char* onGetName() SK_OVERRIDE { |
44 return fName.c_str(); | 44 return fName.c_str(); |
45 } | 45 } |
46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
47 SkRandom rand; | 47 SkRandom rand; |
48 for (int i = 0; i < loops; ++i) { | 48 for (int i = 0; i < loops; ++i) { |
49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
51 false); | 51 false); |
52 } | 52 } |
53 fTree->clear(); | 53 fTree->clear(); |
54 } | 54 } |
55 } | 55 } |
56 private: | 56 private: |
57 SkBBoxHierarchy* fTree; | 57 SkBBoxHierarchy* fTree; |
58 MakeRectProc fProc; | 58 MakeRectProc fProc; |
59 SkString fName; | 59 SkString fName; |
60 typedef SkBenchmark INHERITED; | 60 typedef SkBenchmark INHERITED; |
61 }; | 61 }; |
62 | 62 |
63 // Time how long it takes to perform queries on an QuadTree | 63 // Time how long it takes to perform queries on an QuadTree |
64 class BBoxQueryBench : public SkBenchmark { | 64 class QuadTreeQueryBench : public SkBenchmark { |
65 public: | 65 public: |
66 enum QueryType { | 66 enum QueryType { |
67 kSmall_QueryType, // small queries | 67 kSmall_QueryType, // small queries |
68 kLarge_QueryType, // large queries | 68 kLarge_QueryType, // large queries |
69 kRandom_QueryType,// randomly sized queries | 69 kRandom_QueryType,// randomly sized queries |
70 kFull_QueryType // queries that cover everything | 70 kFull_QueryType // queries that cover everything |
71 }; | 71 }; |
72 | 72 |
73 BBoxQueryBench(const char* name, MakeRectProc proc, | 73 QuadTreeQueryBench(const char* name, MakeRectProc proc, |
74 QueryType q, SkBBoxHierarchy* tree) | 74 QueryType q, SkBBoxHierarchy* tree) |
75 : fTree(tree) | 75 : fTree(tree) |
76 , fProc(proc) | 76 , fProc(proc) |
77 , fQuery(q) { | 77 , fQuery(q) { |
78 fName.append("quadtree_"); | 78 fName.append("quadtree_"); |
79 fName.append(name); | 79 fName.append(name); |
80 fName.append("_query"); | 80 fName.append("_query"); |
81 } | 81 } |
82 | 82 |
83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
84 return backend == kNonRendering_Backend; | 84 return backend == kNonRendering_Backend; |
85 } | 85 } |
86 | 86 |
87 virtual ~BBoxQueryBench() { | 87 virtual ~QuadTreeQueryBench() { |
88 fTree->unref(); | 88 fTree->unref(); |
89 } | 89 } |
90 protected: | 90 protected: |
91 virtual const char* onGetName() SK_OVERRIDE { | 91 virtual const char* onGetName() SK_OVERRIDE { |
92 return fName.c_str(); | 92 return fName.c_str(); |
93 } | 93 } |
94 virtual void onPreDraw() SK_OVERRIDE { | 94 virtual void onPreDraw() SK_OVERRIDE { |
95 SkRandom rand; | 95 SkRandom rand; |
96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { | 96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { |
97 fTree->insert(reinterpret_cast<void*>(j), | 97 fTree->insert(reinterpret_cast<void*>(j), |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
172 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 172 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
173 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 173 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
176 return out; | 176 return out; |
177 } | 177 } |
178 | 178 |
179 /////////////////////////////////////////////////////////////////////////////// | 179 /////////////////////////////////////////////////////////////////////////////// |
180 | 180 |
181 DEF_BENCH( | 181 DEF_BENCH( |
182 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, | 182 return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects, |
183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
184 ) | 184 ) |
185 DEF_BENCH( | 185 DEF_BENCH( |
186 return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, | 186 return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects, |
187 BBoxQueryBench::kRandom_QueryType, | 187 QuadTreeQueryBench::kRandom_QueryType, |
188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
189 ) | 189 ) |
190 DEF_BENCH( | 190 DEF_BENCH( |
191 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, | 191 return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects, |
192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
193 ) | 193 ) |
194 DEF_BENCH( | 194 DEF_BENCH( |
195 return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, | 195 return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects, |
196 BBoxQueryBench::kRandom_QueryType, | 196 QuadTreeQueryBench::kRandom_QueryType, |
197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
198 ) | 198 ) |
199 DEF_BENCH( | 199 DEF_BENCH( |
200 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, | 200 return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects, |
201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
202 ) | 202 ) |
203 DEF_BENCH( | 203 DEF_BENCH( |
204 return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, | 204 return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects, |
205 BBoxQueryBench::kRandom_QueryType, | 205 QuadTreeQueryBench::kRandom_QueryType, |
206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
207 ) | 207 ) |
208 DEF_BENCH( | 208 DEF_BENCH( |
209 return SkNEW_ARGS(BBoxBuildBench, ("concentric", &make_concentric_rects_incr
easing, | 209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_
increasing, |
210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
211 ) | 211 ) |
212 DEF_BENCH( | 212 DEF_BENCH( |
213 return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_incr
easing, | 213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_
increasing, |
214 BBoxQueryBench::kRandom_QueryType, | 214 QuadTreeQueryBench::kRandom_QueryType, |
215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
216 ) | 216 ) |
OLD | NEW |