Make GrResourceCache dynamically change between LRU and random replacement strategies.

src/gpu/GrResourceCache.h

Index: src/gpu/GrResourceCache.h
diff --git a/src/gpu/GrResourceCache.h b/src/gpu/GrResourceCache.h
index ae9a4e7ee7e3bae513b5503083209b96e1d8fb74..d6cdf81612205235060502b17f2e13f06b308f47 100644
--- a/src/gpu/GrResourceCache.h
+++ b/src/gpu/GrResourceCache.h
@@ -13,7 +13,9 @@
 #include "GrGpuResourcePriv.h"
 #include "GrResourceCache.h"
 #include "GrResourceKey.h"
+#include "SkChunkAlloc.h"
 #include "SkMessageBus.h"
+#include "SkRandom.h"
 #include "SkRefCnt.h"
 #include "SkTArray.h"
 #include "SkTDPQueue.h"
@@ -137,13 +139,7 @@ public:
     /**
      * Find a resource that matches a unique key.
      */
-    GrGpuResource* findAndRefUniqueResource(const GrUniqueKey& key) {
-        GrGpuResource* resource = fUniqueHash.find(key);
-        if (resource) {
-            this->refAndMakeResourceMRU(resource);
-        }
-        return resource;
-    }
+    GrGpuResource* findAndRefUniqueResource(const GrUniqueKey& key);
 
     /**
      * Query whether a unique key exists in the cache.
@@ -154,14 +150,19 @@ public:
 
     /** Purges resources to become under budget and processes resources with invalidated unique
         keys. */
-    void purgeAsNeeded();
+    void purgeAsNeeded() { this->internalPurgeAsNeeded(false); }
 
     /** Purges all resources that don't have external owners. */
     void purgeAllUnlocked();
 
     /** Returns true if the cache would like a flush to occur in order to make more resources
         purgeable. */
-    bool requestsFlush() const { return fRequestFlush; }
+    bool requestsFlush() const {
+        // When in random replacement mode we request a flush in order to make as many resources
+        // as possible subject to replacement.
+        return this->overBudget() && (ReplacementStrategy::kRandom == fStrategy ||
+                                      0 == fPurgeableQueue.count());
+    }
 
     enum FlushType {
         kExternal,
@@ -232,10 +233,14 @@ private:
     void refAndMakeResourceMRU(GrGpuResource*);
     /// @}
 
+    void internalPurgeAsNeeded(bool fromFlushNotification);
     void processInvalidUniqueKeys(const SkTArray<GrUniqueKeyInvalidatedMessage>&);
     void addToNonpurgeableArray(GrGpuResource*);
     void removeFromNonpurgeableArray(GrGpuResource*);
     bool overBudget() const { return fBudgetedBytes > fMaxBytes || fBudgetedCount > fMaxCount; }
+    GrGpuResource* selectResourceUsingStrategy();
+    void recordPurgedKey(GrGpuResource*);
+    void recordKeyMiss(const GrUniqueKey&);
 
     bool wouldFit(size_t bytes) {
         return fBudgetedBytes+bytes <= fMaxBytes && fBudgetedCount+1 <= fMaxCount;
@@ -254,22 +259,27 @@ private:
 
     class AvailableForScratchUse;
 
-    struct ScratchMapTraits {
+    struct HashTraitsBase {
+        static uint32_t Hash(const GrResourceKey& key) { return key.hash(); }
+    };
+
+    struct ScratchMapTraits : public HashTraitsBase {
         static const GrScratchKey& GetKey(const GrGpuResource& r) {
             return r.resourcePriv().getScratchKey();
         }
-
-        static uint32_t Hash(const GrScratchKey& key) { return key.hash(); }
     };
     typedef SkTMultiMap<GrGpuResource, GrScratchKey, ScratchMapTraits> ScratchMap;
 
-    struct UniqueHashTraits {
+    struct UniqueHashTraits : public HashTraitsBase {
         static const GrUniqueKey& GetKey(const GrGpuResource& r) { return r.getUniqueKey(); }
-
-        static uint32_t Hash(const GrUniqueKey& key) { return key.hash(); }
     };
     typedef SkTDynamicHash<GrGpuResource, GrUniqueKey, UniqueHashTraits> UniqueHash;
 
+    struct UniqueSetTraits : public HashTraitsBase {
+        static const GrUniqueKey& GetKey(const GrUniqueKey& key) { return key; }
+    };
+    typedef SkTDynamicHash<GrUniqueKey, GrUniqueKey, UniqueSetTraits> UniqueKeySet;
+
     static bool CompareTimestamp(GrGpuResource* const& a, GrGpuResource* const& b) {
         return a->cacheAccess().timestamp() < b->cacheAccess().timestamp();
     }
@@ -278,6 +288,22 @@ private:
         return res->cacheAccess().accessCacheIndex();
     }
 
+    /**
+     * The resource cache chooses one of these replacement strategies based on a "strategy score"
+     * updated after each external flush based on unique key cache misses.
+     */
+    enum class ReplacementStrategy {
+        kLRU,
+        kRandom
+    };
+    /**
+     * When the current strategy score is >=0 LRU is chosen, when it is < 0 random is chosen. The
+     * absolute value of the score moves by 1 each flush.
+     */
+    static constexpr int kStrategyScoreMin = -5;
+    static constexpr int kStrategyScoreMax = 4;
+    static constexpr int kInitialStrategyScore = 2;
+
     typedef SkMessageBus<GrUniqueKeyInvalidatedMessage>::Inbox InvalidUniqueKeyInbox;
     typedef SkTDPQueue<GrGpuResource*, CompareTimestamp, AccessResourceIndex> PurgeableQueue;
     typedef SkTDArray<GrGpuResource*> ResourceArray;
@@ -299,6 +325,17 @@ private:
     size_t                              fMaxBytes;
     int                                 fMaxUnusedFlushes;
 
+    // Data related to replacement strategy.
+    SkRandom                            fRandom;
+    ReplacementStrategy                 fStrategy;
+    int                                 fStrategyScore;
+    int                                 fTotalMissesThisFlush;
+    int                                 fMissesThisFlushPurgedRecently;
+    UniqueKeySet                        fUniqueKeysPurgedThisFlush[2];
+    // These are pointers to SkChunckAlloc because of gcc bug 63707
+    SkChunkAlloc*                       fUniqueKeysPurgedThisFlushStorage[2];
+    int                                 fFlushParity;
+
 #if GR_CACHE_STATS
     int                                 fHighWaterCount;
     size_t                              fHighWaterBytes;
@@ -314,9 +351,10 @@ private:
     int                                 fBudgetedCount;
     size_t                              fBudgetedBytes;
 
-    bool                                fRequestFlush;
     uint32_t                            fExternalFlushCnt;
 
+    bool                                fIsPurging;
+
     InvalidUniqueKeyInbox               fInvalidUniqueKeyInbox;
 
     // This resource is allowed to be in the nonpurgeable array for the sake of validate() because