OILS / vendor / souffle / utility / CacheUtil.h View on Github | oilshell.org

291 lines, 139 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2021, The Souffle Developers. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8
9/************************************************************************
10 *
11 * @file CacheUtil.h
12 *
13 * @brief Datalog project utilities
14 *
15 ***********************************************************************/
16
17#pragma once
18
19#include <array>
20#include <fstream>
21
22// -------------------------------------------------------------------------------
23// Hint / Cache
24// -------------------------------------------------------------------------------
25
26namespace souffle {
27
28/**
29 * An Least-Recently-Used cache for arbitrary element types. Elements can be signaled
30 * to be accessed and iterated through in their LRU order.
31 */
32template <typename T, unsigned size = 1>
33class LRUCache {
34 // the list of pointers maintained
35 std::array<T, size> entries;
36
37 // pointer to predecessor / successor in the entries list
38 std::array<std::size_t, size> priv; // < predecessor of element i
39 std::array<std::size_t, size> post; // < successor of element i
40
41 std::size_t first{0}; // < index of the first element
42 std::size_t last{size - 1}; // < index of the last element
43
44public:
45 // creates a new, empty cache
46 LRUCache(const T& val = T()) {
47 for (unsigned i = 0; i < size; i++) {
48 entries[i] = val;
49 priv[i] = i - 1;
50 post[i] = i + 1;
51 }
52 priv[first] = last;
53 post[last] = first;
54 }
55
56 // clears the content of this cache
57 void clear(const T& val = T()) {
58 for (auto& cur : entries) {
59 cur = val;
60 }
61 }
62
63 // registers an access to the given element
64 void access(const T& val) {
65 // test whether it is contained
66 for (std::size_t i = 0; i < size; i++) {
67 if (entries[i] != val) {
68 continue;
69 }
70
71 // -- move this one to the front --
72
73 // if it is the first, nothing to handle
74 if (i == first) {
75 return;
76 }
77
78 // if this is the last, just first and last need to change
79 if (i == last) {
80 auto tmp = last;
81 last = priv[last];
82 first = tmp;
83 return;
84 }
85
86 // otherwise we need to update the linked list
87
88 // remove from current position
89 post[priv[i]] = post[i];
90 priv[post[i]] = priv[i];
91
92 // insert in first position
93 post[i] = first;
94 priv[i] = last;
95 priv[first] = i;
96 post[last] = i;
97
98 // update first pointer
99 first = i;
100 return;
101 }
102 // not present => drop last, make it first
103 entries[last] = val;
104 auto tmp = last;
105 last = priv[last];
106 first = tmp;
107 }
108
109 /**
110 * Iterates over the elements within this cache in LRU order.
111 * The operator is applied on each element. If the operation
112 * returns false, iteration is continued. If the operator return
113 * true, iteration is stopped -- similar to the any operator.
114 *
115 * @param op the operator to be applied on every element
116 * @return true if op returned true for any entry, false otherwise
117 */
118 template <typename Op>
119 bool forEachInOrder(const Op& op) const {
120 std::size_t i = first;
121 while (i != last) {
122 if (op(entries[i])) return true;
123 i = post[i];
124 }
125 return op(entries[i]);
126 }
127
128 // equivalent to forEachInOrder
129 template <typename Op>
130 bool any(const Op& op) const {
131 return forEachInOrder(op);
132 }
133};
134
135template <typename T, unsigned size>
136std::ostream& operator<<(std::ostream& out, const LRUCache<T, size>& cache) {
137 bool first = true;
138 cache.forEachInOrder([&](const T& val) {
139 if (!first) {
140 out << ",";
141 }
142 first = false;
143 out << val;
144 return false;
145 });
146 return out;
147}
148
149// a specialization for a single-entry cache
150template <typename T>
151class LRUCache<T, 1> {
152 // the single entry in this cache
153 T entry;
154
155public:
156 // creates a new, empty cache
157 LRUCache() : entry() {}
158
159 // creates a new, empty cache storing the given value
160 LRUCache(const T& val) : entry(val) {}
161
162 // clears the content of this cache
163 void clear(const T& val = T()) {
164 entry = val;
165 }
166
167 // registers an access to the given element
168 void access(const T& val) {
169 entry = val;
170 }
171
172 /**
173 * See description in most general case.
174 */
175 template <typename Op>
176 bool forEachInOrder(const Op& op) const {
177 return op(entry);
178 }
179
180 // equivalent to forEachInOrder
181 template <typename Op>
182 bool any(const Op& op) const {
183 return forEachInOrder(op);
184 }
185
186 // --- print support ---
187
188 friend std::ostream& operator<<(std::ostream& out, const LRUCache& cache) {
189 return out << cache.entry;
190 }
191};
192
193// a specialization for no-entry caches.
194template <typename T>
195class LRUCache<T, 0> {
196public:
197 // creates a new, empty cache
198 LRUCache(const T& = T()) {}
199
200 // clears the content of this cache
201 void clear(const T& = T()) {
202 // nothing to do
203 }
204
205 // registers an access to the given element
206 void access(const T&) {
207 // nothing to do
208 }
209
210 /**
211 * Always returns false.
212 */
213 template <typename Op>
214 bool forEachInOrder(const Op&) const {
215 return false;
216 }
217
218 // equivalent to forEachInOrder
219 template <typename Op>
220 bool any(const Op& op) const {
221 return forEachInOrder(op);
222 }
223
224 // --- print support ---
225
226 friend std::ostream& operator<<(std::ostream& out, const LRUCache& /* cache */) {
227 return out << "-empty-";
228 }
229};
230
231// -------------------------------------------------------------------------------
232// Hint / Cache Profiling
233// -------------------------------------------------------------------------------
234
235/**
236 * cache hits/misses.
237 */
238#ifdef _SOUFFLE_STATS
239
240#include <atomic>
241
242class CacheAccessCounter {
243 std::atomic<std::size_t> hits;
244 std::atomic<std::size_t> misses;
245
246public:
247 CacheAccessCounter() : hits(0), misses(0) {}
248 CacheAccessCounter(const CacheAccessCounter& other) : hits(other.getHits()), misses(other.getMisses()) {}
249 void addHit() {
250 hits.fetch_add(1, std::memory_order_relaxed);
251 }
252 void addMiss() {
253 misses.fetch_add(1, std::memory_order_relaxed);
254 }
255 std::size_t getHits() const {
256 return hits;
257 }
258 std::size_t getMisses() const {
259 return misses;
260 }
261 std::size_t getAccesses() const {
262 return getHits() + getMisses();
263 }
264 void reset() {
265 hits = 0;
266 misses = 0;
267 }
268};
269
270#else
271
272class CacheAccessCounter {
273public:
274 CacheAccessCounter() = default;
275 CacheAccessCounter(const CacheAccessCounter& /* other */) = default;
276 inline void addHit() {}
277 inline void addMiss() {}
278 inline std::size_t getHits() {
279 return 0;
280 }
281 inline std::size_t getMisses() {
282 return 0;
283 }
284 inline std::size_t getAccesses() {
285 return 0;
286 }
287 inline void reset() {}
288};
289
290#endif
291} // end namespace souffle