souffle  2.0.2-371-g6315b36
CacheUtil.h
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2013, Oracle and/or its affiliates. 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;
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
souffle::LRUCache::clear
void clear(const T &val=T())
Definition: CacheUtil.h:69
souffle::CacheAccessCounter::CacheAccessCounter
CacheAccessCounter()=default
souffle::CacheAccessCounter::addMiss
void addMiss()
Definition: CacheUtil.h:283
TCB_SPAN_NAMESPACE_NAME::detail::size
constexpr auto size(const C &c) -> decltype(c.size())
Definition: span.h:198
souffle::LRUCache::post
std::array< std::size_t, size > post
Definition: CacheUtil.h:51
souffle::LRUCache::first
std::size_t first
Definition: CacheUtil.h:53
souffle::LRUCache::last
std::size_t last
Definition: CacheUtil.h:54
souffle::LRUCache
An Least-Recently-Used cache for arbitrary element types.
Definition: CacheUtil.h:39
souffle::LRUCache::priv
std::array< std::size_t, size > priv
Definition: CacheUtil.h:50
souffle::CacheAccessCounter::getMisses
std::size_t getMisses()
Definition: CacheUtil.h:287
i
size_t i
Definition: json11.h:663
souffle::CacheAccessCounter::getAccesses
std::size_t getAccesses()
Definition: CacheUtil.h:290
souffle::LRUCache::entries
std::array< T, size > entries
Definition: CacheUtil.h:47
souffle::CacheAccessCounter::addHit
void addHit()
Definition: CacheUtil.h:282
souffle::operator<<
std::ostream & operator<<(std::ostream &os, AggregateOp op)
Definition: AggregateOp.h:51
souffle::LRUCache::any
bool any(const Op &op) const
Definition: CacheUtil.h:142
souffle::CacheAccessCounter::getHits
std::size_t getHits()
Definition: CacheUtil.h:284
souffle
Definition: AggregateOp.h:25
souffle::LRUCache::access
void access(const T &val)
Definition: CacheUtil.h:76
souffle::CacheAccessCounter::reset
void reset()
Definition: CacheUtil.h:293
souffle::CacheAccessCounter
cache hits/misses.
Definition: CacheUtil.h:278
souffle::LRUCache::LRUCache
LRUCache(const T &val=T())
Definition: CacheUtil.h:58
souffle::LRUCache::forEachInOrder
bool forEachInOrder(const Op &op) const
Iterates over the elements within this cache in LRU order.
Definition: CacheUtil.h:131