R-Tree -- Don't sort draw commands unless specified.

src/core/SkRTree.cpp

 
 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkRTree.h"
 #include "SkTSort.h"
 
 static inline uint32_t get_area(const SkIRect& rect);
 static inline uint32_t get_overlap(const SkIRect& rect1, const SkIRect& rect2);
 static inline uint32_t get_margin(const SkIRect& rect);
 static inline uint32_t get_overlap_increase(const SkIRect& rect1, const SkIRect& rect2,
                                             SkIRect expandBy);
 static inline uint32_t get_area_increase(const SkIRect& rect1, SkIRect rect2);
 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out);
 
 ///////////////////////////////////////////////////////////////////////////////////////////////////
 
 SK_DEFINE_INST_COUNT(SkRTree)
 
-SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio) {
+SkRTree* SkRTree::Create(int minChildren, int maxChildren, SkScalar aspectRatio,
+            bool sortWhenBulkLoading) {
     if (minChildren < maxChildren && (maxChildren + 1) / 2 >= minChildren &&
         minChildren > 0 && maxChildren < static_cast<int>(SK_MaxU16)) {
-        return new SkRTree(minChildren, maxChildren, aspectRatio);
+        return new SkRTree(minChildren, maxChildren, aspectRatio, sortWhenBulkLoading);
     }
     return NULL;
 }
 
-SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio)
+SkRTree::SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio,
+        bool sortWhenBulkLoading)
     : fMinChildren(minChildren)
     , fMaxChildren(maxChildren)
     , fNodeSize(sizeof(Node) + sizeof(Branch) * maxChildren)
     , fCount(0)
     , fNodes(fNodeSize * 256)
-    , fAspectRatio(aspectRatio) {
+    , fAspectRatio(aspectRatio)
+    , fSortWhenBulkLoading(sortWhenBulkLoading) {
     SkASSERT(minChildren < maxChildren && minChildren > 0 && maxChildren <
              static_cast<int>(SK_MaxU16));
     SkASSERT((maxChildren + 1) / 2 >= minChildren);
     this->validate();
 }
 
 SkRTree::~SkRTree() {
     this->clear();
 }
 
@@ skipping 267 matching lines @@
     }
 }
 
 SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
     if (branches->count() == 1) {
         // Only one branch: it will be the root
         Branch out = (*branches)[0];
         branches->rewind();
         return out;
     } else {
-        // First we sort the whole list by y coordinates
-        SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
+        // We sort the whole list by y coordinates, if we are told to do so.
+        //
+        // We expect Webkit / Blink to give us a reasonable x,y order.
+        // Avoiding this call resulted in a 17% win for recording with
+        // negligible difference in playback speed.
+        if (fSortWhenBulkLoading) {
+            SkTQSort(branches->begin(), branches->end() - 1, RectLessY());
+        }
 
         int numBranches = branches->count() / fMaxChildren;
         int remainder = branches->count() % fMaxChildren;
         int newBranches = 0;
 
         if (0 != remainder) {
             ++numBranches;
             // If the remainder isn't enough to fill a node, we'll need to add fewer nodes to
             // some other branches to make up for it
             if (remainder >= fMinChildren) {
                 remainder = 0;
             } else {
                 remainder = fMinChildren - remainder;
             }
         }
 
         int numStrips = SkScalarCeil(SkScalarSqrt(SkIntToScalar(numBranches) *
                                      SkScalarInvert(fAspectRatio)));
         int numTiles = SkScalarCeil(SkIntToScalar(numBranches) /
                                     SkIntToScalar(numStrips));
         int currentBranch = 0;
 
         for (int i = 0; i < numStrips; ++i) {
-            int begin = currentBranch;
-            int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
-                      (fMaxChildren - fMinChildren) * numTiles);
-            if (end > branches->count()) {
-                end = branches->count();
+            // Once again, if we are told to do so, we sort by x.
+            if (fSortWhenBulkLoading) {
+                int begin = currentBranch;
+                int end = currentBranch + numTiles * fMaxChildren - SkMin32(remainder,
+                        (fMaxChildren - fMinChildren) * numTiles);
+                if (end > branches->count()) {
+                    end = branches->count();
+                }
+
+                // Now we sort horizontal strips of rectangles by their x coords
+                SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
             }
 
-            // Now we sort horizontal strips of rectangles by their x coords
-            SkTQSort(branches->begin() + begin, branches->begin() + end - 1, RectLessX());
-
             for (int j = 0; j < numTiles && currentBranch < branches->count(); ++j) {
                 int incrementBy = fMaxChildren;
                 if (remainder != 0) {
                     // if need be, omit some nodes to make up for remainder
                     if (remainder <= fMaxChildren - fMinChildren) {
                         incrementBy -= remainder;
                         remainder = 0;
                     } else {
                         incrementBy = fMinChildren;
                         remainder -= fMaxChildren - fMinChildren;
@@ skipping 101 matching lines @@
 
 // Expand 'out' to include 'joinWith'
 static inline void join_no_empty_check(const SkIRect& joinWith, SkIRect* out) {
     // since we check for empty bounds on insert, we know we'll never have empty rects
     // and we can save the empty check that SkIRect::join requires
     if (joinWith.fLeft < out->fLeft) { out->fLeft = joinWith.fLeft; }
     if (joinWith.fTop < out->fTop) { out->fTop = joinWith.fTop; }
     if (joinWith.fRight > out->fRight) { out->fRight = joinWith.fRight; }
     if (joinWith.fBottom > out->fBottom) { out->fBottom = joinWith.fBottom; }
 }