RTreeBench.cpp revision c289743864e2ab926a95e617a5cd1d29b26d1825 
1
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "SkBenchmark.h"
10#include "SkCanvas.h"
11#include "SkRTree.h"
12#include "SkRandom.h"
13#include "SkString.h"
14
15// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
16static const int GENERATE_EXTENTS = 1000;
17static const int NUM_BUILD_RECTS = 500;
18static const int NUM_QUERY_RECTS = 5000;
19static const int GRID_WIDTH = 100;
20
21typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
22
23// Time how long it takes to build an R-Tree either bulk-loaded or not
24class BBoxBuildBench : public SkBenchmark {
25public:
26    BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
27                    SkBBoxHierarchy* tree)
28        : INHERITED(param)
29        , fTree(tree)
30        , fProc(proc)
31        , fBulkLoad(bulkLoad) {
32        fName.append("rtree_");
33        fName.append(name);
34        fName.append("_build");
35        if (fBulkLoad) {
36            fName.append("_bulk");
37        }
38        fIsRendering = false;
39    }
40    virtual ~BBoxBuildBench() {
41        fTree->unref();
42    }
43protected:
44    virtual const char* onGetName() SK_OVERRIDE {
45        return fName.c_str();
46    }
47    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
48        SkRandom rand;
49        for (int i = 0; i < this->getLoops(); ++i) {
50            for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
51                fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
52                              fBulkLoad);
53            }
54            fTree->flushDeferredInserts();
55            fTree->clear();
56        }
57    }
58private:
59    SkBBoxHierarchy* fTree;
60    MakeRectProc fProc;
61    SkString fName;
62    bool fBulkLoad;
63    typedef SkBenchmark INHERITED;
64};
65
66// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
67class BBoxQueryBench : public SkBenchmark {
68public:
69    enum QueryType {
70        kSmall_QueryType, // small queries
71        kLarge_QueryType, // large queries
72        kRandom_QueryType,// randomly sized queries
73        kFull_QueryType   // queries that cover everything
74    };
75
76    BBoxQueryBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
77                    QueryType q, SkBBoxHierarchy* tree)
78        : INHERITED(param)
79        , fTree(tree)
80        , fProc(proc)
81        , fBulkLoad(bulkLoad)
82        , fQuery(q) {
83        fName.append("rtree_");
84        fName.append(name);
85        fName.append("_query");
86        if (fBulkLoad) {
87            fName.append("_bulk");
88        }
89        fIsRendering = false;
90    }
91    virtual ~BBoxQueryBench() {
92        fTree->unref();
93    }
94protected:
95    virtual const char* onGetName() SK_OVERRIDE {
96        return fName.c_str();
97    }
98    virtual void onPreDraw() SK_OVERRIDE {
99        SkRandom rand;
100        for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
101            fTree->insert(reinterpret_cast<void*>(j),
102                          fProc(rand, j, NUM_QUERY_RECTS),
103                          fBulkLoad);
104        }
105        fTree->flushDeferredInserts();
106    }
107
108    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
109        SkRandom rand;
110        for (int i = 0; i < this->getLoops(); ++i) {
111            SkTDArray<void*> hits;
112            SkIRect query;
113            switch(fQuery) {
114                case kSmall_QueryType:
115                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
116                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
117                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
118                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
119                    break;
120                case kLarge_QueryType:
121                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
122                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
123                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
124                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
125                    break;
126                case kFull_QueryType:
127                    query.fLeft = -GENERATE_EXTENTS;
128                    query.fTop = -GENERATE_EXTENTS;
129                    query.fRight = 2 * GENERATE_EXTENTS;
130                    query.fBottom = 2 * GENERATE_EXTENTS;
131                    break;
132                default: // fallthrough
133                case kRandom_QueryType:
134                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
135                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
136                    query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
137                    query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
138                    break;
139            };
140            fTree->search(query, &hits);
141        }
142    }
143private:
144    SkBBoxHierarchy* fTree;
145    MakeRectProc fProc;
146    SkString fName;
147    bool fBulkLoad;
148    QueryType fQuery;
149    typedef SkBenchmark INHERITED;
150};
151
152static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) {
153    SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS};
154    return out;
155}
156
157static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
158    SkIRect out = {0, 0, index + 1, index + 1};
159    return out;
160}
161
162static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) {
163    SkIRect out = {0, 0, numRects - index, numRects - index};
164    return out;
165}
166
167static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
168    SkIRect out;
169    out.fLeft = index % GRID_WIDTH;
170    out.fTop = index / GRID_WIDTH;
171    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
172    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
173    return out;
174}
175static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
176    SkIRect out;
177    out.fLeft = index / GRID_WIDTH;
178    out.fTop = index % GRID_WIDTH;
179    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
180    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
181    return out;
182}
183
184static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects) {
185    SkIRect out;
186    out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
187    out.fTop    = rand.nextU() % GENERATE_EXTENTS;
188    out.fRight  = out.fLeft + (GENERATE_EXTENTS / 200);
189    out.fBottom = out.fTop + (GENERATE_EXTENTS / 200);
190    return out;
191}
192
193static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
194    SkIRect out;
195    out.fLeft   = rand.nextS() % GENERATE_EXTENTS;
196    out.fTop    = rand.nextS() % GENERATE_EXTENTS;
197    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
198    out.fBottom = out.fTop  + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
199    return out;
200}
201
202static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects) {
203    SkIRect out;
204    out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
205    out.fTop    = rand.nextU() % GENERATE_EXTENTS;
206    out.fRight  = out.fLeft + (GENERATE_EXTENTS / 3);
207    out.fBottom = out.fTop  + (GENERATE_EXTENTS / 3);
208    return out;
209}
210
211///////////////////////////////////////////////////////////////////////////////
212
213static inline SkBenchmark* Fact0(void* p) {
214    return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, false,
215                      SkRTree::Create(5, 16)));
216}
217static inline SkBenchmark* Fact1(void* p) {
218    return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, true,
219                      SkRTree::Create(5, 16)));
220}
221static inline SkBenchmark* Fact2(void* p) {
222    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
223                      SkRTree::Create(5, 16, 1, false)));
224}
225static inline SkBenchmark* Fact3(void* p) {
226    return SkNEW_ARGS(BBoxQueryBench, (p, "XYordered", &make_XYordered_rects, true,
227                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
228}
229static inline SkBenchmark* Fact4(void* p) {
230    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
231                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
232}
233
234static inline SkBenchmark* Fact5(void* p) {
235    return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, false,
236                      SkRTree::Create(5, 16)));
237}
238static inline SkBenchmark* Fact6(void* p) {
239    return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, true,
240                      SkRTree::Create(5, 16)));
241}
242static inline SkBenchmark* Fact7(void* p) {
243    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
244                      SkRTree::Create(5, 16, 1, false)));
245}
246static inline SkBenchmark* Fact8(void* p) {
247    return SkNEW_ARGS(BBoxQueryBench, (p, "YXordered", &make_YXordered_rects, true,
248                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
249}
250static inline SkBenchmark* Fact9(void* p) {
251    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
252                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
253}
254
255static inline SkBenchmark* Fact10(void* p) {
256    return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
257                      SkRTree::Create(5, 16)));
258}
259static inline SkBenchmark* Fact11(void* p) {
260    return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
261                      SkRTree::Create(5, 16)));
262}
263static inline SkBenchmark* Fact12(void* p) {
264    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)random", &make_random_rects, true,
265                      SkRTree::Create(5, 16, 1, false)));
266}
267static inline SkBenchmark* Fact13(void* p) {
268    return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
269                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
270}
271static inline SkBenchmark* Fact14(void* p) {
272    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)random", &make_random_rects, true,
273                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
274}
275
276static inline SkBenchmark* Fact15(void* p) {
277    return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
278                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
279}
280static inline SkBenchmark* Fact16(void* p) {
281    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)concentric",
282                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
283}
284static inline SkBenchmark* Fact17(void* p) {
285    return SkNEW_ARGS(BBoxQueryBench, (p, "concentric", &make_concentric_rects_increasing, true,
286                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
287}
288static inline SkBenchmark* Fact18(void* p) {
289    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)concentric", &make_concentric_rects_increasing, true,
290                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
291}
292
293static BenchRegistry gReg18(Fact18);
294static BenchRegistry gReg17(Fact17);
295static BenchRegistry gReg16(Fact16);
296static BenchRegistry gReg15(Fact15);
297static BenchRegistry gReg14(Fact14);
298static BenchRegistry gReg13(Fact13);
299static BenchRegistry gReg12(Fact12);
300static BenchRegistry gReg11(Fact11);
301static BenchRegistry gReg10(Fact10);
302static BenchRegistry gReg9(Fact9);
303static BenchRegistry gReg8(Fact8);
304static BenchRegistry gReg7(Fact7);
305static BenchRegistry gReg6(Fact6);
306static BenchRegistry gReg5(Fact5);
307static BenchRegistry gReg4(Fact4);
308static BenchRegistry gReg3(Fact3);
309static BenchRegistry gReg2(Fact2);
310static BenchRegistry gReg1(Fact1);
311static BenchRegistry gReg0(Fact0);
312