rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 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" |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 9 | #include "SkCanvas.h" |
| 10 | #include "SkRTree.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: |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 15 | static const SkScalar GENERATE_EXTENTS = 1000.0f; |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 16 | static const int NUM_BUILD_RECTS = 500; |
| 17 | static const int NUM_QUERY_RECTS = 5000; |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 18 | static const int GRID_WIDTH = 100; |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 19 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 20 | typedef SkRect (*MakeRectProc)(SkRandom&, int, int); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 21 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 22 | // Time how long it takes to build an R-Tree. |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 23 | class RTreeBuildBench : public Benchmark { |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 24 | public: |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 25 | RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) { |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 26 | fName.printf("rtree_%s_build", name); |
rileya@google.com | 61348d1 | 2012-09-06 13:38:53 +0000 | [diff] [blame] | 27 | } |
commit-bot@chromium.org | 644629c | 2013-11-21 06:21:58 +0000 | [diff] [blame] | 28 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 29 | bool isSuitableFor(Backend backend) override { |
commit-bot@chromium.org | 644629c | 2013-11-21 06:21:58 +0000 | [diff] [blame] | 30 | return backend == kNonRendering_Backend; |
| 31 | } |
| 32 | |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 33 | protected: |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 34 | const char* onGetName() override { |
rileya@google.com | 61348d1 | 2012-09-06 13:38:53 +0000 | [diff] [blame] | 35 | return fName.c_str(); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 36 | } |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 37 | void onDraw(const int loops, SkCanvas* canvas) override { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 38 | SkRandom rand; |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 39 | SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS); |
| 40 | for (int i = 0; i < NUM_BUILD_RECTS; ++i) { |
| 41 | rects[i] = fProc(rand, i, NUM_BUILD_RECTS); |
| 42 | } |
| 43 | |
commit-bot@chromium.org | 3361471 | 2013-12-03 18:17:16 +0000 | [diff] [blame] | 44 | for (int i = 0; i < loops; ++i) { |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 45 | SkRTree tree; |
mtklein | bfd5bff | 2015-02-10 13:44:27 -0800 | [diff] [blame] | 46 | tree.insert(rects.get(), NUM_BUILD_RECTS); |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 47 | SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects. |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 48 | } |
| 49 | } |
| 50 | private: |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 51 | MakeRectProc fProc; |
rileya@google.com | 61348d1 | 2012-09-06 13:38:53 +0000 | [diff] [blame] | 52 | SkString fName; |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 53 | typedef Benchmark INHERITED; |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 54 | }; |
| 55 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 56 | // Time how long it takes to perform queries on an R-Tree. |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 57 | class RTreeQueryBench : public Benchmark { |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 58 | public: |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 59 | RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) { |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 60 | fName.printf("rtree_%s_query", name); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 61 | } |
commit-bot@chromium.org | 644629c | 2013-11-21 06:21:58 +0000 | [diff] [blame] | 62 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 63 | bool isSuitableFor(Backend backend) override { |
commit-bot@chromium.org | 644629c | 2013-11-21 06:21:58 +0000 | [diff] [blame] | 64 | return backend == kNonRendering_Backend; |
| 65 | } |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 66 | protected: |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 67 | const char* onGetName() override { |
rileya@google.com | 61348d1 | 2012-09-06 13:38:53 +0000 | [diff] [blame] | 68 | return fName.c_str(); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 69 | } |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 70 | void onPreDraw() override { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 71 | SkRandom rand; |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 72 | SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS); |
| 73 | for (int i = 0; i < NUM_QUERY_RECTS; ++i) { |
| 74 | rects[i] = fProc(rand, i, NUM_QUERY_RECTS); |
commit-bot@chromium.org | 7fb83c8 | 2013-08-01 15:58:07 +0000 | [diff] [blame] | 75 | } |
mtklein | bfd5bff | 2015-02-10 13:44:27 -0800 | [diff] [blame] | 76 | fTree.insert(rects.get(), NUM_QUERY_RECTS); |
commit-bot@chromium.org | 7fb83c8 | 2013-08-01 15:58:07 +0000 | [diff] [blame] | 77 | } |
| 78 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 79 | void onDraw(const int loops, SkCanvas* canvas) override { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 80 | SkRandom rand; |
commit-bot@chromium.org | 3361471 | 2013-12-03 18:17:16 +0000 | [diff] [blame] | 81 | for (int i = 0; i < loops; ++i) { |
mtklein | 6bd4196 | 2014-10-02 07:41:56 -0700 | [diff] [blame] | 82 | SkTDArray<unsigned> hits; |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 83 | SkRect query; |
mtklein | 4477c3c | 2014-10-27 10:27:10 -0700 | [diff] [blame] | 84 | query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
| 85 | query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
| 86 | query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); |
| 87 | query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 88 | fTree.search(query, &hits); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 89 | } |
| 90 | } |
| 91 | private: |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 92 | SkRTree fTree; |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 93 | MakeRectProc fProc; |
rileya@google.com | 61348d1 | 2012-09-06 13:38:53 +0000 | [diff] [blame] | 94 | SkString fName; |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 95 | typedef Benchmark INHERITED; |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 96 | }; |
| 97 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 98 | static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { |
| 99 | SkRect out; |
| 100 | out.fLeft = SkIntToScalar(index % GRID_WIDTH); |
| 101 | out.fTop = SkIntToScalar(index / GRID_WIDTH); |
| 102 | out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
| 103 | out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 104 | return out; |
| 105 | } |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 106 | static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { |
| 107 | SkRect out; |
| 108 | out.fLeft = SkIntToScalar(index / GRID_WIDTH); |
| 109 | out.fTop = SkIntToScalar(index % GRID_WIDTH); |
| 110 | out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
| 111 | out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); |
sglez@google.com | 8c90212 | 2013-08-30 17:27:47 +0000 | [diff] [blame] | 112 | return out; |
| 113 | } |
| 114 | |
mtklein | 533eb78 | 2014-08-27 10:39:42 -0700 | [diff] [blame] | 115 | static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) { |
| 116 | SkRect out; |
| 117 | out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); |
| 118 | out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); |
| 119 | out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
| 120 | out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 121 | return out; |
| 122 | } |
| 123 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 124 | static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) { |
| 125 | return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); |
| 126 | } |
| 127 | |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 128 | /////////////////////////////////////////////////////////////////////////////// |
| 129 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 130 | DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY", &make_XYordered_rects))); |
| 131 | DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX", &make_YXordered_rects))); |
| 132 | DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects))); |
| 133 | DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects))); |
rileya@google.com | 981b33a | 2012-09-05 18:36:17 +0000 | [diff] [blame] | 134 | |
mtklein | a06a953 | 2014-11-18 09:27:49 -0800 | [diff] [blame] | 135 | DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY", &make_XYordered_rects))); |
| 136 | DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX", &make_YXordered_rects))); |
| 137 | DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects))); |
| 138 | DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects))); |