Make GrResourceCache dynamically change between LRU and random replacement strategies.

src/gpu/GrResourceCache.h

 /*
  * Copyright 2014 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #ifndef GrResourceCache_DEFINED
 #define GrResourceCache_DEFINED
 
 #include "GrGpuResource.h"
 #include "GrGpuResourceCacheAccess.h"
 #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"
 #include "SkTInternalLList.h"
 #include "SkTMultiMap.h"
 
 class GrCaps;
 class SkString;
 class SkTraceMemoryDump;
 
@@ skipping 103 matching lines @@
 #ifdef SK_DEBUG
     // This is not particularly fast and only used for validation, so debug only.
     int countScratchEntriesForKey(const GrScratchKey& scratchKey) const {
         return fScratchMap.countForKey(scratchKey);
     }
 #endif
 
     /**
      * 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.
      */
     bool hasUniqueKey(const GrUniqueKey& key) const {
         return SkToBool(fUniqueHash.find(key));
     }
 
     /** 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,
         kImmediateMode,
         kCacheRequested,
     };
     void notifyFlushOccurred(FlushType);
 
 #if GR_CACHE_STATS
     struct Stats {
@@ skipping 50 matching lines @@
     void removeResource(GrGpuResource*);
     void notifyCntReachedZero(GrGpuResource*, uint32_t flags);
     void didChangeGpuMemorySize(const GrGpuResource*, size_t oldSize);
     void changeUniqueKey(GrGpuResource*, const GrUniqueKey&);
     void removeUniqueKey(GrGpuResource*);
     void willRemoveScratchKey(const GrGpuResource*);
     void didChangeBudgetStatus(GrGpuResource*);
     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;
     }
 
     uint32_t getNextTimestamp();
 
 #ifdef SK_DEBUG
     bool isInCache(const GrGpuResource* r) const;
     void validate() const;
 #else
     void validate() const {}
 #endif
 
     class AutoValidate;
 
     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();
     }
 
     static int* AccessResourceIndex(GrGpuResource* const& res) {
         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;
 
     // Whenever a resource is added to the cache or the result of a cache lookup, fTimestamp is
     // assigned as the resource's timestamp and then incremented. fPurgeableQueue orders the
     // purgeable resources by this value, and thus is used to purge resources in LRU order.
     uint32_t                            fTimestamp;
     PurgeableQueue                      fPurgeableQueue;
     ResourceArray                       fNonpurgeableResources;
 
     // This map holds all resources that can be used as scratch resources.
     ScratchMap                          fScratchMap;
     // This holds all resources that have unique keys.
     UniqueHash                          fUniqueHash;
 
     // our budget, used in purgeAsNeeded()
     int                                 fMaxCount;
     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;
     int                                 fBudgetedHighWaterCount;
     size_t                              fBudgetedHighWaterBytes;
 #endif
 
     // our current stats for all resources
     SkDEBUGCODE(int                     fCount;)
     size_t                              fBytes;
 
     // our current stats for resources that count against the budget
     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
     // we're in the midst of converting it to purgeable status.
     SkDEBUGCODE(GrGpuResource*          fNewlyPurgeableResourceForValidation;)
 
     bool                                fPreferVRAMUseOverFlushes;
 };
 
 class GrResourceCache::ResourceAccess {
@@ skipping 73 matching lines @@
 
     friend class GrGpuResource; // To access all the proxy inline methods.
     friend class GrResourceCache; // To create this type.
 };
 
 inline GrResourceCache::ResourceAccess GrResourceCache::resourceAccess() {
     return ResourceAccess(this);
 }
 
 #endif