Home | History | Annotate | Download | only in bench 
      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:
     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     }
     40     virtual ~BBoxBuildBench() {
     41         fTree->unref();
     42     }
     43 protected:
     44     virtual const char* onGetName() {
     45         return fName.c_str();
     46     }
     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 
     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     }
     97     virtual ~BBoxQueryBench() {
     98         fTree->unref();
     99     }
    100 protected:
    101     virtual const char* onGetName() {
    102         return fName.c_str();
    103     }
    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 
    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 
    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 
    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 
    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 
    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 
    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 
    192 static inline SkBenchmark* Fact0(void* p) {
    193     return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
    194                       SkRTree::Create(5, 16)));
    195 }
    196 static inline SkBenchmark* Fact1(void* p) {
    197     return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
    198                       SkRTree::Create(5, 16)));
    199 }
    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 }
    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 }
    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