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