From 8c902126a90f37b6a038a78488c6215fa0c34b7d Mon Sep 17 00:00:00 2001 From: "sglez@google.com" Date: Fri, 30 Aug 2013 17:27:47 +0000 Subject: R-Tree -- Don't sort draw commands unless specified. We expect Webkit and Bink to give us draw commands in a reasonable x,y order. We can maintain correctness and get a 17% recording speedup for the R-Tree by not sorting in x and y when bulk-loading. R=caryclark@google.com, reed@google.com Review URL: https://codereview.chromium.org/23480002 git-svn-id: http://skia.googlecode.com/svn/trunk@11037 2bbb7eff-a529-9590-31e7-b0007b416f81 --- bench/RTreeBench.cpp | 112 ++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 102 insertions(+), 10 deletions(-) (limited to 'bench/RTreeBench.cpp') diff --git a/bench/RTreeBench.cpp b/bench/RTreeBench.cpp index bce1b67513..d017f39972 100644 --- a/bench/RTreeBench.cpp +++ b/bench/RTreeBench.cpp @@ -17,6 +17,7 @@ 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; +static const int GRID_WIDTH = 100; typedef SkIRect (*MakeRectProc)(SkMWCRandom&, int, int); @@ -163,6 +164,23 @@ static inline SkIRect make_concentric_rects_decreasing(SkMWCRandom&, int index, return out; } +static inline SkIRect make_XYordered_rects(SkMWCRandom& rand, int index, int numRects) { + SkIRect out; + out.fLeft = index % GRID_WIDTH; + out.fTop = index / GRID_WIDTH; + out.fRight = 1 + rand.nextU() % (GENERATE_EXTENTS / 3); + out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS / 3); + return out; +} +static inline SkIRect make_YXordered_rects(SkMWCRandom& rand, int index, int numRects) { + SkIRect out; + out.fLeft = index / GRID_WIDTH; + out.fTop = index % GRID_WIDTH; + out.fRight = 1 + rand.nextU() % (GENERATE_EXTENTS / 3); + out.fBottom = 1 + rand.nextU() % (GENERATE_EXTENTS / 3); + return out; +} + static inline SkIRect make_point_rects(SkMWCRandom& rand, int index, int numRects) { SkIRect out; out.fLeft = rand.nextU() % GENERATE_EXTENTS; @@ -193,28 +211,102 @@ static inline SkIRect make_large_rects(SkMWCRandom& rand, int index, int numRect /////////////////////////////////////////////////////////////////////////////// static inline SkBenchmark* Fact0(void* p) { - return SkNEW_ARGS(BBoxBuildBench, (p, "random", &make_random_rects, true, + 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, "random", &make_random_rects, false, + 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, "concentric", - &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); + 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, "random", &make_random_rects, true, + 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, "random", &make_random_rects, false, + 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 BenchRegistry gReg0(Fact0); -static BenchRegistry gReg1(Fact1); -static BenchRegistry gReg2(Fact2); -static BenchRegistry gReg3(Fact3); +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); + -- cgit v1.2.3