From 1aa5129680859eba35f27e2a2b435947edb1a192 Mon Sep 17 00:00:00 2001
From: "tomhudson@google.com"
 <tomhudson@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Fri, 5 Apr 2013 14:21:04 +0000
Subject: [PATCH] Reduce size of second iteration in SkTileGridNextDatum<>().

Rather than iterating over the entire dataset twice, during the first pass
track how large the second pass needs to be. Entirely data-dependent but
in practice approaches 2x speedup.

BUG=1212
R=junov
https://codereview.appspot.com/8315044/



git-svn-id: http://skia.googlecode.com/svn/trunk@8543 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkTileGrid.h | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/src/core/SkTileGrid.h b/src/core/SkTileGrid.h
index 3152fa3..e272673 100644
--- a/src/core/SkTileGrid.h
+++ b/src/core/SkTileGrid.h
@@ -94,19 +94,27 @@ template <typename T>
 void* SkTileGridNextDatum(SkTDArray<void*>** tileData, SkTDArray<int>& tileIndices) {
     T* minVal = NULL;
     int tileCount = tileIndices.count();
-    // Find the next Datum
+    int minIndex = tileCount;
+    int maxIndex = 0;
+    // Find the next Datum; track where it's found so we reduce the size of the second loop.
     for (int tile = 0; tile < tileCount; ++tile) {
         int pos = tileIndices[tile];
         if (pos != SkTileGrid::kTileFinished) {
             T* candidate = (T*)(*tileData[tile])[pos];
             if (NULL == minVal || (*candidate) < (*minVal)) {
                 minVal = candidate;
+                minIndex = tile;
+                maxIndex = tile;
+            } else if (!((*minVal) < (*candidate))) {
+                // We don't require operator==; if !(candidate<minVal) && !(minVal<candidate),
+                // candidate==minVal and we have to add this tile to the range searched.
+                maxIndex = tile;
             }
         }
     }
     // Increment indices past the next datum
     if (minVal != NULL) {
-        for (int tile = 0; tile < tileCount; ++tile) {
+        for (int tile = minIndex; tile <= maxIndex; ++tile) {
             int pos = tileIndices[tile];
             if (pos != SkTileGrid::kTileFinished && (*tileData[tile])[pos] == minVal) {
                 if (++(tileIndices[tile]) >= tileData[tile]->count()) {
-- 
2.7.4