1/*
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
8#include "Benchmark.h"
9#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
25class QuadTreeBuildBench : public Benchmark {
26public:
27    QuadTreeBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree)
28        : 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
39    virtual ~QuadTreeBuildBench() {
40        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;
60    typedef Benchmark INHERITED;
61};
62
63// Time how long it takes to perform queries on an QuadTree
64class QuadTreeQueryBench : public Benchmark {
65public:
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
73    QuadTreeQueryBench(const char* name, MakeRectProc proc,
74                    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
87    virtual ~QuadTreeQueryBench() {
88        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;
144    typedef Benchmark INHERITED;
145};
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(
182    return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects,
183                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
184)
185DEF_BENCH(
186    return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects,
187                      QuadTreeQueryBench::kRandom_QueryType,
188                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
189)
190DEF_BENCH(
191    return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects,
192                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
193)
194DEF_BENCH(
195    return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects,
196                      QuadTreeQueryBench::kRandom_QueryType,
197                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
198)
199DEF_BENCH(
200    return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects,
201                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
202)
203DEF_BENCH(
204    return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects,
205                      QuadTreeQueryBench::kRandom_QueryType,
206                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
207)
208DEF_BENCH(
209    return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing,
210                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
211)
212DEF_BENCH(
213    return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing,
214                      QuadTreeQueryBench::kRandom_QueryType,
215                      SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
216)
217