OLD | NEW |
1 | 1 |
2 /* | 2 /* |
3 * Copyright 2012 Google Inc. | 3 * Copyright 2012 Google Inc. |
4 * | 4 * |
5 * Use of this source code is governed by a BSD-style license that can be | 5 * Use of this source code is governed by a BSD-style license that can be |
6 * found in the LICENSE file. | 6 * found in the LICENSE file. |
7 */ | 7 */ |
8 | 8 |
9 #include "SkBenchmark.h" | 9 #include "SkBenchmark.h" |
10 #include "SkCanvas.h" | 10 #include "SkCanvas.h" |
11 #include "SkRTree.h" | 11 #include "SkRTree.h" |
12 #include "SkRandom.h" | 12 #include "SkRandom.h" |
13 #include "SkString.h" | 13 #include "SkString.h" |
14 | 14 |
15 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: | 15 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: |
16 static const int GENERATE_EXTENTS = 1000; | 16 static const int GENERATE_EXTENTS = 1000; |
17 static const int NUM_BUILD_RECTS = 500; | 17 static const int NUM_BUILD_RECTS = 500; |
18 static const int NUM_QUERY_RECTS = 5000; | 18 static const int NUM_QUERY_RECTS = 5000; |
19 static const int GRID_WIDTH = 100; | 19 static const int GRID_WIDTH = 100; |
20 | 20 |
21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
22 | 22 |
23 // Time how long it takes to build an R-Tree either bulk-loaded or not | 23 // Time how long it takes to build an R-Tree either bulk-loaded or not |
24 class BBoxBuildBench : public SkBenchmark { | 24 class RTreeBuildBench : public SkBenchmark { |
25 public: | 25 public: |
26 BBoxBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, | 26 RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, |
27 SkBBoxHierarchy* tree) | 27 SkBBoxHierarchy* tree) |
28 : fTree(tree) | 28 : fTree(tree) |
29 , fProc(proc) | 29 , fProc(proc) |
30 , fBulkLoad(bulkLoad) { | 30 , fBulkLoad(bulkLoad) { |
31 fName.append("rtree_"); | 31 fName.append("rtree_"); |
32 fName.append(name); | 32 fName.append(name); |
33 fName.append("_build"); | 33 fName.append("_build"); |
34 if (fBulkLoad) { | 34 if (fBulkLoad) { |
35 fName.append("_bulk"); | 35 fName.append("_bulk"); |
36 } | 36 } |
37 } | 37 } |
38 | 38 |
39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
40 return backend == kNonRendering_Backend; | 40 return backend == kNonRendering_Backend; |
41 } | 41 } |
42 | 42 |
43 virtual ~BBoxBuildBench() { | 43 virtual ~RTreeBuildBench() { |
44 fTree->unref(); | 44 fTree->unref(); |
45 } | 45 } |
46 protected: | 46 protected: |
47 virtual const char* onGetName() SK_OVERRIDE { | 47 virtual const char* onGetName() SK_OVERRIDE { |
48 return fName.c_str(); | 48 return fName.c_str(); |
49 } | 49 } |
50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
51 SkRandom rand; | 51 SkRandom rand; |
52 for (int i = 0; i < loops; ++i) { | 52 for (int i = 0; i < loops; ++i) { |
53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
54 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 54 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
55 fBulkLoad); | 55 fBulkLoad); |
56 } | 56 } |
57 fTree->flushDeferredInserts(); | 57 fTree->flushDeferredInserts(); |
58 fTree->clear(); | 58 fTree->clear(); |
59 } | 59 } |
60 } | 60 } |
61 private: | 61 private: |
62 SkBBoxHierarchy* fTree; | 62 SkBBoxHierarchy* fTree; |
63 MakeRectProc fProc; | 63 MakeRectProc fProc; |
64 SkString fName; | 64 SkString fName; |
65 bool fBulkLoad; | 65 bool fBulkLoad; |
66 typedef SkBenchmark INHERITED; | 66 typedef SkBenchmark INHERITED; |
67 }; | 67 }; |
68 | 68 |
69 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not | 69 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not |
70 class BBoxQueryBench : public SkBenchmark { | 70 class RTreeQueryBench : public SkBenchmark { |
71 public: | 71 public: |
72 enum QueryType { | 72 enum QueryType { |
73 kSmall_QueryType, // small queries | 73 kSmall_QueryType, // small queries |
74 kLarge_QueryType, // large queries | 74 kLarge_QueryType, // large queries |
75 kRandom_QueryType,// randomly sized queries | 75 kRandom_QueryType,// randomly sized queries |
76 kFull_QueryType // queries that cover everything | 76 kFull_QueryType // queries that cover everything |
77 }; | 77 }; |
78 | 78 |
79 BBoxQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, | 79 RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, |
80 QueryType q, SkBBoxHierarchy* tree) | 80 QueryType q, SkBBoxHierarchy* tree) |
81 : fTree(tree) | 81 : fTree(tree) |
82 , fProc(proc) | 82 , fProc(proc) |
83 , fBulkLoad(bulkLoad) | 83 , fBulkLoad(bulkLoad) |
84 , fQuery(q) { | 84 , fQuery(q) { |
85 fName.append("rtree_"); | 85 fName.append("rtree_"); |
86 fName.append(name); | 86 fName.append(name); |
87 fName.append("_query"); | 87 fName.append("_query"); |
88 if (fBulkLoad) { | 88 if (fBulkLoad) { |
89 fName.append("_bulk"); | 89 fName.append("_bulk"); |
90 } | 90 } |
91 } | 91 } |
92 | 92 |
93 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 93 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
94 return backend == kNonRendering_Backend; | 94 return backend == kNonRendering_Backend; |
95 } | 95 } |
96 | 96 |
97 virtual ~BBoxQueryBench() { | 97 virtual ~RTreeQueryBench() { |
98 fTree->unref(); | 98 fTree->unref(); |
99 } | 99 } |
100 protected: | 100 protected: |
101 virtual const char* onGetName() SK_OVERRIDE { | 101 virtual const char* onGetName() SK_OVERRIDE { |
102 return fName.c_str(); | 102 return fName.c_str(); |
103 } | 103 } |
104 virtual void onPreDraw() SK_OVERRIDE { | 104 virtual void onPreDraw() SK_OVERRIDE { |
105 SkRandom rand; | 105 SkRandom rand; |
106 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { | 106 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { |
107 fTree->insert(reinterpret_cast<void*>(j), | 107 fTree->insert(reinterpret_cast<void*>(j), |
(...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
183 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 183 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
185 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 185 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
186 return out; | 186 return out; |
187 } | 187 } |
188 | 188 |
189 /////////////////////////////////////////////////////////////////////////////// | 189 /////////////////////////////////////////////////////////////////////////////// |
190 | 190 |
191 DEF_BENCH( | 191 DEF_BENCH( |
192 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, false
, | 192 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, fals
e, |
193 SkRTree::Create(5, 16))); | 193 SkRTree::Create(5, 16))); |
194 ) | 194 ) |
195 DEF_BENCH( | 195 DEF_BENCH( |
196 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, true, | 196 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true
, |
197 SkRTree::Create(5, 16))); | 197 SkRTree::Create(5, 16))); |
198 ) | 198 ) |
199 DEF_BENCH( | 199 DEF_BENCH( |
200 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, | 200 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, |
201 SkRTree::Create(5, 16, 1, false))); | 201 SkRTree::Create(5, 16, 1, false))); |
202 ) | 202 ) |
203 DEF_BENCH( | 203 DEF_BENCH( |
204 return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, true, | 204 return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true
, |
205 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 205 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
206 ) | 206 ) |
207 DEF_BENCH( | 207 DEF_BENCH( |
208 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, | 208 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, |
209 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 209 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
210 ) | 210 ) |
211 | 211 |
212 DEF_BENCH( | 212 DEF_BENCH( |
213 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, false
, | 213 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, fals
e, |
214 SkRTree::Create(5, 16))); | 214 SkRTree::Create(5, 16))); |
215 ) | 215 ) |
216 DEF_BENCH( | 216 DEF_BENCH( |
217 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, true, | 217 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true
, |
218 SkRTree::Create(5, 16))); | 218 SkRTree::Create(5, 16))); |
219 ) | 219 ) |
220 DEF_BENCH( | 220 DEF_BENCH( |
221 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, | 221 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, |
222 SkRTree::Create(5, 16, 1, false))); | 222 SkRTree::Create(5, 16, 1, false))); |
223 ) | 223 ) |
224 DEF_BENCH( | 224 DEF_BENCH( |
225 return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, true, | 225 return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true
, |
226 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 226 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
227 ) | 227 ) |
228 DEF_BENCH( | 228 DEF_BENCH( |
229 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, | 229 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, |
230 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 230 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
231 ) | 231 ) |
232 | 232 |
233 DEF_BENCH( | 233 DEF_BENCH( |
234 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, false, | 234 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, |
235 SkRTree::Create(5, 16))); | 235 SkRTree::Create(5, 16))); |
236 ) | 236 ) |
237 DEF_BENCH( | 237 DEF_BENCH( |
238 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, true, | 238 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, |
239 SkRTree::Create(5, 16))); | 239 SkRTree::Create(5, 16))); |
240 ) | 240 ) |
241 DEF_BENCH( | 241 DEF_BENCH( |
242 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)random", &make_random_rects, t
rue, | 242 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects,
true, |
243 SkRTree::Create(5, 16, 1, false))); | 243 SkRTree::Create(5, 16, 1, false))); |
244 ) | 244 ) |
245 DEF_BENCH( | 245 DEF_BENCH( |
246 return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, true, | 246 return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, |
247 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 247 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
248 ) | 248 ) |
249 DEF_BENCH( | 249 DEF_BENCH( |
250 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)random", &make_random_rects, t
rue, | 250 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects,
true, |
251 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 251 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
252 ) | 252 ) |
253 | 253 |
254 DEF_BENCH( | 254 DEF_BENCH( |
255 return SkNEW_ARGS(BBoxBuildBench, ("concentric", | 255 return SkNEW_ARGS(RTreeBuildBench, ("concentric", |
256 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); | 256 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); |
257 ) | 257 ) |
258 DEF_BENCH( | 258 DEF_BENCH( |
259 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)concentric", | 259 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", |
260 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); | 260 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); |
261 ) | 261 ) |
262 DEF_BENCH( | 262 DEF_BENCH( |
263 return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_incr
easing, true, | 263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_inc
reasing, true, |
264 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 264 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
265 ) | 265 ) |
266 DEF_BENCH( | 266 DEF_BENCH( |
267 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)concentric", &make_concentric_
rects_increasing, true, | 267 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric
_rects_increasing, true, |
268 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 268 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
269 ) | 269 ) |
OLD | NEW |