bench/RTreeBench.cpp

   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:
  15 static const SkScalar GENERATE_EXTENTS = 1000.0f;
  16 static const int NUM_BUILD_RECTS = 500;
  17 static const int NUM_QUERY_RECTS = 5000;
  18 static const int GRID_WIDTH = 100;
  19
  20 typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
  21
  22 // Time how long it takes to build an R-Tree.
  23 class RTreeBuildBench : public Benchmark {
  24 public:
  25     RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
  26         fName.printf("rtree_%s_build", name);
  27     }
  28
  29     bool isSuitableFor(Backend backend) SK_OVERRIDE {
  30         return backend == kNonRendering_Backend;
  31     }
  32
  33 protected:
  34     const char* onGetName() SK_OVERRIDE {
  35         return fName.c_str();
  36     }
  37     void onDraw(const int loops, SkCanvas* canvas) SK_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 != NULL);  // It'd break this bench if the tree took ownership of rects.
  48         }
  49     }
  50 private:
  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.
  57 class RTreeQueryBench : public Benchmark {
  58 public:
  59     RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
  60         fName.printf("rtree_%s_query", name);
  61     }
  62
  63     bool isSuitableFor(Backend backend) SK_OVERRIDE {
  64         return backend == kNonRendering_Backend;
  65     }
  66 protected:
  67     const char* onGetName() SK_OVERRIDE {
  68         return fName.c_str();
  69     }
  70     void onPreDraw() SK_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(const int loops, SkCanvas* canvas) SK_OVERRIDE {
  80         SkRandom rand;
  81         for (int i = 0; i < loops; ++i) {
  82             SkTDArray<unsigned> 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     }
  91 private:
  92     SkRTree fTree;
  93     MakeRectProc fProc;
  94     SkString fName;
  95     typedef Benchmark INHERITED;
  96 };
  97
  98 static 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 }
 106 static 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
 115 static 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
 124 static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
 125     return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
 126 }
 127
 128 ///////////////////////////////////////////////////////////////////////////////
 129
 130 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("XY",         &make_XYordered_rects)));
 131 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("YX",         &make_YXordered_rects)));
 132 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("random",     &make_random_rects)));
 133 DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, ("concentric", &make_concentric_rects)));
 134
 135 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("XY",         &make_XYordered_rects)));
 136 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("YX",         &make_YXordered_rects)));
 137 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("random",     &make_random_rects)));
 138 DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects)));