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 "Benchmark.h" | 9 #include "Benchmark.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 SkScalar GENERATE_EXTENTS = 1000.0f; |
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 GRID_WIDTH = 100; | 19 static const int GRID_WIDTH = 100; |
20 | 20 |
21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 21 typedef SkRect (*MakeRectProc)(SkRandom&, 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 RTreeBuildBench : public Benchmark { | 24 class RTreeBuildBench : public Benchmark { |
25 public: | 25 public: |
26 RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, | 26 RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, |
27 SkBBoxHierarchy* tree) | 27 SkBBoxHierarchy* tree) |
28 : fTree(tree) | 28 : fTree(tree) |
29 , fProc(proc) | 29 , fProc(proc) |
30 , fBulkLoad(bulkLoad) { | 30 , fBulkLoad(bulkLoad) { |
31 fName.append("rtree_"); | 31 fName.append("rtree_"); |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
108 fProc(rand, j, NUM_QUERY_RECTS), | 108 fProc(rand, j, NUM_QUERY_RECTS), |
109 fBulkLoad); | 109 fBulkLoad); |
110 } | 110 } |
111 fTree->flushDeferredInserts(); | 111 fTree->flushDeferredInserts(); |
112 } | 112 } |
113 | 113 |
114 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 114 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
115 SkRandom rand; | 115 SkRandom rand; |
116 for (int i = 0; i < loops; ++i) { | 116 for (int i = 0; i < loops; ++i) { |
117 SkTDArray<void*> hits; | 117 SkTDArray<void*> hits; |
118 SkIRect query; | 118 SkRect query; |
119 switch(fQuery) { | 119 switch(fQuery) { |
120 case kSmall_QueryType: | 120 case kSmall_QueryType: |
121 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 121 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
122 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 122 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
123 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | 123 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
124 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | 124 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
125 break; | 125 break; |
126 case kLarge_QueryType: | 126 case kLarge_QueryType: |
127 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 127 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
128 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 128 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
129 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); | 129 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); |
130 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); | 130 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); |
131 break; | 131 break; |
132 case kFull_QueryType: | 132 case kFull_QueryType: |
133 query.fLeft = -GENERATE_EXTENTS; | 133 query.fLeft = -GENERATE_EXTENTS; |
134 query.fTop = -GENERATE_EXTENTS; | 134 query.fTop = -GENERATE_EXTENTS; |
135 query.fRight = 2 * GENERATE_EXTENTS; | 135 query.fRight = 2 * GENERATE_EXTENTS; |
136 query.fBottom = 2 * GENERATE_EXTENTS; | 136 query.fBottom = 2 * GENERATE_EXTENTS; |
137 break; | 137 break; |
138 default: // fallthrough | 138 default: // fallthrough |
139 case kRandom_QueryType: | 139 case kRandom_QueryType: |
140 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 140 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
141 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 141 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
142 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EX
TENTS / 2); | 142 query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERAT
E_EXTENTS/2); |
143 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EX
TENTS / 2); | 143 query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERAT
E_EXTENTS/2); |
144 break; | 144 break; |
145 }; | 145 }; |
146 fTree->search(query, &hits); | 146 fTree->search(query, &hits); |
147 } | 147 } |
148 } | 148 } |
149 private: | 149 private: |
150 SkBBoxHierarchy* fTree; | 150 SkBBoxHierarchy* fTree; |
151 MakeRectProc fProc; | 151 MakeRectProc fProc; |
152 SkString fName; | 152 SkString fName; |
153 bool fBulkLoad; | 153 bool fBulkLoad; |
154 QueryType fQuery; | 154 QueryType fQuery; |
155 typedef Benchmark INHERITED; | 155 typedef Benchmark INHERITED; |
156 }; | 156 }; |
157 | 157 |
158 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { | 158 static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { |
159 SkIRect out = {0, 0, index + 1, index + 1}; | 159 SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); |
160 return out; | 160 return out; |
161 } | 161 } |
162 | 162 |
163 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
ts) { | 163 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRect
s) { |
164 SkIRect out; | 164 SkRect out; |
165 out.fLeft = index % GRID_WIDTH; | 165 out.fLeft = SkIntToScalar(index % GRID_WIDTH); |
166 out.fTop = index / GRID_WIDTH; | 166 out.fTop = SkIntToScalar(index / GRID_WIDTH); |
167 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 167 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
168 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 168 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
169 return out; | 169 return out; |
170 } | 170 } |
171 static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRec
ts) { | 171 static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRect
s) { |
172 SkIRect out; | 172 SkRect out; |
173 out.fLeft = index / GRID_WIDTH; | 173 out.fLeft = SkIntToScalar(index / GRID_WIDTH); |
174 out.fTop = index % GRID_WIDTH; | 174 out.fTop = SkIntToScalar(index % GRID_WIDTH); |
175 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 175 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
176 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 176 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
177 return out; | 177 return out; |
178 } | 178 } |
179 | 179 |
180 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
{ | 180 static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects)
{ |
181 SkIRect out; | 181 SkRect out; |
182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 182 out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
183 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 183 out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 184 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
185 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 185 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
186 return out; | 186 return out; |
187 } | 187 } |
188 | 188 |
189 /////////////////////////////////////////////////////////////////////////////// | 189 /////////////////////////////////////////////////////////////////////////////// |
190 | 190 |
191 DEF_BENCH( | 191 DEF_BENCH( |
192 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, fals
e, | 192 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, fals
e, |
193 SkRTree::Create(5, 16))); | 193 SkRTree::Create(5, 16))); |
194 ) | 194 ) |
195 DEF_BENCH( | 195 DEF_BENCH( |
(...skipping 64 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
260 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); | 260 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); |
261 ) | 261 ) |
262 DEF_BENCH( | 262 DEF_BENCH( |
263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_inc
reasing, true, | 263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_inc
reasing, true, |
264 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); | 264 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
265 ) | 265 ) |
266 DEF_BENCH( | 266 DEF_BENCH( |
267 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric
_rects_increasing, true, | 267 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric
_rects_increasing, true, |
268 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 268 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
269 ) | 269 ) |
OLD | NEW |