fmatvec  0.0.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Friends Pages
lrucache.h
1 #ifndef _FMATVEC_LRUCACHE_H_
2 #define _FMATVEC_LRUCACHE_H_
3 
4 #include <list>
5 #include <cmath>
6 #include <unordered_map>
7 #include <functional>
8 #include <boost/container_hash/hash.hpp>
9 #include <fmatvec/fmatvec.h>
10 #include <fmatvec/atom.h>
11 
12 namespace boost {
13 
14  template<class Row, class AT>
15  struct hash<fmatvec::Vector<Row,AT>> {
16  size_t operator()(const fmatvec::Vector<Row,AT> &v) const {
17  size_t h=0;
18  for(int i=0; i<v.size(); ++i)
19  hash_combine(h, v(i));
20  return h;
21  };
22  };
23 
24  template<class Col, class AT>
25  struct hash<fmatvec::RowVector<Col,AT>> {
26  size_t operator()(const fmatvec::RowVector<Col,AT> &v) const {
27  size_t h=0;
28  for(int i=0; i<v.size(); ++i)
29  hash_combine(h, v(i));
30  return h;
31  };
32  };
33 
34  template<class Type, class Row, class Col, class AT>
35  struct hash<fmatvec::Matrix<Type,Row,Col,AT>> {
36  size_t operator()(const fmatvec::Matrix<Type,Row,Col,AT> &v) const {
37  size_t h=0;
38  for(int r=0; r<v.rows(); ++r)
39  for(int c=0; c<v.cols(); ++c)
40  hash_combine(h, v(r,c));
41  return h;
42  };
43  };
44 
45 }
46 
47 namespace fmatvec {
48 
49  template<class T>
50  inline void assign(T &dst, const T &src);
51 
60  template<class In,
61  class Out,
62  class InHash = boost::hash<In>,
63  class InKeyEqual = std::equal_to<In>,
64  class UnorderedMapAllocator = std::allocator<std::pair<const In, typename std::list<std::pair<const In&,Out>>::iterator>>,
65  class ListAllocator = std::allocator<std::pair<const In&, Out>> >
66  class LRUCache {
67  public:
69  LRUCache(size_t size_, size_t smallSize=45, double bucketSizeFactor = 1.5);
71  ~LRUCache();
78  inline std::pair<Out&, bool> operator()(const In &in);
79  double getCacheHitRate() const;
80  // Set the name of the LRUCache. It's only used to print this name in the dtor to Atom::Debug.
81  void setName(const std::string &name_) { name = name_; }
82  private:
83  std::list<std::pair<const In&,Out>, ListAllocator> itemList;
84  std::unordered_map<In, decltype(itemList.begin()), InHash, InKeyEqual, UnorderedMapAllocator> itemMap;
85  size_t size;
86  size_t allCalls { 0 }, cacheHits { 0 };
87  std::string name;
88 
89  bool useSmallSizeCode;
90  // special variables for small size <= smallSize
91  std::vector<size_t> timeCache;
92  std::vector<In> inCache;
93  std::vector<Out> outCache;
94  };
95 
96  template<class In, class Out, class InHash, class InKeyEqual, class UnorderedMapAllocator, class ListAllocator>
97  LRUCache<In,Out,InHash,InKeyEqual,UnorderedMapAllocator,ListAllocator>::LRUCache(size_t size_, size_t smallSize, double bucketSizeFactor) {
98  // we can override the LRU cache size with FMATVEC_LRUCACHE_SIZE
99  static auto envSize = static_cast<size_t>(-1);
100  if(envSize == static_cast<size_t>(-1)) {
101  const char *env = getenv("FMATVEC_LRUCACHE_SIZE");
102  if(env)
103  envSize = atoi(env);
104  else
105  envSize = 0;
106  }
107  if(envSize != 0)
108  size_ = envSize;
109 
110  size = size_;
111  useSmallSizeCode = size<=smallSize;
112  if(useSmallSizeCode) {
113  timeCache.resize(size);
114  inCache.resize(size);
115  outCache.resize(size);
116  for(size_t i=0; i<size; ++i)
117  timeCache[i] = 0;
118  }
119  else
120  itemMap.rehash(floor(bucketSizeFactor*size));
121  }
122 
123  template<class In, class Out, class InHash, class InKeyEqual, class UnorderedMapAllocator, class ListAllocator>
125  if(Atom::msgActStatic(Atom::Debug))
126  Atom::msgStatic(Atom::Debug)<<"Cache hit rate of '"<<name<<"' = "<<getCacheHitRate()*100<<"%"<<std::endl;
127  }
128 
129  template<class In, class Out, class InHash, class InKeyEqual, class UnorderedMapAllocator, class ListAllocator>
131  allCalls++;
132  if(useSmallSizeCode) {
133  bool created = true;
134  size_t minTime = std::numeric_limits<size_t>::max();
135  size_t minTimeIdx = 0;
136  size_t i;
137 #ifdef FMATVEC_LRUCACHE_SMALLSIZE_WORSTPERFORMANCE
138  size_t iSaved;
139 #endif
140  for(i=0; i<size && i<allCalls-1; ++i) {
141  if(timeCache[i] < minTime) {
142  minTime = timeCache[i];
143  minTimeIdx = i;
144  }
145  if(inCache[i]==in) {
146  created = false;
147 #ifdef FMATVEC_LRUCACHE_SMALLSIZE_WORSTPERFORMANCE // for performance testing we can enable the worst performance possible
148  iSaved=i;
149 #else
150  break;
151 #endif
152  }
153  }
154 #ifdef FMATVEC_LRUCACHE_SMALLSIZE_WORSTPERFORMANCE
155  i=iSaved;
156 #endif
157  if(!created) {
158  cacheHits++;
159  timeCache[i]=allCalls;
160  return {outCache[i], false};
161  }
162  else {
163  assign(inCache[minTimeIdx], in);
164  assign(outCache[minTimeIdx], Out());
165  timeCache[minTimeIdx] = allCalls;
166  return {outCache[minTimeIdx], true};
167  }
168  }
169  else {
170  auto [it, created] = itemMap.emplace(in, itemList.begin());
171 
172  if(created) {
173  // new itemMap{in,it_dummy} was created by the above call (as "it")
174  itemList.emplace_front(it->first, Out()); // create a new first itemList with a default ctor out value
175  // remove old item(s) if too many items exist
176  if(itemMap.size() > size) {
177  auto itLast = --itemList.end();
178  itemMap.erase(itLast->first);
179  itemList.pop_back();
180  }
181  }
182  else {
183  cacheHits++;
184  // a existing itemMap{in,it_to_itemList} was selected by the above call (as "it")
185  itemList.emplace_front(it->first, std::move(it->second->second)); // create a new first itemList by move-ctor out from the existing
186  itemList.erase(it->second); // remove the old itemList
187  }
188  it->second = itemList.begin(); // fix second value of itemMap (it was either created with a dummy iterator or has changed)
189  return {it->second->second,created};
190  }
191  }
192 
193  template<class In, class Out, class InHash, class InKeyEqual, class UnorderedMapAllocator, class ListAllocator>
195  return allCalls==0 ? -1 : static_cast<double>(cacheHits)/allCalls;
196  }
197 
198  template<class T>
199  void assign(T &dst, const T &src) {
200  dst = src;
201  }
202 
203  template<class Row, class AT>
204  void assign(Vector<Row,AT> &dst, const Vector<Row,AT> &src) {
205  dst <<= src;
206  };
207 
208  template<class Row, class AT>
209  void assign(RowVector<Row,AT> &dst, const RowVector<Row,AT> &src) {
210  dst <<= src;
211  };
212 
213  template<class Type, class Row, class Col, class AT>
214  void assign(Matrix<Type,Row,Col,AT> &dst, const Matrix<Type,Row,Col,AT> &src) {
215  dst <<= src;
216  };
217 
218 }
219 
220 #endif
static std::ostream & msgStatic(MsgType type)
Definition: atom.h:93
This is the basic matrix class for arbitrary matrices.
Definition: fmatvec.h:42
Definition: fmatvec.h:51
int rows() const
Number of rows.
int cols() const
Number of columns.
Definition: fmatvec.h:48
static bool msgActStatic(MsgType type)
Definition: atom.h:98
Definition: lrucache.h:66
LRUCache(size_t size_, size_t smallSize=45, double bucketSizeFactor=1.5)
Create a LRU cache of at most size items.
Definition: lrucache.h:97
std::pair< Out &, bool > operator()(const In &in)
Definition: lrucache.h:130
~LRUCache()
Prints the cache hit rate in debug builds to the stream Atom::Debug.
Definition: lrucache.h:124