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 "Benchmark.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 RTreeBuildBench : public Benchmark {
25public:
26    RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad,
27                    SkBBoxHierarchy* tree)
28        : fTree(tree)
29        , fProc(proc)
30        , fBulkLoad(bulkLoad) {
31        fName.append("rtree_");
32        fName.append(name);
33        fName.append("_build");
34        if (fBulkLoad) {
35            fName.append("_bulk");
36        }
37    }
38
39    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
40        return backend == kNonRendering_Backend;
41    }
42
43    virtual ~RTreeBuildBench() {
44        fTree->unref();
45    }
46protected:
47    virtual const char* onGetName() SK_OVERRIDE {
48        return fName.c_str();
49    }
50    virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
51        SkRandom rand;
52        for (int i = 0; i < loops; ++i) {
53            for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
54                fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
55                              fBulkLoad);
56            }
57            fTree->flushDeferredInserts();
58            fTree->clear();
59        }
60    }
61private:
62    SkBBoxHierarchy* fTree;
63    MakeRectProc fProc;
64    SkString fName;
65    bool fBulkLoad;
66    typedef Benchmark INHERITED;
67};
68
69// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
70class RTreeQueryBench : public Benchmark {
71public:
72    enum QueryType {
73        kSmall_QueryType, // small queries
74        kLarge_QueryType, // large queries
75        kRandom_QueryType,// randomly sized queries
76        kFull_QueryType   // queries that cover everything
77    };
78
79    RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad,
80                    QueryType q, SkBBoxHierarchy* tree)
81        : fTree(tree)
82        , fProc(proc)
83        , fBulkLoad(bulkLoad)
84        , fQuery(q) {
85        fName.append("rtree_");
86        fName.append(name);
87        fName.append("_query");
88        if (fBulkLoad) {
89            fName.append("_bulk");
90        }
91    }
92
93    virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
94        return backend == kNonRendering_Backend;
95    }
96
97    virtual ~RTreeQueryBench() {
98        fTree->unref();
99    }
100protected:
101    virtual const char* onGetName() SK_OVERRIDE {
102        return fName.c_str();
103    }
104    virtual void onPreDraw() SK_OVERRIDE {
105        SkRandom rand;
106        for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
107            fTree->insert(reinterpret_cast<void*>(j),
108                          fProc(rand, j, NUM_QUERY_RECTS),
109                          fBulkLoad);
110        }
111        fTree->flushDeferredInserts();
112    }
113
114    virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
115        SkRandom rand;
116        for (int i = 0; i < loops; ++i) {
117            SkTDArray<void*> hits;
118            SkIRect query;
119            switch(fQuery) {
120                case kSmall_QueryType:
121                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
122                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
123                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
124                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
125                    break;
126                case kLarge_QueryType:
127                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
128                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
129                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
130                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
131                    break;
132                case kFull_QueryType:
133                    query.fLeft = -GENERATE_EXTENTS;
134                    query.fTop = -GENERATE_EXTENTS;
135                    query.fRight = 2 * GENERATE_EXTENTS;
136                    query.fBottom = 2 * GENERATE_EXTENTS;
137                    break;
138                default: // fallthrough
139                case kRandom_QueryType:
140                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
141                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
142                    query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
143                    query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
144                    break;
145            };
146            fTree->search(query, &hits);
147        }
148    }
149private:
150    SkBBoxHierarchy* fTree;
151    MakeRectProc fProc;
152    SkString fName;
153    bool fBulkLoad;
154    QueryType fQuery;
155    typedef Benchmark INHERITED;
156};
157
158static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
159    SkIRect out = {0, 0, index + 1, index + 1};
160    return out;
161}
162
163static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
164    SkIRect out;
165    out.fLeft = index % GRID_WIDTH;
166    out.fTop = index / GRID_WIDTH;
167    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
168    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
169    return out;
170}
171static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
172    SkIRect out;
173    out.fLeft = index / GRID_WIDTH;
174    out.fTop = index % GRID_WIDTH;
175    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
176    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
177    return out;
178}
179
180static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
181    SkIRect out;
182    out.fLeft   = rand.nextS() % GENERATE_EXTENTS;
183    out.fTop    = rand.nextS() % GENERATE_EXTENTS;
184    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
185    out.fBottom = out.fTop  + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
186    return out;
187}
188
189///////////////////////////////////////////////////////////////////////////////
190
191DEF_BENCH(
192    return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false,
193                      SkRTree::Create(5, 16)));
194)
195DEF_BENCH(
196    return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true,
197                      SkRTree::Create(5, 16)));
198)
199DEF_BENCH(
200    return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
201                      SkRTree::Create(5, 16, 1, false)));
202)
203DEF_BENCH(
204    return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true,
205                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
206)
207DEF_BENCH(
208    return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
209                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
210)
211
212DEF_BENCH(
213    return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false,
214                      SkRTree::Create(5, 16)));
215)
216DEF_BENCH(
217    return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true,
218                      SkRTree::Create(5, 16)));
219)
220DEF_BENCH(
221    return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
222                      SkRTree::Create(5, 16, 1, false)));
223)
224DEF_BENCH(
225    return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true,
226                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
227)
228DEF_BENCH(
229    return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
230                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
231)
232
233DEF_BENCH(
234    return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false,
235                      SkRTree::Create(5, 16)));
236)
237DEF_BENCH(
238    return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true,
239                      SkRTree::Create(5, 16)));
240)
241DEF_BENCH(
242    return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true,
243                      SkRTree::Create(5, 16, 1, false)));
244)
245DEF_BENCH(
246    return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true,
247                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
248)
249DEF_BENCH(
250    return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true,
251                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
252)
253
254DEF_BENCH(
255    return SkNEW_ARGS(RTreeBuildBench, ("concentric",
256                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
257)
258DEF_BENCH(
259    return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric",
260                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
261)
262DEF_BENCH(
263    return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true,
264                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
265)
266DEF_BENCH(
267    return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true,
268                      RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
269)
270