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