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
