| 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 RTreeBuildBench : public SkBenchmark { |
| 25 public: | 25 public: |
| 26 BBoxBuildBench(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_"); |
| 32 fName.append(name); | 32 fName.append(name); |
| 33 fName.append("_build"); | 33 fName.append("_build"); |
| 34 if (fBulkLoad) { | 34 if (fBulkLoad) { |
| 35 fName.append("_bulk"); | 35 fName.append("_bulk"); |
| 36 } | 36 } |
| 37 } | 37 } |
| 38 | 38 |
| 39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 39 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 40 return backend == kNonRendering_Backend; | 40 return backend == kNonRendering_Backend; |
| 41 } | 41 } |
| 42 | 42 |
| 43 virtual ~BBoxBuildBench() { | 43 virtual ~RTreeBuildBench() { |
| 44 fTree->unref(); | 44 fTree->unref(); |
| 45 } | 45 } |
| 46 protected: | 46 protected: |
| 47 virtual const char* onGetName() SK_OVERRIDE { | 47 virtual const char* onGetName() SK_OVERRIDE { |
| 48 return fName.c_str(); | 48 return fName.c_str(); |
| 49 } | 49 } |
| 50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 50 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
| 51 SkRandom rand; | 51 SkRandom rand; |
| 52 for (int i = 0; i < loops; ++i) { | 52 for (int i = 0; i < loops; ++i) { |
| 53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 53 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
| 54 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 54 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
| 55 fBulkLoad); | 55 fBulkLoad); |
| 56 } | 56 } |
| 57 fTree->flushDeferredInserts(); | 57 fTree->flushDeferredInserts(); |
| 58 fTree->clear(); | 58 fTree->clear(); |
| 59 } | 59 } |
| 60 } | 60 } |
| 61 private: | 61 private: |
| 62 SkBBoxHierarchy* fTree; | 62 SkBBoxHierarchy* fTree; |
| 63 MakeRectProc fProc; | 63 MakeRectProc fProc; |
| 64 SkString fName; | 64 SkString fName; |
| 65 bool fBulkLoad; | 65 bool fBulkLoad; |
| 66 typedef SkBenchmark INHERITED; | 66 typedef SkBenchmark INHERITED; |
| 67 }; | 67 }; |
| 68 | 68 |
| 69 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not | 69 // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not |
| 70 class BBoxQueryBench : public SkBenchmark { | 70 class RTreeQueryBench : public SkBenchmark { |
| 71 public: | 71 public: |
| 72 enum QueryType { | 72 enum QueryType { |
| 73 kSmall_QueryType, // small queries | 73 kSmall_QueryType, // small queries |
| 74 kLarge_QueryType, // large queries | 74 kLarge_QueryType, // large queries |
| 75 kRandom_QueryType,// randomly sized queries | 75 kRandom_QueryType,// randomly sized queries |
| 76 kFull_QueryType // queries that cover everything | 76 kFull_QueryType // queries that cover everything |
| 77 }; | 77 }; |
| 78 | 78 |
| 79 BBoxQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, | 79 RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, |
| 80 QueryType q, SkBBoxHierarchy* tree) | 80 QueryType q, SkBBoxHierarchy* tree) |
| 81 : fTree(tree) | 81 : fTree(tree) |
| 82 , fProc(proc) | 82 , fProc(proc) |
| 83 , fBulkLoad(bulkLoad) | 83 , fBulkLoad(bulkLoad) |
| 84 , fQuery(q) { | 84 , fQuery(q) { |
| 85 fName.append("rtree_"); | 85 fName.append("rtree_"); |
| 86 fName.append(name); | 86 fName.append(name); |
| 87 fName.append("_query"); | 87 fName.append("_query"); |
| 88 if (fBulkLoad) { | 88 if (fBulkLoad) { |
| 89 fName.append("_bulk"); | 89 fName.append("_bulk"); |
| 90 } | 90 } |
| 91 } | 91 } |
| 92 | 92 |
| 93 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 93 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 94 return backend == kNonRendering_Backend; | 94 return backend == kNonRendering_Backend; |
| 95 } | 95 } |
| 96 | 96 |
| 97 virtual ~BBoxQueryBench() { | 97 virtual ~RTreeQueryBench() { |
| 98 fTree->unref(); | 98 fTree->unref(); |
| 99 } | 99 } |
| 100 protected: | 100 protected: |
| 101 virtual const char* onGetName() SK_OVERRIDE { | 101 virtual const char* onGetName() SK_OVERRIDE { |
| 102 return fName.c_str(); | 102 return fName.c_str(); |
| 103 } | 103 } |
| 104 virtual void onPreDraw() SK_OVERRIDE { | 104 virtual void onPreDraw() SK_OVERRIDE { |
| 105 SkRandom rand; | 105 SkRandom rand; |
| 106 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { | 106 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { |
| 107 fTree->insert(reinterpret_cast<void*>(j), | 107 fTree->insert(reinterpret_cast<void*>(j), |
| (...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 182 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
| 183 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 183 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
| 184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 184 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 185 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 185 out.fBottom = out.fTop + 1 + rand.nextU() % (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(BBoxBuildBench, ("XYordered", &make_XYordered_rects, false
, | 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( |
| 196 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, true, | 196 return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true
, |
| 197 SkRTree::Create(5, 16))); | 197 SkRTree::Create(5, 16))); |
| 198 ) | 198 ) |
| 199 DEF_BENCH( | 199 DEF_BENCH( |
| 200 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, | 200 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, |
| 201 SkRTree::Create(5, 16, 1, false))); | 201 SkRTree::Create(5, 16, 1, false))); |
| 202 ) | 202 ) |
| 203 DEF_BENCH( | 203 DEF_BENCH( |
| 204 return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, true, | 204 return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true
, |
| 205 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 205 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
| 206 ) | 206 ) |
| 207 DEF_BENCH( | 207 DEF_BENCH( |
| 208 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)XYordered", &make_XYordered_re
cts, true, | 208 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_r
ects, true, |
| 209 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 209 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 210 ) | 210 ) |
| 211 | 211 |
| 212 DEF_BENCH( | 212 DEF_BENCH( |
| 213 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, false
, | 213 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, fals
e, |
| 214 SkRTree::Create(5, 16))); | 214 SkRTree::Create(5, 16))); |
| 215 ) | 215 ) |
| 216 DEF_BENCH( | 216 DEF_BENCH( |
| 217 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, true, | 217 return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true
, |
| 218 SkRTree::Create(5, 16))); | 218 SkRTree::Create(5, 16))); |
| 219 ) | 219 ) |
| 220 DEF_BENCH( | 220 DEF_BENCH( |
| 221 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, | 221 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, |
| 222 SkRTree::Create(5, 16, 1, false))); | 222 SkRTree::Create(5, 16, 1, false))); |
| 223 ) | 223 ) |
| 224 DEF_BENCH( | 224 DEF_BENCH( |
| 225 return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, true, | 225 return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true
, |
| 226 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 226 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
| 227 ) | 227 ) |
| 228 DEF_BENCH( | 228 DEF_BENCH( |
| 229 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)YXordered", &make_YXordered_re
cts, true, | 229 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_r
ects, true, |
| 230 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 230 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 231 ) | 231 ) |
| 232 | 232 |
| 233 DEF_BENCH( | 233 DEF_BENCH( |
| 234 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, false, | 234 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, |
| 235 SkRTree::Create(5, 16))); | 235 SkRTree::Create(5, 16))); |
| 236 ) | 236 ) |
| 237 DEF_BENCH( | 237 DEF_BENCH( |
| 238 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, true, | 238 return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, |
| 239 SkRTree::Create(5, 16))); | 239 SkRTree::Create(5, 16))); |
| 240 ) | 240 ) |
| 241 DEF_BENCH( | 241 DEF_BENCH( |
| 242 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)random", &make_random_rects, t
rue, | 242 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects,
true, |
| 243 SkRTree::Create(5, 16, 1, false))); | 243 SkRTree::Create(5, 16, 1, false))); |
| 244 ) | 244 ) |
| 245 DEF_BENCH( | 245 DEF_BENCH( |
| 246 return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, true, | 246 return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, |
| 247 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 247 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)
)); |
| 248 ) | 248 ) |
| 249 DEF_BENCH( | 249 DEF_BENCH( |
| 250 return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)random", &make_random_rects, t
rue, | 250 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects,
true, |
| 251 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 251 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 252 ) | 252 ) |
| 253 | 253 |
| 254 DEF_BENCH( | 254 DEF_BENCH( |
| 255 return SkNEW_ARGS(BBoxBuildBench, ("concentric", | 255 return SkNEW_ARGS(RTreeBuildBench, ("concentric", |
| 256 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); | 256 &make_concentric_rects_increasing, true, SkRTree::Create(5
, 16))); |
| 257 ) | 257 ) |
| 258 DEF_BENCH( | 258 DEF_BENCH( |
| 259 return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)concentric", | 259 return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", |
| 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(BBoxQueryBench, ("concentric", &make_concentric_rects_incr
easing, true, | 263 return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_inc
reasing, true, |
| 264 BBoxQueryBench::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(BBoxQueryBench, ("(unsorted)concentric", &make_concentric_
rects_increasing, true, | 267 return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric
_rects_increasing, true, |
| 268 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); | 268 RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16,
1, false))); |
| 269 ) | 269 ) |
| OLD | NEW |