LSST Applications  21.0.0-142-gef555c1e+42c9bccae2,22.0.0+052faf71bd,22.0.0+1c4650f311,22.0.0+40ce427c77,22.0.0+5b6c068b1a,22.0.0+7589c3a021,22.0.0+81ed51be6d,22.0.1-1-g7d6de66+6cae67f2c6,22.0.1-1-g87000a6+314cd8b7ea,22.0.1-1-g8760c09+052faf71bd,22.0.1-1-g8e32f31+5b6c068b1a,22.0.1-10-g779eefa+a163f08322,22.0.1-12-g3bd7ecb+bbeacc25a9,22.0.1-15-g63cc0c1+2a7037787d,22.0.1-17-ge5a99e88+3d2c1afe2e,22.0.1-19-g88addfe+6cae67f2c6,22.0.1-2-g1cb3e5b+84de06d286,22.0.1-2-g8ef0a89+6cae67f2c6,22.0.1-2-g92698f7+1c4650f311,22.0.1-2-ga9b0f51+052faf71bd,22.0.1-2-gb66926d+5b6c068b1a,22.0.1-2-gcb770ba+0723a13595,22.0.1-2-ge470956+ff9f1dc8d5,22.0.1-22-g608e23ac+2ac85e833c,22.0.1-29-g184b6e44e+8b185d4e2d,22.0.1-3-g59f966b+11ba4df19d,22.0.1-3-g8c1d971+f90df4c6d0,22.0.1-3-g997b569+d69a7aa2f8,22.0.1-3-gaaec9c0+4d194bf81c,22.0.1-4-g1930a60+283d9d2f1a,22.0.1-4-g5b7b756+c1283a92b8,22.0.1-4-g8623105+6cae67f2c6,22.0.1-7-gba73697+283d9d2f1a,22.0.1-8-g47d23f5+43acea82f3,master-g5f2689bdc5+40ce427c77,w.2021.38
LSST Data Management Base Package
Cache.h
Go to the documentation of this file.
1 /*
2  * LSST Data Management System
3  * See COPYRIGHT file at the top of the source tree.
4  *
5  * This product includes software developed by the
6  * LSST Project (http://www.lsst.org/).
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the LSST License Statement and
19  * the GNU General Public License along with this program. If not,
20  * see <http://www.lsstcorp.org/LegalNotices/>.
21  */
22 #ifndef LSST_UTILS_CACHE_H
23 #define LSST_UTILS_CACHE_H
24 
25 #include <vector>
26 #include <utility> // std::pair
27 
28 #include "boost/multi_index_container.hpp"
29 #include "boost/multi_index/sequenced_index.hpp"
30 #include "boost/multi_index/hashed_index.hpp"
31 #include "boost/multi_index/composite_key.hpp"
32 #include "boost/multi_index/member.hpp"
33 #include "boost/format.hpp"
34 
35 #include "lsst/pex/exceptions.h"
36 #include "lsst/utils/CacheFwd.h"
37 
38 //#define LSST_CACHE_DEBUG 1 // Define this variable to instrument for debugging
39 
40 
41 #ifdef LSST_CACHE_DEBUG
42 #include <iostream>
43 #include <fstream>
44 #include <typeinfo>
45 #include "lsst/utils/Demangle.h"
46 #endif
47 
48 namespace lsst {
49 namespace utils {
50 
73 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
74 class Cache {
75  public:
84  Cache(std::size_t maxElements=0) : _maxElements(maxElements) {
85  _container.template get<Hash>().reserve(maxElements);
86 #ifdef LSST_CACHE_DEBUG
87  _debuggingEnabled = false;
88  _hits = 0;
89  _total = 0;
90  _requests.reserve(maxElements);
91 #endif
92  }
93 
94  // Defaulted stuff
95  Cache(Cache const &) = default;
96  Cache(Cache &&) = default;
97  Cache & operator=(Cache const &) = default;
98  Cache & operator=(Cache &&) = default;
99 
101 #ifdef LSST_CACHE_DEBUG
104  ~Cache();
105 #else
106  ~Cache() = default;
107 #endif
108 
129  template <typename Generator>
130  Value operator()(Key const& key, Generator func);
131 
132  /* Lookup a value
133  *
134  * If the key is in the cache, it will be promoted to the
135  * most recently used value.
136  *
137  * @throws lsst::pex::exceptions::NotFoundError If key is not in the
138  * cache.
139  *
140  * @exceptsafe Basic exception safety: exceptions will leave the
141  * system in a valid but unpredictable state.
142  */
143  Value operator[](Key const& key);
144 
153  void add(Key const& key, Value const& value);
154 
160  std::size_t size() const { return _container.size(); }
161 
167  std::vector<Key> keys() const;
168 
177  bool contains(Key const& key) { return _lookup(key).second; }
178 
183  std::size_t capacity() const { return _maxElements; }
184 
190  void reserve(std::size_t maxElements) { _maxElements = maxElements; _trim(); }
191 
197  void flush();
198 
199 #ifdef LSST_CACHE_DEBUG
200  void enableDebugging() { _debuggingEnabled = true; }
201 #endif
202 
203  private:
204 
205  // Trim the cache to size
206  void _trim() {
207  if (capacity() == 0) return; // Allowed to grow without limit
208  while (size() > capacity()) {
209  _container.template get<Sequence>().pop_back();
210  }
211  }
212 
213  // Element in the multi_index container
214  typedef std::pair<Key, Value> Element;
215 
216  // Tags for multi_index container
217  struct Sequence {};
218  struct Hash {};
219 
220  // The multi_index container
221  typedef boost::multi_index_container<
222  Element,
223  boost::multi_index::indexed_by<
224  boost::multi_index::sequenced<boost::multi_index::tag<Sequence>>,
225  boost::multi_index::hashed_unique<
226  boost::multi_index::tag<Hash>,
227  boost::multi_index::member<Element, Key, &Element::first>,
228  KeyHash>>> Container;
229 
230  // Lookup key in the container
231  //
232  // Returns the iterator and whether there's anything there.
233  //
234  // If the key exists, updates the cache to make that key the most recent.
236  auto const& hashContainer = _container.template get<Hash>();
237  auto it = hashContainer.find(key);
238  bool found = (it != hashContainer.end());
239  if (found) {
240  _container.relocate(_container.template get<Sequence>().begin(),
241  _container.template project<Sequence>(it));
242  }
243 #ifdef LSST_CACHE_DEBUG
244  if (_debuggingEnabled) {
245  _requests.push_back(key);
246  ++_total;
247  if (found) ++_hits;
248  }
249 #endif
250  return std::make_pair(it, found);
251  }
252 
253  // Add a key-value pair that are not already present
254  void _addNew(Key const& key, Value const& value) {
255  _container.template get<Sequence>().emplace_front(key, value);
256  _trim();
257  }
258 
259  std::size_t _maxElements; // Maximum number of elements; 0 means infinite
260  Container _container; // Container of key,value pairs
261 #ifdef LSST_CACHE_DEBUG
262  bool _debuggingEnabled;
263  mutable std::size_t _hits, _total; // Statistics of cache hits
264  mutable std::vector<Key> _requests; // Cache requests
265  static std::size_t getId() {
266  static std::size_t _id = 0; // Identifier
267  return _id++;
268  }
269 #endif
270 };
271 
272 // Definitions
273 
274 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
275 template <typename Generator>
277  Key const& key,
278  Generator func
279 ) {
280  auto result = _lookup(key);
281  if (result.second) {
282  return result.first->second;
283  }
284  Value value = func(key);
285  _addNew(key, value);
286  return value;
287 }
288 
289 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
291  auto result = _lookup(key);
292  if (result.second) {
293  return result.first->second;
294  }
296  (boost::format("Unable to find key: %s") % key).str());
297 }
298 
299 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
300 void Cache<Key, Value, KeyHash, KeyPred>::add(Key const& key, Value const& value) {
301  auto result = _lookup(key);
302  if (!result.second) {
303  _addNew(key, value);
304  }
305 }
306 
307 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
310  result.reserve(size());
311  for (auto & keyValue : _container.template get<Sequence>()) {
312  result.push_back(keyValue.first);
313  }
314  return result;
315 }
316 
317 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
319  while (size() > 0) {
320  _container.template get<Sequence>().pop_back();
321  }
322 }
323 
324 #ifdef LSST_CACHE_DEBUG
325 template <typename Key, typename Value, typename KeyHash, typename KeyPred>
327  if (!_debuggingEnabled) {
328  return;
329  }
330  std::string filename = (boost::format("lsst-cache-%s-%d.dat") %
331  demangleType(typeid(*this).name()) % getId()).str();
332  std::ofstream file(filename);
333  for (auto const& key : _requests) {
334  file << key << "\n";
335  }
336  file.close();
337  std::cerr << "Wrote cache requests to " << filename << ": " << _hits << "/" << _total << " hits";
338  std::cerr << std::endl;
339 }
340 #endif
341 
342 }} // namespace lsst::utils
343 
344 
345 #endif // ifndef LSST_UTILS_CACHE_H
py::object result
Definition: _schema.cc:429
#define LSST_EXCEPT(type,...)
Create an exception with a given type.
Definition: Exception.h:48
Reports attempts to access elements using an invalid key.
Definition: Runtime.h:151
Cache of most recently used values.
Definition: Cache.h:74
bool contains(Key const &key)
Does the cache contain the key?
Definition: Cache.h:177
Cache(Cache const &)=default
Value operator[](Key const &key)
Definition: Cache.h:290
void reserve(std::size_t maxElements)
Change the capacity of the cache.
Definition: Cache.h:190
Value operator()(Key const &key, Generator func)
Lookup or generate a value.
Definition: Cache.h:276
void add(Key const &key, Value const &value)
Add a value to the cache.
Definition: Cache.h:300
std::vector< Key > keys() const
Return all keys in the cache, most recent first.
Definition: Cache.h:308
Cache(Cache &&)=default
std::size_t size() const
Return the number of values in the cache.
Definition: Cache.h:160
Cache & operator=(Cache const &)=default
void flush()
Empty the cache.
Definition: Cache.h:318
Cache(std::size_t maxElements=0)
Ctor.
Definition: Cache.h:84
Cache & operator=(Cache &&)=default
std::size_t capacity() const
Return the capacity of the cache.
Definition: Cache.h:183
~Cache()=default
Dtor.
T endl(T... args)
T make_pair(T... args)
def format(config, name=None, writeSourceLine=True, prefix="", verbose=False)
Definition: history.py:174
std::string demangleType(std::string const _typeName)
Definition: Demangle.cc:113
A base class for image defects.