src/third_party/skia/bench/RTreeBench.cpp

   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:
  16 static const SkScalar GENERATE_EXTENTS = 1000.0f;
  17 static const int NUM_BUILD_RECTS = 500;
  18 static const int NUM_QUERY_RECTS = 5000;
  19 static const int GRID_WIDTH = 100;
  20
  21 typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
  22
  23 // Time how long it takes to build an R-Tree either bulk-loaded or not
  24 class RTreeBuildBench : public Benchmark {
  25 public:
  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     }
  46 protected:
  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     }
  61 private:
  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
  70 class RTreeQueryBench : public Benchmark {
  71 public:
  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     }
 100 protected:
 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             SkRect query;
 119             switch(fQuery) {
 120                 case kSmall_QueryType:
 121                     query.fLeft   = rand.nextRangeF(0, GENERATE_EXTENTS);
 122                     query.fTop    = rand.nextRangeF(0, 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.nextRangeF(0, GENERATE_EXTENTS);
 128                     query.fTop    = rand.nextRangeF(0, 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.nextRangeF(0, GENERATE_EXTENTS);
 141                     query.fTop    = rand.nextRangeF(0, GENERATE_EXTENTS);
 142                     query.fRight  = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
 143                     query.fBottom = query.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
 144                     break;
 145             };
 146             fTree->search(query, &hits);
 147         }
 148     }
 149 private:
 150     SkBBoxHierarchy* fTree;
 151     MakeRectProc fProc;
 152     SkString fName;
 153     bool fBulkLoad;
 154     QueryType fQuery;
 155     typedef Benchmark INHERITED;
 156 };
 157
 158 static inline SkRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
 159     SkRect out = SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
 160     return out;
 161 }
 162
 163 static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
 164     SkRect out;
 165     out.fLeft   = SkIntToScalar(index % GRID_WIDTH);
 166     out.fTop    = SkIntToScalar(index / GRID_WIDTH);
 167     out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
 168     out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
 169     return out;
 170 }
 171 static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
 172     SkRect out;
 173     out.fLeft   = SkIntToScalar(index / GRID_WIDTH);
 174     out.fTop    = SkIntToScalar(index % GRID_WIDTH);
 175     out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
 176     out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
 177     return out;
 178 }
 179
 180 static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) {
 181     SkRect out;
 182     out.fLeft   = rand.nextRangeF(0, GENERATE_EXTENTS);
 183     out.fTop    = rand.nextRangeF(0, GENERATE_EXTENTS);
 184     out.fRight  = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
 185     out.fBottom = out.fTop  + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
 186     return out;
 187 }
 188
 189 ///////////////////////////////////////////////////////////////////////////////
 190
 191 DEF_BENCH(
 192     return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false,
 193                       SkRTree::Create(5, 16)));
 194 )
 195 DEF_BENCH(
 196     return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true,
 197                       SkRTree::Create(5, 16)));
 198 )
 199 DEF_BENCH(
 200     return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
 201                       SkRTree::Create(5, 16, 1, false)));
 202 )
 203 DEF_BENCH(
 204     return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true,
 205                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
 206 )
 207 DEF_BENCH(
 208     return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
 209                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
 210 )
 211
 212 DEF_BENCH(
 213     return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false,
 214                       SkRTree::Create(5, 16)));
 215 )
 216 DEF_BENCH(
 217     return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true,
 218                       SkRTree::Create(5, 16)));
 219 )
 220 DEF_BENCH(
 221     return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
 222                       SkRTree::Create(5, 16, 1, false)));
 223 )
 224 DEF_BENCH(
 225     return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true,
 226                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
 227 )
 228 DEF_BENCH(
 229     return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
 230                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
 231 )
 232
 233 DEF_BENCH(
 234     return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false,
 235                       SkRTree::Create(5, 16)));
 236 )
 237 DEF_BENCH(
 238     return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true,
 239                       SkRTree::Create(5, 16)));
 240 )
 241 DEF_BENCH(
 242     return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true,
 243                       SkRTree::Create(5, 16, 1, false)));
 244 )
 245 DEF_BENCH(
 246     return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true,
 247                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
 248 )
 249 DEF_BENCH(
 250     return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true,
 251                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
 252 )
 253
 254 DEF_BENCH(
 255     return SkNEW_ARGS(RTreeBuildBench, ("concentric",
 256                       &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
 257 )
 258 DEF_BENCH(
 259     return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric",
 260                       &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
 261 )
 262 DEF_BENCH(
 263     return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true,
 264                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
 265 )
 266 DEF_BENCH(
 267     return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true,
 268                       RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
 269 )