blob: 39c2aa116c14e5362bfdca54422ba78b7b3c0e49 [file] [log] [blame]
rileya@google.com981b33a2012-09-05 18:36:17 +00001/*
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
tfarinaf168b862014-06-19 12:32:29 -07008#include "Benchmark.h"
rileya@google.com981b33a2012-09-05 18:36:17 +00009#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:
mtklein533eb782014-08-27 10:39:42 -070015static const SkScalar GENERATE_EXTENTS = 1000.0f;
rileya@google.com981b33a2012-09-05 18:36:17 +000016static const int NUM_BUILD_RECTS = 500;
17static const int NUM_QUERY_RECTS = 5000;
sglez@google.com8c902122013-08-30 17:27:47 +000018static const int GRID_WIDTH = 100;
rileya@google.com981b33a2012-09-05 18:36:17 +000019
mtklein533eb782014-08-27 10:39:42 -070020typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
rileya@google.com981b33a2012-09-05 18:36:17 +000021
mtkleina06a9532014-11-18 09:27:49 -080022// Time how long it takes to build an R-Tree.
tfarinaf168b862014-06-19 12:32:29 -070023class RTreeBuildBench : public Benchmark {
rileya@google.com981b33a2012-09-05 18:36:17 +000024public:
mtkleina06a9532014-11-18 09:27:49 -080025 RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
mtklein4477c3c2014-10-27 10:27:10 -070026 fName.printf("rtree_%s_build", name);
rileya@google.com61348d12012-09-06 13:38:53 +000027 }
commit-bot@chromium.org644629c2013-11-21 06:21:58 +000028
mtklein72c9faa2015-01-09 10:06:39 -080029 bool isSuitableFor(Backend backend) SK_OVERRIDE {
commit-bot@chromium.org644629c2013-11-21 06:21:58 +000030 return backend == kNonRendering_Backend;
31 }
32
rileya@google.com981b33a2012-09-05 18:36:17 +000033protected:
mtklein72c9faa2015-01-09 10:06:39 -080034 const char* onGetName() SK_OVERRIDE {
rileya@google.com61348d12012-09-06 13:38:53 +000035 return fName.c_str();
rileya@google.com981b33a2012-09-05 18:36:17 +000036 }
mtklein72c9faa2015-01-09 10:06:39 -080037 void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000038 SkRandom rand;
mtklein4477c3c2014-10-27 10:27:10 -070039 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.org33614712013-12-03 18:17:16 +000044 for (int i = 0; i < loops; ++i) {
mtkleina06a9532014-11-18 09:27:49 -080045 SkRTree tree;
46 tree.insert(&rects, NUM_BUILD_RECTS);
mtklein4477c3c2014-10-27 10:27:10 -070047 SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects.
rileya@google.com981b33a2012-09-05 18:36:17 +000048 }
49 }
50private:
rileya@google.com981b33a2012-09-05 18:36:17 +000051 MakeRectProc fProc;
rileya@google.com61348d12012-09-06 13:38:53 +000052 SkString fName;
tfarinaf168b862014-06-19 12:32:29 -070053 typedef Benchmark INHERITED;
rileya@google.com981b33a2012-09-05 18:36:17 +000054};
55
mtkleina06a9532014-11-18 09:27:49 -080056// Time how long it takes to perform queries on an R-Tree.
tfarinaf168b862014-06-19 12:32:29 -070057class RTreeQueryBench : public Benchmark {
rileya@google.com981b33a2012-09-05 18:36:17 +000058public:
mtkleina06a9532014-11-18 09:27:49 -080059 RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
mtklein4477c3c2014-10-27 10:27:10 -070060 fName.printf("rtree_%s_query", name);
rileya@google.com981b33a2012-09-05 18:36:17 +000061 }
commit-bot@chromium.org644629c2013-11-21 06:21:58 +000062
mtklein72c9faa2015-01-09 10:06:39 -080063 bool isSuitableFor(Backend backend) SK_OVERRIDE {
commit-bot@chromium.org644629c2013-11-21 06:21:58 +000064 return backend == kNonRendering_Backend;
65 }
rileya@google.com981b33a2012-09-05 18:36:17 +000066protected:
mtklein72c9faa2015-01-09 10:06:39 -080067 const char* onGetName() SK_OVERRIDE {
rileya@google.com61348d12012-09-06 13:38:53 +000068 return fName.c_str();
rileya@google.com981b33a2012-09-05 18:36:17 +000069 }
mtklein72c9faa2015-01-09 10:06:39 -080070 void onPreDraw() SK_OVERRIDE {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000071 SkRandom rand;
mtklein4477c3c2014-10-27 10:27:10 -070072 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.org7fb83c82013-08-01 15:58:07 +000075 }
mtkleina06a9532014-11-18 09:27:49 -080076 fTree.insert(&rects, NUM_QUERY_RECTS);
commit-bot@chromium.org7fb83c82013-08-01 15:58:07 +000077 }
78
mtklein72c9faa2015-01-09 10:06:39 -080079 void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000080 SkRandom rand;
commit-bot@chromium.org33614712013-12-03 18:17:16 +000081 for (int i = 0; i < loops; ++i) {
mtklein6bd41962014-10-02 07:41:56 -070082 SkTDArray<unsigned> hits;
mtklein533eb782014-08-27 10:39:42 -070083 SkRect query;
mtklein4477c3c2014-10-27 10:27:10 -070084 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);
mtkleina06a9532014-11-18 09:27:49 -080088 fTree.search(query, &hits);
rileya@google.com981b33a2012-09-05 18:36:17 +000089 }
90 }
91private:
mtkleina06a9532014-11-18 09:27:49 -080092 SkRTree fTree;
rileya@google.com981b33a2012-09-05 18:36:17 +000093 MakeRectProc fProc;
rileya@google.com61348d12012-09-06 13:38:53 +000094 SkString fName;
tfarinaf168b862014-06-19 12:32:29 -070095 typedef Benchmark INHERITED;
rileya@google.com981b33a2012-09-05 18:36:17 +000096};
97
mtklein533eb782014-08-27 10:39:42 -070098static 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.com8c902122013-08-30 17:27:47 +0000104 return out;
105}
mtklein533eb782014-08-27 10:39:42 -0700106static 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.com8c902122013-08-30 17:27:47 +0000112 return out;
113}
114
mtklein533eb782014-08-27 10:39:42 -0700115static 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.com981b33a2012-09-05 18:36:17 +0000121 return out;
122}
123
mtkleina06a9532014-11-18 09:27:49 -0800124static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
125 return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
126}
127
rileya@google.com981b33a2012-09-05 18:36:17 +0000128///////////////////////////////////////////////////////////////////////////////
129
mtkleina06a9532014-11-18 09:27:49 -0800130DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY", &make_XYordered_rects)));
131DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX", &make_YXordered_rects)));
132DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects)));
133DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects)));
rileya@google.com981b33a2012-09-05 18:36:17 +0000134
mtkleina06a9532014-11-18 09:27:49 -0800135DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY", &make_XYordered_rects)));
136DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX", &make_YXordered_rects)));
137DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects)));
138DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects)));