From 981b33abc65d968523d78d45e69cb071e8e03e91 Mon Sep 17 00:00:00 2001 From: "rileya@google.com" Date: Wed, 5 Sep 2012 18:36:17 +0000 Subject: Add R-Tree bench. Review URL: https://codereview.appspot.com/6497086 git-svn-id: http://skia.googlecode.com/svn/trunk@5404 2bbb7eff-a529-9590-31e7-b0007b416f81 --- bench/RTreeBench.cpp | 213 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 213 insertions(+) create mode 100644 bench/RTreeBench.cpp (limited to 'bench/RTreeBench.cpp') diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp new file mode 100644 index 0000000000..ece81c09d9 --- /dev/null +++ b/bench/RTreeBench.cpp @@ -0,0 +1,213 @@ + +/* + * 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 NUM_QUERIES = 1000; + +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) + , fName(name) + , fBulkLoad(bulkLoad) { } +protected: + virtual const char* onGetName() { + SkString str; + str.append("rtree_"); + str.append(fName); + str.append("_build"); + if (fBulkLoad) { + str.append("_bulk"); + } + return str.c_str(); + } + virtual void onDraw(SkCanvas* canvas) { + SkRandom rand; + for (int i = 0; i < SkBENCHLOOP(100); ++i) { + for (int j = 0; j < NUM_BUILD_RECTS; ++j) { + fTree->insert(reinterpret_cast(j), fProc(rand, j, NUM_BUILD_RECTS), + fBulkLoad); + } + fTree->flushDeferredInserts(); + fTree->clear(); + } + } +private: + SkBBoxHierarchy* fTree; + MakeRectProc fProc; + const char* 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) + , fName(name) + , fBulkLoad(bulkLoad) + , fQuery(q) { + SkRandom rand; + for (int j = 0; j < SkBENCHLOOP(NUM_QUERY_RECTS); ++j) { + fTree->insert(reinterpret_cast(j), fProc(rand, j, + SkBENCHLOOP(NUM_QUERY_RECTS)), fBulkLoad); + } + fTree->flushDeferredInserts(); + } +protected: + virtual const char* onGetName() { + SkString str; + str.append("rtree_"); + str.append(fName); + str.append("_query"); + if (fBulkLoad) { + str.append("_bulk"); + } + return str.c_str(); + } + virtual void onDraw(SkCanvas* canvas) { + SkRandom rand; + for (int i = 0; i < SkBENCHLOOP(NUM_QUERIES); ++i) { + SkTDArray 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; + const char* fName; + bool fBulkLoad; + QueryType fQuery; + typedef SkBenchmark INHERITED; +}; + +static SkIRect make_simple_rect(SkRandom&, int index, int numRects) { + SkIRect out = {0, 0, GENERATE_EXTENTS, GENERATE_EXTENTS}; + return out; +} + +static SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { + SkIRect out = {0, 0, index + 1, index + 1}; + return out; +} + +static SkIRect make_concentric_rects_decreasing(SkRandom&, int index, int numRects) { + SkIRect out = {0, 0, numRects - index, numRects - index}; + return out; +} + +static 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 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 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 SkBenchmark* Fact0(void* p) { + return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true, + SkRTree::Create(5, 16))); +} +static SkBenchmark* Fact1(void* p) { + return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, false, + SkRTree::Create(5, 16))); +} +static SkBenchmark* Fact2(void* p) { + return SkNEW_ARGS(BBoxBuildBench, (p, "concentric", + &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); +} +static SkBenchmark* Fact3(void* p) { + return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, true, + BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); +} +static SkBenchmark* Fact4(void* p) { + return SkNEW_ARGS(BBoxQueryBench, (p, "random", &make_random_rects, false, + BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); +} + +static BenchRegistry gReg0(Fact0); +static BenchRegistry gReg1(Fact1); +static BenchRegistry gReg2(Fact2); +static BenchRegistry gReg3(Fact3); +static BenchRegistry gReg4(Fact4); + -- cgit v1.2.3