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 "bench/Benchmark.h"
9 #include "include/core/SkCanvas.h"
10 #include "include/core/SkString.h"
11 #include "include/private/base/SkTemplates.h"
12 #include "src/base/SkRandom.h"
13 #include "src/core/SkRTree.h"
14
15 using namespace skia_private;
16
17 // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
18 static const SkScalar GENERATE_EXTENTS = 1000.0f;
19 static const int NUM_BUILD_RECTS = 500;
20 static const int NUM_QUERY_RECTS = 5000;
21 static const int GRID_WIDTH = 100;
22
23 typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
24
25 // Time how long it takes to build an R-Tree.
26 class RTreeBuildBench : public Benchmark {
27 public:
RTreeBuildBench(const char * name,MakeRectProc proc)28 RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
29 fName.printf("rtree_%s_build", name);
30 }
31
isSuitableFor(Backend backend)32 bool isSuitableFor(Backend backend) override {
33 return backend == kNonRendering_Backend;
34 }
35
36 protected:
onGetName()37 const char* onGetName() override {
38 return fName.c_str();
39 }
onDraw(int loops,SkCanvas * canvas)40 void onDraw(int loops, SkCanvas* canvas) override {
41 SkRandom rand;
42 AutoTMalloc<SkRect> rects(NUM_BUILD_RECTS);
43 for (int i = 0; i < NUM_BUILD_RECTS; ++i) {
44 rects[i] = fProc(rand, i, NUM_BUILD_RECTS);
45 }
46
47 for (int i = 0; i < loops; ++i) {
48 SkRTree tree;
49 tree.insert(rects.get(), NUM_BUILD_RECTS);
50 SkASSERT(rects != nullptr); // It'd break this bench if the tree took ownership of rects.
51 }
52 }
53 private:
54 MakeRectProc fProc;
55 SkString fName;
56 using INHERITED = Benchmark;
57 };
58
59 // Time how long it takes to perform queries on an R-Tree.
60 class RTreeQueryBench : public Benchmark {
61 public:
RTreeQueryBench(const char * name,MakeRectProc proc)62 RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
63 fName.printf("rtree_%s_query", name);
64 }
65
isSuitableFor(Backend backend)66 bool isSuitableFor(Backend backend) override {
67 return backend == kNonRendering_Backend;
68 }
69 protected:
onGetName()70 const char* onGetName() override {
71 return fName.c_str();
72 }
onDelayedSetup()73 void onDelayedSetup() override {
74 SkRandom rand;
75 AutoTMalloc<SkRect> rects(NUM_QUERY_RECTS);
76 for (int i = 0; i < NUM_QUERY_RECTS; ++i) {
77 rects[i] = fProc(rand, i, NUM_QUERY_RECTS);
78 }
79 fTree.insert(rects.get(), NUM_QUERY_RECTS);
80 }
81
onDraw(int loops,SkCanvas * canvas)82 void onDraw(int loops, SkCanvas* canvas) override {
83 SkRandom rand;
84 for (int i = 0; i < loops; ++i) {
85 std::vector<int> hits;
86 SkRect query;
87 query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
88 query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
89 query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
90 query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
91 fTree.search(query, &hits);
92 }
93 }
94 private:
95 SkRTree fTree;
96 MakeRectProc fProc;
97 SkString fName;
98 using INHERITED = Benchmark;
99 };
100
make_XYordered_rects(SkRandom & rand,int index,int numRects)101 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
102 SkRect out;
103 out.fLeft = SkIntToScalar(index % GRID_WIDTH);
104 out.fTop = SkIntToScalar(index / GRID_WIDTH);
105 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
106 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
107 return out;
108 }
make_YXordered_rects(SkRandom & rand,int index,int numRects)109 static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
110 SkRect out;
111 out.fLeft = SkIntToScalar(index / GRID_WIDTH);
112 out.fTop = SkIntToScalar(index % GRID_WIDTH);
113 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
114 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
115 return out;
116 }
117
make_random_rects(SkRandom & rand,int index,int numRects)118 static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) {
119 SkRect out;
120 out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
121 out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
122 out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
123 out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
124 return out;
125 }
126
make_concentric_rects(SkRandom &,int index,int numRects)127 static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
128 return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
129 }
130
131 ///////////////////////////////////////////////////////////////////////////////
132
133 DEF_BENCH(return new RTreeBuildBench("XY", &make_XYordered_rects));
134 DEF_BENCH(return new RTreeBuildBench("YX", &make_YXordered_rects));
135 DEF_BENCH(return new RTreeBuildBench("random", &make_random_rects));
136 DEF_BENCH(return new RTreeBuildBench("concentric", &make_concentric_rects));
137
138 DEF_BENCH(return new RTreeQueryBench("XY", &make_XYordered_rects));
139 DEF_BENCH(return new RTreeQueryBench("YX", &make_YXordered_rects));
140 DEF_BENCH(return new RTreeQueryBench("random", &make_random_rects));
141 DEF_BENCH(return new RTreeQueryBench("concentric", &make_concentric_rects));
142