1981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com/* 2981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * Copyright 2012 Google Inc. 3981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * 4981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * Use of this source code is governed by a BSD-style license that can be 5981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * found in the LICENSE file. 6981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com */ 7981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 8f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina#include "Benchmark.h" 9981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkCanvas.h" 10981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkRTree.h" 11981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkRandom.h" 12981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkString.h" 13981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 14981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs: 15533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinstatic const SkScalar GENERATE_EXTENTS = 1000.0f; 16981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comstatic const int NUM_BUILD_RECTS = 500; 17981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comstatic const int NUM_QUERY_RECTS = 5000; 188c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.comstatic const int GRID_WIDTH = 100; 19981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 20533eb782edaa0b6fece6166d3001edf72ec39f11mtkleintypedef SkRect (*MakeRectProc)(SkRandom&, int, int); 21981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 22a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein// Time how long it takes to build an R-Tree. 23f168b86d7fafc5c20c87bebc6fd393cb17e120catfarinaclass RTreeBuildBench : public Benchmark { 24981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.compublic: 25a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) { 264477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein fName.printf("rtree_%s_build", name); 2761348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com } 28644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 2936352bf5e38f45a70ee4f4fc132a38048d38206dmtklein bool isSuitableFor(Backend backend) override { 30644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org return backend == kNonRendering_Backend; 31644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org } 32644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 3361348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.comprotected: 3436352bf5e38f45a70ee4f4fc132a38048d38206dmtklein const char* onGetName() override { 3561348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com return fName.c_str(); 36981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 372880df2609eba09b555ca37be04b6ad89290c765Tom Hudson void onDraw(int loops, SkCanvas* canvas) override { 38e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 394477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS); 404477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein for (int i = 0; i < NUM_BUILD_RECTS; ++i) { 414477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein rects[i] = fProc(rand, i, NUM_BUILD_RECTS); 424477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein } 434477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein 443361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org for (int i = 0; i < loops; ++i) { 45a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein SkRTree tree; 46bfd5bff75c0ce27a70f02e4b5578d66aa9d6e306mtklein tree.insert(rects.get(), NUM_BUILD_RECTS); 472880df2609eba09b555ca37be04b6ad89290c765Tom Hudson SkASSERT(rects != nullptr); // It'd break this bench if the tree took ownership of rects. 48981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 49981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 50981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprivate: 51981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com MakeRectProc fProc; 5261348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com SkString fName; 53f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina typedef Benchmark INHERITED; 54981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com}; 55981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 56a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein// Time how long it takes to perform queries on an R-Tree. 57f168b86d7fafc5c20c87bebc6fd393cb17e120catfarinaclass RTreeQueryBench : public Benchmark { 58981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.compublic: 59a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) { 604477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein fName.printf("rtree_%s_query", name); 61981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 62644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 6336352bf5e38f45a70ee4f4fc132a38048d38206dmtklein bool isSuitableFor(Backend backend) override { 64644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org return backend == kNonRendering_Backend; 65644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org } 66981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprotected: 6736352bf5e38f45a70ee4f4fc132a38048d38206dmtklein const char* onGetName() override { 6861348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com return fName.c_str(); 69981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 702880df2609eba09b555ca37be04b6ad89290c765Tom Hudson void onDelayedSetup() override { 71e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 724477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS); 734477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein for (int i = 0; i < NUM_QUERY_RECTS; ++i) { 744477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein rects[i] = fProc(rand, i, NUM_QUERY_RECTS); 757fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org } 76bfd5bff75c0ce27a70f02e4b5578d66aa9d6e306mtklein fTree.insert(rects.get(), NUM_QUERY_RECTS); 777fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org } 787fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org 792880df2609eba09b555ca37be04b6ad89290c765Tom Hudson void onDraw(int loops, SkCanvas* canvas) override { 80e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 813361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org for (int i = 0; i < loops; ++i) { 822880df2609eba09b555ca37be04b6ad89290c765Tom Hudson SkTDArray<int> hits; 83533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkRect query; 844477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 854477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 864477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); 874477c3c0e6eb064772aefe8737425cd1c2ce557fmtklein query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2); 88a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein fTree.search(query, &hits); 89981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 90981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 91981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprivate: 92a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein SkRTree fTree; 93981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com MakeRectProc fProc; 9461348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com SkString fName; 95f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina typedef Benchmark INHERITED; 96981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com}; 97981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 98533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinstatic inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 99533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkRect out; 100533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fLeft = SkIntToScalar(index % GRID_WIDTH); 101533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fTop = SkIntToScalar(index / GRID_WIDTH); 102533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 103533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 1048c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com return out; 1058c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com} 106533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinstatic inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 107533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkRect out; 108533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fLeft = SkIntToScalar(index / GRID_WIDTH); 109533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fTop = SkIntToScalar(index % GRID_WIDTH); 110533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 111533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3); 1128c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com return out; 1138c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com} 1148c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com 115533eb782edaa0b6fece6166d3001edf72ec39f11mtkleinstatic inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) { 116533eb782edaa0b6fece6166d3001edf72ec39f11mtklein SkRect out; 117533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS); 118533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS); 119533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); 120533eb782edaa0b6fece6166d3001edf72ec39f11mtklein out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5); 121981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com return out; 122981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com} 123981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 124a06a9531213d2f00a0fe1dc07acd96eba57e6044mtkleinstatic inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) { 125a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1)); 126a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein} 127a06a9531213d2f00a0fe1dc07acd96eba57e6044mtklein 128981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com/////////////////////////////////////////////////////////////////////////////// 129981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 1302880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeBuildBench("XY", &make_XYordered_rects)); 1312880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeBuildBench("YX", &make_YXordered_rects)); 1322880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeBuildBench("random", &make_random_rects)); 1332880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeBuildBench("concentric", &make_concentric_rects)); 134385fe4d4b62d7d1dd76116dd570df3290a2f487bhalcanary 1352880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeQueryBench("XY", &make_XYordered_rects)); 1362880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeQueryBench("YX", &make_YXordered_rects)); 1372880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeQueryBench("random", &make_random_rects)); 1382880df2609eba09b555ca37be04b6ad89290c765Tom HudsonDEF_BENCH(return new RTreeQueryBench("concentric", &make_concentric_rects)); 139