Change VkPipelineStateCahce to use Hash and LRU LList.

This simplifies the caching code and forms the base for a caching template
that will be easier to use for other objects within Vulkan.

BUG=skia:
GOLD_TRYBOT_URL= https://gold.skia.org/search2?unt=true&query=source_type%3Dgm&master=false&issue=1836863002

Review URL: https://codereview.chromium.org/1836863002

5 files changed, 103 insertions, 196 deletions

diff --git a/src/gpu/vk/GrVkGpu.cpp b/src/gpu/vk/GrVkGpu.cpp
index e0aa2d2987..496f38c3df 100644
--- a/src/gpu/vk/GrVkGpu.cpp
+++ b/src/gpu/vk/GrVkGpu.cpp
@@ -1293,26 +1293,26 @@ bool GrVkGpu::onReadPixels(GrSurface* surface,
 
     return true;
 }
-bool GrVkGpu::prepareDrawState(const GrPipeline& pipeline,
-                               const GrPrimitiveProcessor& primProc,
-                               GrPrimitiveType primitiveType,
-                               const GrVkRenderPass& renderPass,
-                               GrVkPipelineState** pipelineState) {
-    *pipelineState = fResourceProvider.findOrCreateCompatiblePipelineState(pipeline,
-                                                                           primProc,
-                                                                           primitiveType,
-                                                                           renderPass);
+sk_sp<GrVkPipelineState> GrVkGpu::prepareDrawState(const GrPipeline& pipeline,
+                                                   const GrPrimitiveProcessor& primProc,
+                                                   GrPrimitiveType primitiveType,
+                                                   const GrVkRenderPass& renderPass) {
+    sk_sp<GrVkPipelineState> pipelineState =
+        fResourceProvider.findOrCreateCompatiblePipelineState(pipeline,
+                                                              primProc,
+                                                              primitiveType,
+                                                              renderPass);
     if (!pipelineState) {
-        return false;
+        return pipelineState;
     }
 
-    (*pipelineState)->setData(this, primProc, pipeline);
+    pipelineState->setData(this, primProc, pipeline);
 
-    (*pipelineState)->bind(this, fCurrentCmdBuffer);
+    pipelineState->bind(this, fCurrentCmdBuffer);
 
     GrVkPipeline::SetDynamicState(this, fCurrentCmdBuffer, pipeline);
 
-    return true;
+    return pipelineState;
 }
 
 void GrVkGpu::onDraw(const GrPipeline& pipeline,
@@ -1329,9 +1329,12 @@ void GrVkGpu::onDraw(const GrPipeline& pipeline,
 
     fCurrentCmdBuffer->beginRenderPass(this, renderPass, *vkRT);
 
-    GrVkPipelineState* pipelineState = nullptr;
     GrPrimitiveType primitiveType = meshes[0].primitiveType();
-    if (!this->prepareDrawState(pipeline, primProc, primitiveType, *renderPass, &pipelineState)) {
+    sk_sp<GrVkPipelineState> pipelineState = this->prepareDrawState(pipeline,
+                                                                    primProc,
+                                                                    primitiveType,
+                                                                    *renderPass);
+    if (!pipelineState) {
         return;
     }
 
@@ -1386,11 +1389,13 @@ void GrVkGpu::onDraw(const GrPipeline& pipeline,
                 // pipelineState:setData but this will allow for quicker freeing of resources if the
                 // pipelineState sits in a cache for a while.
                 pipelineState->freeTempResources(this);
-                pipelineState->unref();
                 SkDEBUGCODE(pipelineState = nullptr);
                 primitiveType = nonIdxMesh->primitiveType();
-                if (!this->prepareDrawState(pipeline, primProc, primitiveType, *renderPass,
-                                            &pipelineState)) {
+                pipelineState = this->prepareDrawState(pipeline,
+                                                       primProc,
+                                                       primitiveType,
+                                                       *renderPass);
+                if (!pipelineState) {
                     return;
                 }
             }
@@ -1422,7 +1427,6 @@ void GrVkGpu::onDraw(const GrPipeline& pipeline,
     // pipelineState:setData but this will allow for quicker freeing of resources if the
     // pipelineState sits in a cache for a while.
     pipelineState->freeTempResources(this);
-    pipelineState->unref();
 
 #if SWAP_PER_DRAW
     glFlush();
diff --git a/src/gpu/vk/GrVkGpu.h b/src/gpu/vk/GrVkGpu.h
index bf25f1cee6..91a67b6deb 100644
--- a/src/gpu/vk/GrVkGpu.h
+++ b/src/gpu/vk/GrVkGpu.h
@@ -160,11 +160,10 @@ private:
 
     void onResolveRenderTarget(GrRenderTarget* target) override {}
 
-    bool prepareDrawState(const GrPipeline&,
-                          const GrPrimitiveProcessor&,
-                          GrPrimitiveType,
-                          const GrVkRenderPass&,
-                          GrVkPipelineState** pipelineState);
+    sk_sp<GrVkPipelineState> prepareDrawState(const GrPipeline&,
+                                              const GrPrimitiveProcessor&,
+                                              GrPrimitiveType,
+                                              const GrVkRenderPass&);
 
     // Bind vertex and index buffers
     void bindGeometry(const GrPrimitiveProcessor&, const GrNonInstancedMesh&);
diff --git a/src/gpu/vk/GrVkPipelineStateCache.cpp b/src/gpu/vk/GrVkPipelineStateCache.cpp
index f2092af981..a250dcac99 100644
--- a/src/gpu/vk/GrVkPipelineStateCache.cpp
+++ b/src/gpu/vk/GrVkPipelineStateCache.cpp
@@ -12,117 +12,91 @@
 #include "GrVkPipelineState.h"
 #include "GrVkPipelineStateBuilder.h"
 #include "SkRTConf.h"
-#include "SkTSearch.h"
 #include "glsl/GrGLSLFragmentProcessor.h"
 #include "glsl/GrGLSLProgramDataManager.h"
 
-#ifdef PIPELINE_STATE_CACHE_STATS
-SK_CONF_DECLARE(bool, c_DisplayCache, "gpu.displayCache", false,
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
+SK_CONF_DECLARE(bool, c_DisplayVkPipelineCache, "gpu.displayyVkPipelineCache", false,
                 "Display pipeline state cache usage.");
 #endif
 
-typedef GrGLSLProgramDataManager::UniformHandle UniformHandle;
-
 struct GrVkResourceProvider::PipelineStateCache::Entry {
 
-    Entry() : fPipelineState(nullptr), fLRUStamp(0) {}
-
-    SkAutoTUnref<GrVkPipelineState> fPipelineState;
-    unsigned int                    fLRUStamp;
-};
+    Entry() : fPipelineState(nullptr) {}
 
-struct GrVkResourceProvider::PipelineStateCache::PipelineDescLess {
-    bool operator() (const GrVkPipelineState::Desc& desc, const Entry* entry) {
-        SkASSERT(entry->fPipelineState.get());
-        return GrVkPipelineState::Desc::Less(desc, entry->fPipelineState->getDesc());
+    static const GrVkPipelineState::Desc& GetKey(const Entry* entry) {
+        return entry->fPipelineState->getDesc();
     }
 
-    bool operator() (const Entry* entry, const GrVkPipelineState::Desc& desc) {
-        SkASSERT(entry->fPipelineState.get());
-        return GrVkPipelineState::Desc::Less(entry->fPipelineState->getDesc(), desc);
+    static uint32_t Hash(const GrVkPipelineState::Desc& key) {
+        return key.fChecksum;
     }
+
+    sk_sp<GrVkPipelineState> fPipelineState;
+
+private:
+    SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
 };
 
 GrVkResourceProvider::PipelineStateCache::PipelineStateCache(GrVkGpu* gpu)
     : fCount(0)
-    , fCurrLRUStamp(0)
     , fGpu(gpu)
-#ifdef PIPELINE_STATE_CACHE_STATS
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
     , fTotalRequests(0)
     , fCacheMisses(0)
-    , fHashMisses(0)
 #endif
-{
-    for (int i = 0; i < 1 << kHashBits; ++i) {
-        fHashTable[i] = nullptr;
-    }
-}
+{}
 
 GrVkResourceProvider::PipelineStateCache::~PipelineStateCache() {
     SkASSERT(0 == fCount);
     // dump stats
-#ifdef PIPELINE_STATE_CACHE_STATS
-    if (c_DisplayCache) {
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
+    if (c_DisplayVkPipelineCache) {
         SkDebugf("--- Pipeline State Cache ---\n");
         SkDebugf("Total requests: %d\n", fTotalRequests);
         SkDebugf("Cache misses: %d\n", fCacheMisses);
         SkDebugf("Cache miss %%: %f\n", (fTotalRequests > 0) ?
                  100.f * fCacheMisses / fTotalRequests :
                  0.f);
-        int cacheHits = fTotalRequests - fCacheMisses;
-        SkDebugf("Hash miss %%: %f\n", (cacheHits > 0) ? 100.f * fHashMisses / cacheHits : 0.f);
         SkDebugf("---------------------\n");
     }
 #endif
 }
 
 void GrVkResourceProvider::PipelineStateCache::reset() {
-    for (int i = 0; i < fCount; ++i) {
-        delete fEntries[i];
-        fEntries[i] = nullptr;
-    }
+    fHashTable.foreach([](Entry** entry) {
+        delete *entry;
+    });
+    fHashTable.reset();
     fCount = 0;
-
-    // zero out hash table
-    for (int i = 0; i < 1 << kHashBits; i++) {
-        fHashTable[i] = nullptr;
-    }
-
-    fCurrLRUStamp = 0;
 }
 
 void GrVkResourceProvider::PipelineStateCache::abandon() {
-    for (int i = 0; i < fCount; ++i) {
-        SkASSERT(fEntries[i]->fPipelineState.get());
-        fEntries[i]->fPipelineState->abandonGPUResources();
-    }
+    fHashTable.foreach([](Entry** entry) {
+        SkASSERT((*entry)->fPipelineState.get());
+        (*entry)->fPipelineState->abandonGPUResources();
+    });
+
     this->reset();
 }
 
 void GrVkResourceProvider::PipelineStateCache::release() {
-    for (int i = 0; i < fCount; ++i) {
-        SkASSERT(fEntries[i]->fPipelineState.get());
-        fEntries[i]->fPipelineState->freeGPUResources(fGpu);
-    }
-    this->reset();
-}
+    fHashTable.foreach([this](Entry** entry) {
+        SkASSERT((*entry)->fPipelineState.get());
+        (*entry)->fPipelineState->freeGPUResources(fGpu);
+    });
 
-int GrVkResourceProvider::PipelineStateCache::search(const GrVkPipelineState::Desc& desc) const {
-    PipelineDescLess less;
-    return SkTSearch(fEntries, fCount, desc, sizeof(Entry*), less);
+    this->reset();
 }
 
-GrVkPipelineState* GrVkResourceProvider::PipelineStateCache::refPipelineState(
+sk_sp<GrVkPipelineState> GrVkResourceProvider::PipelineStateCache::refPipelineState(
                                                                const GrPipeline& pipeline,
                                                                const GrPrimitiveProcessor& primProc,
-                                                               GrPrimitiveType primiteType,
+                                                               GrPrimitiveType primitiveType,
                                                                const GrVkRenderPass& renderPass) {
-#ifdef PIPELINE_STATE_CACHE_STATS
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
     ++fTotalRequests;
 #endif
-
-    Entry* entry = nullptr;
-
     // Get GrVkProgramDesc
     GrVkPipelineState::Desc desc;
     if (!GrVkProgramDescBuilder::Build(&desc.fProgramDesc,
@@ -134,7 +108,7 @@ GrVkPipelineState* GrVkResourceProvider::PipelineStateCache::refPipelineState(
     }
 
     // Get vulkan specific descriptor key
-    GrVkPipelineState::BuildStateKey(pipeline, primiteType, &desc.fStateKey);
+    GrVkPipelineState::BuildStateKey(pipeline, primitiveType, &desc.fStateKey);
     // Get checksum of entire PipelineDesc
     int keyLength = desc.fStateKey.count();
     SkASSERT(0 == (keyLength % 4));
@@ -142,108 +116,42 @@ GrVkPipelineState* GrVkResourceProvider::PipelineStateCache::refPipelineState(
     desc.fChecksum = SkChecksum::Murmur3(desc.fStateKey.begin(), keyLength,
                                          desc.fProgramDesc.getChecksum());
 
-    uint32_t hashIdx = desc.fChecksum;
-    hashIdx ^= hashIdx >> 16;
-    if (kHashBits <= 8) {
-        hashIdx ^= hashIdx >> 8;
-    }
-    hashIdx &= ((1 << kHashBits) - 1);
-    Entry* hashedEntry = fHashTable[hashIdx];
-    if (hashedEntry && hashedEntry->fPipelineState->getDesc() == desc) {
-        SkASSERT(hashedEntry->fPipelineState);
-        entry = hashedEntry;
-    }
-
-    int entryIdx;
-    if (nullptr == entry) {
-        entryIdx = this->search(desc);
-        if (entryIdx >= 0) {
-            entry = fEntries[entryIdx];
-#ifdef PIPELINE_STATE_CACHE_STATS
-            ++fHashMisses;
-#endif
-        }
+    Entry* entry = nullptr;
+    if (Entry** entryptr = fHashTable.find(desc)) {
+        SkASSERT(*entryptr);
+        entry = *entryptr;
     }
-
-    if (nullptr == entry) {
-        // We have a cache miss
-#ifdef PIPELINE_STATE_CACHE_STATS
+    if (!entry) {
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
         ++fCacheMisses;
 #endif
-        GrVkPipelineState* pipelineState =
+        sk_sp<GrVkPipelineState> pipelineState(
             GrVkPipelineStateBuilder::CreatePipelineState(fGpu,
                                                           pipeline,
                                                           primProc,
-                                                          primiteType,
+                                                          primitiveType,
                                                           desc,
-                                                          renderPass);
+                                                          renderPass));
         if (nullptr == pipelineState) {
             return nullptr;
         }
-        int purgeIdx = 0;
         if (fCount < kMaxEntries) {
             entry = new Entry;
-            purgeIdx = fCount++;
-            fEntries[purgeIdx] = entry;
+            fCount++;
         } else {
             SkASSERT(fCount == kMaxEntries);
-            purgeIdx = 0;
-            for (int i = 1; i < kMaxEntries; ++i) {
-                if (fEntries[i]->fLRUStamp < fEntries[purgeIdx]->fLRUStamp) {
-                    purgeIdx = i;
-                }
-            }
-            entry = fEntries[purgeIdx];
-            int purgedHashIdx = entry->fPipelineState->getDesc().fChecksum & ((1 << kHashBits) - 1);
-            if (fHashTable[purgedHashIdx] == entry) {
-                fHashTable[purgedHashIdx] = nullptr;
-            }
+            entry = fLRUList.head();
+            fLRUList.remove(entry);
             entry->fPipelineState->freeGPUResources(fGpu);
+            fHashTable.remove(entry->fPipelineState->getDesc());
         }
-        SkASSERT(fEntries[purgeIdx] == entry);
-        entry->fPipelineState.reset(pipelineState);
-        // We need to shift fEntries around so that the entry currently at purgeIdx is placed
-        // just before the entry at ~entryIdx (in order to keep fEntries sorted by descriptor).
-        entryIdx = ~entryIdx;
-        if (entryIdx < purgeIdx) {
-            //  Let E and P be the entries at index entryIdx and purgeIdx, respectively.
-            //  If the entries array looks like this:
-            //       aaaaEbbbbbPccccc
-            //  we rearrange it to look like this:
-            //       aaaaPEbbbbbccccc
-            size_t copySize = (purgeIdx - entryIdx) * sizeof(Entry*);
-            memmove(fEntries + entryIdx + 1, fEntries + entryIdx, copySize);
-            fEntries[entryIdx] = entry;
-        } else if (purgeIdx < entryIdx) {
-            //  If the entries array looks like this:
-            //       aaaaPbbbbbEccccc
-            //  we rearrange it to look like this:
-            //       aaaabbbbbPEccccc
-            size_t copySize = (entryIdx - purgeIdx - 1) * sizeof(Entry*);
-            memmove(fEntries + purgeIdx, fEntries + purgeIdx + 1, copySize);
-            fEntries[entryIdx - 1] = entry;
-        }
-#ifdef SK_DEBUG
-        SkASSERT(fEntries[0]->fPipelineState.get());
-        for (int i = 0; i < fCount - 1; ++i) {
-            SkASSERT(fEntries[i + 1]->fPipelineState.get());
-            const GrVkPipelineState::Desc& a = fEntries[i]->fPipelineState->getDesc();
-            const GrVkPipelineState::Desc& b = fEntries[i + 1]->fPipelineState->getDesc();
-            SkASSERT(GrVkPipelineState::Desc::Less(a, b));
-            SkASSERT(!GrVkPipelineState::Desc::Less(b, a));
-        }
-#endif
-    }
-
-    fHashTable[hashIdx] = entry;
-    entry->fLRUStamp = fCurrLRUStamp;
-
-    if (SK_MaxU32 == fCurrLRUStamp) {
-        // wrap around! just trash our LRU, one time hit.
-        for (int i = 0; i < fCount; ++i) {
-            fEntries[i]->fLRUStamp = 0;
-        }
+        entry->fPipelineState = std::move(pipelineState);
+        fHashTable.set(entry);
+        fLRUList.addToTail(entry);
+        return entry->fPipelineState;
+    } else {
+        fLRUList.remove(entry);
+        fLRUList.addToTail(entry);
     }
-    ++fCurrLRUStamp;
-    return SkRef(entry->fPipelineState.get());
+    return entry->fPipelineState;
 }
diff --git a/src/gpu/vk/GrVkResourceProvider.cpp b/src/gpu/vk/GrVkResourceProvider.cpp
index 8bdb946cb8..8bb3911c76 100644
--- a/src/gpu/vk/GrVkResourceProvider.cpp
+++ b/src/gpu/vk/GrVkResourceProvider.cpp
@@ -96,7 +96,7 @@ GrVkSampler* GrVkResourceProvider::findOrCreateCompatibleSampler(const GrTexture
     return sampler;
 }
 
-GrVkPipelineState* GrVkResourceProvider::findOrCreateCompatiblePipelineState(
+sk_sp<GrVkPipelineState> GrVkResourceProvider::findOrCreateCompatiblePipelineState(
                                                                  const GrPipeline& pipeline,
                                                                  const GrPrimitiveProcessor& proc,
                                                                  GrPrimitiveType primitiveType,
diff --git a/src/gpu/vk/GrVkResourceProvider.h b/src/gpu/vk/GrVkResourceProvider.h
index 6d9389775d..1fdf1441e3 100644
--- a/src/gpu/vk/GrVkResourceProvider.h
+++ b/src/gpu/vk/GrVkResourceProvider.h
@@ -15,6 +15,8 @@
 #include "GrVkUtil.h"
 #include "SkTArray.h"
 #include "SkTDynamicHash.h"
+#include "SkTHash.h"
+#include "SkTInternalLList.h"
 
 #include "vk/GrVkDefines.h"
 
@@ -63,10 +65,10 @@ public:
     // The refcount is incremented and a pointer returned.
     GrVkSampler* findOrCreateCompatibleSampler(const GrTextureParams&);
 
-    GrVkPipelineState* findOrCreateCompatiblePipelineState(const GrPipeline&,
-                                                           const GrPrimitiveProcessor&,
-                                                           GrPrimitiveType,
-                                                           const GrVkRenderPass& renderPass);
+    sk_sp<GrVkPipelineState> findOrCreateCompatiblePipelineState(const GrPipeline&,
+                                                                 const GrPrimitiveProcessor&,
+                                                                 GrPrimitiveType,
+                                                                 const GrVkRenderPass& renderPass);
 
     // Destroy any cached resources. To be called before destroying the VkDevice.
     // The assumption is that all queues are idle and all command buffers are finished.
@@ -80,6 +82,11 @@ public:
     void abandonResources();
 
 private:
+
+#ifdef SK_DEVELOPER
+#define GR_PIPELINE_STATE_CACHE_STATS
+#endif
+
     class PipelineStateCache : public ::SkNoncopyable {
     public:
         PipelineStateCache(GrVkGpu* gpu);
@@ -87,42 +94,31 @@ private:
 
         void abandon();
         void release();
-        GrVkPipelineState* refPipelineState(const GrPipeline&,
-                                            const GrPrimitiveProcessor&,
-                                            GrPrimitiveType,
-                                            const GrVkRenderPass& renderPass);
+        sk_sp<GrVkPipelineState> refPipelineState(const GrPipeline&,
+                                                  const GrPrimitiveProcessor&,
+                                                  GrPrimitiveType,
+                                                  const GrVkRenderPass& renderPass);
 
     private:
         enum {
             // We may actually have kMaxEntries+1 PipelineStates in context because we create a new
             // PipelineState before evicting from the cache.
             kMaxEntries = 128,
-            kHashBits = 6,
         };
 
         struct Entry;
 
-        struct PipelineDescLess;
-
         void reset();
 
-        // binary search for entry matching desc. returns index into fEntries that matches desc or ~
-        // of the index of where it should be inserted.
-        int search(const GrVkPipelineState::Desc& desc) const;
-
-        // sorted array of all the entries
-        Entry*                      fEntries[kMaxEntries];
-        // hash table based on lowest kHashBits bits of the pipeline state key. Used to avoid binary
-        // searching fEntries.
-        Entry*                      fHashTable[1 << kHashBits];
-
         int                         fCount;
-        unsigned int                fCurrLRUStamp;
+        SkTHashTable<Entry*, const GrVkPipelineState::Desc&, Entry> fHashTable;
+        SkTInternalLList<Entry> fLRUList;
+
         GrVkGpu*                    fGpu;
-#ifdef PIPELINE_STATE_CACHE_STATS
+
+#ifdef GR_PIPELINE_STATE_CACHE_STATS
         int                         fTotalRequests;
         int                         fCacheMisses;
-        int                         fHashMisses; // cache hit but hash table missed
 #endif
     };