LSST Applications  21.0.0+04719a4bac,21.0.0-1-ga51b5d4+f5e6047307,21.0.0-11-g2b59f77+a9c1acf22d,21.0.0-11-ga42c5b2+86977b0b17,21.0.0-12-gf4ce030+76814010d2,21.0.0-13-g1721dae+760e7a6536,21.0.0-13-g3a573fe+768d78a30a,21.0.0-15-g5a7caf0+f21cbc5713,21.0.0-16-g0fb55c1+b60e2d390c,21.0.0-19-g4cded4ca+71a93a33c0,21.0.0-2-g103fe59+bb20972958,21.0.0-2-g45278ab+04719a4bac,21.0.0-2-g5242d73+3ad5d60fb1,21.0.0-2-g7f82c8f+8babb168e8,21.0.0-2-g8f08a60+06509c8b61,21.0.0-2-g8faa9b5+616205b9df,21.0.0-2-ga326454+8babb168e8,21.0.0-2-gde069b7+5e4aea9c2f,21.0.0-2-gecfae73+1d3a86e577,21.0.0-2-gfc62afb+3ad5d60fb1,21.0.0-25-g1d57be3cd+e73869a214,21.0.0-3-g357aad2+ed88757d29,21.0.0-3-g4a4ce7f+3ad5d60fb1,21.0.0-3-g4be5c26+3ad5d60fb1,21.0.0-3-g65f322c+e0b24896a3,21.0.0-3-g7d9da8d+616205b9df,21.0.0-3-ge02ed75+a9c1acf22d,21.0.0-4-g591bb35+a9c1acf22d,21.0.0-4-g65b4814+b60e2d390c,21.0.0-4-gccdca77+0de219a2bc,21.0.0-4-ge8a399c+6c55c39e83,21.0.0-5-gd00fb1e+05fce91b99,21.0.0-6-gc675373+3ad5d60fb1,21.0.0-64-g1122c245+4fb2b8f86e,21.0.0-7-g04766d7+cd19d05db2,21.0.0-7-gdf92d54+04719a4bac,21.0.0-8-g5674e7b+d1bd76f71f,master-gac4afde19b+a9c1acf22d,w.2021.13
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:430
#define LSST_EXCEPT(type,...)
Create an exception with a given type.
Definition: Exception.h:48
Key< U > key
Definition: Schema.cc:281
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.