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 NUM_QUERIES = 1000;
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(void * param,const char * name,MakeRectProc proc,bool bulkLoad,SkBBoxHierarchy * tree)26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
27 SkBBoxHierarchy* tree)
28 : INHERITED(param)
29 , fTree(tree)
30 , fProc(proc)
31 , fBulkLoad(bulkLoad) {
32 fName.append("rtree_");
33 fName.append(name);
34 fName.append("_build");
35 if (fBulkLoad) {
36 fName.append("_bulk");
37 }
38 fIsRendering = false;
39 }
~BBoxBuildBench()40 virtual ~BBoxBuildBench() {
41 fTree->unref();
42 }
43 protected:
onGetName()44 virtual const char* onGetName() {
45 return fName.c_str();
46 }
onDraw(SkCanvas * canvas)47 virtual void onDraw(SkCanvas* canvas) {
48 SkRandom rand;
49 for (int i = 0; i < SkBENCHLOOP(100); ++i) {
50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
52 fBulkLoad);
53 }
54 fTree->flushDeferredInserts();
55 fTree->clear();
56 }
57 }
58 private:
59 SkBBoxHierarchy* fTree;
60 MakeRectProc fProc;
61 SkString fName;
62 bool fBulkLoad;
63 typedef SkBenchmark INHERITED;
64 };
65
66 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
67 class BBoxQueryBench : public SkBenchmark {
68 public:
69 enum QueryType {
70 kSmall_QueryType, // small queries
71 kLarge_QueryType, // large queries
72 kRandom_QueryType,// randomly sized queries
73 kFull_QueryType // queries that cover everything
74 };
75
BBoxQueryBench(void * param,const char * name,MakeRectProc proc,bool bulkLoad,QueryType q,SkBBoxHierarchy * tree)76 BBoxQueryBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
77 QueryType q, SkBBoxHierarchy* tree)
78 : INHERITED(param)
79 , fTree(tree)
80 , fProc(proc)
81 , fBulkLoad(bulkLoad)
82 , fQuery(q) {
83 fName.append("rtree_");
84 fName.append(name);
85 fName.append("_query");
86 if (fBulkLoad) {
87 fName.append("_bulk");
88 }
89 SkRandom rand;
90 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) {
91 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j,
92 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad);
93 }
94 fTree->flushDeferredInserts();
95 fIsRendering = false;
96 }
~BBoxQueryBench()97 virtual ~BBoxQueryBench() {
98 fTree->unref();
99 }
100 protected:
onGetName()101 virtual const char* onGetName() {
102 return fName.c_str();
103 }
onDraw(SkCanvas * canvas)104 virtual void onDraw(SkCanvas* canvas) {
105 SkRandom rand;
106 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) {
107 SkTDArray<void*> hits;
108 SkIRect query;
109 switch(fQuery) {
110 case kSmall_QueryType:
111 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
112 query.fTop = rand.nextU() % GENERATE_EXTENTS;
113 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
114 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
115 break;
116 case kLarge_QueryType:
117 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
118 query.fTop = rand.nextU() % GENERATE_EXTENTS;
119 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
120 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
121 break;
122 case kFull_QueryType:
123 query.fLeft = -GENERATE_EXTENTS;
124 query.fTop = -GENERATE_EXTENTS;
125 query.fRight = 2 * GENERATE_EXTENTS;
126 query.fBottom = 2 * GENERATE_EXTENTS;
127 break;
128 default: // fallthrough
129 case kRandom_QueryType:
130 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
131 query.fTop = rand.nextU() % GENERATE_EXTENTS;
132 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
133 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
134 break;
135 };
136 fTree->search(query, &hits);
137 }
138 }
139 private:
140 SkBBoxHierarchy* fTree;
141 MakeRectProc fProc;
142 SkString fName;
143 bool fBulkLoad;
144 QueryType fQuery;
145 typedef SkBenchmark INHERITED;
146 };
147
make_simple_rect(SkRandom &,int index,int numRects)148 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) {
149 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS};
150 return out;
151 }
152
make_concentric_rects_increasing(SkRandom &,int index,int numRects)153 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
154 SkIRect out = {0, 0, index + 1, index + 1};
155 return out;
156 }
157
make_concentric_rects_decreasing(SkRandom &,int index,int numRects)158 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) {
159 SkIRect out = {0, 0, numRects - index, numRects - index};
160 return out;
161 }
162
make_point_rects(SkRandom & rand,int index,int numRects)163 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects) {
164 SkIRect out;
165 out.fLeft = rand.nextU() % GENERATE_EXTENTS;
166 out.fTop = rand.nextU() % GENERATE_EXTENTS;
167 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200);
168 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200);
169 return out;
170 }
171
make_random_rects(SkRandom & rand,int index,int numRects)172 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
173 SkIRect out;
174 out.fLeft = rand.nextS() % GENERATE_EXTENTS;
175 out.fTop = rand.nextS() % GENERATE_EXTENTS;
176 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
177 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
178 return out;
179 }
180
make_large_rects(SkRandom & rand,int index,int numRects)181 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects) {
182 SkIRect out;
183 out.fLeft = rand.nextU() % GENERATE_EXTENTS;
184 out.fTop = rand.nextU() % GENERATE_EXTENTS;
185 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3);
186 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3);
187 return out;
188 }
189
190 ///////////////////////////////////////////////////////////////////////////////
191
Fact0(void * p)192 static inline SkBenchmark* Fact0(void* p) {
193 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
194 SkRTree::Create(5, 16)));
195 }
Fact1(void * p)196 static inline SkBenchmark* Fact1(void* p) {
197 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
198 SkRTree::Create(5, 16)));
199 }
Fact2(void * p)200 static inline SkBenchmark* Fact2(void* p) {
201 return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
202 &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
203 }
Fact3(void * p)204 static inline SkBenchmark* Fact3(void* p) {
205 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
206 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
207 }
Fact4(void * p)208 static inline SkBenchmark* Fact4(void* p) {
209 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false,
210 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
211 }
212
213 static BenchRegistry gReg0(Fact0);
214 static BenchRegistry gReg1(Fact1);
215 static BenchRegistry gReg2(Fact2);
216 static BenchRegistry gReg3(Fact3);
217 static BenchRegistry gReg4(Fact4);
218