fmatvec 0.0.0

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>
124 LRUCache<In,Out,InHash,InKeyEqual,UnorderedMapAllocator,ListAllocator>::~LRUCache() {
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>
130 std::pair<Out&, bool> LRUCache<In,Out,InHash,InKeyEqual,UnorderedMapAllocator,ListAllocator>::operator()(const In &in) {
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>
194 double LRUCache<In,Out,InHash,InKeyEqual,UnorderedMapAllocator,ListAllocator>::getCacheHitRate() const {
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
fmatvec::Atom::msgStatic
static std::ostream & msgStatic(MsgType type)
Definition: atom.h:93
fmatvec::Matrix
This is the basic matrix class for arbitrary matrices.
Definition: fmatvec.h:42
fmatvec::RowVector
Definition: fmatvec.h:51
fmatvec::Vector
Definition: fmatvec.h:48
fmatvec::Atom::msgActStatic
static bool msgActStatic(MsgType type)
Definition: atom.h:98
fmatvec
Namespace fmatvec.
Definition: _memory.cc:28
fmatvec::LRUCache
Definition: lrucache.h:66
fmatvec::LRUCache::LRUCache
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
fmatvec::LRUCache::operator()
std::pair< Out &, bool > operator()(const In &in)
Definition: lrucache.h:130
fmatvec::LRUCache::~LRUCache
~LRUCache()
Prints the cache hit rate in debug builds to the stream Atom::Debug.
Definition: lrucache.h:124