• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
16 static const int GENERATE_EXTENTS = 1000;
17 static const int NUM_BUILD_RECTS = 500;
18 static const int NUM_QUERY_RECTS = 5000;
19 static const int NUM_QUERIES = 1000;
20 
21 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
22 
23 // Time how long it takes to build an R-Tree either bulk-loaded or not
24 class BBoxBuildBench : public SkBenchmark {
25 public:
BBoxBuildBench(void * param,const char * name,MakeRectProc proc,bool bulkLoad,SkBBoxHierarchy * tree)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     }
~BBoxBuildBench()40     virtual ~BBoxBuildBench() {
41         fTree->unref();
42     }
43 protected:
onGetName()44     virtual const char* onGetName() {
45         return fName.c_str();
46     }
onDraw(SkCanvas * canvas)47     virtual void onDraw(SkCanvas* canvas) {
48         SkRandom rand;
49         for (int i = 0; i < SkBENCHLOOP(100); ++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     }
58 private:
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
67 class BBoxQueryBench : public SkBenchmark {
68 public:
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 
BBoxQueryBench(void * param,const char * name,MakeRectProc proc,bool bulkLoad,QueryType q,SkBBoxHierarchy * tree)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         SkRandom rand;
90         for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) {
91             fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j,
92                            SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad);
93         }
94         fTree->flushDeferredInserts();
95         fIsRendering = false;
96     }
~BBoxQueryBench()97     virtual ~BBoxQueryBench() {
98         fTree->unref();
99     }
100 protected:
onGetName()101     virtual const char* onGetName() {
102         return fName.c_str();
103     }
onDraw(SkCanvas * canvas)104     virtual void onDraw(SkCanvas* canvas) {
105         SkRandom rand;
106         for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++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     }
139 private:
140     SkBBoxHierarchy* fTree;
141     MakeRectProc fProc;
142     SkString fName;
143     bool fBulkLoad;
144     QueryType fQuery;
145     typedef SkBenchmark INHERITED;
146 };
147 
make_simple_rect(SkRandom &,int index,int numRects)148 static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) {
149     SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS};
150     return out;
151 }
152 
make_concentric_rects_increasing(SkRandom &,int index,int numRects)153 static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
154     SkIRect out = {0, 0, index + 1, index + 1};
155     return out;
156 }
157 
make_concentric_rects_decreasing(SkRandom &,int index,int numRects)158 static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) {
159     SkIRect out = {0, 0, numRects - index, numRects - index};
160     return out;
161 }
162 
make_point_rects(SkRandom & rand,int index,int numRects)163 static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects) {
164     SkIRect out;
165     out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
166     out.fTop    = rand.nextU() % GENERATE_EXTENTS;
167     out.fRight  = out.fLeft + (GENERATE_EXTENTS / 200);
168     out.fBottom = out.fTop + (GENERATE_EXTENTS / 200);
169     return out;
170 }
171 
make_random_rects(SkRandom & rand,int index,int numRects)172 static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
173     SkIRect out;
174     out.fLeft   = rand.nextS() % GENERATE_EXTENTS;
175     out.fTop    = rand.nextS() % GENERATE_EXTENTS;
176     out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
177     out.fBottom = out.fTop  + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
178     return out;
179 }
180 
make_large_rects(SkRandom & rand,int index,int numRects)181 static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects) {
182     SkIRect out;
183     out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
184     out.fTop    = rand.nextU() % GENERATE_EXTENTS;
185     out.fRight  = out.fLeft + (GENERATE_EXTENTS / 3);
186     out.fBottom = out.fTop  + (GENERATE_EXTENTS / 3);
187     return out;
188 }
189 
190 ///////////////////////////////////////////////////////////////////////////////
191 
Fact0(void * p)192 static inline SkBenchmark* Fact0(void* p) {
193     return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
194                       SkRTree::Create(5, 16)));
195 }
Fact1(void * p)196 static inline SkBenchmark* Fact1(void* p) {
197     return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
198                       SkRTree::Create(5, 16)));
199 }
Fact2(void * p)200 static inline SkBenchmark* Fact2(void* p) {
201     return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
202                       &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
203 }
Fact3(void * p)204 static inline SkBenchmark* Fact3(void* p) {
205     return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
206                       BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
207 }
Fact4(void * p)208 static inline SkBenchmark* Fact4(void* p) {
209     return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false,
210                       BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
211 }
212 
213 static BenchRegistry gReg0(Fact0);
214 static BenchRegistry gReg1(Fact1);
215 static BenchRegistry gReg2(Fact2);
216 static BenchRegistry gReg3(Fact3);
217 static BenchRegistry gReg4(Fact4);
218