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 |
|
26 | namespace 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 | */
|
32 | template <typename T, unsigned size = 1>
|
33 | class 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 |
|
44 | public:
|
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 |
|
135 | template <typename T, unsigned size>
|
136 | std::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
|
150 | template <typename T>
|
151 | class LRUCache<T, 1> {
|
152 | // the single entry in this cache
|
153 | T entry;
|
154 |
|
155 | public:
|
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.
|
194 | template <typename T>
|
195 | class LRUCache<T, 0> {
|
196 | public:
|
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 |
|
242 | class CacheAccessCounter {
|
243 | std::atomic<std::size_t> hits;
|
244 | std::atomic<std::size_t> misses;
|
245 |
|
246 | public:
|
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 |
|
272 | class CacheAccessCounter {
|
273 | public:
|
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
|