userver: userver/cache/impl/slru.hpp Source File
Loading...
Searching...
No Matches
slru.hpp
1#pragma once
2
3#include <memory>
4#include <utility>
5
6#include <userver/cache/impl/lru.hpp>
7
8/*
9
10Hit rate on real data:
11
12Keys count Cache size Lru Slru
131988740 1000 0.0561333 0.0502915
14 5000 0.0860699 0.0816721
15 10000 0.110102 0.111687
16 20000 0.151564 0.158751
17 50000 0.274651 0.275751
18 100000 0.428465 0.424846
19
203595824 1000 0.357814 0.377788
21 5000 0.697188 0.705449
22 10000 0.831651 0.83536
23 20000 0.920158 0.920761
24 50000 0.971804 0.971791
25 100000 0.977242 0.977242
26
27*/
28
29USERVER_NAMESPACE_BEGIN
30
31namespace cache::impl {
32
33template <typename T, typename U, typename Hash = std::hash<T>,
34 typename Equal = std::equal_to<T>>
35class SlruBase final {
36 public:
37 using NodeType = std::unique_ptr<LruNode<T, U>>;
38
39 explicit SlruBase(std::size_t probation_size, std::size_t protected_size,
40 const Hash& hash = Hash(), const Equal& equal = Equal());
41 ~SlruBase() = default;
42
43 SlruBase(SlruBase&& other) noexcept = default;
44
45 SlruBase& operator=(SlruBase&& other) noexcept = default;
46
47 SlruBase(const SlruBase& slru) = delete;
48 SlruBase& operator=(const SlruBase& slru) = delete;
49
50 bool Put(const T& key, U value);
51
52 template <typename... Args>
53 U* Emplace(const T& key, Args&&... args);
54
55 void Erase(const T& key);
56
57 U* Get(const T& key);
58
59 const T* GetLeastUsedKey() const;
60
61 U* GetLeastUsedValue();
62
63 NodeType ExtractLeastUsedNode();
64
65 void SetMaxSize(std::size_t new_probation_size,
66 std::size_t new_protected_size);
67
68 void Clear() noexcept;
69
70 template <typename Function>
71 void VisitAll(Function&& func) const;
72
73 template <typename Function>
74 void VisitAll(Function&& func);
75
76 std::size_t GetSize() const;
77
78 std::size_t GetCapacity() const;
79
80 U& InsertNode(NodeType&& node) noexcept;
81 NodeType ExtractNode(const T& key) noexcept;
82
83 private:
84 cache::impl::LruBase<T, U, Hash, Equal> probation_part_;
85 cache::impl::LruBase<T, U, Hash, Equal> protected_part_;
86};
87
88template <typename T, typename U, typename Hash, typename Equal>
89SlruBase<T, U, Hash, Equal>::SlruBase(std::size_t probation_size,
90 std::size_t protected_size,
91 const Hash& hash, const Equal& equal)
92 : probation_part_(probation_size, hash, equal),
93 protected_part_(protected_size, hash, equal) {}
94
95template <typename T, typename U, typename Hash, typename Equal>
96bool SlruBase<T, U, Hash, Equal>::Put(const T& key, U value) {
97 auto* const value_ptr = protected_part_.Get(key);
98 if (value_ptr) {
99 *value_ptr = std::move(value);
100 return false;
101 }
102
103 auto node_to_protected = probation_part_.ExtractNode(key);
104 if (node_to_protected) {
105 node_to_protected->SetValue(std::move(value));
106 if (protected_part_.GetSize() == protected_part_.GetCapacity()) {
107 auto node_to_probation = protected_part_.ExtractLeastUsedNode();
108 probation_part_.InsertNode(std::move(node_to_probation));
109 }
110 protected_part_.InsertNode(std::move(node_to_protected));
111 return false;
112 }
113
114 return probation_part_.Put(key, std::move(value));
115}
116
117template <typename T, typename U, typename Hash, typename Equal>
118template <typename... Args>
119U* SlruBase<T, U, Hash, Equal>::Emplace(const T& key, Args&&... args) {
120 auto value_ptr = protected_part_.Get(key);
121 if (value_ptr) {
122 return value_ptr;
123 }
124
125 auto node_to_protected = probation_part_.ExtractNode(key);
126 if (node_to_protected) {
127 return protected_part_.Emplace(key, std::forward<Args>(args)...);
128 }
129
130 return probation_part_.Emplace(key, std::forward<Args>(args)...);
131}
132
133template <typename T, typename U, typename Hash, typename Equal>
134void SlruBase<T, U, Hash, Equal>::Erase(const T& key) {
135 probation_part_.Erase(key);
136 protected_part_.Erase(key);
137}
138
139template <typename T, typename U, typename Hash, typename Equal>
140U* SlruBase<T, U, Hash, Equal>::Get(const T& key) {
141 auto value_ptr = protected_part_.Get(key);
142 if (value_ptr) {
143 return value_ptr;
144 }
145
146 auto node_to_protected = probation_part_.ExtractNode(key);
147 if (node_to_protected) {
148 if (protected_part_.GetSize() == protected_part_.GetCapacity()) {
149 auto node_to_probation = protected_part_.ExtractLeastUsedNode();
150 probation_part_.InsertNode(std::move(node_to_probation));
151 }
152 return &protected_part_.InsertNode(std::move(node_to_protected));
153 }
154 return nullptr;
155}
156
157template <typename T, typename U, typename Hash, typename Equal>
158const T* SlruBase<T, U, Hash, Equal>::GetLeastUsedKey() const {
159 return probation_part_.GetLeastUsedKey();
160}
161
162template <typename T, typename U, typename Hash, typename Equal>
163U* SlruBase<T, U, Hash, Equal>::GetLeastUsedValue() {
164 return probation_part_.GetLeastUsedValue();
165}
166
167template <typename T, typename U, typename Hash, typename Equal>
168typename SlruBase<T, U, Hash, Equal>::NodeType
169SlruBase<T, U, Hash, Equal>::ExtractLeastUsedNode() {
170 return probation_part_.ExtractLeastUsedNode();
171}
172
173template <typename T, typename U, typename Hash, typename Equal>
174void SlruBase<T, U, Hash, Equal>::SetMaxSize(std::size_t new_probation_size,
175 std::size_t new_protected_size) {
176 probation_part_.SetMaxSize(new_probation_size);
177 protected_part_.SetMaxSize(new_protected_size);
178}
179
180template <typename T, typename U, typename Hash, typename Equal>
181void SlruBase<T, U, Hash, Equal>::Clear() noexcept {
182 probation_part_.Clear();
183 protected_part_.Clear();
184}
185
186template <typename T, typename U, typename Hash, typename Equal>
187template <typename Function>
188void SlruBase<T, U, Hash, Equal>::VisitAll(Function&& func) const {
189 probation_part_.VisitAll(std::forward<Function>(func));
190 protected_part_.VisitAll(std::forward<Function>(func));
191}
192
193template <typename T, typename U, typename Hash, typename Equal>
194template <typename Function>
195void SlruBase<T, U, Hash, Equal>::VisitAll(Function&& func) {
196 probation_part_.VisitAll(std::forward<Function>(func));
197 protected_part_.VisitAll(std::forward<Function>(func));
198}
199
200template <typename T, typename U, typename Hash, typename Equal>
201std::size_t SlruBase<T, U, Hash, Equal>::GetSize() const {
202 return probation_part_.GetSize() + protected_part_.GetSize();
203}
204
205template <typename T, typename U, typename Hash, typename Equal>
206std::size_t SlruBase<T, U, Hash, Equal>::GetCapacity() const {
207 return probation_part_.GetCapacity() + protected_part_.GetCapacity();
208}
209
210template <typename T, typename U, typename Hash, typename Equal>
211U& SlruBase<T, U, Hash, Equal>::InsertNode(NodeType&& node) noexcept {
212 return probation_part_.InsertNode(std::move(node));
213}
214
215template <typename T, typename U, typename Hash, typename Equal>
216typename SlruBase<T, U, Hash, Equal>::NodeType
217SlruBase<T, U, Hash, Equal>::ExtractNode(const T& key) noexcept {
218 auto protected_node = protected_part_.ExtractNode(key);
219 if (protected_node) {
220 return protected_node;
221 }
222
223 return probation_part_.ExtractNode(key);
224}
225
226} // namespace cache::impl
227
228USERVER_NAMESPACE_END