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 NUM_QUERIES = 1000; | 19 static const int NUM_QUERIES = 1000; |
20 static const int GRID_WIDTH = 100; | 20 static const int GRID_WIDTH = 100; |
21 | 21 |
22 typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int); | 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
23 | 23 |
24 // Time how long it takes to build an R-Tree either bulk-loaded or not | 24 // Time how long it takes to build an R-Tree either bulk-loaded or not |
25 class BBoxBuildBench : public SkBenchmark { | 25 class BBoxBuildBench : public SkBenchmark { |
26 public: | 26 public: |
27 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, | 27 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, |
28 SkBBoxHierarchy* tree) | 28 SkBBoxHierarchy* tree) |
29 : INHERITED(param) | 29 : INHERITED(param) |
30 , fTree(tree) | 30 , fTree(tree) |
31 , fProc(proc) | 31 , fProc(proc) |
32 , fBulkLoad(bulkLoad) { | 32 , fBulkLoad(bulkLoad) { |
33 fName.append("rtree_"); | 33 fName.append("rtree_"); |
34 fName.append(name); | 34 fName.append(name); |
35 fName.append("_build"); | 35 fName.append("_build"); |
36 if (fBulkLoad) { | 36 if (fBulkLoad) { |
37 fName.append("_bulk"); | 37 fName.append("_bulk"); |
38 } | 38 } |
39 fIsRendering = false; | 39 fIsRendering = false; |
40 } | 40 } |
41 virtual ~BBoxBuildBench() { | 41 virtual ~BBoxBuildBench() { |
42 fTree->unref(); | 42 fTree->unref(); |
43 } | 43 } |
44 protected: | 44 protected: |
45 virtual const char* onGetName() SK_OVERRIDE { | 45 virtual const char* onGetName() SK_OVERRIDE { |
46 return fName.c_str(); | 46 return fName.c_str(); |
47 } | 47 } |
48 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { | 48 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
49 SkMWCRandom rand; | 49 SkRandom rand; |
50 for (int i = 0; i < SkBENCHLOOP(100); ++i) { | 50 for (int i = 0; i < SkBENCHLOOP(100); ++i) { |
51 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 51 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
52 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 52 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
53 fBulkLoad); | 53 fBulkLoad); |
54 } | 54 } |
55 fTree->flushDeferredInserts(); | 55 fTree->flushDeferredInserts(); |
56 fTree->clear(); | 56 fTree->clear(); |
57 } | 57 } |
58 } | 58 } |
59 private: | 59 private: |
(...skipping 30 matching lines...) Expand all Loading... |
90 fIsRendering = false; | 90 fIsRendering = false; |
91 } | 91 } |
92 virtual ~BBoxQueryBench() { | 92 virtual ~BBoxQueryBench() { |
93 fTree->unref(); | 93 fTree->unref(); |
94 } | 94 } |
95 protected: | 95 protected: |
96 virtual const char* onGetName() SK_OVERRIDE { | 96 virtual const char* onGetName() SK_OVERRIDE { |
97 return fName.c_str(); | 97 return fName.c_str(); |
98 } | 98 } |
99 virtual void onPreDraw() SK_OVERRIDE { | 99 virtual void onPreDraw() SK_OVERRIDE { |
100 SkMWCRandom rand; | 100 SkRandom rand; |
101 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { | 101 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { |
102 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, | 102 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, |
103 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); | 103 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); |
104 } | 104 } |
105 fTree->flushDeferredInserts(); | 105 fTree->flushDeferredInserts(); |
106 } | 106 } |
107 | 107 |
108 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { | 108 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
109 SkMWCRandom rand; | 109 SkRandom rand; |
110 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { | 110 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { |
111 SkTDArray<void*> hits; | 111 SkTDArray<void*> hits; |
112 SkIRect query; | 112 SkIRect query; |
113 switch(fQuery) { | 113 switch(fQuery) { |
114 case kSmall_QueryType: | 114 case kSmall_QueryType: |
115 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 115 query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
116 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 116 query.fTop = rand.nextU() % GENERATE_EXTENTS; |
117 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | 117 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
118 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | 118 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
119 break; | 119 break; |
(...skipping 22 matching lines...) Expand all Loading... |
142 } | 142 } |
143 private: | 143 private: |
144 SkBBoxHierarchy* fTree; | 144 SkBBoxHierarchy* fTree; |
145 MakeRectProc fProc; | 145 MakeRectProc fProc; |
146 SkString fName; | 146 SkString fName; |
147 bool fBulkLoad; | 147 bool fBulkLoad; |
148 QueryType fQuery; | 148 QueryType fQuery; |
149 typedef SkBenchmark INHERITED; | 149 typedef SkBenchmark INHERITED; |
150 }; | 150 }; |
151 | 151 |
152 static inline SkIRect make_simple_rect(SkMWCRandom&, int index, int numRects) { | 152 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) { |
153 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; | 153 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; |
154 return out; | 154 return out; |
155 } | 155 } |
156 | 156 |
157 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index,
int numRects) { | 157 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { |
158 SkIRect out = {0, 0, index + 1, index + 1}; | 158 SkIRect out = {0, 0, index + 1, index + 1}; |
159 return out; | 159 return out; |
160 } | 160 } |
161 | 161 |
162 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index,
int numRects) { | 162 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int
numRects) { |
163 SkIRect out = {0, 0, numRects - index, numRects - index}; | 163 SkIRect out = {0, 0, numRects - index, numRects - index}; |
164 return out; | 164 return out; |
165 } | 165 } |
166 | 166 |
167 static inline SkIRect make_XYordered_rects(SkMWCRandom& rand, int index, int num
Rects) { | 167 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
ts) { |
168 SkIRect out; | 168 SkIRect out; |
169 out.fLeft = index % GRID_WIDTH; | 169 out.fLeft = index % GRID_WIDTH; |
170 out.fTop = index / GRID_WIDTH; | 170 out.fTop = index / GRID_WIDTH; |
171 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 171 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
172 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 172 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
173 return out; | 173 return out; |
174 } | 174 } |
175 static inline SkIRect make_YXordered_rects(SkMWCRandom& rand, int index, int num
Rects) { | 175 static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRec
ts) { |
176 SkIRect out; | 176 SkIRect out; |
177 out.fLeft = index / GRID_WIDTH; | 177 out.fLeft = index / GRID_WIDTH; |
178 out.fTop = index % GRID_WIDTH; | 178 out.fTop = index % GRID_WIDTH; |
179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
181 return out; | 181 return out; |
182 } | 182 } |
183 | 183 |
184 static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRect
s) { | 184 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects)
{ |
185 SkIRect out; | 185 SkIRect out; |
186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
187 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); | 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); |
189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); | 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); |
190 return out; | 190 return out; |
191 } | 191 } |
192 | 192 |
193 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRec
ts) { | 193 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
{ |
194 SkIRect out; | 194 SkIRect out; |
195 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 195 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
196 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 196 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
197 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 197 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
198 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 198 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
199 return out; | 199 return out; |
200 } | 200 } |
201 | 201 |
202 static inline SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect
s) { | 202 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects)
{ |
203 SkIRect out; | 203 SkIRect out; |
204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
205 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 205 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); | 206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); |
207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); | 207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); |
208 return out; | 208 return out; |
209 } | 209 } |
210 | 210 |
211 /////////////////////////////////////////////////////////////////////////////// | 211 /////////////////////////////////////////////////////////////////////////////// |
212 | 212 |
(...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
302 static BenchRegistry gReg9(Fact9); | 302 static BenchRegistry gReg9(Fact9); |
303 static BenchRegistry gReg8(Fact8); | 303 static BenchRegistry gReg8(Fact8); |
304 static BenchRegistry gReg7(Fact7); | 304 static BenchRegistry gReg7(Fact7); |
305 static BenchRegistry gReg6(Fact6); | 305 static BenchRegistry gReg6(Fact6); |
306 static BenchRegistry gReg5(Fact5); | 306 static BenchRegistry gReg5(Fact5); |
307 static BenchRegistry gReg4(Fact4); | 307 static BenchRegistry gReg4(Fact4); |
308 static BenchRegistry gReg3(Fact3); | 308 static BenchRegistry gReg3(Fact3); |
309 static BenchRegistry gReg2(Fact2); | 309 static BenchRegistry gReg2(Fact2); |
310 static BenchRegistry gReg1(Fact1); | 310 static BenchRegistry gReg1(Fact1); |
311 static BenchRegistry gReg0(Fact0); | 311 static BenchRegistry gReg0(Fact0); |
OLD | NEW |