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::kInitialStrategyScore;
 
 GrResourceCache::GrResourceCache(const GrCaps* caps)
     : fTimestamp(0)
     , fMaxCount(kDefaultMaxCount)
     , fMaxBytes(kDefaultMaxSize)
     , fMaxUnusedFlushes(kDefaultMaxUnusedFlushes)
+    , fStrategy(ReplacementStrategy::kLRU)
+    , fStrategyScore(kInitialStrategyScore)
+    , fTotalMissesThisFlush(0)
+    , fMissesThisFlushPurgedRecently(0)
+    , fUniqueKeysPurgedThisFlushStorage {new SkChunkAlloc(8*sizeof(GrUniqueKey)),
+                                         new SkChunkAlloc(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)
     , fExternalFlushCnt(0)
+    , fIsPurging(false)
     , fPreferVRAMUseOverFlushes(caps->preferVRAMUseOverFlushes()) {
     SkDEBUGCODE(fCount = 0;)
     SkDEBUGCODE(fNewlyPurgeableResourceForValidation = nullptr;)
 }
 
 GrResourceCache::~GrResourceCache() {
     this->releaseAll();
+    delete fUniqueKeysPurgedThisFlushStorage[0];
+    delete fUniqueKeysPurgedThisFlushStorage[1];
 }
 
 void GrResourceCache::setLimits(int count, size_t bytes, int maxUnusedFlushes) {
     fMaxCount = count;
     fMaxBytes = bytes;
     fMaxUnusedFlushes = maxUnusedFlushes;
     this->purgeAsNeeded();
 }
 
 void GrResourceCache::insertResource(GrGpuResource* resource) {
@@ skipping 125 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 104 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);
+    }
+}
+
+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) {
+    if (fIsPurging) {
+        return;
+    }
+    fIsPurging = true;
     SkTArray<GrUniqueKeyInvalidatedMessage> invalidKeyMsgs;
     fInvalidUniqueKeyInbox.poll(&invalidKeyMsgs);
     if (invalidKeyMsgs.count()) {
         this->processInvalidUniqueKeys(invalidKeyMsgs);
     }
 
     if (fMaxUnusedFlushes > 0) {
         // We want to know how many complete flushes have occurred without the resource being used.
         // If the resource was tagged when fExternalFlushCnt was N then this means it became
         // purgeable during activity that became the N+1th flush. So when the flush count is N+2
         // it has sat in the purgeable queue for one entire flush.
         uint32_t oldestAllowedFlushCnt = fExternalFlushCnt - fMaxUnusedFlushes - 1;
         // check for underflow
         if (oldestAllowedFlushCnt < fExternalFlushCnt) {
             while (fPurgeableQueue.count()) {
                 uint32_t flushWhenResourceBecamePurgeable =
                         fPurgeableQueue.peek()->cacheAccess().flushCntWhenResourceBecamePurgeable();
                 if (oldestAllowedFlushCnt < flushWhenResourceBecamePurgeable) {
                     // Resources were given both LRU timestamps and tagged with a flush cnt when
                     // they first became purgeable. The LRU timestamp won't change again until the
                     // resource is made non-purgeable again. So, at this point all the remaining
                     // resources in the timestamp-sorted queue will have a flush count >= to this
                     // one.
                     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());
+        fIsPurging = false;
+        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;
-    }
+    fIsPurging = false;
 }
 
 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();
             }
-
             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();
@@ skipping 30 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();
             ++fExternalFlushCnt;
             if (0 == fExternalFlushCnt) {
                 // When this wraps just reset all the purgeable resources' last used flush state.
                 for (int i = 0; i < fPurgeableQueue.count(); ++i) {
                     fPurgeableQueue.at(i)->cacheAccess().setFlushCntWhenResourceBecamePurgeable(0);
                 }
             }
             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