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