| 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 | 20 |
| 21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int); | 21 typedef SkIRect (*MakeRectProc)(SkMWCRandom&, 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 BBoxBuildBench : public SkBenchmark { |
| 25 public: | 25 public: |
| 26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, | 26 BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLo
ad, |
| 27 SkBBoxHierarchy* tree) | 27 SkBBoxHierarchy* tree) |
| 28 : INHERITED(param) | 28 : INHERITED(param) |
| 29 , fTree(tree) | 29 , fTree(tree) |
| 30 , fProc(proc) | 30 , fProc(proc) |
| 31 , fBulkLoad(bulkLoad) { | 31 , fBulkLoad(bulkLoad) { |
| 32 fName.append("rtree_"); | 32 fName.append("rtree_"); |
| 33 fName.append(name); | 33 fName.append(name); |
| 34 fName.append("_build"); | 34 fName.append("_build"); |
| 35 if (fBulkLoad) { | 35 if (fBulkLoad) { |
| 36 fName.append("_bulk"); | 36 fName.append("_bulk"); |
| 37 } | 37 } |
| 38 fIsRendering = false; | 38 fIsRendering = false; |
| 39 } | 39 } |
| 40 virtual ~BBoxBuildBench() { | 40 virtual ~BBoxBuildBench() { |
| 41 fTree->unref(); | 41 fTree->unref(); |
| 42 } | 42 } |
| 43 protected: | 43 protected: |
| 44 virtual const char* onGetName() { | 44 virtual const char* onGetName() SK_OVERRIDE { |
| 45 return fName.c_str(); | 45 return fName.c_str(); |
| 46 } | 46 } |
| 47 virtual void onDraw(SkCanvas* canvas) { | 47 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
| 48 SkRandom rand; | 48 SkMWCRandom rand; |
| 49 for (int i = 0; i < SkBENCHLOOP(100); ++i) { | 49 for (int i = 0; i < SkBENCHLOOP(100); ++i) { |
| 50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { | 50 for (int j = 0; j < NUM_BUILD_RECTS; ++j) { |
| 51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), | 51 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUI
LD_RECTS), |
| 52 fBulkLoad); | 52 fBulkLoad); |
| 53 } | 53 } |
| 54 fTree->flushDeferredInserts(); | 54 fTree->flushDeferredInserts(); |
| 55 fTree->clear(); | 55 fTree->clear(); |
| 56 } | 56 } |
| 57 } | 57 } |
| 58 private: | 58 private: |
| (...skipping 20 matching lines...) Expand all Loading... |
| 79 , fTree(tree) | 79 , fTree(tree) |
| 80 , fProc(proc) | 80 , fProc(proc) |
| 81 , fBulkLoad(bulkLoad) | 81 , fBulkLoad(bulkLoad) |
| 82 , fQuery(q) { | 82 , fQuery(q) { |
| 83 fName.append("rtree_"); | 83 fName.append("rtree_"); |
| 84 fName.append(name); | 84 fName.append(name); |
| 85 fName.append("_query"); | 85 fName.append("_query"); |
| 86 if (fBulkLoad) { | 86 if (fBulkLoad) { |
| 87 fName.append("_bulk"); | 87 fName.append("_bulk"); |
| 88 } | 88 } |
| 89 SkRandom rand; | |
| 90 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { | |
| 91 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, | |
| 92 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); | |
| 93 } | |
| 94 fTree->flushDeferredInserts(); | |
| 95 fIsRendering = false; | 89 fIsRendering = false; |
| 96 } | 90 } |
| 97 virtual ~BBoxQueryBench() { | 91 virtual ~BBoxQueryBench() { |
| 98 fTree->unref(); | 92 fTree->unref(); |
| 99 } | 93 } |
| 100 protected: | 94 protected: |
| 101 virtual const char* onGetName() { | 95 virtual const char* onGetName() SK_OVERRIDE { |
| 102 return fName.c_str(); | 96 return fName.c_str(); |
| 103 } | 97 } |
| 104 virtual void onDraw(SkCanvas* canvas) { | 98 virtual void onPreDraw() SK_OVERRIDE { |
| 105 SkRandom rand; | 99 SkMWCRandom rand; |
| 100 for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { |
| 101 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, |
| 102 SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); |
| 103 } |
| 104 fTree->flushDeferredInserts(); |
| 105 } |
| 106 |
| 107 virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE { |
| 108 SkMWCRandom rand; |
| 106 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { | 109 for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { |
| 107 SkTDArray<void*> hits; | 110 SkTDArray<void*> hits; |
| 108 SkIRect query; | 111 SkIRect query; |
| 109 switch(fQuery) { | 112 switch(fQuery) { |
| 110 case kSmall_QueryType: | 113 case kSmall_QueryType: |
| 111 query.fLeft = rand.nextU() % GENERATE_EXTENTS; | 114 query.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 112 query.fTop = rand.nextU() % GENERATE_EXTENTS; | 115 query.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 113 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); | 116 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); |
| 114 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); | 117 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); |
| 115 break; | 118 break; |
| (...skipping 22 matching lines...) Expand all Loading... |
| 138 } | 141 } |
| 139 private: | 142 private: |
| 140 SkBBoxHierarchy* fTree; | 143 SkBBoxHierarchy* fTree; |
| 141 MakeRectProc fProc; | 144 MakeRectProc fProc; |
| 142 SkString fName; | 145 SkString fName; |
| 143 bool fBulkLoad; | 146 bool fBulkLoad; |
| 144 QueryType fQuery; | 147 QueryType fQuery; |
| 145 typedef SkBenchmark INHERITED; | 148 typedef SkBenchmark INHERITED; |
| 146 }; | 149 }; |
| 147 | 150 |
| 148 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) { | 151 static inline SkIRect make_simple_rect(SkMWCRandom&, int index, int numRects) { |
| 149 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; | 152 SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; |
| 150 return out; | 153 return out; |
| 151 } | 154 } |
| 152 | 155 |
| 153 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int
numRects) { | 156 static inline SkIRect make_concentric_rects_increasing(SkMWCRandom&, int index,
int numRects) { |
| 154 SkIRect out = {0, 0, index + 1, index + 1}; | 157 SkIRect out = {0, 0, index + 1, index + 1}; |
| 155 return out; | 158 return out; |
| 156 } | 159 } |
| 157 | 160 |
| 158 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int
numRects) { | 161 static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index,
int numRects) { |
| 159 SkIRect out = {0, 0, numRects - index, numRects - index}; | 162 SkIRect out = {0, 0, numRects - index, numRects - index}; |
| 160 return out; | 163 return out; |
| 161 } | 164 } |
| 162 | 165 |
| 163 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects)
{ | 166 static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRect
s) { |
| 164 SkIRect out; | 167 SkIRect out; |
| 165 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 168 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 166 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 169 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 167 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); | 170 out.fRight = out.fLeft + (GENERATE_EXTENTS / 200); |
| 168 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); | 171 out.fBottom = out.fTop + (GENERATE_EXTENTS / 200); |
| 169 return out; | 172 return out; |
| 170 } | 173 } |
| 171 | 174 |
| 172 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
{ | 175 static inline SkIRect make_random_rects(SkMWCRandom& rand, int index, int numRec
ts) { |
| 173 SkIRect out; | 176 SkIRect out; |
| 174 out.fLeft = rand.nextS() % GENERATE_EXTENTS; | 177 out.fLeft = rand.nextS() % GENERATE_EXTENTS; |
| 175 out.fTop = rand.nextS() % GENERATE_EXTENTS; | 178 out.fTop = rand.nextS() % GENERATE_EXTENTS; |
| 176 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 179 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 177 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); | 180 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); |
| 178 return out; | 181 return out; |
| 179 } | 182 } |
| 180 | 183 |
| 181 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects)
{ | 184 static inline SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect
s) { |
| 182 SkIRect out; | 185 SkIRect out; |
| 183 out.fLeft = rand.nextU() % GENERATE_EXTENTS; | 186 out.fLeft = rand.nextU() % GENERATE_EXTENTS; |
| 184 out.fTop = rand.nextU() % GENERATE_EXTENTS; | 187 out.fTop = rand.nextU() % GENERATE_EXTENTS; |
| 185 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); | 188 out.fRight = out.fLeft + (GENERATE_EXTENTS / 3); |
| 186 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); | 189 out.fBottom = out.fTop + (GENERATE_EXTENTS / 3); |
| 187 return out; | 190 return out; |
| 188 } | 191 } |
| 189 | 192 |
| 190 /////////////////////////////////////////////////////////////////////////////// | 193 /////////////////////////////////////////////////////////////////////////////// |
| 191 | 194 |
| (...skipping 16 matching lines...) Expand all Loading... |
| 208 static inline SkBenchmark* Fact4(void* p) { | 211 static inline SkBenchmark* Fact4(void* p) { |
| 209 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, | 212 return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, |
| 210 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); | 213 BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))
); |
| 211 } | 214 } |
| 212 | 215 |
| 213 static BenchRegistry gReg0(Fact0); | 216 static BenchRegistry gReg0(Fact0); |
| 214 static BenchRegistry gReg1(Fact1); | 217 static BenchRegistry gReg1(Fact1); |
| 215 static BenchRegistry gReg2(Fact2); | 218 static BenchRegistry gReg2(Fact2); |
| 216 static BenchRegistry gReg3(Fact3); | 219 static BenchRegistry gReg3(Fact3); |
| 217 static BenchRegistry gReg4(Fact4); | 220 static BenchRegistry gReg4(Fact4); |
| OLD | NEW |