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

1 files changed, 58 insertions, 145 deletions

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<SkRect> 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<SkRect> 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<unsigned> 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)));)