Make GrResourceCache dynamically change between LRU and random replacement strategies.

src/gpu/GrResourceCache.cpp

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 
 #include "GrResourceCache.h"
 
@@ skipping 39 matching lines @@
 
 class GrResourceCache::AutoValidate : ::SkNoncopyable {
 public:
     AutoValidate(GrResourceCache* cache) : fCache(cache) { cache->validate(); }
     ~AutoValidate() { fCache->validate(); }
 private:
     GrResourceCache* fCache;
 };
 
  //////////////////////////////////////////////////////////////////////////////
-
+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)
     , fBudgetedHighWaterCount(0)
     , fBudgetedHighWaterBytes(0)
 #endif
     , fBytes(0)
     , fBudgetedCount(0)
     , fBudgetedBytes(0)
-    , fRequestFlush(false)
     , fFlushTimestamps(nullptr)
     , fLastFlushTimestampIndex(0)
     , fPreferVRAMUseOverFlushes(caps->preferVRAMUseOverFlushes()) {
     SkDEBUGCODE(fCount = 0;)
     SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr;)
     this->resetFlushTimestamps();
 }
 
 GrResourceCache::~GrResourceCache() {
     this->releaseAll();
@@ skipping 159 matching lines @@
         return !fRejectPendingIO || !resource->internalHasPendingIO();
     }
 
 private:
     bool fRejectPendingIO;
 };
 
 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));
         if (resource) {
             this->refAndMakeResourceMRU(resource);
             this->validate();
             return resource;
         } else if (flags & kRequireNoPendingIO_ScratchFlag) {
             return nullptr;
         }
         // We would prefer to consume more available VRAM rather than flushing
         // immediately, but on ANGLE this can lead to starving of the GPU.
         if (fPreferVRAMUseOverFlushes && this->wouldFit(resourceSize)) {
             // kPrefer is specified, we didn't find a resource without pending io,
             // but there is still space in our budget for the resource so force
             // the caller to allocate a new resource.
             return nullptr;
         }
     }
     resource = fScratchMap.find(scratchKey, AvailableForScratchUse(false));
     if (resource) {
         this->refAndMakeResourceMRU(resource);
         this->validate();
     }
     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()) {
         fScratchMap.remove(resource->resourcePriv().getScratchKey(), resource);
     }
 }
 
 void GrResourceCache::removeUniqueKey(GrGpuResource* resource) {
     // Someone has a ref to this resource in order to have removed the key. When the ref count
     // reaches zero we will get a ref cnt notification and figure out what to do with it.
@@ skipping 103 matching lines @@
             // We won't purge an existing resource to make room for this one.
             if (fBudgetedCount < fMaxCount &&
                 fBudgetedBytes + resource->gpuMemorySize() <= fMaxBytes) {
                 resource->resourcePriv().makeBudgeted();
                 return;
             }
         }
     } 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;
         }
     }
 
     SkDEBUGCODE(int beforeCount = this->getResourceCount();)
     resource->cacheAccess().release();
     // We should at least free this resource, perhaps dependent resources as well.
     SkASSERT(this->getResourceCount() < beforeCount);
     this->validate();
 }
@@ skipping 39 matching lines @@
     } else {
         --fBudgetedCount;
         fBudgetedBytes -= size;
     }
     TRACE_COUNTER2(TRACE_DISABLED_BY_DEFAULT("skia.gpu.cache"), "skia budget", "used",
                    fBudgetedBytes, "free", fMaxBytes - fBudgetedBytes);
 
     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()) {
         this->processInvalidUniqueKeys(invalidKeyMsgs);
     }
 
     if (fFlushTimestamps) {
         // Assuming kNumFlushesToDeleteUnusedResource is a power of 2.
         SkASSERT(SkIsPow2(fMaxUnusedFlushes));
         int oldestFlushIndex = (fLastFlushTimestampIndex + 1) & (fMaxUnusedFlushes - 1);
 
         uint32_t oldestAllowedTimestamp = fFlushTimestamps[oldestFlushIndex];
         while (fPurgeableQueue.count()) {
             uint32_t oldestResourceTimestamp = fPurgeableQueue.peek()->cacheAccess().timestamp();
             if (oldestAllowedTimestamp < oldestResourceTimestamp) {
                 break;
             }
             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() {
     // We could disable maintaining the heap property here, but it would add a lot of complexity.
     // Moreover, this is rarely called.
     while (fPurgeableQueue.count()) {
         GrGpuResource* resource = fPurgeableQueue.peek();
         SkASSERT(resource->isPurgeable());
         resource->cacheAccess().release();
     }
@@ skipping 39 matching lines @@
             // Reset all the timestamps. We sort the resources by timestamp and then assign
             // sequential timestamps beginning with 0. This is O(n*lg(n)) but it should be extremely
             // rare.
             SkTDArray<GrGpuResource*> sortedPurgeableResources;
             sortedPurgeableResources.setReserve(fPurgeableQueue.count());
 
             while (fPurgeableQueue.count()) {
                 *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.
             int currP = 0;
             int currNP = 0;
             while (currP < sortedPurgeableResources.count() &&
                    currNP < fNonpurgeableResources.count()) {
                 uint32_t tsP = sortedPurgeableResources[currP]->cacheAccess().timestamp();
                 uint32_t tsNP = fNonpurgeableResources[currNP]->cacheAccess().timestamp();
                 SkASSERT(tsP != tsNP);
@@ skipping 31 matching lines @@
         }
     }
     return fTimestamp++;
 }
 
 void GrResourceCache::notifyFlushOccurred(FlushType type) {
     switch (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);
                 // get the timestamp before accessing fFlushTimestamps because getNextTimestamp will
                 // reallocate fFlushTimestamps on timestamp overflow.
                 uint32_t timestamp = this->getNextTimestamp();
                 fFlushTimestamps[fLastFlushTimestampIndex] = timestamp;
             }
             break;
+        }
     }
-    this->purgeAsNeeded();
+    this->internalPurgeAsNeeded(true);
 }
 
 void GrResourceCache::dumpMemoryStatistics(SkTraceMemoryDump* traceMemoryDump) const {
     for (int i = 0; i < fNonpurgeableResources.count(); ++i) {
         fNonpurgeableResources[i]->dumpMemoryStatistics(traceMemoryDump);
     }
     for (int i = 0; i < fPurgeableQueue.count(); ++i) {
         fPurgeableQueue.at(i)->dumpMemoryStatistics(traceMemoryDump);
     }
 }
@@ skipping 127 matching lines @@
         return true;
     }
     if (index < fNonpurgeableResources.count() && fNonpurgeableResources[index] == resource) {
         return true;
     }
     SkDEBUGFAIL("Resource index should be -1 or the resource should be in the cache.");
     return false;
 }
 
 #endif