aboutsummaryrefslogtreecommitdiffhomepage
diff options
context:
space:
mode:
Diffstat
-rw-r--r--gn/tests.gni1
-rw-r--r--src/core/SkLRUCache.h97
-rw-r--r--src/gpu/gl/GrGLGpu.h26
-rw-r--r--src/gpu/gl/GrGLGpuProgramCache.cpp144
-rw-r--r--tests/LRUCacheTest.cpp70
5 files changed, 188 insertions, 150 deletions
diff --git a/gn/tests.gni b/gn/tests.gni
index 8473e0eabe..5f2d8b7931 100644
--- a/gn/tests.gni
+++ b/gn/tests.gni
@@ -117,6 +117,7 @@ tests_sources = [
"$_tests/LayerDrawLooperTest.cpp",
"$_tests/LayerRasterizerTest.cpp",
"$_tests/LListTest.cpp",
+ "$_tests/LRUCacheTest.cpp",
"$_tests/MallocPixelRefTest.cpp",
"$_tests/MaskCacheTest.cpp",
"$_tests/MathTest.cpp",
diff --git a/src/core/SkLRUCache.h b/src/core/SkLRUCache.h
new file mode 100644
index 0000000000..f7941bb76c
--- /dev/null
+++ b/src/core/SkLRUCache.h
@@ -0,0 +1,97 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkLRUCache_DEFINED
+#define SkLRUCache_DEFINED
+
+#include "SkChecksum.h"
+#include "SkTHash.h"
+#include "SkTInternalLList.h"
+
+/**
+ * A generic LRU cache.
+ */
+template <typename K, typename V, typename HashK = SkGoodHash>
+class SkLRUCache : public SkNoncopyable {
+public:
+ explicit SkLRUCache(int maxCount)
+ : fMaxCount(maxCount) {}
+
+ ~SkLRUCache() {
+ Entry* node = fLRU.head();
+ while (node) {
+ fLRU.remove(node);
+ delete node;
+ node = fLRU.head();
+ }
+ }
+
+ V* find(const K& key) {
+ Entry** value = fMap.find(key);
+ if (!value) {
+ return nullptr;
+ }
+ Entry* entry = *value;
+ if (entry != fLRU.head()) {
+ fLRU.remove(entry);
+ fLRU.addToHead(entry);
+ } // else it's already at head position, don't need to do anything
+ return &entry->fValue;
+ }
+
+ V* insert(const K& key, V value) {
+ Entry* entry = new Entry(key, std::move(value));
+ fMap.set(entry);
+ fLRU.addToHead(entry);
+ while (fMap.count() > fMaxCount) {
+ this->remove(fLRU.tail()->fKey);
+ }
+ return &entry->fValue;
+ }
+
+ int count() {
+ return fMap.count();
+ }
+
+private:
+ struct Entry {
+ Entry(const K& key, V&& value)
+ : fKey(key)
+ , fValue(std::move(value)) {}
+
+ K fKey;
+ V fValue;
+
+ SK_DECLARE_INTERNAL_LLIST_INTERFACE(Entry);
+ };
+
+ struct Traits {
+ static const K& GetKey(Entry* e) {
+ return e->fKey;
+ }
+
+ static uint32_t Hash(const K& k) {
+ return HashK()(k);
+ }
+ };
+
+ void remove(const K& key) {
+ Entry** value = fMap.find(key);
+ SkASSERT(value);
+ Entry* entry = *value;
+ SkASSERT(key == entry->fKey);
+ fMap.remove(key);
+ fLRU.remove(entry);
+ delete entry;
+ }
+
+ int fMaxCount;
+ SkTHashTable<Entry*, K, Traits> fMap;
+ SkTInternalLList<Entry> fLRU;
+};
+
+#endif
diff --git a/src/gpu/gl/GrGLGpu.h b/src/gpu/gl/GrGLGpu.h
index 0c3d0605c7..c9c3fc4409 100644
--- a/src/gpu/gl/GrGLGpu.h
+++ b/src/gpu/gl/GrGLGpu.h
@@ -20,6 +20,7 @@
#include "GrTexturePriv.h"
#include "GrWindowRectsState.h"
#include "GrXferProcessor.h"
+#include "SkLRUCache.h"
#include "SkTArray.h"
#include "SkTypes.h"
@@ -279,29 +280,24 @@ private:
bool hasPointSize);
private:
- enum {
- // We may actually have kMaxEntries+1 shaders in the GL context because we create a new
- // shader before evicting from the cache.
- kMaxEntries = 128,
- kHashBits = 6,
- };
+ // We may actually have kMaxEntries+1 shaders in the GL context because we create a new
+ // shader before evicting from the cache.
+ static const int kMaxEntries = 128;
struct Entry;
- struct ProgDescLess;
-
// 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 GrProgramDesc& desc) const;
- // sorted array of all the entries
- Entry* fEntries[kMaxEntries];
- // hash table based on lowest kHashBits bits of the program key. Used to avoid binary
- // searching fEntries.
- Entry* fHashTable[1 << kHashBits];
+ struct DescHash {
+ uint32_t operator()(const GrProgramDesc& desc) const {
+ return SkOpts::hash_fn(desc.asKey(), desc.keyLength(), 0);
+ }
+ };
+
+ SkLRUCache<GrProgramDesc, std::unique_ptr<Entry>, DescHash> fMap;
- int fCount;
- unsigned int fCurrLRUStamp;
GrGLGpu* fGpu;
#ifdef PROGRAM_CACHE_STATS
int fTotalRequests;
diff --git a/src/gpu/gl/GrGLGpuProgramCache.cpp b/src/gpu/gl/GrGLGpuProgramCache.cpp
index bf6a5980fb..c1ca16096a 100644
--- a/src/gpu/gl/GrGLGpuProgramCache.cpp
+++ b/src/gpu/gl/GrGLGpuProgramCache.cpp
@@ -23,44 +23,23 @@ static const bool c_DisplayCache{false};
typedef GrGLSLProgramDataManager::UniformHandle UniformHandle;
struct GrGLGpu::ProgramCache::Entry {
+ Entry(sk_sp<GrGLProgram> program)
+ : fProgram(std::move(program)) {}
- Entry() : fProgram(nullptr), fLRUStamp(0) {}
-
- sk_sp<GrGLProgram> fProgram;
- unsigned int fLRUStamp;
-};
-
-struct GrGLGpu::ProgramCache::ProgDescLess {
- bool operator() (const GrProgramDesc& desc, const Entry* entry) {
- SkASSERT(entry->fProgram.get());
- return GrProgramDesc::Less(desc, entry->fProgram->getDesc());
- }
-
- bool operator() (const Entry* entry, const GrProgramDesc& desc) {
- SkASSERT(entry->fProgram.get());
- return GrProgramDesc::Less(entry->fProgram->getDesc(), desc);
- }
+ sk_sp<GrGLProgram> fProgram;
};
GrGLGpu::ProgramCache::ProgramCache(GrGLGpu* gpu)
- : fCount(0)
- , fCurrLRUStamp(0)
+ : fMap(kMaxEntries)
, fGpu(gpu)
#ifdef PROGRAM_CACHE_STATS
, fTotalRequests(0)
, fCacheMisses(0)
, fHashMisses(0)
#endif
-{
- for (int i = 0; i < 1 << kHashBits; ++i) {
- fHashTable[i] = nullptr;
- }
-}
+{}
GrGLGpu::ProgramCache::~ProgramCache() {
- for (int i = 0; i < fCount; ++i){
- delete fEntries[i];
- }
// dump stats
#ifdef PROGRAM_CACHE_STATS
if (c_DisplayCache) {
@@ -78,20 +57,6 @@ GrGLGpu::ProgramCache::~ProgramCache() {
}
void GrGLGpu::ProgramCache::abandon() {
- for (int i = 0; i < fCount; ++i) {
- SkASSERT(fEntries[i]->fProgram.get());
- fEntries[i]->fProgram->abandon();
- delete fEntries[i];
- fEntries[i] = nullptr;
- }
- fCount = 0;
-
- // zero out hash table
- for (int i = 0; i < 1 << kHashBits; i++) {
- fHashTable[i] = nullptr;
- }
-
- fCurrLRUStamp = 0;
#ifdef PROGRAM_CACHE_STATS
fTotalRequests = 0;
fCacheMisses = 0;
@@ -99,11 +64,6 @@ void GrGLGpu::ProgramCache::abandon() {
#endif
}
-int GrGLGpu::ProgramCache::search(const GrProgramDesc& desc) const {
- ProgDescLess less;
- return SkTSearch(fEntries, fCount, desc, sizeof(Entry*), less);
-}
-
GrGLProgram* GrGLGpu::ProgramCache::refProgram(const GrGLGpu* gpu,
const GrPipeline& pipeline,
const GrPrimitiveProcessor& primProc,
@@ -119,33 +79,8 @@ GrGLProgram* GrGLGpu::ProgramCache::refProgram(const GrGLGpu* gpu,
return nullptr;
}
desc.finalize();
-
- Entry* entry = nullptr;
-
- uint32_t hashIdx = desc.getChecksum();
- hashIdx ^= hashIdx >> 16;
- if (kHashBits <= 8) {
- hashIdx ^= hashIdx >> 8;
- }
- hashIdx &=((1 << kHashBits) - 1);
- Entry* hashedEntry = fHashTable[hashIdx];
- if (hashedEntry && hashedEntry->fProgram->getDesc() == desc) {
- SkASSERT(hashedEntry->fProgram);
- entry = hashedEntry;
- }
-
- int entryIdx;
- if (nullptr == entry) {
- entryIdx = this->search(desc);
- if (entryIdx >= 0) {
- entry = fEntries[entryIdx];
-#ifdef PROGRAM_CACHE_STATS
- ++fHashMisses;
-#endif
- }
- }
-
- if (nullptr == entry) {
+ std::unique_ptr<Entry>* entry = fMap.find(desc);
+ if (!entry) {
// We have a cache miss
#ifdef PROGRAM_CACHE_STATS
++fCacheMisses;
@@ -154,69 +89,8 @@ GrGLProgram* GrGLGpu::ProgramCache::refProgram(const GrGLGpu* gpu,
if (nullptr == program) {
return nullptr;
}
- int purgeIdx = 0;
- if (fCount < kMaxEntries) {
- entry = new Entry;
- purgeIdx = fCount++;
- fEntries[purgeIdx] = entry;
- } 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->fProgram->getDesc().getChecksum() & ((1 << kHashBits) - 1);
- if (fHashTable[purgedHashIdx] == entry) {
- fHashTable[purgedHashIdx] = nullptr;
- }
- }
- SkASSERT(fEntries[purgeIdx] == entry);
- entry->fProgram.reset(program);
- // 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]->fProgram.get());
- for (int i = 0; i < fCount - 1; ++i) {
- SkASSERT(fEntries[i + 1]->fProgram.get());
- const GrProgramDesc& a = fEntries[i]->fProgram->getDesc();
- const GrProgramDesc& b = fEntries[i + 1]->fProgram->getDesc();
- SkASSERT(GrProgramDesc::Less(a, b));
- SkASSERT(!GrProgramDesc::Less(b, a));
- }
-#endif
+ entry = fMap.insert(desc, std::unique_ptr<Entry>(new Entry(sk_sp<GrGLProgram>(program))));
}
- 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;
- }
- }
- ++fCurrLRUStamp;
- return SkRef(entry->fProgram.get());
+ return SkRef((*entry)->fProgram.get());
}
diff --git a/tests/LRUCacheTest.cpp b/tests/LRUCacheTest.cpp
new file mode 100644
index 0000000000..6a65e4ac2d
--- /dev/null
+++ b/tests/LRUCacheTest.cpp
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2016 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "SkLRUCache.h"
+#include "Test.h"
+
+struct Value {
+ Value(int value, int* counter)
+ : fValue(value)
+ , fCounter(counter) {
+ (*fCounter)++;
+ }
+
+ ~Value() {
+ (*fCounter)--;
+ }
+
+ int fValue;
+ int* fCounter;
+};
+
+DEF_TEST(LRUCacheSequential, r) {
+ int instances = 0;
+ {
+ static const int kSize = 100;
+ SkLRUCache<int, std::unique_ptr<Value>> test(kSize);
+ for (int i = 1; i < kSize * 2; i++) {
+ REPORTER_ASSERT(r, !test.find(i));
+ test.insert(i, std::unique_ptr<Value>(new Value(i * i, &instances)));
+ REPORTER_ASSERT(r, test.find(i));
+ REPORTER_ASSERT(r, i * i == (*test.find(i))->fValue);
+ if (i > kSize) {
+ REPORTER_ASSERT(r, kSize == instances);
+ REPORTER_ASSERT(r, !test.find(i - kSize));
+ } else {
+ REPORTER_ASSERT(r, i == instances);
+ }
+ REPORTER_ASSERT(r, (int) test.count() == instances);
+ }
+ }
+ REPORTER_ASSERT(r, 0 == instances);
+}
+
+DEF_TEST(LRUCacheRandom, r) {
+ int instances = 0;
+ {
+ int seq[] = { 0, 1, 2, 3, 4, 1, 6, 2, 7, 5, 3, 2, 2, 3, 1, 7 };
+ int expected[] = { 7, 1, 3, 2, 5 };
+ static const int kSize = 5;
+ SkLRUCache<int, std::unique_ptr<Value>> test(kSize);
+ for (int i = 0; i < (int) (sizeof(seq) / sizeof(int)); i++) {
+ int k = seq[i];
+ if (!test.find(k)) {
+ test.insert(k, std::unique_ptr<Value>(new Value(k, &instances)));
+ }
+ }
+ REPORTER_ASSERT(r, kSize == instances);
+ REPORTER_ASSERT(r, kSize == test.count());
+ for (int i = 0; i < kSize; i++) {
+ int k = expected[i];
+ REPORTER_ASSERT(r, test.find(k));
+ REPORTER_ASSERT(r, k == (*test.find(k))->fValue);
+ }
+ }
+ REPORTER_ASSERT(r, 0 == instances);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-01 12:12:48 +0000