Home | History | Annotate | Download | only in bench 
      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) override {
     30         return backend == kNonRendering_Backend;
     31     }
     32 
     33 protected:
     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     }
     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) override {
     64         return backend == kNonRendering_Backend;
     65     }
     66 protected:
     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     }
     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 new RTreeBuildBench("XY", &make_XYordered_rects));
    131 DEF_BENCH(return new RTreeBuildBench("YX", &make_YXordered_rects));
    132 DEF_BENCH(return new RTreeBuildBench("random", &make_random_rects));
    133 DEF_BENCH(return new RTreeBuildBench("concentric", &make_concentric_rects));
    134 
    135 DEF_BENCH(return new RTreeQueryBench("XY", &make_XYordered_rects));
    136 DEF_BENCH(return new RTreeQueryBench("YX", &make_YXordered_rects));
    137 DEF_BENCH(return new RTreeQueryBench("random", &make_random_rects));
    138 DEF_BENCH(return new RTreeQueryBench("concentric", &make_concentric_rects));
    139