Reimplement LRUCache, fold away LRUSnapshotCache, add tests.
LRUCache previously had a complexity of O(n).
Reimplement using a `std::unordered_set` and a linked list to get this reduced to O(1).
Renamed `LRUCache::query()` to `LRUCache::get()`, as this is a more common verb for a cache, and the `query()` suggests it is side effect free (when it actually makes the entry MRU).
Move `LRUCache.hpp` from `src/Device` to `src/System` so it can be tested by `system-unittests`.
Move the logic of `LRUSnapshotCache` into `VkDevice::SamplingRoutineCache`, as this was the only place it was used, and made it exceptionally hard to separate mutex-locked data from non-locked data.
This is part of the work to get our code statically thread-safe-verifiable.
Bug: b/153194656
Change-Id: Ie02888ae6c7ed4066df77d692dfae28c3bc1664d
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/43489
Reviewed-by: Antonio Maiorano <amaiorano@google.com>
Kokoro-Result: kokoro <noreply+kokoro@google.com>
Presubmit-Ready: Ben Clayton <bclayton@google.com>
Tested-by: Ben Clayton <bclayton@google.com>
diff --git a/src/Device/Blitter.cpp b/src/Device/Blitter.cpp
index 88f11d9..aea4e62 100644
--- a/src/Device/Blitter.cpp
+++ b/src/Device/Blitter.cpp
@@ -1682,7 +1682,7 @@
Blitter::BlitRoutineType Blitter::getBlitRoutine(const State &state)
{
std::unique_lock<std::mutex> lock(blitMutex);
- auto blitRoutine = blitCache.query(state);
+ auto blitRoutine = blitCache.lookup(state);
if(!blitRoutine)
{
@@ -1696,7 +1696,7 @@
Blitter::CornerUpdateRoutineType Blitter::getCornerUpdateRoutine(const State &state)
{
std::unique_lock<std::mutex> lock(cornerUpdateMutex);
- auto cornerUpdateRoutine = cornerUpdateCache.query(state);
+ auto cornerUpdateRoutine = cornerUpdateCache.lookup(state);
if(!cornerUpdateRoutine)
{
diff --git a/src/Device/Blitter.hpp b/src/Device/Blitter.hpp
index 50b7e29..8735feb 100644
--- a/src/Device/Blitter.hpp
+++ b/src/Device/Blitter.hpp
@@ -95,6 +95,7 @@
int destSamples = 0;
bool filter3D = false;
};
+ friend std::hash<Blitter::State>;
struct BlitData
{
@@ -193,4 +194,22 @@
} // namespace sw
+namespace std {
+
+template<>
+struct hash<sw::Blitter::State>
+{
+ uint64_t operator()(const sw::Blitter::State &state) const
+ {
+ uint64_t hash = state.sourceFormat;
+ hash = hash * 31 + state.destFormat;
+ hash = hash * 31 + state.srcSamples;
+ hash = hash * 31 + state.destSamples;
+ hash = hash * 31 + state.filter3D;
+ return hash;
+ }
+};
+
+} // namespace std
+
#endif // sw_Blitter_hpp
diff --git a/src/Device/CMakeLists.txt b/src/Device/CMakeLists.txt
index fae3be4..d7ca09c 100644
--- a/src/Device/CMakeLists.txt
+++ b/src/Device/CMakeLists.txt
@@ -31,7 +31,6 @@
Context.hpp
ETC_Decoder.cpp
ETC_Decoder.hpp
- LRUCache.hpp
Memset.hpp
PixelProcessor.cpp
PixelProcessor.hpp
diff --git a/src/Device/LRUCache.hpp b/src/Device/LRUCache.hpp
deleted file mode 100644
index 848d421..0000000
--- a/src/Device/LRUCache.hpp
+++ /dev/null
@@ -1,192 +0,0 @@
-// Copyright 2016 The SwiftShader Authors. All Rights Reserved.
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-#ifndef sw_LRUCache_hpp
-#define sw_LRUCache_hpp
-
-#include "System/Math.hpp"
-
-#include <type_traits>
-#include <unordered_map>
-
-namespace sw {
-
-template<class Key, class Data>
-class LRUCache
-{
-public:
- LRUCache(int n);
-
- virtual ~LRUCache();
-
- Data query(const Key &key) const;
- virtual Data add(const Key &key, const Data &data);
-
- int getSize() { return size; }
- Key &getKey(int i) { return key[i]; }
-
-protected:
- int size;
- int mask;
- int top;
- int fill;
-
- Key *key;
- Key **ref;
- Data *data;
-};
-
-// An LRU cache which can take a 'snapshot' of its current state. This is useful
-// for allowing concurrent read access without requiring a mutex to be locked.
-template<class Key, class Data, class Hasher = std::hash<Key>>
-class LRUSnapshotCache : public LRUCache<Key, Data>
-{
- using LRUBase = LRUCache<Key, Data>;
-
-public:
- LRUSnapshotCache(int n)
- : LRUBase(n)
- {}
- ~LRUSnapshotCache() { clearSnapshot(); }
-
- Data add(const Key &key, const Data &data) override
- {
- snapshotNeedsUpdate = true;
- return LRUBase::add(key, data);
- }
-
- void updateSnapshot();
- const Data &querySnapshot(const Key &key) const;
-
-private:
- void clearSnapshot();
- bool snapshotNeedsUpdate = false;
- std::unordered_map<Key, Data, Hasher> snapshot;
-};
-
-} // namespace sw
-
-namespace sw {
-
-template<class Key, class Data>
-LRUCache<Key, Data>::LRUCache(int n)
-{
- size = ceilPow2(n);
- mask = size - 1;
- top = 0;
- fill = 0;
-
- key = new Key[size];
- ref = new Key *[size];
- data = new Data[size];
-
- for(int i = 0; i < size; i++)
- {
- ref[i] = &key[i];
- }
-}
-
-template<class Key, class Data>
-LRUCache<Key, Data>::~LRUCache()
-{
- delete[] key;
- key = nullptr;
-
- delete[] ref;
- ref = nullptr;
-
- delete[] data;
- data = nullptr;
-}
-
-template<class Key, class Data>
-Data LRUCache<Key, Data>::query(const Key &key) const
-{
- for(int i = top; i > top - fill; i--)
- {
- int j = i & mask;
-
- if(key == *ref[j])
- {
- Data hit = data[j];
-
- if(i != top)
- {
- // Move one up
- int k = (j + 1) & mask;
-
- Data swapD = data[k];
- data[k] = data[j];
- data[j] = swapD;
-
- Key *swapK = ref[k];
- ref[k] = ref[j];
- ref[j] = swapK;
- }
-
- return hit;
- }
- }
-
- return {}; // Not found
-}
-
-template<class Key, class Data>
-Data LRUCache<Key, Data>::add(const Key &key, const Data &data)
-{
- top = (top + 1) & mask;
- fill = fill + 1 < size ? fill + 1 : size;
-
- *ref[top] = key;
- this->data[top] = data;
-
- return data;
-}
-
-template<class Key, class Data, class Hasher>
-void LRUSnapshotCache<Key, Data, Hasher>::clearSnapshot()
-{
- snapshot.clear();
-}
-
-template<class Key, class Data, class Hasher>
-void LRUSnapshotCache<Key, Data, Hasher>::updateSnapshot()
-{
- if(snapshotNeedsUpdate)
- {
- clearSnapshot();
-
- for(int i = 0; i < LRUBase::size; i++)
- {
- if(LRUBase::data[i])
- {
- snapshot[*LRUBase::ref[i]] = LRUBase::data[i];
- }
- }
-
- snapshotNeedsUpdate = false;
- }
-}
-
-template<class Key, class Data, class Hasher>
-const Data &LRUSnapshotCache<Key, Data, Hasher>::querySnapshot(const Key &key) const
-{
- auto it = snapshot.find(key);
- static Data null = {};
- return (it != snapshot.end()) ? it->second : null;
-}
-
-} // namespace sw
-
-#endif // sw_LRUCache_hpp
diff --git a/src/Device/PixelProcessor.cpp b/src/Device/PixelProcessor.cpp
index 1e25645..6d49315 100644
--- a/src/Device/PixelProcessor.cpp
+++ b/src/Device/PixelProcessor.cpp
@@ -153,7 +153,7 @@
SpirvShader const *pixelShader,
const vk::DescriptorSet::Bindings &descriptorSets)
{
- auto routine = routineCache->query(state);
+ auto routine = routineCache->lookup(state);
if(!routine)
{
diff --git a/src/Device/PixelProcessor.hpp b/src/Device/PixelProcessor.hpp
index c140e0c..3ba54d8 100644
--- a/src/Device/PixelProcessor.hpp
+++ b/src/Device/PixelProcessor.hpp
@@ -164,4 +164,17 @@
} // namespace sw
+namespace std {
+
+template<>
+struct hash<sw::PixelProcessor::State>
+{
+ uint64_t operator()(const sw::PixelProcessor::State &state) const
+ {
+ return state.hash;
+ }
+};
+
+} // namespace std
+
#endif // sw_PixelProcessor_hpp
diff --git a/src/Device/RoutineCache.hpp b/src/Device/RoutineCache.hpp
index 9bf2e31..71046c3 100644
--- a/src/Device/RoutineCache.hpp
+++ b/src/Device/RoutineCache.hpp
@@ -15,7 +15,7 @@
#ifndef sw_RoutineCache_hpp
#define sw_RoutineCache_hpp
-#include "LRUCache.hpp"
+#include "System/LRUCache.hpp"
#include "Reactor/Reactor.hpp"
diff --git a/src/Device/SetupProcessor.cpp b/src/Device/SetupProcessor.cpp
index 19e7843..bda0df0 100644
--- a/src/Device/SetupProcessor.cpp
+++ b/src/Device/SetupProcessor.cpp
@@ -100,7 +100,7 @@
SetupProcessor::RoutineType SetupProcessor::routine(const State &state)
{
- auto routine = routineCache->query(state);
+ auto routine = routineCache->lookup(state);
if(!routine)
{
diff --git a/src/Device/SetupProcessor.hpp b/src/Device/SetupProcessor.hpp
index b8b6d84..c86bb00 100644
--- a/src/Device/SetupProcessor.hpp
+++ b/src/Device/SetupProcessor.hpp
@@ -85,4 +85,17 @@
} // namespace sw
+namespace std {
+
+template<>
+struct hash<sw::SetupProcessor::State>
+{
+ uint64_t operator()(const sw::SetupProcessor::State &state) const
+ {
+ return state.hash;
+ }
+};
+
+} // namespace std
+
#endif // sw_SetupProcessor_hpp
diff --git a/src/Device/VertexProcessor.cpp b/src/Device/VertexProcessor.cpp
index a2a33c5..54d5df8 100644
--- a/src/Device/VertexProcessor.cpp
+++ b/src/Device/VertexProcessor.cpp
@@ -98,7 +98,7 @@
SpirvShader const *vertexShader,
const vk::DescriptorSet::Bindings &descriptorSets)
{
- auto routine = routineCache->query(state);
+ auto routine = routineCache->lookup(state);
if(!routine) // Create one
{
diff --git a/src/Device/VertexProcessor.hpp b/src/Device/VertexProcessor.hpp
index 739ffc6..d8acdd9 100644
--- a/src/Device/VertexProcessor.hpp
+++ b/src/Device/VertexProcessor.hpp
@@ -106,4 +106,17 @@
} // namespace sw
+namespace std {
+
+template<>
+struct hash<sw::VertexProcessor::State>
+{
+ uint64_t operator()(const sw::VertexProcessor::State &state) const
+ {
+ return state.hash;
+ }
+};
+
+} // namespace std
+
#endif // sw_VertexProcessor_hpp
diff --git a/src/Pipeline/SpirvShaderSampling.cpp b/src/Pipeline/SpirvShaderSampling.cpp
index dd84e70..f1a44ef 100644
--- a/src/Pipeline/SpirvShaderSampling.cpp
+++ b/src/Pipeline/SpirvShaderSampling.cpp
@@ -40,11 +40,6 @@
ASSERT(imageDescriptor->device);
- if(auto routine = imageDescriptor->device->querySnapshotCache(key))
- {
- return (ImageSampler *)(routine->getEntry());
- }
-
vk::Device::SamplingRoutineCache *cache = imageDescriptor->device->getSamplingRoutineCache();
auto createSamplingRoutine = [&](const vk::Device::SamplingRoutineCache::Key &key) {
diff --git a/src/System/BUILD.gn b/src/System/BUILD.gn
index c90c835..4595028 100644
--- a/src/System/BUILD.gn
+++ b/src/System/BUILD.gn
@@ -21,6 +21,7 @@
"Configurator.hpp",
"Debug.hpp",
"Half.hpp",
+ "LRUCache.hpp",
"Math.hpp",
"Memory.hpp",
"Socket.cpp",
diff --git a/src/System/CMakeLists.txt b/src/System/CMakeLists.txt
index d7d5f00..bb5f305 100644
--- a/src/System/CMakeLists.txt
+++ b/src/System/CMakeLists.txt
@@ -28,6 +28,7 @@
Debug.hpp
Half.cpp
Half.hpp
+ LRUCache.hpp
Math.cpp
Math.hpp
Memory.cpp
diff --git a/src/System/LRUCache.hpp b/src/System/LRUCache.hpp
new file mode 100644
index 0000000..ff18671
--- /dev/null
+++ b/src/System/LRUCache.hpp
@@ -0,0 +1,357 @@
+// Copyright 2020 The SwiftShader Authors. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#ifndef sw_LRUCache_hpp
+#define sw_LRUCache_hpp
+
+#include "System/Debug.hpp"
+
+#include <cstddef>
+#include <functional>
+#include <unordered_set>
+#include <vector>
+
+namespace sw {
+
+// LRUCache is a least recently used cache of a fixed capacity.
+template<typename KEY, typename DATA, typename HASH = std::hash<KEY> >
+class LRUCache
+{
+ struct Entry;
+
+public:
+ using Key = KEY;
+ using Data = DATA;
+ using Hash = HASH;
+
+ // view is a const accessor of a single cache entry.
+ class view
+ {
+ public:
+ inline view(Entry *);
+
+ inline const Key &key() const;
+ inline const Data &data() const;
+
+ private:
+ Entry *entry;
+ };
+
+ class iterator
+ {
+ public:
+ inline iterator(Entry *);
+ inline view operator*() const;
+ inline iterator &operator++();
+ inline bool operator==(const iterator &) const;
+ inline bool operator!=(const iterator &) const;
+
+ private:
+ Entry *entry;
+ };
+
+ // Construct a LRU cache with the given maximum number of entries.
+ inline LRUCache(size_t capacity);
+ inline ~LRUCache() = default;
+
+ // lookup() looks up the cache entry with the given key.
+ // If the entry is found, this is moved to the most-recent position in the
+ // cache, and its data is returned.
+ // If the entry is not found, then a default initialized Data is returned.
+ inline Data lookup(const Key &key);
+
+ // add() adds the data to the cache using the given key, placed at the
+ // most-recent position in the cache.
+ // If an existing entry exists in the cache with the given key, then this is
+ // replaced with data.
+ // If no existing entry exists in the cache, and the cache is already full
+ // then the least recently used entry is evicted before adding the new
+ // entry.
+ inline void add(const Key &key, const Data &data);
+
+ // clear() clears the cache of all elements.
+ inline void clear();
+
+ // Range based iterators.
+ inline iterator begin() const;
+ inline iterator end() const;
+
+private:
+ LRUCache(const LRUCache &) = delete;
+ LRUCache(LRUCache &&) = delete;
+ LRUCache &operator=(const LRUCache &) = delete;
+ LRUCache &operator=(LRUCache &&) = delete;
+
+ //Keyed holds a key. See find() for more information.
+ struct Keyed
+ {
+ Key key = {};
+ };
+
+ // Cache entry structure.
+ // Holds the unique copy of the key and data, along with pointers for
+ // maintaining the linked list.
+ struct Entry : Keyed
+ {
+ Data data = {};
+ Entry *next = nullptr;
+ Entry *prev = nullptr;
+ };
+
+ // KeyedComparator is a custom hasher and equality helper for Keyed.
+ struct KeyedComparator
+ {
+ // Hash function.
+ inline uint64_t operator()(const Keyed *k) const;
+
+ // Equality function.
+ inline uint64_t operator()(const Keyed *a, const Keyed *b) const;
+ };
+
+ // find() returns the Entry* for the given key, or nullptr.
+ // find() performs this by casting the Key pointer to a Keyed pointer for
+ // searching the std::unordered_set.
+ //
+ // This is to avoid having a duplicate Key held by both an
+ // unordered_map<Key, Entry*> and the Entry itself, as the Key type may be
+ // large.
+ //
+ // While we could use an unordered_set<Entry*>, this then requires the
+ // construction of a temporary Entry to perform the call to
+ // unordered_set<Entry*>::find(). This is undesirable as the Data type might
+ // be large or have an expensive constructor.
+ //
+ // C++20 gains a new templated overload for unordered_set<Entry*>::find()
+ // which would allow us to use unordered_set<Entry*>::find(Key*).
+ // Until we can use C++20, keep this casting nastiness hidden away in this
+ // one function.
+ inline Entry *find(const Key &key);
+
+ // unlinks the entry from the list it is linked in.
+ inline void unlink(Entry *);
+
+ // links the entry to the head of the LRU.
+ inline void link(Entry *);
+
+ // storage holds the allocations of all the entries.
+ // This vector must not change size for the lifetime of the cache.
+ std::vector<Entry> storage;
+
+ // set is an unordered set of Keyed*, using the KeyedComparator for hash and
+ // equality testing.
+ std::unordered_set<const Keyed *, KeyedComparator, KeyedComparator> set;
+
+ Entry *free = nullptr; // Singly-linked (prev is nullptr) list of free entries.
+ Entry *head = nullptr; // Pointer to the most recently used entry in the LRU.
+ Entry *tail = nullptr; // Pointer to the least recently used entry in the LRU.
+};
+
+////////////////////////////////////////////////////////////////////////////////
+// LRUCache<>::view
+////////////////////////////////////////////////////////////////////////////////
+template<typename KEY, typename DATA, typename HASH>
+LRUCache<KEY, DATA, HASH>::view::view(Entry *entry)
+ : entry(entry)
+{}
+
+template<typename KEY, typename DATA, typename HASH>
+const KEY &LRUCache<KEY, DATA, HASH>::view::key() const
+{
+ return entry->key;
+}
+
+template<typename KEY, typename DATA, typename HASH>
+const DATA &LRUCache<KEY, DATA, HASH>::view::data() const
+{
+ return entry->data;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// LRUCache<>::iterator
+////////////////////////////////////////////////////////////////////////////////
+template<typename KEY, typename DATA, typename HASH>
+LRUCache<KEY, DATA, HASH>::iterator::iterator(Entry *entry)
+ : entry(entry)
+{}
+
+template<typename KEY, typename DATA, typename HASH>
+typename LRUCache<KEY, DATA, HASH>::view LRUCache<KEY, DATA, HASH>::iterator::operator*() const
+{
+ return view{ entry };
+}
+
+template<typename KEY, typename DATA, typename HASH>
+typename LRUCache<KEY, DATA, HASH>::iterator &LRUCache<KEY, DATA, HASH>::iterator::operator++()
+{
+ entry = entry->next;
+ return *this;
+}
+
+template<typename KEY, typename DATA, typename HASH>
+bool LRUCache<KEY, DATA, HASH>::iterator::operator==(const iterator &rhs) const
+{
+ return entry == rhs.entry;
+}
+
+template<typename KEY, typename DATA, typename HASH>
+bool LRUCache<KEY, DATA, HASH>::iterator::operator!=(const iterator &rhs) const
+{
+ return entry != rhs.entry;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// LRUCache<>
+////////////////////////////////////////////////////////////////////////////////
+template<typename KEY, typename DATA, typename HASH>
+LRUCache<KEY, DATA, HASH>::LRUCache(size_t capacity)
+ : storage(capacity)
+{
+ for(size_t i = 0; i < capacity; i++)
+ {
+ Entry *entry = &storage[i];
+ entry->next = free; // No need for back link here.
+ free = entry;
+ }
+}
+
+template<typename KEY, typename DATA, typename HASH>
+DATA LRUCache<KEY, DATA, HASH>::lookup(const Key &key)
+{
+ if(Entry *entry = find(key))
+ {
+ unlink(entry);
+ link(entry);
+ return entry->data;
+ }
+ return {};
+}
+
+template<typename KEY, typename DATA, typename HASH>
+void LRUCache<KEY, DATA, HASH>::add(const Key &key, const Data &data)
+{
+ if(Entry *entry = find(key))
+ {
+ // Move entry to front.
+ unlink(entry);
+ link(entry);
+ entry->data = data;
+ return;
+ }
+
+ Entry *entry = free;
+ if(entry)
+ {
+ // Unlink from free.
+ free = entry->next;
+ entry->next = nullptr;
+ }
+ else
+ {
+ // Unlink least recently used.
+ entry = tail;
+ unlink(entry);
+ set.erase(entry);
+ }
+
+ // link as most recently used.
+ link(entry);
+ if(tail == nullptr)
+ {
+ tail = entry;
+ }
+
+ entry->key = key;
+ entry->data = data;
+ set.emplace(entry);
+}
+
+template<typename KEY, typename DATA, typename HASH>
+void LRUCache<KEY, DATA, HASH>::clear()
+{
+ while(Entry *entry = head)
+ {
+ unlink(entry);
+ entry->next = free; // No need for back link here.
+ free = entry;
+ }
+ set.clear();
+}
+
+template<typename KEY, typename DATA, typename HASH>
+typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::begin() const
+{
+ return { head };
+}
+
+template<typename KEY, typename DATA, typename HASH>
+typename LRUCache<KEY, DATA, HASH>::iterator LRUCache<KEY, DATA, HASH>::end() const
+{
+ return { nullptr };
+}
+
+template<typename KEY, typename DATA, typename HASH>
+void LRUCache<KEY, DATA, HASH>::unlink(Entry *entry)
+{
+ if(head == entry) { head = entry->next; }
+ if(tail == entry) { tail = entry->prev; }
+ if(entry->prev) { entry->prev->next = entry->next; }
+ if(entry->next) { entry->next->prev = entry->prev; }
+ entry->prev = nullptr;
+ entry->next = nullptr;
+}
+
+template<typename KEY, typename DATA, typename HASH>
+void LRUCache<KEY, DATA, HASH>::link(Entry *entry)
+{
+ ASSERT_MSG(entry->next == nullptr, "link() called on entry already linked");
+ ASSERT_MSG(entry->prev == nullptr, "link() called on entry already linked");
+ if(head)
+ {
+ entry->next = head;
+ head->prev = entry;
+ }
+ head = entry;
+ if(!tail) { tail = entry; }
+}
+
+template<typename KEY, typename DATA, typename HASH>
+typename LRUCache<KEY, DATA, HASH>::Entry *LRUCache<KEY, DATA, HASH>::find(const Key &key)
+{
+ auto asKeyed = reinterpret_cast<const Keyed *>(&key);
+ auto it = set.find(asKeyed);
+ if(it == set.end())
+ {
+ return nullptr;
+ }
+ return const_cast<Entry *>(static_cast<const Entry *>(*it));
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// LRUCache<>::KeyedComparator
+////////////////////////////////////////////////////////////////////////////////
+template<typename KEY, typename DATA, typename HASH>
+uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *k) const
+{
+ return Hash()(k->key);
+}
+
+template<typename KEY, typename DATA, typename HASH>
+uint64_t LRUCache<KEY, DATA, HASH>::KeyedComparator::operator()(const Keyed *a, const Keyed *b) const
+{
+ return a->key == b->key;
+}
+
+} // namespace sw
+
+#endif // sw_LRUCache_hpp
diff --git a/src/Vulkan/VkDevice.cpp b/src/Vulkan/VkDevice.cpp
index 982c10a..0961243 100644
--- a/src/Vulkan/VkDevice.cpp
+++ b/src/Vulkan/VkDevice.cpp
@@ -38,16 +38,21 @@
namespace vk {
-rr::Routine *Device::SamplingRoutineCache::querySnapshot(const vk::Device::SamplingRoutineCache::Key &key) const
-{
- return cache.querySnapshot(key).get();
-}
-
void Device::SamplingRoutineCache::updateSnapshot()
{
- std::lock_guard<std::mutex> lock(mutex);
+ std::unique_lock<std::mutex> lock(mutex);
- cache.updateSnapshot();
+ if(snapshotNeedsUpdate)
+ {
+ snapshot.clear();
+
+ for(auto it : cache)
+ {
+ snapshot[it.key()] = it.data();
+ }
+
+ snapshotNeedsUpdate = false;
+ }
}
Device::SamplerIndexer::~SamplerIndexer()
@@ -57,7 +62,7 @@
uint32_t Device::SamplerIndexer::index(const SamplerState &samplerState)
{
- std::lock_guard<std::mutex> lock(mutex);
+ std::unique_lock<std::mutex> lock(mutex);
auto it = map.find(samplerState);
@@ -76,7 +81,7 @@
void Device::SamplerIndexer::remove(const SamplerState &samplerState)
{
- std::lock_guard<std::mutex> lock(mutex);
+ std::unique_lock<std::mutex> lock(mutex);
auto it = map.find(samplerState);
ASSERT(it != map.end());
@@ -293,11 +298,6 @@
return samplingRoutineCache.get();
}
-rr::Routine *Device::querySnapshotCache(const SamplingRoutineCache::Key &key) const
-{
- return samplingRoutineCache->querySnapshot(key);
-}
-
void Device::updateSamplingRoutineSnapshotCache()
{
samplingRoutineCache->updateSnapshot();
diff --git a/src/Vulkan/VkDevice.hpp b/src/Vulkan/VkDevice.hpp
index 8931949..abf1191 100644
--- a/src/Vulkan/VkDevice.hpp
+++ b/src/Vulkan/VkDevice.hpp
@@ -17,12 +17,13 @@
#include "VkObject.hpp"
#include "VkSampler.hpp"
-#include "Device/LRUCache.hpp"
#include "Reactor/Routine.hpp"
+#include "System/LRUCache.hpp"
#include <map>
#include <memory>
#include <mutex>
+#include <unordered_map>
namespace marl {
class Scheduler;
@@ -95,29 +96,33 @@
template<typename Function>
std::shared_ptr<rr::Routine> getOrCreate(const Key &key, Function &&createRoutine)
{
- std::lock_guard<std::mutex> lock(mutex);
+ auto it = snapshot.find(key);
+ if(it != snapshot.end()) { return it->second; }
- if(auto existingRoutine = cache.query(key))
+ std::unique_lock<std::mutex> lock(mutex);
+ if(auto existingRoutine = cache.lookup(key))
{
return existingRoutine;
}
std::shared_ptr<rr::Routine> newRoutine = createRoutine(key);
cache.add(key, newRoutine);
+ snapshotNeedsUpdate = true;
return newRoutine;
}
- rr::Routine *querySnapshot(const Key &key) const;
void updateSnapshot();
private:
- sw::LRUSnapshotCache<Key, std::shared_ptr<rr::Routine>, Key::Hash> cache; // guarded by mutex
+ bool snapshotNeedsUpdate = false;
+ std::unordered_map<Key, std::shared_ptr<rr::Routine>, Key::Hash> snapshot;
+
+ sw::LRUCache<Key, std::shared_ptr<rr::Routine>, Key::Hash> cache; // guarded by mutex
std::mutex mutex;
};
SamplingRoutineCache *getSamplingRoutineCache() const;
- rr::Routine *querySnapshotCache(const SamplingRoutineCache::Key &key) const;
void updateSamplingRoutineSnapshotCache();
class SamplerIndexer
