From 4477c3c0e6eb064772aefe8737425cd1c2ce557f Mon Sep 17 00:00:00 2001 From: mtklein Date: Mon, 27 Oct 2014 10:27:10 -0700 Subject: Cut down SkBBH API more. - The expected case is now a single bulk-load insert() call instead of N; - reserve() and flushDeferredInserts() can fold into insert() now; - SkBBH subclasses may take ownership of the bounds This appears to be a performance no-op on both my Mac and N5. I guess even the simplest indirect branch predictor ("same as last time") can predict the repeated virtual calls to SkBBH::insert() perfectly. BUG=skia: Review URL: https://codereview.chromium.org/670213002 --- bench/RTreeBench.cpp | 203 +++++++++++++++------------------------------------ 1 file changed, 58 insertions(+), 145 deletions(-) (limited to 'bench/RTreeBench.cpp') diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp index 08d6bf4bdb..030d376017 100644 --- a/bench/RTreeBench.cpp +++ b/bench/RTreeBench.cpp @@ -1,4 +1,3 @@ - /* * Copyright 2012 Google Inc. * @@ -23,17 +22,10 @@ typedef SkRect (*MakeRectProc)(SkRandom&, int, int); // Time how long it takes to build an R-Tree either bulk-loaded or not class RTreeBuildBench : public Benchmark { public: - RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, - SkRTree* tree) + RTreeBuildBench(const char* name, MakeRectProc proc, SkRTree* tree) : fTree(tree) - , fProc(proc) - , fBulkLoad(bulkLoad) { - fName.append("rtree_"); - fName.append(name); - fName.append("_build"); - if (fBulkLoad) { - fName.append("_bulk"); - } + , fProc(proc) { + fName.printf("rtree_%s_build", name); } virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { @@ -49,11 +41,14 @@ protected: } virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { SkRandom rand; + SkAutoTMalloc rects(NUM_BUILD_RECTS); + for (int i = 0; i < NUM_BUILD_RECTS; ++i) { + rects[i] = fProc(rand, i, NUM_BUILD_RECTS); + } + for (int i = 0; i < loops; ++i) { - for (int j = 0; j < NUM_BUILD_RECTS; ++j) { - fTree->insert(j, fProc(rand, j, NUM_BUILD_RECTS), fBulkLoad); - } - fTree->flushDeferredInserts(); + fTree->insert(&rects, NUM_BUILD_RECTS); + SkASSERT(rects != NULL); // It'd break this bench if the tree took ownership of rects. fTree->clear(); } } @@ -61,32 +56,16 @@ private: SkRTree* fTree; MakeRectProc fProc; SkString fName; - bool fBulkLoad; typedef Benchmark INHERITED; }; // Time how long it takes to perform queries on an R-Tree, bulk-loaded or not class RTreeQueryBench : public Benchmark { public: - enum QueryType { - kSmall_QueryType, // small queries - kLarge_QueryType, // large queries - kRandom_QueryType,// randomly sized queries - kFull_QueryType // queries that cover everything - }; - - RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, - QueryType q, SkRTree* tree) + RTreeQueryBench(const char* name, MakeRectProc proc, SkRTree* tree) : fTree(tree) - , fProc(proc) - , fBulkLoad(bulkLoad) - , fQuery(q) { - fName.append("rtree_"); - fName.append(name); - fName.append("_query"); - if (fBulkLoad) { - fName.append("_bulk"); - } + , fProc(proc) { + fName.printf("rtree_%s_query", name); } virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { @@ -102,10 +81,11 @@ protected: } virtual void onPreDraw() SK_OVERRIDE { SkRandom rand; - for (int j = 0; j < NUM_QUERY_RECTS; ++j) { - fTree->insert(j, fProc(rand, j, NUM_QUERY_RECTS), fBulkLoad); + SkAutoTMalloc rects(NUM_QUERY_RECTS); + for (int i = 0; i < NUM_QUERY_RECTS; ++i) { + rects[i] = fProc(rand, i, NUM_QUERY_RECTS); } - fTree->flushDeferredInserts(); + fTree->insert(&rects, NUM_QUERY_RECTS); } virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { @@ -113,33 +93,10 @@ protected: for (int i = 0; i < loops; ++i) { SkTDArray hits; SkRect query; - switch(fQuery) { - case kSmall_QueryType: - query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); - query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); - query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); - query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); - break; - case kLarge_QueryType: - query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); - query.fTop = rand.nextRangeF(0, 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.nextRangeF(0, GENERATE_EXTENTS); - query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); - query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); - query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); - break; - }; + query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); + query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); + query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); + query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); fTree->search(query, &hits); } } @@ -147,8 +104,6 @@ private: SkBBoxHierarchy* fTree; MakeRectProc fProc; SkString fName; - bool fBulkLoad; - QueryType fQuery; typedef Benchmark INHERITED; }; @@ -185,82 +140,40 @@ static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) /////////////////////////////////////////////////////////////////////////////// -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true, - SkRTree::Create(5, 16, 1, false))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); -) - -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true, - SkRTree::Create(5, 16, 1, false))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); -) - -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, - SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true, - SkRTree::Create(5, 16, 1, false))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); -) - -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("concentric", - &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", - &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); -) -DEF_BENCH( - return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true, - RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); -) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeBuildBench, + ("concentric_unsorted", + &make_concentric_rects_increasing, + SkRTree::Create(5, 16, 1, false)));) + +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("XY_sorted", &make_XYordered_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("XY_unsorted", &make_XYordered_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("YX_sorted", &make_YXordered_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("YX_unsorted", &make_YXordered_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("random_sorted", &make_random_rects, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("random_unsorted", &make_random_rects, SkRTree::Create(5, 16, 1, false)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("concentric_sorted", &make_concentric_rects_increasing, SkRTree::Create(5, 16)));) +DEF_BENCH(return SkNEW_ARGS(RTreeQueryBench, + ("concentric_unsorted", + &make_concentric_rects_increasing, + SkRTree::Create(5, 16, 1, false)));) -- cgit v1.2.3