• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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