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
8 #include "Benchmark.h"
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:
15 static const SkScalar GENERATE_EXTENTS = 1000.0f;
16 static const int NUM_BUILD_RECTS = 500;
17 static const int NUM_QUERY_RECTS = 5000;
18 static const int GRID_WIDTH = 100;
19
20 typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
21
22 // Time how long it takes to build an R-Tree.
23 class RTreeBuildBench : public Benchmark {
24 public:
RTreeBuildBench(const char * name,MakeRectProc proc)25 RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
26 fName.printf("rtree_%s_build", name);
27 }
28
isSuitableFor(Backend backend)29 bool isSuitableFor(Backend backend) override {
30 return backend == kNonRendering_Backend;
31 }
32
33 protected:
onGetName()34 const char* onGetName() override {
35 return fName.c_str();
36 }
onDraw(int loops,SkCanvas * canvas)37 void onDraw(int loops, SkCanvas* canvas) override {
38 SkRandom rand;
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
44 for (int i = 0; i < loops; ++i) {
45 SkRTree tree;
46 tree.insert(rects.get(), NUM_BUILD_RECTS);
47 SkASSERT(rects != nullptr); // It'd break this bench if the tree took ownership of rects.
48 }
49 }
50 private:
51 MakeRectProc fProc;
52 SkString fName;
53 typedef Benchmark INHERITED;
54 };
55
56 // Time how long it takes to perform queries on an R-Tree.
57 class RTreeQueryBench : public Benchmark {
58 public:
RTreeQueryBench(const char * name,MakeRectProc proc)59 RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
60 fName.printf("rtree_%s_query", name);
61 }
62
isSuitableFor(Backend backend)63 bool isSuitableFor(Backend backend) override {
64 return backend == kNonRendering_Backend;
65 }
66 protected:
onGetName()67 const char* onGetName() override {
68 return fName.c_str();
69 }
onDelayedSetup()70 void onDelayedSetup() override {
71 SkRandom rand;
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);
75 }
76 fTree.insert(rects.get(), NUM_QUERY_RECTS);
77 }
78
onDraw(int loops,SkCanvas * canvas)79 void onDraw(int loops, SkCanvas* canvas) override {
80 SkRandom rand;
81 for (int i = 0; i < loops; ++i) {
82 SkTDArray<int> hits;
83 SkRect query;
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);
88 fTree.search(query, &hits);
89 }
90 }
91 private:
92 SkRTree fTree;
93 MakeRectProc fProc;
94 SkString fName;
95 typedef Benchmark INHERITED;
96 };
97
make_XYordered_rects(SkRandom & rand,int index,int numRects)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);
104 return out;
105 }
make_YXordered_rects(SkRandom & rand,int index,int numRects)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);
112 return out;
113 }
114
make_random_rects(SkRandom & rand,int index,int numRects)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);
121 return out;
122 }
123
make_concentric_rects(SkRandom &,int index,int numRects)124 static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
125 return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
126 }
127
128 ///////////////////////////////////////////////////////////////////////////////
129
130 DEF_BENCH(return new RTreeBuildBench("XY", &make_XYordered_rects));
131 DEF_BENCH(return new RTreeBuildBench("YX", &make_YXordered_rects));
132 DEF_BENCH(return new RTreeBuildBench("random", &make_random_rects));
133 DEF_BENCH(return new RTreeBuildBench("concentric", &make_concentric_rects));
134
135 DEF_BENCH(return new RTreeQueryBench("XY", &make_XYordered_rects));
136 DEF_BENCH(return new RTreeQueryBench("YX", &make_YXordered_rects));
137 DEF_BENCH(return new RTreeQueryBench("random", &make_random_rects));
138 DEF_BENCH(return new RTreeQueryBench("concentric", &make_concentric_rects));
139