| 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 "Benchmark.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 QuadTreeBuildBench : public SkBenchmark { | 25 class QuadTreeBuildBench : public Benchmark { |
| 26 public: | 26 public: |
| 27 QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tre
e) | 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 { |
| (...skipping 14 matching lines...) Expand all Loading... |
| 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 Benchmark 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 QuadTreeQueryBench : public SkBenchmark { | 64 class QuadTreeQueryBench : public Benchmark { |
| 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 QuadTreeQueryBench(const char* name, MakeRectProc proc, | 73 QuadTreeQueryBench(const char* name, MakeRectProc proc, |
| 74 QueryType q, SkBBoxHierarchy* tree) | 74 QueryType q, SkBBoxHierarchy* tree) |
| (...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 134 break; | 134 break; |
| 135 }; | 135 }; |
| 136 fTree->search(query, &hits); | 136 fTree->search(query, &hits); |
| 137 } | 137 } |
| 138 } | 138 } |
| 139 private: | 139 private: |
| 140 SkBBoxHierarchy* fTree; | 140 SkBBoxHierarchy* fTree; |
| 141 MakeRectProc fProc; | 141 MakeRectProc fProc; |
| 142 SkString fName; | 142 SkString fName; |
| 143 QueryType fQuery; | 143 QueryType fQuery; |
| 144 typedef SkBenchmark INHERITED; | 144 typedef Benchmark INHERITED; |
| 145 }; | 145 }; |
| 146 | 146 |
| 147 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { | 147 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { |
| 148 SkIRect out = {0, 0, index + 1, index + 1}; | 148 SkIRect out = {0, 0, index + 1, index + 1}; |
| 149 return out; | 149 return out; |
| 150 } | 150 } |
| 151 | 151 |
| 152 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
ts) { | 152 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
ts) { |
| 153 SkIRect out; | 153 SkIRect out; |
| 154 out.fLeft = index % GRID_WIDTH; | 154 out.fLeft = index % GRID_WIDTH; |
| (...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 207 ) | 207 ) |
| 208 DEF_BENCH( | 208 DEF_BENCH( |
| 209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_
increasing, | 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(QuadTreeQueryBench, ("concentric", &make_concentric_rects_
increasing, | 213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_
increasing, |
| 214 QuadTreeQueryBench::kRandom_QueryType, | 214 QuadTreeQueryBench::kRandom_QueryType, |
| 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); | 215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
| 216 ) | 216 ) |
| OLD | NEW |