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

We expect Webkit and Bink to give us draw commands in a reasonable x,y order.
We can maintain correctness and get a 17% recording speedup for the R-Tree by
not sorting in x and y when bulk-loading.

R=caryclark@google.com, reed@google.com

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

git-svn-id: http://skia.googlecode.com/svn/trunk@11037 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 33 insertions, 17 deletions

diff --git a/src/core/SkPicture.cpp b/src/core/SkPicture.cpp
index 1aa45284aa..f70f16ee5f 100644
--- a/src/core/SkPicture.cpp
+++ b/src/core/SkPicture.cpp
@@ -232,8 +232,10 @@ SkBBoxHierarchy* SkPicture::createBBoxHierarchy() const {
 
     SkScalar aspectRatio = SkScalarDiv(SkIntToScalar(fWidth),
                                        SkIntToScalar(fHeight));
+    bool sortDraws = false;  // Do not sort draw calls when bulk loading.
+
     return SkRTree::Create(kRTreeMinChildren, kRTreeMaxChildren,
-                           aspectRatio);
+                           aspectRatio, sortDraws);
 }
 
 SkCanvas* SkPicture::getRecordingCanvas() const {
diff --git a/src/core/SkRTree.cpp b/src/core/SkRTree.cpp
index d7a15d5957..95e4336ac7 100644
--- a/src/core/SkRTree.cpp
+++ b/src/core/SkRTree.cpp
@@ -21,21 +21,24 @@ 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);
@@ -323,8 +326,14 @@ SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
         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;
@@ -348,15 +357,18 @@ SkRTree::Branch SkRTree::bulkLoad(SkTDArray<Branch>* branches, int level) {
         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;
diff --git a/src/core/SkRTree.h b/src/core/SkRTree.h
index 2d11f28a57..54421de14c 100644
--- a/src/core/SkRTree.h
+++ b/src/core/SkRTree.h
@@ -55,7 +55,8 @@ public:
      * 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);
+    static SkRTree* Create(int minChildren, int maxChildren, SkScalar aspectRatio = 1,
+            bool orderWhenBulkLoading = true);
     virtual ~SkRTree();
 
     /**
@@ -144,7 +145,7 @@ private:
         }
     };
 
-    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio);
+    SkRTree(int minChildren, int maxChildren, SkScalar aspectRatio, bool orderWhenBulkLoading);
 
     /**
      * Recursively descend the tree to find an insertion position for 'branch', updates
@@ -184,6 +185,7 @@ private:
     SkChunkAlloc fNodes;
     SkTDArray<Branch> fDeferredInserts;
     SkScalar fAspectRatio;
+    bool fSortWhenBulkLoading;
 
     Node* allocateNode(uint16_t level);