1981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 2981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com/* 3981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * Copyright 2012 Google Inc. 4981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * 5981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * Use of this source code is governed by a BSD-style license that can be 6981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com * found in the LICENSE file. 7981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com */ 8981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 9f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina#include "Benchmark.h" 10981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkCanvas.h" 11981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkRTree.h" 12981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkRandom.h" 13981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com#include "SkString.h" 14981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 15981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com// confine rectangles to a smallish area, so queries generally hit something, and overlap occurs: 16981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comstatic const int GENERATE_EXTENTS = 1000; 17981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comstatic const int NUM_BUILD_RECTS = 500; 18981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comstatic const int NUM_QUERY_RECTS = 5000; 198c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.comstatic const int GRID_WIDTH = 100; 20981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 21e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgtypedef SkIRect (*MakeRectProc)(SkRandom&, int, int); 22981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 23981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com// Time how long it takes to build an R-Tree either bulk-loaded or not 24f168b86d7fafc5c20c87bebc6fd393cb17e120catfarinaclass RTreeBuildBench : public Benchmark { 25981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.compublic: 26b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeBuildBench(const char* name, MakeRectProc proc, bool bulkLoad, 27981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkBBoxHierarchy* tree) 28410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com : fTree(tree) 29981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com , fProc(proc) 3061348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com , fBulkLoad(bulkLoad) { 3161348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("rtree_"); 3261348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append(name); 3361348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("_build"); 34981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com if (fBulkLoad) { 3561348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("_bulk"); 36981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 3761348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com } 38644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 39644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 40644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org return backend == kNonRendering_Backend; 41644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org } 42644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 43b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org virtual ~RTreeBuildBench() { 444813458d89fb276680168848bd861b307cf83f51rileya@google.com fTree->unref(); 4507a05d5130ee0d8444960fdba574e69b7254f1dfrobertphillips@google.com } 4661348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.comprotected: 477fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org virtual const char* onGetName() SK_OVERRIDE { 4861348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com return fName.c_str(); 49981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 503361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 51e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 523361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org for (int i = 0; i < loops; ++i) { 53981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com for (int j = 0; j < NUM_BUILD_RECTS; ++j) { 54981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com fTree->insert(reinterpret_cast<void*>(j), fProc(rand, j, NUM_BUILD_RECTS), 55981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com fBulkLoad); 56981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 57981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com fTree->flushDeferredInserts(); 58981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com fTree->clear(); 59981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 60981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 61981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprivate: 62981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkBBoxHierarchy* fTree; 63981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com MakeRectProc fProc; 6461348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com SkString fName; 65981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com bool fBulkLoad; 66f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina typedef Benchmark INHERITED; 67981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com}; 68981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 69981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com// Time how long it takes to perform queries on an R-Tree, bulk-loaded or not 70f168b86d7fafc5c20c87bebc6fd393cb17e120catfarinaclass RTreeQueryBench : public Benchmark { 71981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.compublic: 72981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com enum QueryType { 73981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com kSmall_QueryType, // small queries 74981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com kLarge_QueryType, // large queries 75981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com kRandom_QueryType,// randomly sized queries 76981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com kFull_QueryType // queries that cover everything 77981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com }; 78981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 79b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench(const char* name, MakeRectProc proc, bool bulkLoad, 80981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com QueryType q, SkBBoxHierarchy* tree) 81410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com : fTree(tree) 82981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com , fProc(proc) 83981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com , fBulkLoad(bulkLoad) 84981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com , fQuery(q) { 8561348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("rtree_"); 8661348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append(name); 8761348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("_query"); 8861348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com if (fBulkLoad) { 8961348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com fName.append("_bulk"); 9061348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com } 91981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 92644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 93644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org virtual bool isSuitableFor(Backend backend) SK_OVERRIDE { 94644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org return backend == kNonRendering_Backend; 95644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org } 96644629c1c7913a43ced172b98d56e0f471bc348bcommit-bot@chromium.org 97b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org virtual ~RTreeQueryBench() { 984813458d89fb276680168848bd861b307cf83f51rileya@google.com fTree->unref(); 9907a05d5130ee0d8444960fdba574e69b7254f1dfrobertphillips@google.com } 100981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprotected: 1017fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org virtual const char* onGetName() SK_OVERRIDE { 10261348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com return fName.c_str(); 103981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 1047fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org virtual void onPreDraw() SK_OVERRIDE { 105e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 106c289743864e2ab926a95e617a5cd1d29b26d1825mtklein@google.com for (int j = 0; j < NUM_QUERY_RECTS; ++j) { 107c289743864e2ab926a95e617a5cd1d29b26d1825mtklein@google.com fTree->insert(reinterpret_cast<void*>(j), 108c289743864e2ab926a95e617a5cd1d29b26d1825mtklein@google.com fProc(rand, j, NUM_QUERY_RECTS), 109c289743864e2ab926a95e617a5cd1d29b26d1825mtklein@google.com fBulkLoad); 1107fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org } 1117fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org fTree->flushDeferredInserts(); 1127fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org } 1137fb83c8c72f2a035e84a4ee4ee6abcf5a4872166commit-bot@chromium.org 1143361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE { 115e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.org SkRandom rand; 1163361471a3504ecd0351ff70f4c42d8d6fee963d4commit-bot@chromium.org for (int i = 0; i < loops; ++i) { 117981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkTDArray<void*> hits; 118981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkIRect query; 119981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com switch(fQuery) { 120981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com case kSmall_QueryType: 121981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fLeft = rand.nextU() % GENERATE_EXTENTS; 122981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fTop = rand.nextU() % GENERATE_EXTENTS; 123981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fRight = query.fLeft + (GENERATE_EXTENTS / 20); 124981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fBottom = query.fTop + (GENERATE_EXTENTS / 20); 125981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com break; 126981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com case kLarge_QueryType: 127981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fLeft = rand.nextU() % GENERATE_EXTENTS; 128981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fTop = rand.nextU() % GENERATE_EXTENTS; 129981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fRight = query.fLeft + (GENERATE_EXTENTS / 2); 130981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fBottom = query.fTop + (GENERATE_EXTENTS / 2); 131981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com break; 132981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com case kFull_QueryType: 133981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fLeft = -GENERATE_EXTENTS; 134981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fTop = -GENERATE_EXTENTS; 135981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fRight = 2 * GENERATE_EXTENTS; 136981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fBottom = 2 * GENERATE_EXTENTS; 137981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com break; 138981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com default: // fallthrough 139981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com case kRandom_QueryType: 140981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fLeft = rand.nextU() % GENERATE_EXTENTS; 141981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fTop = rand.nextU() % GENERATE_EXTENTS; 142981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fRight = query.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 143981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com query.fBottom = query.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 2); 144981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com break; 145981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com }; 146981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com fTree->search(query, &hits); 147981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 148981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com } 149981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.comprivate: 150981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkBBoxHierarchy* fTree; 151981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com MakeRectProc fProc; 15261348d1cc68e7fa40d08c2c4bc03218305033838rileya@google.com SkString fName; 153981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com bool fBulkLoad; 154981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com QueryType fQuery; 155f168b86d7fafc5c20c87bebc6fd393cb17e120catfarina typedef Benchmark INHERITED; 156981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com}; 157981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 158e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgstatic inline SkIRect make_concentric_rects_increasing(SkRandom&, int index, int numRects) { 159981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkIRect out = {0, 0, index + 1, index + 1}; 160981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com return out; 161981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com} 162981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 163e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgstatic inline SkIRect make_XYordered_rects(SkRandom& rand, int index, int numRects) { 1648c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkIRect out; 1658c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com out.fLeft = index % GRID_WIDTH; 1668c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com out.fTop = index / GRID_WIDTH; 1670d60db60109951053f97bd6deac8fe00526b7231sglez@google.com out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 1680d60db60109951053f97bd6deac8fe00526b7231sglez@google.com out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 1698c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com return out; 1708c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com} 171e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgstatic inline SkIRect make_YXordered_rects(SkRandom& rand, int index, int numRects) { 1728c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkIRect out; 1738c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com out.fLeft = index / GRID_WIDTH; 1748c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com out.fTop = index % GRID_WIDTH; 1750d60db60109951053f97bd6deac8fe00526b7231sglez@google.com out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 1760d60db60109951053f97bd6deac8fe00526b7231sglez@google.com out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 3); 1778c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com return out; 1788c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com} 1798c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com 180e0e7cfe44bb9d66d76120a79e5275c294bacaa22commit-bot@chromium.orgstatic inline SkIRect make_random_rects(SkRandom& rand, int index, int numRects) { 181981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkIRect out; 182981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com out.fLeft = rand.nextS() % GENERATE_EXTENTS; 183981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com out.fTop = rand.nextS() % GENERATE_EXTENTS; 184981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com out.fRight = out.fLeft + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 185981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com out.fBottom = out.fTop + 1 + rand.nextU() % (GENERATE_EXTENTS / 5); 186981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com return out; 187981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com} 188981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 189981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com/////////////////////////////////////////////////////////////////////////////// 190981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 191410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 192b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, false, 193981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkRTree::Create(5, 16))); 194410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 195410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 196b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("XYordered", &make_XYordered_rects, true, 197981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com SkRTree::Create(5, 16))); 198410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 199410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 200b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 2018c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16, 1, false))); 202410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 203410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 204b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("XYordered", &make_XYordered_rects, true, 205b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 206410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 207410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 208b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)XYordered", &make_XYordered_rects, true, 209b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 210410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 2118c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com 212410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 213b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, false, 2148c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16))); 215410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 216410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 217b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("YXordered", &make_YXordered_rects, true, 2188c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16))); 219410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 220410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 221b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 2228c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16, 1, false))); 223410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 224410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 225b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("YXordered", &make_YXordered_rects, true, 226b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 227410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 228410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 229b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)YXordered", &make_YXordered_rects, true, 230b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 231410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 232981b33abc65d968523d78d45e69cb071e8e03e91rileya@google.com 233410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 234b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, false, 2358c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16))); 236410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 237410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 238b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("random", &make_random_rects, true, 2398c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16))); 240410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 241410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 242b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)random", &make_random_rects, true, 2438c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com SkRTree::Create(5, 16, 1, false))); 244410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 245410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 246b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("random", &make_random_rects, true, 247b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 248410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 249410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 250b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)random", &make_random_rects, true, 251b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 252410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 2538c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com 254410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 255b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("concentric", 2568c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com &make_concentric_rects_increasing, true, SkRTree::Create(5, 16))); 257410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 258410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 259b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeBuildBench, ("(unsorted)concentric", 2608c902126a90f37b6a038a78488c6215fa0c34b7dsglez@google.com &make_concentric_rects_increasing, true, SkRTree::Create(5, 16, 1, false))); 261410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 262410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 263b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("concentric", &make_concentric_rects_increasing, true, 264b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16))); 265410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 266410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.comDEF_BENCH( 267b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org return SkNEW_ARGS(RTreeQueryBench, ("(unsorted)concentric", &make_concentric_rects_increasing, true, 268b2db44376eedaba05f6eae4251016009cd3c607dcommit-bot@chromium.org RTreeQueryBench::kRandom_QueryType, SkRTree::Create(5, 16, 1, false))); 269410e6e80f00a6c660675c80904807a041c7b7d2amtklein@google.com) 270