src/third_party/skia/bench/QuadTreeBench.cpp

   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:
  15 static const int GENERATE_EXTENTS = 1000;
  16 static const int NUM_BUILD_RECTS = 500;
  17 static const int NUM_QUERY_RECTS = 5000;
  18 static const int GRID_WIDTH = 100;
  19 static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB(
  20     -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS);
  21
  22 typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
  23
  24 // Time how long it takes to build an QuadTree
  25 class QuadTreeBuildBench : public Benchmark {
  26 public:
  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     }
  42 protected:
  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     }
  56 private:
  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
  64 class QuadTreeQueryBench : public Benchmark {
  65 public:
  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     }
  90 protected:
  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     }
 139 private:
 140     SkBBoxHierarchy* fTree;
 141     MakeRectProc fProc;
 142     SkString fName;
 143     QueryType fQuery;
 144     typedef Benchmark INHERITED;
 145 };
 146
 147 static 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
 152 static 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
 161 static 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
 170 static 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
 181 DEF_BENCH(
 182     return SkNEW_ARGS(QuadTreeBuildBench, ("XYordered", &make_XYordered_rects,
 183                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 184 )
 185 DEF_BENCH(
 186     return SkNEW_ARGS(QuadTreeQueryBench, ("XYordered", &make_XYordered_rects,
 187                       QuadTreeQueryBench::kRandom_QueryType,
 188                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 189 )
 190 DEF_BENCH(
 191     return SkNEW_ARGS(QuadTreeBuildBench, ("YXordered", &make_YXordered_rects,
 192                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 193 )
 194 DEF_BENCH(
 195     return SkNEW_ARGS(QuadTreeQueryBench, ("YXordered", &make_YXordered_rects,
 196                       QuadTreeQueryBench::kRandom_QueryType,
 197                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 198 )
 199 DEF_BENCH(
 200     return SkNEW_ARGS(QuadTreeBuildBench, ("random", &make_random_rects,
 201                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 202 )
 203 DEF_BENCH(
 204     return SkNEW_ARGS(QuadTreeQueryBench, ("random", &make_random_rects,
 205                       QuadTreeQueryBench::kRandom_QueryType,
 206                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 207 )
 208 DEF_BENCH(
 209     return SkNEW_ARGS(QuadTreeBuildBench, ("concentric", &make_concentric_rects_increasing,
 210                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 211 )
 212 DEF_BENCH(
 213     return SkNEW_ARGS(QuadTreeQueryBench, ("concentric", &make_concentric_rects_increasing,
 214                       QuadTreeQueryBench::kRandom_QueryType,
 215                       SkNEW_ARGS(SkQuadTree, (QUAD_TREE_BOUNDS))));
 216 )