| 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 NUM_QUERIES = 1000; | 19 static const int NUM_QUERIES = 1000; |
| 20 static const int GRID_WIDTH = 100; | 20 static const int GRID_WIDTH = 100; |
| 21 | 21 |
| 22 typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int); | 22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); |
| 23 | 23 |
| 24 // Time how long it takes to build an R-Tree either bulk-loaded or not | 24 // Time how long it takes to build an R-Tree either bulk-loaded or not |
| 25 class BBoxBuildBench : public SkBenchmark { | 25 class BBoxBuildBench : public SkBenchmark { |
| 26 public: | 26 public: |
| 27 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, | 27 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, |
| 28 SkBBoxHierarchy* tree) | 28 SkBBoxHierarchy* tree) |
| 29 : INHERITED(param) | 29 : INHERITED(param) |
| 30 , fTree(tree) | 30 , fTree(tree) |
| 31 , fProc(proc) | 31 , fProc(proc) |
| 32 , fBulkLoad(bulkLoad) { | 32 , fBulkLoad(bulkLoad) { |
| 33 fName.append("rtree_"); | 33 fName.append("rtree_"); |
| 34 fName.append(name); | 34 fName.append(name); |
| 35 fName.append("_build"); | 35 fName.append("_build"); |
| 36 if (fBulkLoad) { | 36 if (fBulkLoad) { |
| 37 fName.append("_bulk"); | 37 fName.append("_bulk"); |
| 38 } | 38 } |
| 39 fIsRendering = false; | 39 fIsRendering = false; |
| 40 } | 40 } |
| 41 virtual ~BBoxBuildBench() { | 41 virtual ~BBoxBuildBench() { |
| 42 fTree->unref(); | 42 fTree->unref(); |
| 43 } | 43 } |
| 44 protected: | 44 protected: |
| 45 virtual const char* onGetName() SK_OVERRIDE { | 45 virtual const char* onGetName() SK_OVERRIDE { |
| 46 return fName.c_str(); | 46 return fName.c_str(); |
| 47 } | 47 } |
| 48 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { | 48 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
| 49 SkMWCRandom rand; | 49 SkRandom rand; |
| 50 for (int i = 0; i < SkBENCHLOOP(100); ++i) { | 50 for (int i = 0; i < SkBENCHLOOP(100); ++i) { |
| 51 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 51 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
| 52 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 52 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
| 53 fBulkLoad); | 53 fBulkLoad); |
| 54 } | 54 } |
| 55 fTree->flushDeferredInserts(); | 55 fTree->flushDeferredInserts(); |
| 56 fTree->clear(); | 56 fTree->clear(); |
| 57 } | 57 } |
| 58 } | 58 } |
| 59 private: | 59 private: |
| (...skipping 30 matching lines...) Expand all Loading... |
| 90 fIsRendering = false; | 90 fIsRendering = false; |
| 91 } | 91 } |
| 92 virtual ~BBoxQueryBench() { | 92 virtual ~BBoxQueryBench() { |
| 93 fTree->unref(); | 93 fTree->unref(); |
| 94 } | 94 } |
| 95 protected: | 95 protected: |
| 96 virtual const char* onGetName() SK_OVERRIDE { | 96 virtual const char* onGetName() SK_OVERRIDE { |
| 97 return fName.c_str(); | 97 return fName.c_str(); |
| 98 } | 98 } |
| 99 virtual void onPreDraw() SK_OVERRIDE { | 99 virtual void onPreDraw() SK_OVERRIDE { |
| 100 SkMWCRandom rand; | 100 SkRandom rand; |
| 101 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { | 101 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { |
| 102 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, | 102 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, |
| 103 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); | 103 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); |
| 104 } | 104 } |
| 105 fTree->flushDeferredInserts(); | 105 fTree->flushDeferredInserts(); |
| 106 } | 106 } |
| 107 | 107 |
| 108 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { | 108 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
| 109 SkMWCRandom rand; | 109 SkRandom rand; |
| 110 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { | 110 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { |
| 111 SkTDArray<void*> hits; | 111 SkTDArray<void*> hits; |
| 112 SkIRect query; | 112 SkIRect query; |
| 113 switch(fQuery) { | 113 switch(fQuery) { |
| 114 case kSmall_QueryType: | 114 case kSmall_QueryType: |
| 115 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 115 query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 116 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 116 query.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 117 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | 117 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
| 118 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | 118 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
| 119 break; | 119 break; |
| (...skipping 22 matching lines...) Expand all Loading... |
| 142 } | 142 } |
| 143 private: | 143 private: |
| 144 SkBBoxHierarchy* fTree; | 144 SkBBoxHierarchy* fTree; |
| 145 MakeRectProc fProc; | 145 MakeRectProc fProc; |
| 146 SkString fName; | 146 SkString fName; |
| 147 bool fBulkLoad; | 147 bool fBulkLoad; |
| 148 QueryType fQuery; | 148 QueryType fQuery; |
| 149 typedef SkBenchmark INHERITED; | 149 typedef SkBenchmark INHERITED; |
| 150 }; | 150 }; |
| 151 | 151 |
| 152 static inline SkIRect make_simple_rect(SkMWCRandom&, int index, int numRects) { | 152 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) { |
| 153 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; | 153 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; |
| 154 return out; | 154 return out; |
| 155 } | 155 } |
| 156 | 156 |
| 157 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index,
int numRects) { | 157 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { |
| 158 SkIRect out = {0, 0, index + 1, index + 1}; | 158 SkIRect out = {0, 0, index + 1, index + 1}; |
| 159 return out; | 159 return out; |
| 160 } | 160 } |
| 161 | 161 |
| 162 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index,
int numRects) { | 162 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int
numRects) { |
| 163 SkIRect out = {0, 0, numRects - index, numRects - index}; | 163 SkIRect out = {0, 0, numRects - index, numRects - index}; |
| 164 return out; | 164 return out; |
| 165 } | 165 } |
| 166 | 166 |
| 167 static inline SkIRect make_XYordered_rects(SkMWCRandom& rand, int index, int num
Rects) { | 167 static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
ts) { |
| 168 SkIRect out; | 168 SkIRect out; |
| 169 out.fLeft = index % GRID_WIDTH; | 169 out.fLeft = index % GRID_WIDTH; |
| 170 out.fTop = index / GRID_WIDTH; | 170 out.fTop = index / GRID_WIDTH; |
| 171 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 171 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 172 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 172 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 173 return out; | 173 return out; |
| 174 } | 174 } |
| 175 static inline SkIRect make_YXordered_rects(SkMWCRandom& rand, int index, int num
Rects) { | 175 static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRec
ts) { |
| 176 SkIRect out; | 176 SkIRect out; |
| 177 out.fLeft = index / GRID_WIDTH; | 177 out.fLeft = index / GRID_WIDTH; |
| 178 out.fTop = index % GRID_WIDTH; | 178 out.fTop = index % GRID_WIDTH; |
| 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); | 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); |
| 181 return out; | 181 return out; |
| 182 } | 182 } |
| 183 | 183 |
| 184 static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRect
s) { | 184 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects)
{ |
| 185 SkIRect out; | 185 SkIRect out; |
| 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); | 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); |
| 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); | 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); |
| 190 return out; | 190 return out; |
| 191 } | 191 } |
| 192 | 192 |
| 193 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRec
ts) { | 193 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
{ |
| 194 SkIRect out; | 194 SkIRect out; |
| 195 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 195 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
| 196 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 196 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
| 197 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 197 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 198 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 198 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 199 return out; | 199 return out; |
| 200 } | 200 } |
| 201 | 201 |
| 202 static inline SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect
s) { | 202 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects)
{ |
| 203 SkIRect out; | 203 SkIRect out; |
| 204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 204 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 205 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 205 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); | 206 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); |
| 207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); | 207 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); |
| 208 return out; | 208 return out; |
| 209 } | 209 } |
| 210 | 210 |
| 211 /////////////////////////////////////////////////////////////////////////////// | 211 /////////////////////////////////////////////////////////////////////////////// |
| 212 | 212 |
| (...skipping 89 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 302 static BenchRegistry gReg9(Fact9); | 302 static BenchRegistry gReg9(Fact9); |
| 303 static BenchRegistry gReg8(Fact8); | 303 static BenchRegistry gReg8(Fact8); |
| 304 static BenchRegistry gReg7(Fact7); | 304 static BenchRegistry gReg7(Fact7); |
| 305 static BenchRegistry gReg6(Fact6); | 305 static BenchRegistry gReg6(Fact6); |
| 306 static BenchRegistry gReg5(Fact5); | 306 static BenchRegistry gReg5(Fact5); |
| 307 static BenchRegistry gReg4(Fact4); | 307 static BenchRegistry gReg4(Fact4); |
| 308 static BenchRegistry gReg3(Fact3); | 308 static BenchRegistry gReg3(Fact3); |
| 309 static BenchRegistry gReg2(Fact2); | 309 static BenchRegistry gReg2(Fact2); |
| 310 static BenchRegistry gReg1(Fact1); | 310 static BenchRegistry gReg1(Fact1); |
| 311 static BenchRegistry gReg0(Fact0); | 311 static BenchRegistry gReg0(Fact0); |
| OLD | NEW |