Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(2891)

Issues Search
    My Issues | Starred     Open | Closed | All

Unified Diff: bench/QuadTreeBench.cpp

Issue 131343011: Initial QuadTree implementation (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Fixed SkScalar conversion issue Created 6 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | gyp/bench.gyp » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: bench/QuadTreeBench.cpp
diff --git a/bench/RTreeBench.cpp b/bench/QuadTreeBench.cpp
similarity index 63%
copy from bench/RTreeBench.cpp
copy to bench/QuadTreeBench.cpp
index b51cc4c6a90b4dc552e9e3fda499bdf4a33c7dee..f1d5bcf36756672b6ab9506d844b21009a637b61 100644
--- a/bench/RTreeBench.cpp
+++ b/bench/QuadTreeBench.cpp
@@ -1,6 +1,5 @@
-
/*
- * Copyright 2012 Google Inc.
+ * Copyright 2014 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
@@ -8,7 +7,7 @@
#include "SkBenchmark.h"
#include "SkCanvas.h"
-#include "SkRTree.h"
+#include "SkQuadTree.h"
#include "SkRandom.h"
#include "SkString.h"
@@ -17,23 +16,20 @@ 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;
+static const SkIRect QUAD_TREE_BOUNDS = SkIRect::MakeLTRB(
+ -GENERATE_EXTENTS, -GENERATE_EXTENTS, 2 * GENERATE_EXTENTS, 2 * GENERATE_EXTENTS);
typedef SkIRect (*MakeRectProc)(SkRandom&, int, int);
-// Time how long it takes to build an R-Tree either bulk-loaded or not
+// Time how long it takes to build an QuadTree
class BBoxBuildBench : public SkBenchmark {
public:
- BBoxBuildBench(const char* name, MakeRectProc proc, bool bulkLoad,
- SkBBoxHierarchy* tree)
+ BBoxBuildBench(const char* name, MakeRectProc proc, SkBBoxHierarchy* tree)
: fTree(tree)
- , fProc(proc)
- , fBulkLoad(bulkLoad) {
- fName.append("rtree_");
+ , fProc(proc) {
+ fName.append("quadtree_");
fName.append(name);
fName.append("_build");
- if (fBulkLoad) {
- fName.append("_bulk");
- }
}
virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
@@ -52,9 +48,8 @@ protected:
for (int i = 0; i < loops; ++i) {
for (int j = 0; j < NUM_BUILD_RECTS; ++j) {
fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS),
- fBulkLoad);
+ false);
}
- fTree->flushDeferredInserts();
fTree->clear();
}
}
@@ -62,11 +57,10 @@ 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
+// Time how long it takes to perform queries on an QuadTree
class BBoxQueryBench : public SkBenchmark {
public:
enum QueryType {
@@ -76,18 +70,14 @@ public:
kFull_QueryType // queries that cover everything
};
- BBoxQueryBench(const char* name, MakeRectProc proc, bool bulkLoad,
+ BBoxQueryBench(const char* name, MakeRectProc proc,
QueryType q, SkBBoxHierarchy* tree)
: fTree(tree)
, fProc(proc)
- , fBulkLoad(bulkLoad)
, fQuery(q) {
- fName.append("rtree_");
+ fName.append("quadtree_");
fName.append(name);
fName.append("_query");
- if (fBulkLoad) {
- fName.append("_bulk");
- }
}
virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
@@ -106,7 +96,7 @@ protected:
for (int j = 0; j < NUM_QUERY_RECTS; ++j) {
fTree->insert(reinterpret_cast<void*>(j),
fProc(rand, j, NUM_QUERY_RECTS),
- fBulkLoad);
+ false);
}
fTree->flushDeferredInserts();
}
@@ -150,7 +140,6 @@ private:
SkBBoxHierarchy* fTree;
MakeRectProc fProc;
SkString fName;
- bool fBulkLoad;
QueryType fQuery;
typedef SkBenchmark INHERITED;
};
@@ -168,6 +157,7 @@ static inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRec
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;
@@ -189,81 +179,34 @@ static inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects)
///////////////////////////////////////////////////////////////////////////////
DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, false,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects, true,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
-
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, false,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects, true,
- SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxBuildBench, ("XYordered", &make_XYordered_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+ return SkNEW_ARGS(BBoxQueryBench, ("XYordered", &make_XYordered_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
-
DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, false,
- SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxBuildBench, ("YXordered", &make_YXordered_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects, true,
- SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxQueryBench, ("YXordered", &make_YXordered_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)random", &make_random_rects, true,
- SkRTree::Create(5, 16, 1, false)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
-)
-DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)random", &make_random_rects, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
-)
-
-DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("concentric",
- &make_concentric_rects_increasing, true, SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxBuildBench, ("random", &make_random_rects,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxBuildBench, ("(unsorted)concentric",
- &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false)));
+ return SkNEW_ARGS(BBoxQueryBench, ("random", &make_random_rects,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_increasing, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16)));
+ return SkNEW_ARGS(BBoxBuildBench, ("concentric", &make_concentric_rects_increasing,
+ SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
DEF_BENCH(
- return SkNEW_ARGS(BBoxQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true,
- BBoxQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false)));
+ return SkNEW_ARGS(BBoxQueryBench, ("concentric", &make_concentric_rects_increasing,
+ BBoxQueryBench::kRandom_QueryType, SkQuadTree::Create(QUAD_TREE_BOUNDS)));
)
« no previous file with comments | « no previous file | gyp/bench.gyp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698