Make GrResourceCache dynamically change between LRU and random replacement strategies.

src/gpu/GrResourceCache.cpp

Index: src/gpu/GrResourceCache.cpp
diff --git a/src/gpu/GrResourceCache.cpp b/src/gpu/GrResourceCache.cpp
index 529f87c124880bbefd0c724bd2e48016841d4cd9..838136a918cc8fe861c1a7c341657fd0e12c09cf 100644
--- a/src/gpu/GrResourceCache.cpp
+++ b/src/gpu/GrResourceCache.cpp
@@ -57,13 +57,21 @@ private:
 };
 
  //////////////////////////////////////////////////////////////////////////////
-
+constexpr int GrResourceCache::kStrategyScoreMin;
+constexpr int GrResourceCache::kStrategyScoreMax;
+constexpr int GrResourceCache::kInitialStrategyScoreMax;
 
 GrResourceCache::GrResourceCache(const GrCaps* caps)
     : fTimestamp(0)
     , fMaxCount(kDefaultMaxCount)
     , fMaxBytes(kDefaultMaxSize)
     , fMaxUnusedFlushes(kDefaultMaxUnusedFlushes)
+    , fStrategy(ReplacementStrategy::kLRU)

[robertphillips, 2016/09/13 13:05:21]

Should kInitialStrategyScoreMax just be kInitialStrategyScore ?

[bsalomon, 2016/09/13 13:31:32]

Ha, yes.

+    , fStrategyScore(kInitialStrategyScoreMax)
+    , fTotalMissesThisFlush(0)
+    , fMissesThisFlushPurgedRecently(0)
+    , fUniqueKeysPurgedThisFlushStorage {{8*sizeof(GrUniqueKey)}, {8*sizeof(GrUniqueKey)}}
+    , fFlushParity(0)
 #if GR_CACHE_STATS
     , fHighWaterCount(0)
     , fHighWaterBytes(0)
@@ -73,7 +81,6 @@ GrResourceCache::GrResourceCache(const GrCaps* caps)
     , fBytes(0)
     , fBudgetedCount(0)
     , fBudgetedBytes(0)
-    , fRequestFlush(false)
     , fFlushTimestamps(nullptr)
     , fLastFlushTimestampIndex(0)
     , fPreferVRAMUseOverFlushes(caps->preferVRAMUseOverFlushes()) {
@@ -253,8 +260,10 @@ private:
 GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& scratchKey,
                                                           size_t resourceSize,
                                                           uint32_t flags) {
+    // We don't currently track misses for scratch resources for selecting the replacement policy.
+    // The reason is that it is common to look for a scratch resource before creating a texture
+    // that will immediately become uniquely keyed.
     SkASSERT(scratchKey.isValid());
-
     GrGpuResource* resource;
     if (flags & (kPreferNoPendingIO_ScratchFlag | kRequireNoPendingIO_ScratchFlag)) {
         resource = fScratchMap.find(scratchKey, AvailableForScratchUse(true));
@@ -282,6 +291,25 @@ GrGpuResource* GrResourceCache::findAndRefScratchResource(const GrScratchKey& sc
     return resource;
 }
 
+GrGpuResource* GrResourceCache::findAndRefUniqueResource(const GrUniqueKey& key) {
+    GrGpuResource* resource = fUniqueHash.find(key);
+    if (resource) {
+        this->refAndMakeResourceMRU(resource);
+    } else {
+        this->recordKeyMiss(key);
+    }
+    return resource;
+}
+
+void GrResourceCache::recordKeyMiss(const GrUniqueKey& key) {
+    // If a resource with this key was purged either this flush or the previous flush, consider it
+    // a recent purge.
+    if (fUniqueKeysPurgedThisFlush[0].find(key) || fUniqueKeysPurgedThisFlush[1].find(key)) {
+        ++fMissesThisFlushPurgedRecently;
+    }
+    ++fTotalMissesThisFlush;
+}
+
 void GrResourceCache::willRemoveScratchKey(const GrGpuResource* resource) {
     SkASSERT(resource->resourcePriv().getScratchKey().isValid());
     if (!resource->getUniqueKey().isValid()) {
@@ -405,9 +433,12 @@ void GrResourceCache::notifyCntReachedZero(GrGpuResource* resource, uint32_t fla
     } else {
         // Purge the resource immediately if we're over budget
         // Also purge if the resource has neither a valid scratch key nor a unique key.
-        bool noKey = !resource->resourcePriv().getScratchKey().isValid() &&
-                     !resource->getUniqueKey().isValid();
-        if (!this->overBudget() && !noKey) {
+        bool hasKey = resource->resourcePriv().getScratchKey().isValid() ||
+                      resource->getUniqueKey().isValid();
+        if (hasKey) {
+            if (this->overBudget()) {
+                this->purgeAsNeeded();
+            }
             return;
         }
     }
@@ -467,7 +498,32 @@ void GrResourceCache::didChangeBudgetStatus(GrGpuResource* resource) {
     this->validate();
 }
 
-void GrResourceCache::purgeAsNeeded() {
+void GrResourceCache::recordPurgedKey(GrGpuResource* resource) {
+    // This maximum exists to avoid allocating too much space for key tracking.
+    static constexpr int kMaxTrackedKeys = 256;
+    if (fUniqueKeysPurgedThisFlush[fFlushParity].count() >= kMaxTrackedKeys) {
+        return;
+    }
+    if (resource->getUniqueKey().isValid() &&
+        !fUniqueKeysPurgedThisFlush[fFlushParity].find(resource->getUniqueKey())) {
+        void* p = fUniqueKeysPurgedThisFlushStorage[fFlushParity].allocThrow(sizeof(GrUniqueKey));
+        GrUniqueKey* copy = new (p) GrUniqueKey;
+        *copy = resource->getUniqueKey();
+        fUniqueKeysPurgedThisFlush[fFlushParity].add(copy);
+    }
+}
+

[robertphillips, 2016/09/13 13:05:21]

I wonder if it would be better to use function pointers rather than always
having an if test.

[bsalomon, 2016/09/13 13:31:33]

We're about to perform a fairly heavy operation, so I'm not sure it matters from
a performance perspective. Or did you mean for clarity?

[robertphillips, 2016/09/13 13:56:48]

A bit of both but it is certainly fine as is.

+GrGpuResource* GrResourceCache::selectResourceUsingStrategy() {
+    switch (fStrategy) {
+        case ReplacementStrategy::kLRU:
+            return fPurgeableQueue.peek();
+        case ReplacementStrategy::kRandom:
+            return fPurgeableQueue.at(fRandom.nextULessThan(fPurgeableQueue.count()));
+    }
+    return nullptr;
+}
+
+void GrResourceCache::internalPurgeAsNeeded(bool fromFlushNotification) {
     SkTArray<GrUniqueKeyInvalidatedMessage> invalidKeyMsgs;
     fInvalidUniqueKeyInbox.poll(&invalidKeyMsgs);
     if (invalidKeyMsgs.count()) {
@@ -487,25 +543,27 @@ void GrResourceCache::purgeAsNeeded() {
             }
             GrGpuResource* resource = fPurgeableQueue.peek();
             SkASSERT(resource->isPurgeable());
+            this->recordPurgedKey(resource);
             resource->cacheAccess().release();
         }
     }
+    if (ReplacementStrategy::kRandom == fStrategy && !fromFlushNotification) {
+        // Wait until after the requested flush when all the pending IO resources will be eligible
+        // for the draft.
+        SkASSERT(!this->overBudget() || this->requestsFlush());
+        return;
+    }
 
     bool stillOverbudget = this->overBudget();
     while (stillOverbudget && fPurgeableQueue.count()) {
-        GrGpuResource* resource = fPurgeableQueue.peek();
+        GrGpuResource* resource = this->selectResourceUsingStrategy();
         SkASSERT(resource->isPurgeable());
+        this->recordPurgedKey(resource);
         resource->cacheAccess().release();
         stillOverbudget = this->overBudget();
     }
 
     this->validate();
-
-    if (stillOverbudget) {
-        // Set this so that GrDrawingManager will issue a flush to free up resources with pending
-        // IO that we were unable to purge in this pass.
-        fRequestFlush = true;
-    }
 }
 
 void GrResourceCache::purgeAllUnlocked() {
@@ -565,14 +623,8 @@ uint32_t GrResourceCache::getNextTimestamp() {
                 *sortedPurgeableResources.append() = fPurgeableQueue.peek();
                 fPurgeableQueue.pop();
             }
-
-            struct Less {
-                bool operator()(GrGpuResource* a, GrGpuResource* b) {
-                    return CompareTimestamp(a,b);
-                }
-            };
-            Less less;
-            SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1, less);
+            SkTQSort(fNonpurgeableResources.begin(), fNonpurgeableResources.end() - 1,
+                     CompareTimestamp);
 
             // Pick resources out of the purgeable and non-purgeable arrays based on lowest
             // timestamp and assign new timestamps.
@@ -624,10 +676,25 @@ void GrResourceCache::notifyFlushOccurred(FlushType type) {
         case FlushType::kImmediateMode:
             break;
         case FlushType::kCacheRequested:
-            SkASSERT(fRequestFlush);
-            fRequestFlush = false;
             break;
-        case FlushType::kExternal:
+        case FlushType::kExternal: {
+            int scoreDelta = 1;
+            if (fMissesThisFlushPurgedRecently) {
+                // If > 60% of our cache misses were things we purged in the last two flushes
+                // then we move closer towards selecting random replacement.
+                if ((float)fMissesThisFlushPurgedRecently / fTotalMissesThisFlush > 0.6f) {
+                    scoreDelta = -1;
+                }
+            }
+            fStrategyScore = SkTPin(fStrategyScore + scoreDelta, kStrategyScoreMin,
+                                    kStrategyScoreMax);
+            fStrategy = fStrategyScore < 0 ? ReplacementStrategy::kRandom
+                                           : ReplacementStrategy::kLRU;
+            fMissesThisFlushPurgedRecently = 0;
+            fTotalMissesThisFlush = 0;
+            fFlushParity = -(fFlushParity - 1);
+            fUniqueKeysPurgedThisFlush[fFlushParity].reset();
+            fUniqueKeysPurgedThisFlushStorage[fFlushParity].rewind();
             if (fFlushTimestamps) {
                 SkASSERT(SkIsPow2(fMaxUnusedFlushes));
                 fLastFlushTimestampIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
@@ -637,8 +704,9 @@ void GrResourceCache::notifyFlushOccurred(FlushType type) {
                 fFlushTimestamps[fLastFlushTimestampIndex] = timestamp;
             }
             break;
+        }
     }
-    this->purgeAsNeeded();
+    this->internalPurgeAsNeeded(true);
 }
 
 void GrResourceCache::dumpMemoryStatistics(SkTraceMemoryDump* traceMemoryDump) const {