OLD | NEW |
1 | |
2 /* | 1 /* |
3 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
4 * | 3 * |
5 * 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 |
6 * found in the LICENSE file. | 5 * found in the LICENSE file. |
7 */ | 6 */ |
8 | 7 |
9 #include "Benchmark.h" | 8 #include "Benchmark.h" |
10 #include "SkCanvas.h" | 9 #include "SkCanvas.h" |
11 #include "SkRTree.h" | 10 #include "SkRTree.h" |
12 #include "SkRandom.h" | 11 #include "SkRandom.h" |
13 #include "SkString.h" | 12 #include "SkString.h" |
14 | 13 |
15 // 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: |
16 static const SkScalar GENERATE_EXTENTS = 1000.0f; | 15 static const SkScalar GENERATE_EXTENTS = 1000.0f; |
17 static const int NUM_BUILD_RECTS = 500; | 16 static const int NUM_BUILD_RECTS = 500; |
18 static const int NUM_QUERY_RECTS = 5000; | 17 static const int NUM_QUERY_RECTS = 5000; |
19 static const int GRID_WIDTH = 100; | 18 static const int GRID_WIDTH = 100; |
20 | 19 |
21 typedef SkRect (*MakeRectProc)(SkRandom&, int, int); | 20 typedef SkRect (*MakeRectProc)(SkRandom&, int, int); |
22 | 21 |
23 // Time how long it takes to build an R-Tree either bulk-loaded or not | 22 // Time how long it takes to build an R-Tree either bulk-loaded or not |
24 class RTreeBuildBench : public Benchmark { | 23 class RTreeBuildBench : public Benchmark { |
25 public: | 24 public: |
26 RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, | 25 RTreeBuildBench(const char* name, MakeRectProc proc, SkRTree* tree) |
27 SkRTree* tree) | |
28 : fTree(tree) | 26 : fTree(tree) |
29 , fProc(proc) | 27 , fProc(proc) { |
30 , fBulkLoad(bulkLoad) { | 28 fName.printf("rtree_%s_build", name); |
31 fName.append("rtree_"); | |
32 fName.append(name); | |
33 fName.append("_build"); | |
34 if (fBulkLoad) { | |
35 fName.append("_bulk"); | |
36 } | |
37 } | 29 } |
38 | 30 |
39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 31 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
40 return backend == kNonRendering_Backend; | 32 return backend == kNonRendering_Backend; |
41 } | 33 } |
42 | 34 |
43 virtual ~RTreeBuildBench() { | 35 virtual ~RTreeBuildBench() { |
44 fTree->unref(); | 36 fTree->unref(); |
45 } | 37 } |
46 protected: | 38 protected: |
47 virtual const char* onGetName() SK_OVERRIDE { | 39 virtual const char* onGetName() SK_OVERRIDE { |
48 return fName.c_str(); | 40 return fName.c_str(); |
49 } | 41 } |
50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 42 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
51 SkRandom rand; | 43 SkRandom rand; |
| 44 SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS); |
| 45 for (int i = 0; i < NUM_BUILD_RECTS; ++i) { |
| 46 rects[i] = fProc(rand, i, NUM_BUILD_RECTS); |
| 47 } |
| 48 |
52 for (int i = 0; i < loops; ++i) { | 49 for (int i = 0; i < loops; ++i) { |
53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 50 fTree->insert(&rects, NUM_BUILD_RECTS); |
54 fTree->insert(j, fProc(rand, j, NUM_BUILD_RECTS), fBulkLoad); | 51 SkASSERT(rects != NULL); // It'd break this bench if the tree took
ownership of rects. |
55 } | |
56 fTree->flushDeferredInserts(); | |
57 fTree->clear(); | 52 fTree->clear(); |
58 } | 53 } |
59 } | 54 } |
60 private: | 55 private: |
61 SkRTree* fTree; | 56 SkRTree* fTree; |
62 MakeRectProc fProc; | 57 MakeRectProc fProc; |
63 SkString fName; | 58 SkString fName; |
64 bool fBulkLoad; | |
65 typedef Benchmark INHERITED; | 59 typedef Benchmark INHERITED; |
66 }; | 60 }; |
67 | 61 |
68 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not | 62 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not |
69 class RTreeQueryBench : public Benchmark { | 63 class RTreeQueryBench : public Benchmark { |
70 public: | 64 public: |
71 enum QueryType { | 65 RTreeQueryBench(const char* name, MakeRectProc proc, SkRTree* tree) |
72 kSmall_QueryType, // small queries | |
73 kLarge_QueryType, // large queries | |
74 kRandom_QueryType,// randomly sized queries | |
75 kFull_QueryType // queries that cover everything | |
76 }; | |
77 | |
78 RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, | |
79 QueryType q, SkRTree* tree) | |
80 : fTree(tree) | 66 : fTree(tree) |
81 , fProc(proc) | 67 , fProc(proc) { |
82 , fBulkLoad(bulkLoad) | 68 fName.printf("rtree_%s_query", name); |
83 , fQuery(q) { | |
84 fName.append("rtree_"); | |
85 fName.append(name); | |
86 fName.append("_query"); | |
87 if (fBulkLoad) { | |
88 fName.append("_bulk"); | |
89 } | |
90 } | 69 } |
91 | 70 |
92 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 71 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
93 return backend == kNonRendering_Backend; | 72 return backend == kNonRendering_Backend; |
94 } | 73 } |
95 | 74 |
96 virtual ~RTreeQueryBench() { | 75 virtual ~RTreeQueryBench() { |
97 fTree->unref(); | 76 fTree->unref(); |
98 } | 77 } |
99 protected: | 78 protected: |
100 virtual const char* onGetName() SK_OVERRIDE { | 79 virtual const char* onGetName() SK_OVERRIDE { |
101 return fName.c_str(); | 80 return fName.c_str(); |
102 } | 81 } |
103 virtual void onPreDraw() SK_OVERRIDE { | 82 virtual void onPreDraw() SK_OVERRIDE { |
104 SkRandom rand; | 83 SkRandom rand; |
105 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { | 84 SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS); |
106 fTree->insert(j, fProc(rand, j, NUM_QUERY_RECTS), fBulkLoad); | 85 for (int i = 0; i < NUM_QUERY_RECTS; ++i) { |
| 86 rects[i] = fProc(rand, i, NUM_QUERY_RECTS); |
107 } | 87 } |
108 fTree->flushDeferredInserts(); | 88 fTree->insert(&rects, NUM_QUERY_RECTS); |
109 } | 89 } |
110 | 90 |
111 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 91 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
112 SkRandom rand; | 92 SkRandom rand; |
113 for (int i = 0; i < loops; ++i) { | 93 for (int i = 0; i < loops; ++i) { |
114 SkTDArray<unsigned> hits; | 94 SkTDArray<unsigned> hits; |
115 SkRect query; | 95 SkRect query; |
116 switch(fQuery) { | 96 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
117 case kSmall_QueryType: | 97 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
118 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); | 98 query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENT
S/2); |
119 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); | 99 query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENT
S/2); |
120 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | |
121 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | |
122 break; | |
123 case kLarge_QueryType: | |
124 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); | |
125 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); | |
126 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); | |
127 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); | |
128 break; | |
129 case kFull_QueryType: | |
130 query.fLeft = -GENERATE_EXTENTS; | |
131 query.fTop = -GENERATE_EXTENTS; | |
132 query.fRight = 2 * GENERATE_EXTENTS; | |
133 query.fBottom = 2 * GENERATE_EXTENTS; | |
134 break; | |
135 default: // fallthrough | |
136 case kRandom_QueryType: | |
137 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); | |
138 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); | |
139 query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERAT
E_EXTENTS/2); | |
140 query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERAT
E_EXTENTS/2); | |
141 break; | |
142 }; | |
143 fTree->search(query, &hits); | 100 fTree->search(query, &hits); |
144 } | 101 } |
145 } | 102 } |
146 private: | 103 private: |
147 SkBBoxHierarchy* fTree; | 104 SkBBoxHierarchy* fTree; |
148 MakeRectProc fProc; | 105 MakeRectProc fProc; |
149 SkString fName; | 106 SkString fName; |
150 bool fBulkLoad; | |
151 QueryType fQuery; | |
152 typedef Benchmark INHERITED; | 107 typedef Benchmark INHERITED; |
153 }; | 108 }; |
154 | 109 |
155 static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { | 110 static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { |
156 SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); | 111 SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); |
157 return out; | 112 return out; |
158 } | 113 } |
159 | 114 |
160 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRect
s) { | 115 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRect
s) { |
161 SkRect out; | 116 SkRect out; |
(...skipping 16 matching lines...) Expand all Loading... |
178 SkRect out; | 133 SkRect out; |
179 out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); | 134 out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
180 out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); | 135 out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
181 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); | 136 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
182 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); | 137 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
183 return out; | 138 return out; |
184 } | 139 } |
185 | 140 |
186 /////////////////////////////////////////////////////////////////////////////// | 141 /////////////////////////////////////////////////////////////////////////////// |
187 | 142 |
188 DEF_BENCH( | 143 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
189 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, fals
e, | 144 ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));) |
190 SkRTree::Create(5, 16))); | 145 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
191 ) | 146 ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, fal
se)));) |
192 DEF_BENCH( | 147 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
193 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true
, | 148 ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));) |
194 SkRTree::Create(5, 16))); | 149 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
195 ) | 150 ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, fal
se)));) |
196 DEF_BENCH( | 151 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
197 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, | 152 ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));) |
198 SkRTree::Create(5, 16, 1, false))); | 153 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
199 ) | 154 ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, fa
lse)));) |
200 DEF_BENCH( | 155 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
201 return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true
, | 156 ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Cr
eate(5, 16)));) |
202 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); | 157 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, |
203 ) | 158 ("concentric_unsorted", |
204 DEF_BENCH( | 159 &make_concentric_rects_increasing, |
205 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, | 160 SkRTree::Create(5, 16, 1, false)));) |
206 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | |
207 ) | |
208 | 161 |
209 DEF_BENCH( | 162 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
210 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, fals
e, | 163 ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));) |
211 SkRTree::Create(5, 16))); | 164 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
212 ) | 165 ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, fal
se)));) |
213 DEF_BENCH( | 166 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
214 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true
, | 167 ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));) |
215 SkRTree::Create(5, 16))); | 168 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
216 ) | 169 ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, fal
se)));) |
217 DEF_BENCH( | 170 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
218 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, | 171 ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));) |
219 SkRTree::Create(5, 16, 1, false))); | 172 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
220 ) | 173 ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, fa
lse)));) |
221 DEF_BENCH( | 174 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
222 return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true
, | 175 ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Cr
eate(5, 16)));) |
223 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); | 176 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, |
224 ) | 177 ("concentric_unsorted", |
225 DEF_BENCH( | 178 &make_concentric_rects_increasing, |
226 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, | 179 SkRTree::Create(5, 16, 1, false)));) |
227 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | |
228 ) | |
229 | |
230 DEF_BENCH( | |
231 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, | |
232 SkRTree::Create(5, 16))); | |
233 ) | |
234 DEF_BENCH( | |
235 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, | |
236 SkRTree::Create(5, 16))); | |
237 ) | |
238 DEF_BENCH( | |
239 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects,
true, | |
240 SkRTree::Create(5, 16, 1, false))); | |
241 ) | |
242 DEF_BENCH( | |
243 return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, | |
244 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); | |
245 ) | |
246 DEF_BENCH( | |
247 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects,
true, | |
248 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | |
249 ) | |
250 | |
251 DEF_BENCH( | |
252 return SkNEW_ARGS(RTreeBuildBench, ("concentric", | |
253 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); | |
254 ) | |
255 DEF_BENCH( | |
256 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", | |
257 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); | |
258 ) | |
259 DEF_BENCH( | |
260 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_inc
reasing, true, | |
261 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); | |
262 ) | |
263 DEF_BENCH( | |
264 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric
_rects_increasing, true, | |
265 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | |
266 ) | |
OLD | NEW |