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 bf7b237006b0fd270a1056744c130b5ce006be94..a481c222171a9ae4e71d09a0753233046879416a 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"
@@ -142,13 +144,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.
@@ -159,14 +155,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,
@@ -237,11 +238,15 @@ private:
     void refAndMakeResourceMRU(GrGpuResource*);
     /// @}
 
+    void internalPurgeAsNeeded(bool fromFlushNotification);
     void resetFlushTimestamps();
     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;
@@ -260,22 +265,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;
 

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

missing space before '{' ?

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

Done.

+    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();
     }
@@ -284,6 +294,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 kInitialStrategyScoreMax = 3;
+
     typedef SkMessageBus<GrUniqueKeyInvalidatedMessage>::Inbox InvalidUniqueKeyInbox;
     typedef SkTDPQueue<GrGpuResource*, CompareTimestamp, AccessResourceIndex> PurgeableQueue;
     typedef SkTDArray<GrGpuResource*> ResourceArray;
@@ -305,6 +331,16 @@ private:
     size_t                              fMaxBytes;
     int                                 fMaxUnusedFlushes;
 
+    // Data related to replacement strategy.
+    SkRandom                            fRandom;
+    ReplacementStrategy                 fStrategy;
+    int                                 fStrategyScore;
+    int                                 fTotalMissesThisFlush;
+    int                                 fMissesThisFlushPurgedRecently;
+    UniqueKeySet                        fUniqueKeysPurgedThisFlush[2];
+    SkChunkAlloc                        fUniqueKeysPurgedThisFlushStorage[2];
+    int                                 fFlushParity;
+
 #if GR_CACHE_STATS
     int                                 fHighWaterCount;
     size_t                              fHighWaterBytes;
@@ -320,8 +356,6 @@ private:
     int                                 fBudgetedCount;
     size_t                              fBudgetedBytes;
 
-    bool                                fRequestFlush;
-
     // We keep track of the "timestamps" of the last n flushes. If a resource hasn't been used in
     // that time then we well preemptively purge it to reduce memory usage.
     uint32_t*                           fFlushTimestamps;