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 | 20 |
21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 21 typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int); |
22 | 22 |
23 // Time how long it takes to build an R-Tree either bulk-loaded or not | 23 // Time how long it takes to build an R-Tree either bulk-loaded or not |
24 class BBoxBuildBench : public SkBenchmark { | 24 class BBoxBuildBench : public SkBenchmark { |
25 public: | 25 public: |
26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, | 26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, |
27 SkBBoxHierarchy* tree) | 27 SkBBoxHierarchy* tree) |
28 : INHERITED(param) | 28 : INHERITED(param) |
29 , fTree(tree) | 29 , fTree(tree) |
30 , fProc(proc) | 30 , fProc(proc) |
31 , fBulkLoad(bulkLoad) { | 31 , fBulkLoad(bulkLoad) { |
32 fName.append("rtree_"); | 32 fName.append("rtree_"); |
33 fName.append(name); | 33 fName.append(name); |
34 fName.append("_build"); | 34 fName.append("_build"); |
35 if (fBulkLoad) { | 35 if (fBulkLoad) { |
36 fName.append("_bulk"); | 36 fName.append("_bulk"); |
37 } | 37 } |
38 fIsRendering = false; | 38 fIsRendering = false; |
39 } | 39 } |
40 virtual ~BBoxBuildBench() { | 40 virtual ~BBoxBuildBench() { |
41 fTree->unref(); | 41 fTree->unref(); |
42 } | 42 } |
43 protected: | 43 protected: |
44 virtual const char* onGetName() { | 44 virtual const char* onGetName() SK_OVERRIDE { |
45 return fName.c_str(); | 45 return fName.c_str(); |
46 } | 46 } |
47 virtual void onDraw(SkCanvas* canvas) { | 47 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
48 SkRandom rand; | 48 SkMWCRandom rand; |
49 for (int i = 0; i < SkBENCHLOOP(100); ++i) { | 49 for (int i = 0; i < SkBENCHLOOP(100); ++i) { |
50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
52 fBulkLoad); | 52 fBulkLoad); |
53 } | 53 } |
54 fTree->flushDeferredInserts(); | 54 fTree->flushDeferredInserts(); |
55 fTree->clear(); | 55 fTree->clear(); |
56 } | 56 } |
57 } | 57 } |
58 private: | 58 private: |
(...skipping 20 matching lines...) Expand all Loading... |
79 , fTree(tree) | 79 , fTree(tree) |
80 , fProc(proc) | 80 , fProc(proc) |
81 , fBulkLoad(bulkLoad) | 81 , fBulkLoad(bulkLoad) |
82 , fQuery(q) { | 82 , fQuery(q) { |
83 fName.append("rtree_"); | 83 fName.append("rtree_"); |
84 fName.append(name); | 84 fName.append(name); |
85 fName.append("_query"); | 85 fName.append("_query"); |
86 if (fBulkLoad) { | 86 if (fBulkLoad) { |
87 fName.append("_bulk"); | 87 fName.append("_bulk"); |
88 } | 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; | 89 fIsRendering = false; |
96 } | 90 } |
97 virtual ~BBoxQueryBench() { | 91 virtual ~BBoxQueryBench() { |
98 fTree->unref(); | 92 fTree->unref(); |
99 } | 93 } |
100 protected: | 94 protected: |
101 virtual const char* onGetName() { | 95 virtual const char* onGetName() SK_OVERRIDE { |
102 return fName.c_str(); | 96 return fName.c_str(); |
103 } | 97 } |
104 virtual void onDraw(SkCanvas* canvas) { | 98 virtual void onPreDraw() SK_OVERRIDE { |
105 SkRandom rand; | 99 SkMWCRandom rand; |
| 100 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { |
| 101 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, |
| 102 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); |
| 103 } |
| 104 fTree->flushDeferredInserts(); |
| 105 } |
| 106 |
| 107 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
| 108 SkMWCRandom rand; |
106 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { | 109 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { |
107 SkTDArray<void*> hits; | 110 SkTDArray<void*> hits; |
108 SkIRect query; | 111 SkIRect query; |
109 switch(fQuery) { | 112 switch(fQuery) { |
110 case kSmall_QueryType: | 113 case kSmall_QueryType: |
111 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 114 query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
112 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 115 query.fTop = rand.nextU() % GENERATE_EXTENTS; |
113 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | 116 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
114 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | 117 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
115 break; | 118 break; |
(...skipping 22 matching lines...) Expand all Loading... |
138 } | 141 } |
139 private: | 142 private: |
140 SkBBoxHierarchy* fTree; | 143 SkBBoxHierarchy* fTree; |
141 MakeRectProc fProc; | 144 MakeRectProc fProc; |
142 SkString fName; | 145 SkString fName; |
143 bool fBulkLoad; | 146 bool fBulkLoad; |
144 QueryType fQuery; | 147 QueryType fQuery; |
145 typedef SkBenchmark INHERITED; | 148 typedef SkBenchmark INHERITED; |
146 }; | 149 }; |
147 | 150 |
148 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) { | 151 static inline SkIRect make_simple_rect(SkMWCRandom&, int index, int numRects) { |
149 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; | 152 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; |
150 return out; | 153 return out; |
151 } | 154 } |
152 | 155 |
153 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { | 156 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index,
int numRects) { |
154 SkIRect out = {0, 0, index + 1, index + 1}; | 157 SkIRect out = {0, 0, index + 1, index + 1}; |
155 return out; | 158 return out; |
156 } | 159 } |
157 | 160 |
158 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int
numRects) { | 161 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index,
int numRects) { |
159 SkIRect out = {0, 0, numRects - index, numRects - index}; | 162 SkIRect out = {0, 0, numRects - index, numRects - index}; |
160 return out; | 163 return out; |
161 } | 164 } |
162 | 165 |
163 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects)
{ | 166 static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRect
s) { |
164 SkIRect out; | 167 SkIRect out; |
165 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 168 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
166 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 169 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
167 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); | 170 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); |
168 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); | 171 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); |
169 return out; | 172 return out; |
170 } | 173 } |
171 | 174 |
172 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
{ | 175 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRec
ts) { |
173 SkIRect out; | 176 SkIRect out; |
174 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 177 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
175 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 178 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
176 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
177 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
178 return out; | 181 return out; |
179 } | 182 } |
180 | 183 |
181 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects)
{ | 184 static inline SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect
s) { |
182 SkIRect out; | 185 SkIRect out; |
183 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
184 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
185 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); | 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); |
186 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); | 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); |
187 return out; | 190 return out; |
188 } | 191 } |
189 | 192 |
190 /////////////////////////////////////////////////////////////////////////////// | 193 /////////////////////////////////////////////////////////////////////////////// |
191 | 194 |
(...skipping 16 matching lines...) Expand all Loading... |
208 static inline SkBenchmark* Fact4(void* p) { | 211 static inline SkBenchmark* Fact4(void* p) { |
209 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, | 212 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, |
210 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 213 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
211 } | 214 } |
212 | 215 |
213 static BenchRegistry gReg0(Fact0); | 216 static BenchRegistry gReg0(Fact0); |
214 static BenchRegistry gReg1(Fact1); | 217 static BenchRegistry gReg1(Fact1); |
215 static BenchRegistry gReg2(Fact2); | 218 static BenchRegistry gReg2(Fact2); |
216 static BenchRegistry gReg3(Fact3); | 219 static BenchRegistry gReg3(Fact3); |
217 static BenchRegistry gReg4(Fact4); | 220 static BenchRegistry gReg4(Fact4); |
OLD | NEW |