commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2014 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
| 7 | |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 8 | #include "Benchmark.h" |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 9 | #include "SkCanvas.h" |
| 10 | #include "SkQuadTree.h" |
| 11 | #include "SkRandom.h" |
| 12 | #include "SkString.h" |
| 13 | |
| 14 | // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs: |
| 15 | static const int GENERATE_EXTENTS = 1000; |
| 16 | static const int NUM_BUILD_RECTS = 500; |
| 17 | static const int NUM_QUERY_RECTS = 5000; |
| 18 | static const int GRID_WIDTH = 100; |
| 19 | static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB( |
| 20 | -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS); |
| 21 | |
| 22 | typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
| 23 | |
| 24 | // Time how long it takes to build an QuadTree |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 25 | class QuadTreeBuildBench : public Benchmark { |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 26 | public: |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 27 | QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree) |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 28 | : fTree(tree) |
| 29 | , fProc(proc) { |
| 30 | fName.append("quadtree_"); |
| 31 | fName.append(name); |
| 32 | fName.append("_build"); |
| 33 | } |
| 34 | |
| 35 | virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 36 | return backend == kNonRendering_Backend; |
| 37 | } |
| 38 | |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 39 | virtual ~QuadTreeBuildBench() { |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 40 | fTree->unref(); |
| 41 | } |
| 42 | protected: |
| 43 | virtual const char* onGetName() SK_OVERRIDE { |
| 44 | return fName.c_str(); |
| 45 | } |
| 46 | virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
| 47 | SkRandom rand; |
| 48 | for (int i = 0; i < loops; ++i) { |
| 49 | for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
| 50 | fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS), |
| 51 | false); |
| 52 | } |
| 53 | fTree->clear(); |
| 54 | } |
| 55 | } |
| 56 | private: |
| 57 | SkBBoxHierarchy* fTree; |
| 58 | MakeRectProc fProc; |
| 59 | SkString fName; |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 60 | typedef Benchmark INHERITED; |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 61 | }; |
| 62 | |
| 63 | // Time how long it takes to perform queries on an QuadTree |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 64 | class QuadTreeQueryBench : public Benchmark { |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 65 | public: |
| 66 | enum QueryType { |
| 67 | kSmall_QueryType, // small queries |
| 68 | kLarge_QueryType, // large queries |
| 69 | kRandom_QueryType,// randomly sized queries |
| 70 | kFull_QueryType // queries that cover everything |
| 71 | }; |
| 72 | |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 73 | QuadTreeQueryBench(const char* name, MakeRectProc proc, |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 74 | QueryType q, SkBBoxHierarchy* tree) |
| 75 | : fTree(tree) |
| 76 | , fProc(proc) |
| 77 | , fQuery(q) { |
| 78 | fName.append("quadtree_"); |
| 79 | fName.append(name); |
| 80 | fName.append("_query"); |
| 81 | } |
| 82 | |
| 83 | virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { |
| 84 | return backend == kNonRendering_Backend; |
| 85 | } |
| 86 | |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 87 | virtual ~QuadTreeQueryBench() { |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 88 | fTree->unref(); |
| 89 | } |
| 90 | protected: |
| 91 | virtual const char* onGetName() SK_OVERRIDE { |
| 92 | return fName.c_str(); |
| 93 | } |
| 94 | virtual void onPreDraw() SK_OVERRIDE { |
| 95 | SkRandom rand; |
| 96 | for (int j = 0; j < NUM_QUERY_RECTS; ++j) { |
| 97 | fTree->insert(reinterpret_cast<void*>(j), |
| 98 | fProc(rand, j, NUM_QUERY_RECTS), |
| 99 | false); |
| 100 | } |
| 101 | fTree->flushDeferredInserts(); |
| 102 | } |
| 103 | |
| 104 | virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { |
| 105 | SkRandom rand; |
| 106 | for (int i = 0; i < loops; ++i) { |
| 107 | SkTDArray<void*> hits; |
| 108 | SkIRect query; |
| 109 | switch(fQuery) { |
| 110 | case kSmall_QueryType: |
| 111 | query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 112 | query.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 113 | query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
| 114 | query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
| 115 | break; |
| 116 | case kLarge_QueryType: |
| 117 | query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 118 | query.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 119 | query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); |
| 120 | query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); |
| 121 | break; |
| 122 | case kFull_QueryType: |
| 123 | query.fLeft = -GENERATE_EXTENTS; |
| 124 | query.fTop = -GENERATE_EXTENTS; |
| 125 | query.fRight = 2 * GENERATE_EXTENTS; |
| 126 | query.fBottom = 2 * GENERATE_EXTENTS; |
| 127 | break; |
| 128 | default: // fallthrough |
| 129 | case kRandom_QueryType: |
| 130 | query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 131 | query.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 132 | query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); |
| 133 | query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); |
| 134 | break; |
| 135 | }; |
| 136 | fTree->search(query, &hits); |
| 137 | } |
| 138 | } |
| 139 | private: |
| 140 | SkBBoxHierarchy* fTree; |
| 141 | MakeRectProc fProc; |
| 142 | SkString fName; |
| 143 | QueryType fQuery; |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 144 | typedef Benchmark INHERITED; |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 145 | }; |
| 146 | |
| 147 | static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { |
| 148 | SkIRect out = {0, 0, index + 1, index + 1}; |
| 149 | return out; |
| 150 | } |
| 151 | |
| 152 | static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { |
| 153 | SkIRect out; |
| 154 | out.fLeft = index % GRID_WIDTH; |
| 155 | out.fTop = index / GRID_WIDTH; |
| 156 | out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 157 | out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 158 | return out; |
| 159 | } |
| 160 | |
| 161 | static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { |
| 162 | SkIRect out; |
| 163 | out.fLeft = index / GRID_WIDTH; |
| 164 | out.fTop = index % GRID_WIDTH; |
| 165 | out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 166 | out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 167 | return out; |
| 168 | } |
| 169 | |
| 170 | static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) { |
| 171 | SkIRect out; |
| 172 | out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
| 173 | out.fTop = rand.nextS() % GENERATE_EXTENTS; |
| 174 | out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 175 | out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 176 | return out; |
| 177 | } |
| 178 | |
| 179 | /////////////////////////////////////////////////////////////////////////////// |
| 180 | |
| 181 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 182 | return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 183 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 184 | ) |
| 185 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 186 | return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects, |
| 187 | QuadTreeQueryBench::kRandom_QueryType, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 188 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 189 | ) |
| 190 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 191 | return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 192 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 193 | ) |
| 194 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 195 | return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects, |
| 196 | QuadTreeQueryBench::kRandom_QueryType, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 197 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 198 | ) |
| 199 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 200 | return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 201 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 202 | ) |
| 203 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 204 | return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects, |
| 205 | QuadTreeQueryBench::kRandom_QueryType, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 206 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 207 | ) |
| 208 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 209 | return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 210 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 211 | ) |
| 212 | DEF_BENCH( |
commit-bot@chromium.org | b2db443 | 2014-04-23 21:03:45 +0000 | [diff] [blame] | 213 | return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing, |
| 214 | QuadTreeQueryBench::kRandom_QueryType, |
commit-bot@chromium.org | 949b998 | 2014-03-17 10:38:34 +0000 | [diff] [blame] | 215 | SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS)))); |
commit-bot@chromium.org | c22d139 | 2014-02-03 18:08:33 +0000 | [diff] [blame] | 216 | ) |