blob: 79078a8ae9b92211f35cef491565d6f7dbe760ab [file] [log] [blame]
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +00001/*
2 * Copyright 2014 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"
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +00009#include "SkCanvas.h"
10#include "SkQuadTree.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:
15static const int GENERATE_EXTENTS = 1000;
16static const int NUM_BUILD_RECTS = 500;
17static const int NUM_QUERY_RECTS = 5000;
18static const int GRID_WIDTH = 100;
19static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB(
20 -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS);
21
22typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
23
24// Time how long it takes to build an QuadTree
tfarinaf168b862014-06-19 12:32:29 -070025class QuadTreeBuildBench : public Benchmark {
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000026public:
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +000027 QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree)
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000028 : fTree(tree)
29 , fProc(proc) {
30 fName.append("quadtree_");
31 fName.append(name);
32 fName.append("_build");
33 }
34
35 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
36 return backend == kNonRendering_Backend;
37 }
38
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +000039 virtual ~QuadTreeBuildBench() {
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000040 fTree->unref();
41 }
42protected:
43 virtual const char* onGetName() SK_OVERRIDE {
44 return fName.c_str();
45 }
46 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
47 SkRandom rand;
48 for (int i = 0; i < loops; ++i) {
49 for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
50 fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
51 false);
52 }
53 fTree->clear();
54 }
55 }
56private:
57 SkBBoxHierarchy* fTree;
58 MakeRectProc fProc;
59 SkString fName;
tfarinaf168b862014-06-19 12:32:29 -070060 typedef Benchmark INHERITED;
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000061};
62
63// Time how long it takes to perform queries on an QuadTree
tfarinaf168b862014-06-19 12:32:29 -070064class QuadTreeQueryBench : public Benchmark {
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000065public:
66 enum QueryType {
67 kSmall_QueryType, // small queries
68 kLarge_QueryType, // large queries
69 kRandom_QueryType,// randomly sized queries
70 kFull_QueryType // queries that cover everything
71 };
72
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +000073 QuadTreeQueryBench(const char* name, MakeRectProc proc,
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000074 QueryType q, SkBBoxHierarchy* tree)
75 : fTree(tree)
76 , fProc(proc)
77 , fQuery(q) {
78 fName.append("quadtree_");
79 fName.append(name);
80 fName.append("_query");
81 }
82
83 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
84 return backend == kNonRendering_Backend;
85 }
86
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +000087 virtual ~QuadTreeQueryBench() {
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +000088 fTree->unref();
89 }
90protected:
91 virtual const char* onGetName() SK_OVERRIDE {
92 return fName.c_str();
93 }
94 virtual void onPreDraw() SK_OVERRIDE {
95 SkRandom rand;
96 for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
97 fTree->insert(reinterpret_cast<void*>(j),
98 fProc(rand, j, NUM_QUERY_RECTS),
99 false);
100 }
101 fTree->flushDeferredInserts();
102 }
103
104 virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
105 SkRandom rand;
106 for (int i = 0; i < loops; ++i) {
107 SkTDArray<void*> hits;
108 SkIRect query;
109 switch(fQuery) {
110 case kSmall_QueryType:
111 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
112 query.fTop = rand.nextU() % GENERATE_EXTENTS;
113 query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
114 query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
115 break;
116 case kLarge_QueryType:
117 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
118 query.fTop = rand.nextU() % GENERATE_EXTENTS;
119 query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
120 query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
121 break;
122 case kFull_QueryType:
123 query.fLeft = -GENERATE_EXTENTS;
124 query.fTop = -GENERATE_EXTENTS;
125 query.fRight = 2 * GENERATE_EXTENTS;
126 query.fBottom = 2 * GENERATE_EXTENTS;
127 break;
128 default: // fallthrough
129 case kRandom_QueryType:
130 query.fLeft = rand.nextU() % GENERATE_EXTENTS;
131 query.fTop = rand.nextU() % GENERATE_EXTENTS;
132 query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
133 query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
134 break;
135 };
136 fTree->search(query, &hits);
137 }
138 }
139private:
140 SkBBoxHierarchy* fTree;
141 MakeRectProc fProc;
142 SkString fName;
143 QueryType fQuery;
tfarinaf168b862014-06-19 12:32:29 -0700144 typedef Benchmark INHERITED;
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000145};
146
147static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
148 SkIRect out = {0, 0, index + 1, index + 1};
149 return out;
150}
151
152static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
153 SkIRect out;
154 out.fLeft = index % GRID_WIDTH;
155 out.fTop = index / GRID_WIDTH;
156 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
157 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
158 return out;
159}
160
161static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
162 SkIRect out;
163 out.fLeft = index / GRID_WIDTH;
164 out.fTop = index % GRID_WIDTH;
165 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
166 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
167 return out;
168}
169
170static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
171 SkIRect out;
172 out.fLeft = rand.nextS() % GENERATE_EXTENTS;
173 out.fTop = rand.nextS() % GENERATE_EXTENTS;
174 out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
175 out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
176 return out;
177}
178
179///////////////////////////////////////////////////////////////////////////////
180
181DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000182 return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000183 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000184)
185DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000186 return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects,
187 QuadTreeQueryBench::kRandom_QueryType,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000188 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000189)
190DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000191 return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000192 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000193)
194DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000195 return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects,
196 QuadTreeQueryBench::kRandom_QueryType,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000197 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000198)
199DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000200 return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000201 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000202)
203DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000204 return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects,
205 QuadTreeQueryBench::kRandom_QueryType,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000206 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000207)
208DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000209 return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000210 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000211)
212DEF_BENCH(
commit-bot@chromium.orgb2db4432014-04-23 21:03:45 +0000213 return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing,
214 QuadTreeQueryBench::kRandom_QueryType,
commit-bot@chromium.org949b9982014-03-17 10:38:34 +0000215 SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
commit-bot@chromium.orgc22d1392014-02-03 18:08:33 +0000216)