| 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 GRID_WIDTH = 100; | 19 static const int GRID_WIDTH = 100; |
| 20 | 20 |
| 21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 21 typedef SkIRect (*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 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(const char* name, MakeRectProc proc, bool bulkLoad, |
| 27 SkBBoxHierarchy* tree) | 27 SkBBoxHierarchy* tree) |
| 28 : INHERITED(param) | 28 : fTree(tree) |
| 29 , fTree(tree) | |
| 30 , fProc(proc) | 29 , fProc(proc) |
| 31 , fBulkLoad(bulkLoad) { | 30 , fBulkLoad(bulkLoad) { |
| 32 fName.append("rtree_"); | 31 fName.append("rtree_"); |
| 33 fName.append(name); | 32 fName.append(name); |
| 34 fName.append("_build"); | 33 fName.append("_build"); |
| 35 if (fBulkLoad) { | 34 if (fBulkLoad) { |
| 36 fName.append("_bulk"); | 35 fName.append("_bulk"); |
| 37 } | 36 } |
| 38 fIsRendering = false; | 37 fIsRendering = false; |
| 39 } | 38 } |
| (...skipping 26 matching lines...) Expand all Loading... |
| 66 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not | 65 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not |
| 67 class BBoxQueryBench : public SkBenchmark { | 66 class BBoxQueryBench : public SkBenchmark { |
| 68 public: | 67 public: |
| 69 enum QueryType { | 68 enum QueryType { |
| 70 kSmall_QueryType, // small queries | 69 kSmall_QueryType, // small queries |
| 71 kLarge_QueryType, // large queries | 70 kLarge_QueryType, // large queries |
| 72 kRandom_QueryType,// randomly sized queries | 71 kRandom_QueryType,// randomly sized queries |
| 73 kFull_QueryType // queries that cover everything | 72 kFull_QueryType // queries that cover everything |
| 74 }; | 73 }; |
| 75 | 74 |
| 76 BBoxQueryBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, | 75 BBoxQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, |
| 77 QueryType q, SkBBoxHierarchy* tree) | 76 QueryType q, SkBBoxHierarchy* tree) |
| 78 : INHERITED(param) | 77 : fTree(tree) |
| 79 , fTree(tree) | |
| 80 , fProc(proc) | 78 , fProc(proc) |
| 81 , fBulkLoad(bulkLoad) | 79 , fBulkLoad(bulkLoad) |
| 82 , fQuery(q) { | 80 , fQuery(q) { |
| 83 fName.append("rtree_"); | 81 fName.append("rtree_"); |
| 84 fName.append(name); | 82 fName.append(name); |
| 85 fName.append("_query"); | 83 fName.append("_query"); |
| 86 if (fBulkLoad) { | 84 if (fBulkLoad) { |
| 87 fName.append("_bulk"); | 85 fName.append("_bulk"); |
| 88 } | 86 } |
| 89 fIsRendering = false; | 87 fIsRendering = false; |
| (...skipping 113 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 203 SkIRect out; | 201 SkIRect out; |
| 204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 202 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 205 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 203 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); | 204 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); |
| 207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); | 205 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); |
| 208 return out; | 206 return out; |
| 209 } | 207 } |
| 210 | 208 |
| 211 /////////////////////////////////////////////////////////////////////////////// | 209 /////////////////////////////////////////////////////////////////////////////// |
| 212 | 210 |
| 213 static inline SkBenchmark* Fact0(void* p) { | 211 DEF_BENCH( |
| 214 return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, fa
lse, | 212 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, false
, |
| 215 SkRTree::Create(5, 16))); | 213 SkRTree::Create(5, 16))); |
| 216 } | 214 ) |
| 217 static inline SkBenchmark* Fact1(void* p) { | 215 DEF_BENCH( |
| 218 return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, tr
ue, | 216 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, true, |
| 219 SkRTree::Create(5, 16))); | 217 SkRTree::Create(5, 16))); |
| 220 } | 218 ) |
| 221 static inline SkBenchmark* Fact2(void* p) { | 219 DEF_BENCH( |
| 222 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)XYordered", &make_XYordered
_rects, true, | 220 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, |
| 223 SkRTree::Create(5, 16, 1, false))); | 221 SkRTree::Create(5, 16, 1, false))); |
| 224 } | 222 ) |
| 225 static inline SkBenchmark* Fact3(void* p) { | 223 DEF_BENCH( |
| 226 return SkNEW_ARGS(BBoxQueryBench, (p, "XYordered", &make_XYordered_rects, tr
ue, | 224 return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, true, |
| 227 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 225 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
| 228 } | 226 ) |
| 229 static inline SkBenchmark* Fact4(void* p) { | 227 DEF_BENCH( |
| 230 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered
_rects, true, | 228 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, |
| 231 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 229 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 232 } | 230 ) |
| 233 | 231 |
| 234 static inline SkBenchmark* Fact5(void* p) { | 232 DEF_BENCH( |
| 235 return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, fa
lse, | 233 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, false
, |
| 236 SkRTree::Create(5, 16))); | 234 SkRTree::Create(5, 16))); |
| 237 } | 235 ) |
| 238 static inline SkBenchmark* Fact6(void* p) { | 236 DEF_BENCH( |
| 239 return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, tr
ue, | 237 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, true, |
| 240 SkRTree::Create(5, 16))); | 238 SkRTree::Create(5, 16))); |
| 241 } | 239 ) |
| 242 static inline SkBenchmark* Fact7(void* p) { | 240 DEF_BENCH( |
| 243 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)YXordered", &make_YXordered
_rects, true, | 241 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, |
| 244 SkRTree::Create(5, 16, 1, false))); | 242 SkRTree::Create(5, 16, 1, false))); |
| 245 } | 243 ) |
| 246 static inline SkBenchmark* Fact8(void* p) { | 244 DEF_BENCH( |
| 247 return SkNEW_ARGS(BBoxQueryBench, (p, "YXordered", &make_YXordered_rects, tr
ue, | 245 return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, true, |
| 248 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 246 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
| 249 } | 247 ) |
| 250 static inline SkBenchmark* Fact9(void* p) { | 248 DEF_BENCH( |
| 251 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)YXordered", &make_YXordered
_rects, true, | 249 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, |
| 252 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 250 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 253 } | 251 ) |
| 254 | 252 |
| 255 static inline SkBenchmark* Fact10(void* p) { | 253 DEF_BENCH( |
| 256 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false, | 254 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, false, |
| 257 SkRTree::Create(5, 16))); | 255 SkRTree::Create(5, 16))); |
| 258 } | 256 ) |
| 259 static inline SkBenchmark* Fact11(void* p) { | 257 DEF_BENCH( |
| 260 return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true, | 258 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, true, |
| 261 SkRTree::Create(5, 16))); | 259 SkRTree::Create(5, 16))); |
| 262 } | 260 ) |
| 263 static inline SkBenchmark* Fact12(void* p) { | 261 DEF_BENCH( |
| 264 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)random", &make_random_rects
, true, | 262 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)random", &make_random_rects, t
rue, |
| 265 SkRTree::Create(5, 16, 1, false))); | 263 SkRTree::Create(5, 16, 1, false))); |
| 266 } | 264 ) |
| 267 static inline SkBenchmark* Fact13(void* p) { | 265 DEF_BENCH( |
| 268 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true, | 266 return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, true, |
| 269 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 267 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
| 270 } | 268 ) |
| 271 static inline SkBenchmark* Fact14(void* p) { | 269 DEF_BENCH( |
| 272 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)random", &make_random_rects
, true, | 270 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)random", &make_random_rects, t
rue, |
| 273 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 271 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 274 } | 272 ) |
| 275 | 273 |
| 276 static inline SkBenchmark* Fact15(void* p) { | 274 DEF_BENCH( |
| 277 return SkNEW_ARGS(BBoxBuildBench, (p, "concentric", | 275 return SkNEW_ARGS(BBoxBuildBench, ("concentric", |
| 278 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); | 276 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); |
| 279 } | 277 ) |
| 280 static inline SkBenchmark* Fact16(void* p) { | 278 DEF_BENCH( |
| 281 return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)concentric", | 279 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)concentric", |
| 282 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); | 280 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16, 1, false))); |
| 283 } | 281 ) |
| 284 static inline SkBenchmark* Fact17(void* p) { | 282 DEF_BENCH( |
| 285 return SkNEW_ARGS(BBoxQueryBench, (p, "concentric", &make_concentric_rects_i
ncreasing, true, | 283 return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_incr
easing, true, |
| 286 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 284 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
| 287 } | 285 ) |
| 288 static inline SkBenchmark* Fact18(void* p) { | 286 DEF_BENCH( |
| 289 return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)concentric", &make_concentr
ic_rects_increasing, true, | 287 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)concentric", &make_concentric_
rects_increasing, true, |
| 290 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 288 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 291 } | 289 ) |
| 292 | |
| 293 static BenchRegistry gReg18(Fact18); | |
| 294 static BenchRegistry gReg17(Fact17); | |
| 295 static BenchRegistry gReg16(Fact16); | |
| 296 static BenchRegistry gReg15(Fact15); | |
| 297 static BenchRegistry gReg14(Fact14); | |
| 298 static BenchRegistry gReg13(Fact13); | |
| 299 static BenchRegistry gReg12(Fact12); | |
| 300 static BenchRegistry gReg11(Fact11); | |
| 301 static BenchRegistry gReg10(Fact10); | |
| 302 static BenchRegistry gReg9(Fact9); | |
| 303 static BenchRegistry gReg8(Fact8); | |
| 304 static BenchRegistry gReg7(Fact7); | |
| 305 static BenchRegistry gReg6(Fact6); | |
| 306 static BenchRegistry gReg5(Fact5); | |
| 307 static BenchRegistry gReg4(Fact4); | |
| 308 static BenchRegistry gReg3(Fact3); | |
| 309 static BenchRegistry gReg2(Fact2); | |
| 310 static BenchRegistry gReg1(Fact1); | |
| 311 static BenchRegistry gReg0(Fact0); | |
| OLD | NEW |