| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2014 Google Inc. | 2 * Copyright 2014 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #include "SkBenchmark.h" | 8 #include "SkBenchmark.h" |
| 9 #include "SkCanvas.h" | 9 #include "SkCanvas.h" |
| 10 #include "SkQuadTree.h" | 10 #include "SkQuadTree.h" |
| 11 #include "SkRandom.h" | 11 #include "SkRandom.h" |
| 12 #include "SkString.h" | 12 #include "SkString.h" |
| 13 | 13 |
| 14 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: | 14 // confine rectangles to a smallish area, so queries generally hit something, an
d overlap occurs: |
| 15 static const int GENERATE_EXTENTS = 1000; | 15 static const int GENERATE_EXTENTS = 1000; |
| 16 static const int NUM_BUILD_RECTS = 500; | 16 static const int NUM_BUILD_RECTS = 500; |
| 17 static const int NUM_QUERY_RECTS = 5000; | 17 static const int NUM_QUERY_RECTS = 5000; |
| 18 static const int GRID_WIDTH = 100; | 18 static const int GRID_WIDTH = 100; |
| 19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( | 19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( |
| 20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXT
ENTS); | 20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXT
ENTS); |
| 21 | 21 |
| 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
| 23 | 23 |
| 24 // Time how long it takes to build an QuadTree | 24 // Time how long it takes to build an QuadTree |
| 25 class BBoxBuildBench : public SkBenchmark { | 25 class QuadTreeBuildBench : public SkBenchmark { |
| 26 public: | 26 public: |
| 27 BBoxBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree) | 27 QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tre
e) |
| 28 : fTree(tree) | 28 : fTree(tree) |
| 29 , fProc(proc) { | 29 , fProc(proc) { |
| 30 fName.append("quadtree_"); | 30 fName.append("quadtree_"); |
| 31 fName.append(name); | 31 fName.append(name); |
| 32 fName.append("_build"); | 32 fName.append("_build"); |
| 33 } | 33 } |
| 34 | 34 |
| 35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 36 return backend == kNonRendering_Backend; | 36 return backend == kNonRendering_Backend; |
| 37 } | 37 } |
| 38 | 38 |
| 39 virtual ~BBoxBuildBench() { | 39 virtual ~QuadTreeBuildBench() { |
| 40 fTree->unref(); | 40 fTree->unref(); |
| 41 } | 41 } |
| 42 protected: | 42 protected: |
| 43 virtual const char* onGetName() SK_OVERRIDE { | 43 virtual const char* onGetName() SK_OVERRIDE { |
| 44 return fName.c_str(); | 44 return fName.c_str(); |
| 45 } | 45 } |
| 46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { | 46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
| 47 SkRandom rand; | 47 SkRandom rand; |
| 48 for (int i = 0; i < loops; ++i) { | 48 for (int i = 0; i < loops; ++i) { |
| 49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
| 50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
| 51 false); | 51 false); |
| 52 } | 52 } |
| 53 fTree->clear(); | 53 fTree->clear(); |
| 54 } | 54 } |
| 55 } | 55 } |
| 56 private: | 56 private: |
| 57 SkBBoxHierarchy* fTree; | 57 SkBBoxHierarchy* fTree; |
| 58 MakeRectProc fProc; | 58 MakeRectProc fProc; |
| 59 SkString fName; | 59 SkString fName; |
| 60 typedef SkBenchmark INHERITED; | 60 typedef SkBenchmark INHERITED; |
| 61 }; | 61 }; |
| 62 | 62 |
| 63 // Time how long it takes to perform queries on an QuadTree | 63 // Time how long it takes to perform queries on an QuadTree |
| 64 class BBoxQueryBench : public SkBenchmark { | 64 class QuadTreeQueryBench : public SkBenchmark { |
| 65 public: | 65 public: |
| 66 enum QueryType { | 66 enum QueryType { |
| 67 kSmall_QueryType, // small queries | 67 kSmall_QueryType, // small queries |
| 68 kLarge_QueryType, // large queries | 68 kLarge_QueryType, // large queries |
| 69 kRandom_QueryType,// randomly sized queries | 69 kRandom_QueryType,// randomly sized queries |
| 70 kFull_QueryType // queries that cover everything | 70 kFull_QueryType // queries that cover everything |
| 71 }; | 71 }; |
| 72 | 72 |
| 73 BBoxQueryBench(const char* name, MakeRectProc proc, | 73 QuadTreeQueryBench(const char* name, MakeRectProc proc, |
| 74 QueryType q, SkBBoxHierarchy* tree) | 74 QueryType q, SkBBoxHierarchy* tree) |
| 75 : fTree(tree) | 75 : fTree(tree) |
| 76 , fProc(proc) | 76 , fProc(proc) |
| 77 , fQuery(q) { | 77 , fQuery(q) { |
| 78 fName.append("quadtree_"); | 78 fName.append("quadtree_"); |
| 79 fName.append(name); | 79 fName.append(name); |
| 80 fName.append("_query"); | 80 fName.append("_query"); |
| 81 } | 81 } |
| 82 | 82 |
| 83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { | 83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 84 return backend == kNonRendering_Backend; | 84 return backend == kNonRendering_Backend; |
| 85 } | 85 } |
| 86 | 86 |
| 87 virtual ~BBoxQueryBench() { | 87 virtual ~QuadTreeQueryBench() { |
| 88 fTree->unref(); | 88 fTree->unref(); |
| 89 } | 89 } |
| 90 protected: | 90 protected: |
| 91 virtual const char* onGetName() SK_OVERRIDE { | 91 virtual const char* onGetName() SK_OVERRIDE { |
| 92 return fName.c_str(); | 92 return fName.c_str(); |
| 93 } | 93 } |
| 94 virtual void onPreDraw() SK_OVERRIDE { | 94 virtual void onPreDraw() SK_OVERRIDE { |
| 95 SkRandom rand; | 95 SkRandom rand; |
| 96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { | 96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) { |
| 97 fTree->insert(reinterpret_cast<void*>(j), | 97 fTree->insert(reinterpret_cast<void*>(j), |
| (...skipping 74 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 172 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 172 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
| 173 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 173 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
| 174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 176 return out; | 176 return out; |
| 177 } | 177 } |
| 178 | 178 |
| 179 /////////////////////////////////////////////////////////////////////////////// | 179 /////////////////////////////////////////////////////////////////////////////// |
| 180 | 180 |
| 181 DEF_BENCH( | 181 DEF_BENCH( |
| 182 return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, | 182 return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects, |
| 183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 184 ) | 184 ) |
| 185 DEF_BENCH( | 185 DEF_BENCH( |
| 186 return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, | 186 return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects, |
| 187 BBoxQueryBench::kRandom_QueryType, | 187 QuadTreeQueryBench::kRandom_QueryType, |
| 188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 189 ) | 189 ) |
| 190 DEF_BENCH( | 190 DEF_BENCH( |
| 191 return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, | 191 return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects, |
| 192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 193 ) | 193 ) |
| 194 DEF_BENCH( | 194 DEF_BENCH( |
| 195 return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, | 195 return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects, |
| 196 BBoxQueryBench::kRandom_QueryType, | 196 QuadTreeQueryBench::kRandom_QueryType, |
| 197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 198 ) | 198 ) |
| 199 DEF_BENCH( | 199 DEF_BENCH( |
| 200 return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, | 200 return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects, |
| 201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 202 ) | 202 ) |
| 203 DEF_BENCH( | 203 DEF_BENCH( |
| 204 return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, | 204 return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects, |
| 205 BBoxQueryBench::kRandom_QueryType, | 205 QuadTreeQueryBench::kRandom_QueryType, |
| 206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 207 ) | 207 ) |
| 208 DEF_BENCH( | 208 DEF_BENCH( |
| 209 return SkNEW_ARGS(BBoxBuildBench, ("concentric", &make_concentric_rects_incr
easing, | 209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_
increasing, |
| 210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 211 ) | 211 ) |
| 212 DEF_BENCH( | 212 DEF_BENCH( |
| 213 return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_incr
easing, | 213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_
increasing, |
| 214 BBoxQueryBench::kRandom_QueryType, | 214 QuadTreeQueryBench::kRandom_QueryType, |
| 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 216 ) | 216 ) |
| OLD | NEW |