Prune SkRTree

  - Propagate a bunch of constant parameters through.
  - Delete code that's not used when bulk loading.
  - Allocate all Nodes together.
  - Stay in SkRect.

Doing a single malloc for the nodes can't not have improved memory usage.

Looks like this might improve record performance ~5%, probably mostly from
staying in SkRects.  This finally dethrones building the BBH as the hot spot.
(Now it's mapping user bounds back to device bounds and adjusting for paints.)

Recording time changes from my MBP:
    desk_rectangletransition.skp	11.5us -> 11.7us	1x
             desk_forecastio.skp	 115us ->  114us	0.98x
                desk_booking.skp	 550us ->  541us	0.98x
            tabl_mercurynews.skp	 176us ->  173us	0.98x
                   tabl_hsfi.skp	 294us ->  287us	0.98x
              desk_wordpress.skp	 351us ->  343us	0.98x
           tabl_worldjournal.skp	 439us ->  426us	0.97x
                  tabl_gmail.skp	20.3us -> 19.7us	0.97x
         desk_youtubetvvideo.skp	10.8us -> 10.4us	0.97x
             desk_googleplus.skp	 1.1ms -> 1.07ms	0.97x
               tabl_slashdot.skp	 106us ->  103us	0.97x
         desk_jsfiddlebigcar.skp	26.7us -> 25.7us	0.96x
               tabl_techmeme.skp	95.4us -> 91.7us	0.96x
             tabl_deviantart.skp	 133us ->  127us	0.96x
              desk_pinterest.skp	40.6us -> 38.9us	0.96x
                 desk_carsvg.skp	 195us ->  187us	0.96x
               tabl_engadget.skp	 376us ->  359us	0.96x
                tabl_sahadan.skp	60.5us -> 57.5us	0.95x
      tabl_culturalsolutions.skp	 255us ->  242us	0.95x
                  tabl_gspro.skp	58.3us -> 55.5us	0.95x
               desk_linkedin.skp	 146us ->  138us	0.94x
                   desk_ebay.skp	 192us ->  181us	0.94x
                    tabl_cnn.skp	 467us ->  440us	0.94x
     desk_jsfiddlehumperclip.skp	29.9us -> 28.1us	0.94x
               desk_tigersvg.skp	43.2us -> 40.5us	0.94x
           desk_yahooanswers.skp	 131us ->  123us	0.94x
desk_googlespreadsheetdashed.skp	1.18ms -> 1.11ms	0.94x
                desk_blogger.skp	 193us ->  181us	0.94x
                tabl_mozilla.skp	1.82ms ->  1.7ms	0.94x
                    tabl_mlb.skp	 145us ->  136us	0.93x
              mobi_wikipedia.skp	 577us ->  539us	0.93x
               tabl_frantzen.skp	54.1us -> 50.4us	0.93x
                  desk_baidu.skp	87.9us -> 81.9us	0.93x
             desk_techcrunch.skp	 224us ->  209us	0.93x
                 desk_sfgate.skp	 206us ->  192us	0.93x
                  tabl_ukwsj.skp	 269us ->  250us	0.93x
               desk_facebook.skp	 316us ->  293us	0.93x
            desk_gmailthread.skp	 205us ->  190us	0.93x
         tabl_googlecalendar.skp	 158us ->  147us	0.93x
                   tabl_digg.skp	 382us ->  354us	0.93x
                 desk_amazon.skp	 106us -> 98.5us	0.93x
          tabl_androidpolice.skp	 693us ->  642us	0.93x
                tabl_nytimes.skp	 206us ->  191us	0.92x
                    desk_gws.skp	 124us ->  114us	0.92x
                desk_youtube.skp	 255us ->  235us	0.92x
           tabl_cuteoverload.skp	 583us ->  537us	0.92x
            desk_oldinboxapp.skp	  18us -> 16.6us	0.92x
             desk_mobilenews.skp	 297us ->  273us	0.92x
                 tabl_pravda.skp	 168us ->  154us	0.92x
              tabl_vnexpress.skp	 236us ->  217us	0.92x
          desk_css3gradients.skp	 202us ->  185us	0.92x
            tabl_gamedeksiam.skp	 508us ->  464us	0.91x
                desk_wowwiki.skp	1.02ms ->  929us	0.91x
                   desk_espn.skp	 209us ->  191us	0.91x
             desk_chalkboard.skp	 315us ->  284us	0.9x
                 desk_mapsvg.skp	 607us ->  543us	0.89x
            desk_pokemonwiki.skp	5.18ms -> 4.62ms	0.89x
               desk_samoasvg.skp	 335us ->  298us	0.89x
        desk_youtubetvbrowse.skp	10.1us -> 8.59us	0.85x
BUG=skia:3085, skia:2834

Review URL: https://codereview.chromium.org/734723002

1 files changed, 28 insertions, 108 deletions

diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 00c6c8941d..440411d9b0 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -9,163 +9,83 @@
 #ifndef SkRTree_DEFINED
 #define SkRTree_DEFINED
 
+#include "SkBBoxHierarchy.h"
 #include "SkRect.h"
 #include "SkTDArray.h"
-#include "SkChunkAlloc.h"
-#include "SkBBoxHierarchy.h"
 
 /**
  * An R-Tree implementation. In short, it is a balanced n-ary tree containing a hierarchy of
  * bounding rectangles.
  *
- * Much like a B-Tree it maintains balance by enforcing minimum and maximum child counts, and
- * splitting nodes when they become overfull. Unlike B-trees, however, we're using spatial data; so
- * there isn't a canonical ordering to use when choosing insertion locations and splitting
- * distributions. A variety of heuristics have been proposed for these problems; here, we're using
- * something resembling an R*-tree, which attempts to minimize area and overlap during insertion,
- * and aims to minimize a combination of margin, overlap, and area when splitting.
+ * It only supports bulk-loading, i.e. creation from a batch of bounding rectangles.
+ * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm.
  *
- * One detail that is thus far unimplemented that may improve tree quality is attempting to remove
- * and reinsert nodes when they become full, instead of immediately splitting (nodes that may have
- * been placed well early on may hurt the tree later when more nodes have been added; removing
- * and reinserting nodes generally helps reduce overlap and make a better tree). Deletion of nodes
- * is also unimplemented.
+ * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
+ * which groups rects by position on the Hilbert curve, is probably worth a look). There also
+ * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
  *
  * For more details see:
  *
  *  Beckmann, N.; Kriegel, H. P.; Schneider, R.; Seeger, B. (1990). "The R*-tree:
  *      an efficient and robust access method for points and rectangles"
- *
- * It also supports bulk-loading from a batch of bounds and values; if you don't require the tree
- * to be usable in its intermediate states while it is being constructed, this is significantly
- * quicker than individual insertions and produces more consistent trees.
  */
 class SkRTree : public SkBBoxHierarchy {
 public:
     SK_DECLARE_INST_COUNT(SkRTree)
 
     /**
-     * Create a new R-Tree with specified min/max child counts.
-     * The child counts are valid iff:
-     * - (max + 1) / 2 >= min (splitting an overfull node must be enough to populate 2 nodes)
-     * - min < max
-     * - min > 0
-     * - max < SK_MaxU16
      * If you have some prior information about the distribution of bounds you're expecting, you
-     * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to create
-     * better proportioned tiles of rectangles.
+     * can provide an optional aspect ratio parameter. This allows the bulk-load algorithm to
+     * create better proportioned tiles of rectangles.
      */
-    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
-            bool orderWhenBulkLoading = true);
-    virtual ~SkRTree();
+    explicit SkRTree(SkScalar aspectRatio = 1);
+    virtual ~SkRTree() {}
 
     virtual void insert(SkAutoTMalloc<SkRect>* boundsArray, int N) SK_OVERRIDE;
     virtual void search(const SkRect& query, SkTDArray<unsigned>* results) const SK_OVERRIDE;
 
-    void clear();
+    // Methods and constants below here are only public for tests.
+
     // Return the depth of the tree structure.
-    int getDepth() const { return this->isEmpty() ? 0 : fRoot.fChild.subtree->fLevel + 1; }
+    int getDepth() const { return fCount ? fRoot.fSubtree->fLevel + 1 : 0; }
     // Insertion count (not overall node count, which may be greater).
     int getCount() const { return fCount; }
 
+    // These values were empirically determined to produce reasonable performance in most cases.
+    static const int kMinChildren = 6,
+                     kMaxChildren = 11;
 private:
-    bool isEmpty() const { return 0 == this->getCount(); }
-
     struct Node;
 
-    /**
-     * A branch of the tree, this may contain a pointer to another interior node, or a data value
-     */
     struct Branch {
         union {
-            Node* subtree;
-            unsigned opIndex;
-        } fChild;
-        SkIRect fBounds;
+            Node* fSubtree;
+            unsigned fOpIndex;
+        };
+        SkRect fBounds;
     };
 
-    /**
-     * A node in the tree, has between fMinChildren and fMaxChildren (the root is a special case)
-     */
     struct Node {
         uint16_t fNumChildren;
         uint16_t fLevel;
-        bool isLeaf() { return 0 == fLevel; }
-        // Since we want to be able to pick min/max child counts at runtime, we assume the creator
-        // has allocated sufficient space directly after us in memory, and index into that space
-        Branch* child(size_t index) {
-            return reinterpret_cast<Branch*>(this + 1) + index;
-        }
-    };
-
-    typedef int32_t SkIRect::*SortSide;
-
-    // Helper for sorting our children arrays by sides of their rects
-    struct RectLessThan {
-        RectLessThan(SkRTree::SortSide side) : fSide(side) { }
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) const {
-            return lhs.fBounds.*fSide < rhs.fBounds.*fSide;
-        }
-    private:
-        const SkRTree::SortSide fSide;
-    };
-
-    struct RectLessX {
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
-            return ((lhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1) <
-                   ((rhs.fBounds.fRight - lhs.fBounds.fLeft) >> 1);
-        }
-    };
-
-    struct RectLessY {
-        bool operator()(const SkRTree::Branch lhs, const SkRTree::Branch rhs) {
-            return ((lhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1) <
-                   ((rhs.fBounds.fBottom - lhs.fBounds.fTop) >> 1);
-        }
+        Branch fChildren[kMaxChildren];
     };
 
-    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
-
-    /**
-     * Recursively descend the tree to find an insertion position for 'branch', updates
-     * bounding boxes on the way up.
-     */
-    Branch* insert(Node* root, Branch* branch, uint16_t level = 0);
-
-    int chooseSubtree(Node* root, Branch* branch);
-    SkIRect computeBounds(Node* n);
-    int distributeChildren(Branch* children);
-    void search(Node* root, const SkIRect query, SkTDArray<unsigned>* results) const;
+    void search(Node* root, const SkRect& query, SkTDArray<unsigned>* results) const;
 
-    /**
-     * This performs a bottom-up bulk load using the STR (sort-tile-recursive) algorithm, this
-     * seems to generally produce better, more consistent trees at significantly lower cost than
-     * repeated insertions.
-     *
-     * This consumes the input array.
-     *
-     * TODO: Experiment with other bulk-load algorithms (in particular the Hilbert pack variant,
-     * which groups rects by position on the Hilbert curve, is probably worth a look). There also
-     * exist top-down bulk load variants (VAMSplit, TopDownGreedy, etc).
-     */
+    // Consumes the input array.
     Branch bulkLoad(SkTDArray<Branch>* branches, int level = 0);
 
-    void validate() const;
-    int validateSubtree(Node* root, SkIRect bounds, bool isRoot = false) const;
+    // How many times will bulkLoad() call allocateNodeAtLevel()?
+    static int CountNodes(int branches, SkScalar aspectRatio);
 
-    const int fMinChildren;
-    const int fMaxChildren;
-    const size_t fNodeSize;
+    Node* allocateNodeAtLevel(uint16_t level);
 
     // This is the count of data elements (rather than total nodes in the tree)
     int fCount;
-
-    Branch fRoot;
-    SkChunkAlloc fNodes;
     SkScalar fAspectRatio;
-    bool fSortWhenBulkLoading;
-
-    Node* allocateNode(uint16_t level);
+    Branch fRoot;
+    SkTDArray<Node> fNodes;
 
     typedef SkBBoxHierarchy INHERITED;
 };