cc: Improve texture per second calculation and overhead

cc/ThrottledTextureUploader.cpp

Index: cc/ThrottledTextureUploader.cpp
diff --git a/cc/ThrottledTextureUploader.cpp b/cc/ThrottledTextureUploader.cpp
index c152598aa648e1586aa9b892e16bd4e53750797d..545bf105f65152c0d98b316dd9401d3de5bdd5cc 100644
--- a/cc/ThrottledTextureUploader.cpp
+++ b/cc/ThrottledTextureUploader.cpp
@@ -8,14 +8,15 @@
 #include "Extensions3DChromium.h"
 #include "TraceEvent.h"
 #include <algorithm>
+#include <iterator>
 #include <public/Platform.h>
 #include <public/WebGraphicsContext3D.h>
-#include <vector>
 
 namespace {
 
 // How many previous uploads to use when predicting future throughput.
-static const size_t uploadHistorySize = 100;
+static const size_t uploadHistorySizeMax = 1000;
+static const size_t uploadHistorySizeInitial = 100;
 
 // Global estimated number of textures per second to maintain estimates across
 // subsequent instances of ThrottledTextureUploader.
@@ -87,9 +88,11 @@ bool ThrottledTextureUploader::Query::isNonBlocking()
 
 ThrottledTextureUploader::ThrottledTextureUploader(WebKit::WebGraphicsContext3D* context)
     : m_context(context)
-    , m_texturesPerSecondHistory(uploadHistorySize, estimatedTexturesPerSecondGlobal)
     , m_numBlockingTextureUploads(0)
+    , m_historyRemovalCount(0)
 {
+    for (size_t i = uploadHistorySizeInitial; i > 0; i--)
+        m_texturesPerSecondHistory.insert(estimatedTexturesPerSecondGlobal);
 }
 
 ThrottledTextureUploader::~ThrottledTextureUploader()
@@ -120,15 +123,10 @@ double ThrottledTextureUploader::estimatedTexturesPerSecond()
 {
     processQueries();
 
-    // The history should never be empty because we initialize all elements with an estimate.
-    ASSERT(m_texturesPerSecondHistory.size() == uploadHistorySize);
-
-    // Sort the history and use the median as our estimate.
-    std::vector<double> sortedHistory(m_texturesPerSecondHistory.begin(),
-                                      m_texturesPerSecondHistory.end());
-    std::sort(sortedHistory.begin(), sortedHistory.end());
-
-    estimatedTexturesPerSecondGlobal = sortedHistory[sortedHistory.size() * 2 / 3];
+    // Use the 3/4 median as our optimistic estimate.

[reveman, 2012/10/12 01:41:00]

I'm not convinced that 3/4 median magic number we should use here. Can we tune
these details separately? Preferably after we land your 'fill upload queue
patch'.

+    std::set<double>::iterator median = m_texturesPerSecondHistory.end();
+    std::advance(median, -(int)m_texturesPerSecondHistory.size() / 4);

[reveman, 2012/10/12 01:41:00]

nit: use static_cast<> here

+    estimatedTexturesPerSecondGlobal = *median;
     TRACE_COUNTER1("cc", "estimatedTexturesPerSecond", estimatedTexturesPerSecondGlobal);
     return estimatedTexturesPerSecondGlobal;
 }
@@ -176,10 +174,17 @@ void ThrottledTextureUploader::processQueries()
         if (!m_pendingQueries.first()->isNonBlocking())
             m_numBlockingTextureUploads--;
 
-        // Remove the oldest values from our history and insert the new one
+        // Alternately remove the min or max value from our history and insert the new one.
+        // We remove the min 3/4 of the time and the max 1/4 of the time to keep an optimistic history.
         double texturesPerSecond = 1.0 / (usElapsed * 1e-6);
-        m_texturesPerSecondHistory.pop_back();
-        m_texturesPerSecondHistory.push_front(texturesPerSecond);
+        m_texturesPerSecondHistory.insert(texturesPerSecond);

[reveman, 2012/10/12 01:41:00]

maybe do the remove before adding the new value?

+        if (m_texturesPerSecondHistory.size() >= uploadHistorySizeMax) {
+            if (m_historyRemovalCount & 0x3)

[reveman, 2012/10/12 01:41:00]

how about we save the 3/4 and 1/4 details for later?

lets get rid of m_historyRemovalCount and just do multiple removals here when
size() >= uploadHistorySizeMax.

+                m_texturesPerSecondHistory.erase(m_texturesPerSecondHistory.begin());
+            else
+                m_texturesPerSecondHistory.erase(--m_texturesPerSecondHistory.end());
+            m_historyRemovalCount++;
+        }
 
         m_availableQueries.append(m_pendingQueries.takeFirst());
     }