Add benchmark to compare different BBH query patterns.

bench/PicturePlaybackBench.cpp

Index: bench/PicturePlaybackBench.cpp
diff --git a/bench/PicturePlaybackBench.cpp b/bench/PicturePlaybackBench.cpp
index 947a7844f691661c6ba307a87312cbeec8b21066..1cd43cc4068cd619951c6c0c15ca2028b12c6e39 100644
--- a/bench/PicturePlaybackBench.cpp
+++ b/bench/PicturePlaybackBench.cpp
@@ -11,6 +11,7 @@
 #include "SkPicture.h"
 #include "SkPictureRecorder.h"
 #include "SkPoint.h"
+#include "SkRandom.h"
 #include "SkRect.h"
 #include "SkString.h"
 
@@ -139,3 +140,83 @@ private:
 DEF_BENCH( return new TextPlaybackBench(); )
 DEF_BENCH( return new PosTextPlaybackBench(true); )
 DEF_BENCH( return new PosTextPlaybackBench(false); )
+
+
+enum BBH  { kNone, kRTree, kTileGrid };
+enum Mode { kTiled, kRandom };

[robertphillips, 2014/11/07 18:59:59]

// This bench compares the different BBH techniques with & without perfect hits
// on tile boundaries.

?

[mtklein, 2014/11/07 19:05:36]

Done.

+class TiledPlaybackBench : public Benchmark {
+public:
+    TiledPlaybackBench(BBH bbh, Mode mode) : fBBH(bbh), fMode(mode), fName("tiled_playback") {
+        switch (fBBH) {
+            case kNone:     fName.append("_none"    ); break;
+            case kRTree:    fName.append("_rtree"   ); break;
+            case kTileGrid: fName.append("_tilegrid"); break;
+        }
+        switch (fMode) {
+            case kTiled:  fName.append("_tiled" ); break;
+            case kRandom: fName.append("_random"); break;
+        }
+    }
+
+    virtual const char* onGetName() SK_OVERRIDE { return fName.c_str(); }
+    virtual SkIPoint onGetSize() SK_OVERRIDE { return SkIPoint::Make(1024,1024); }
+
+    virtual void onPreDraw() SK_OVERRIDE {
+        SkTileGridFactory::TileGridInfo info = { { 256, 256 }, {0,0}, {0,0} };
+        SkAutoTDelete<SkBBHFactory> factory;
+        switch (fBBH) {
+            case kNone:                                                 break;
+            case kRTree:    factory.reset(new SkRTreeFactory);          break;
+            case kTileGrid: factory.reset(new SkTileGridFactory(info)); break;
+        }
+
+        SkPictureRecorder recorder;
+        SkCanvas* canvas = recorder.beginRecording(1024, 1024, factory);
+            SkRandom rand;
+            for (int i = 0; i < 10000; i++) {
+                int x = rand.nextULessThan(1024),
+                    y = rand.nextULessThan(1024),

[robertphillips, 2014/11/07 18:59:59]

Just curious, what happens if these are 256 instead of 128?

[mtklein, 2014/11/07 19:05:37]

Slightly different numbers, but all the relative performance comparisons are
pretty much the same.  Should be as we make the rects larger the BBH matters
less and less, right?

+                    w = rand.nextULessThan(128),
+                    h = rand.nextULessThan(128);
+                SkPaint paint;
+                paint.setColor(rand.nextU());
+                paint.setAlpha(0xFF);
+                canvas->drawRect(SkRect::MakeXYWH(x,y,w,h), paint);
+            }
+        fPic.reset(recorder.endRecording());
+    }
+
+    virtual void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+        for (int i = 0; i < loops; i++) {
+            // This inner loop guarantees we make the same choices for all bench variants.
+            SkRandom rand;
+            for (int j = 0; j < 10; j++) {
+                int x,y;
+                switch (fMode) {
+                    case kTiled:  x = 256 * rand.nextULessThan(4);
+                                  y = 256 * rand.nextULessThan(4);
+                                  break;
+                    case kRandom: x = rand.nextULessThan(768),
+                                  y = rand.nextULessThan(768);
+                                  break;
+                }
+                SkAutoCanvasRestore ar(canvas, true/*save now*/);
+                canvas->clipRect(SkRect::MakeXYWH(x,y,256,256));
+                fPic->playback(canvas);
+            }
+        }
+    }
+
+private:
+    BBH                      fBBH;
+    Mode                     fMode;
+    SkString                 fName;
+    SkAutoTDelete<SkPicture> fPic;
+};
+
+DEF_BENCH( return new TiledPlaybackBench(kNone,     kRandom); )
+DEF_BENCH( return new TiledPlaybackBench(kNone,     kTiled ); )
+DEF_BENCH( return new TiledPlaybackBench(kRTree,    kRandom); )
+DEF_BENCH( return new TiledPlaybackBench(kRTree,    kTiled ); )
+DEF_BENCH( return new TiledPlaybackBench(kTileGrid, kRandom); )
+DEF_BENCH( return new TiledPlaybackBench(kTileGrid, kTiled ); )