bench/RTreeBench.cpp

/*
 * Copyright 2012 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkBenchmark.h"
#include "SkCanvas.h"
#include "SkRTree.h"
#include "SkRandom.h"
#include "SkString.h"

// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
static const int GENERATE_EXTENTS = 1000;
static const int NUM_BUILD_RECTS = 500;
static const int NUM_QUERY_RECTS = 5000;
static const int GRID_WIDTH = 100;

typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);

// Time how long it takes to build an R-Tree either bulk-loaded or not
class BBoxBuildBench : public SkBenchmark {
public:
    BBoxBuildBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
                    SkBBoxHierarchy* tree)
        : INHERITED(param)
        , fTree(tree)
        , fProc(proc)
        , fBulkLoad(bulkLoad) {
        fName.append("rtree_");
        fName.append(name);
        fName.append("_build");
        if (fBulkLoad) {
            fName.append("_bulk");
        }
        fIsRendering = false;
    }
    virtual ~BBoxBuildBench() {
        fTree->unref();
    }
protected:
    virtual const char* onGetName() SK_OVERRIDE {
        return fName.c_str();
    }
    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
        SkRandom rand;
        for (int i = 0; i < this->getLoops(); ++i) {
            for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
                fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
                              fBulkLoad);
            }
            fTree->flushDeferredInserts();
            fTree->clear();
        }
    }
private:
    SkBBoxHierarchy* fTree;
    MakeRectProc fProc;
    SkString fName;
    bool fBulkLoad;
    typedef SkBenchmark INHERITED;
};

// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not
class BBoxQueryBench : public SkBenchmark {
public:
    enum QueryType {
        kSmall_QueryType, // small queries
        kLarge_QueryType, // large queries
        kRandom_QueryType,// randomly sized queries
        kFull_QueryType   // queries that cover everything
    };

    BBoxQueryBench(void* param, const char* name, MakeRectProc proc, bool bulkLoad,
                    QueryType q, SkBBoxHierarchy* tree)
        : INHERITED(param)
        , fTree(tree)
        , fProc(proc)
        , fBulkLoad(bulkLoad)
        , fQuery(q) {
        fName.append("rtree_");
        fName.append(name);
        fName.append("_query");
        if (fBulkLoad) {
            fName.append("_bulk");
        }
        fIsRendering = false;
    }
    virtual ~BBoxQueryBench() {
        fTree->unref();
    }
protected:
    virtual const char* onGetName() SK_OVERRIDE {
        return fName.c_str();
    }
    virtual void onPreDraw() SK_OVERRIDE {
        SkRandom rand;
        for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
            fTree->insert(reinterpret_cast<void*>(j),
                          fProc(rand, j, NUM_QUERY_RECTS),
                          fBulkLoad);
        }
        fTree->flushDeferredInserts();
    }

    virtual void onDraw(SkCanvas* canvas) SK_OVERRIDE {
        SkRandom rand;
        for (int i = 0; i < this->getLoops(); ++i) {
            SkTDArray<void*> hits;
            SkIRect query;
            switch(fQuery) {
                case kSmall_QueryType:
                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 20);
                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 20);
                    break;
                case kLarge_QueryType:
                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
                    query.fRight = query.fLeft + (GENERATE_EXTENTS / 2);
                    query.fBottom = query.fTop + (GENERATE_EXTENTS / 2);
                    break;
                case kFull_QueryType:
                    query.fLeft = -GENERATE_EXTENTS;
                    query.fTop = -GENERATE_EXTENTS;
                    query.fRight = 2 * GENERATE_EXTENTS;
                    query.fBottom = 2 * GENERATE_EXTENTS;
                    break;
                default: // fallthrough
                case kRandom_QueryType:
                    query.fLeft = rand.nextU() % GENERATE_EXTENTS;
                    query.fTop = rand.nextU() % GENERATE_EXTENTS;
                    query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
                    query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2);
                    break;
            };
            fTree->search(query, &hits);
        }
    }
private:
    SkBBoxHierarchy* fTree;
    MakeRectProc fProc;
    SkString fName;
    bool fBulkLoad;
    QueryType fQuery;
    typedef SkBenchmark INHERITED;
};

static inline SkIRect make_simple_rect(SkRandom&, int index, int numRects) {
    SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS};
    return out;
}

static inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) {
    SkIRect out = {0, 0, index + 1, index + 1};
    return out;
}

static inline SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) {
    SkIRect out = {0, 0, numRects - index, numRects - index};
    return out;
}

static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
    SkIRect out;
    out.fLeft = index % GRID_WIDTH;
    out.fTop = index / GRID_WIDTH;
    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
    return out;
}
static inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
    SkIRect out;
    out.fLeft = index / GRID_WIDTH;
    out.fTop = index % GRID_WIDTH;
    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
    out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3);
    return out;
}

static inline SkIRect make_point_rects(SkRandom& rand, int index, int numRects) {
    SkIRect out;
    out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
    out.fTop    = rand.nextU() % GENERATE_EXTENTS;
    out.fRight  = out.fLeft + (GENERATE_EXTENTS / 200);
    out.fBottom = out.fTop + (GENERATE_EXTENTS / 200);
    return out;
}

static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) {
    SkIRect out;
    out.fLeft   = rand.nextS() % GENERATE_EXTENTS;
    out.fTop    = rand.nextS() % GENERATE_EXTENTS;
    out.fRight  = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
    out.fBottom = out.fTop  + 1 + rand.nextU() % (GENERATE_EXTENTS / 5);
    return out;
}

static inline SkIRect make_large_rects(SkRandom& rand, int index, int numRects) {
    SkIRect out;
    out.fLeft   = rand.nextU() % GENERATE_EXTENTS;
    out.fTop    = rand.nextU() % GENERATE_EXTENTS;
    out.fRight  = out.fLeft + (GENERATE_EXTENTS / 3);
    out.fBottom = out.fTop  + (GENERATE_EXTENTS / 3);
    return out;
}

///////////////////////////////////////////////////////////////////////////////

static inline SkBenchmark* Fact0(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, false,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact1(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "XYordered", &make_XYordered_rects, true,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact2(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
                      SkRTree::Create(5, 16, 1, false)));
}
static inline SkBenchmark* Fact3(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "XYordered", &make_XYordered_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact4(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)XYordered", &make_XYordered_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
}

static inline SkBenchmark* Fact5(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, false,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact6(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "YXordered", &make_YXordered_rects, true,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact7(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
                      SkRTree::Create(5, 16, 1, false)));
}
static inline SkBenchmark* Fact8(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "YXordered", &make_YXordered_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact9(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)YXordered", &make_YXordered_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
}

static inline SkBenchmark* Fact10(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact11(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true,
                      SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact12(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)random", &make_random_rects, true,
                      SkRTree::Create(5, 16, 1, false)));
}
static inline SkBenchmark* Fact13(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact14(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)random", &make_random_rects, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
}

static inline SkBenchmark* Fact15(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "concentric",
                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact16(void* p) {
    return SkNEW_ARGS(BBoxBuildBench, (p, "(unsorted)concentric",
                      &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
}
static inline SkBenchmark* Fact17(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "concentric", &make_concentric_rects_increasing, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
}
static inline SkBenchmark* Fact18(void* p) {
    return SkNEW_ARGS(BBoxQueryBench, (p, "(unsorted)concentric", &make_concentric_rects_increasing, true,
                      BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
}

static BenchRegistry gReg18(Fact18);
static BenchRegistry gReg17(Fact17);
static BenchRegistry gReg16(Fact16);
static BenchRegistry gReg15(Fact15);
static BenchRegistry gReg14(Fact14);
static BenchRegistry gReg13(Fact13);
static BenchRegistry gReg12(Fact12);
static BenchRegistry gReg11(Fact11);
static BenchRegistry gReg10(Fact10);
static BenchRegistry gReg9(Fact9);
static BenchRegistry gReg8(Fact8);
static BenchRegistry gReg7(Fact7);
static BenchRegistry gReg6(Fact6);
static BenchRegistry gReg5(Fact5);
static BenchRegistry gReg4(Fact4);
static BenchRegistry gReg3(Fact3);
static BenchRegistry gReg2(Fact2);
static BenchRegistry gReg1(Fact1);
static BenchRegistry gReg0(Fact0);