MPQC  3.0.0-alpha
conc_cache.h
1 //
2 
3 // conc_cache.h
4 //
5 // Copyright (C) 2013 David Hollman
6 //
7 // Author: David Hollman
8 // Maintainer: DSH
9 // Created: Nov 19, 2013
10 //
11 // This file is part of the SC Toolkit.
12 //
13 // The SC Toolkit is free software; you can redistribute it and/or modify
14 // it under the terms of the GNU Library General Public License as published by
15 // the Free Software Foundation; either version 2, or (at your option)
16 // any later version.
17 //
18 // The SC Toolkit is distributed in the hope that it will be useful,
19 // but WITHOUT ANY WARRANTY; without even the implied warranty of
20 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 // GNU Library General Public License for more details.
22 //
23 // You should have received a copy of the GNU Library General Public License
24 // along with the SC Toolkit; see the file COPYING.LIB. If not, write to
25 // the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
26 //
27 // The U.S. Government is granted a limited license as per AL 91-7.
28 //
29 
30 #ifndef _util_container_conc_cache_h
31 #define _util_container_conc_cache_h
32 
33 // Standard library includes
34 #include <cassert>
35 #include <utility>
36 #include <functional>
37 
38 // Boost includes
39 #include <boost/tuple/tuple.hpp>
40 #include <boost/tuple/tuple_comparison.hpp>
41 #include <boost/tuple/tuple_io.hpp>
42 #include <boost/utility.hpp>
43 #include <boost/type_traits.hpp>
44 #include <boost/thread/future.hpp>
45 #include <boost/utility/enable_if.hpp>
46 #include <boost/type_traits.hpp>
47 #include <boost/mpl/range_c.hpp>
48 #include <boost/mpl/if.hpp>
49 #include <boost/mpl/at.hpp>
50 #include <boost/mpl/int.hpp>
51 #include <boost/mpl/integral_c.hpp>
52 #include <boost/mpl/vector.hpp>
53 #include <boost/mpl/equal_to.hpp>
54 #include <boost/mpl/comparison.hpp>
55 #include <boost/mpl/push_front.hpp>
56 #include <boost/mpl/replace_if.hpp>
57 #include <boost/mpl/copy.hpp>
58 #include <boost/mpl/vector_c.hpp>
59 #include <boost/mpl/back_inserter.hpp>
60 
61 // Madness includes
62 #include <madness/world/worldhashmap.h>
63 #include <madness/world/future.h>
64 
65 // MPQC imcludes
66 #include <util/misc/iterators.h>
67 #include <util/misc/meta.h>
68 #include <util/container/conc_cache_fwd.h>
69 
70 namespace {
71 
72  template<typename T>
73  struct _hash { };
74 
75  template<typename... key_types>
76  struct _hash<boost::tuple<key_types...>> {
77  inline madness::hashT
78  operator()(const boost::tuple<key_types...>& key) const {
79  madness::hashT seed = 0;
80  hash_recursive(key, seed);
81  return seed;
82  }
83  private:
84 
85  template<typename H, typename T>
86  inline typename boost::disable_if<
87  boost::is_same<T, boost::tuples::null_type>>::type
88  hash_recursive(const boost::tuples::cons<H, T>& key_part, madness::hashT& seed) const
89  {
90  madness::hash_combine(seed, make_hashable(key_part.get_head()));
91  hash_recursive(key_part.get_tail(), seed);
92  }
93 
94  template<typename H, typename T>
95  inline typename boost::enable_if<boost::is_same<T, boost::tuples::null_type>>::type
96  hash_recursive(const boost::tuples::cons<H, T>& key_part, madness::hashT& seed) const
97  {
98  madness::hash_combine(seed, make_hashable(key_part.get_head()));
99  }
100 
101  template<typename T>
102  inline typename boost::enable_if<
103  boost::is_enum<T>,
104  int
105  >::type
106  make_hashable(const T& val) const {
107  return (int)val;
108  }
109 
110  template<typename T>
111  inline typename boost::disable_if<
112  boost::is_enum<T>,
113  const T&
114  >::type
115  make_hashable(const T& val) const {
116  return val;
117  }
118  };
119 
120 }
121 
123 
124 namespace sc {
125 
126 template<int n_indices, int... PermutedIndices>
127 struct KeyPermutation {
128  static constexpr int order = sizeof...(PermutedIndices);
129 };
130 
131 template<int n_indices, int idx_1, int idx_2>
132 struct KeyTransposition
133  : public meta::splat_values<int,
134  KeyPermutation,
135  typename boost::mpl::replace_if<
136  typename boost::mpl::replace_if<
137  typename boost::mpl::copy<
138  boost::mpl::range_c<int, 0, n_indices>,
139  boost::mpl::back_inserter<
140  boost::mpl::vector_c<int, n_indices>
141  >
142  >::type,
143  boost::mpl::equal_to<
144  boost::mpl::_,
145  boost::mpl::int_<idx_1>
146  >,
147  boost::mpl::int_<idx_2>
148  >::type,
149  boost::mpl::equal_to<
150  boost::mpl::_,
151  boost::mpl::int_<idx_2>
152  >,
153  boost::mpl::int_<idx_1>
154  >::type
155  >::type
156 {
157  static constexpr int first_index = idx_1;
158  static constexpr int second_index = idx_2;
159 };
160 
161 template <int nkeys>
162 struct IdentityKeyPermutation
163  : public meta::splat_values<int,
164  KeyPermutation,
165  typename boost::mpl::copy<
166  boost::mpl::range_c<int, 0, nkeys>,
167  boost::mpl::back_inserter< boost::mpl::vector_c<int, nkeys> >
168  >::type
169  >::type
170 { };
171 
172 template<typename... Permutations>
173 struct KeySymmetry {
174  static constexpr int n_permutations = sizeof...(Permutations);
175 };
176 
177 
178 template<
179  typename ValueType,
180  typename... key_types
181 >
182 class ConcurrentCacheBase {
183 
184  public:
185 
187 
188  template<typename... Types> using tuple_type = boost::tuple<Types...>;
191  typedef tuple_type<key_types...> key_tuple;
193 
195 
196  typedef ValueType value_type;
199  typedef boost::shared_future<value_type> future_value;
201  typedef madness::ConcurrentHashMap<key_tuple, future_value, _hash<key_tuple>> future_map;
203  typedef typename future_map::accessor future_map_accessor;
205  typedef typename future_map::const_accessor future_map_const_accessor;
207 
208 
209  ConcurrentCacheBase() : cached_values_()
210  { }
211 
212  ConcurrentCacheBase(int nbins) : cached_values_(nbins)
213  { }
214 
215  // Old version, provided for backwards compatibility
216  value_type get(
217  key_types... keys,
218  const std::function<value_type()>& compute_fxn
219  )
220  {
221 
222  key_tuple k(std::forward<key_types>(keys)...);
223  future_map_accessor a;
224 
225  if(cached_values_.insert(a, std::make_pair(k, future_value()))){
226  boost::promise<value_type> p;
227  p.set_value(compute_fxn());
228  a->second = p.get_future().share();
229  }
230  return a->second.get();
231 
232  }
233 
234  value_type get(
235  key_types... keys,
236  const std::function<value_type(const key_tuple&)>& compute_fxn
237  )
238  {
239 
240  key_tuple k(std::forward<key_types>(keys)...);
241  future_map_accessor a;
242 
243  if(cached_values_.insert(a, std::make_pair(k, future_value()))){
244  boost::promise<value_type> p;
245  p.set_value(compute_fxn(k));
246  a->second = p.get_future().share();
247  }
248  return a->second.get();
249 
250  }
251 
252  void clear()
253  {
254  cached_values_.clear();
255  }
256 
257  protected:
258 
259  // The actual map from key tuples to values
260  future_map cached_values_;
261 
262 };
263 
269 template <
270  typename val_type,
271  typename symmetry,
272  typename... key_types
273 >
274 class ConcurrentCacheWithSymmetry
275  : public ConcurrentCacheBase<val_type, key_types...>
276 {
277  public:
278  typedef ConcurrentCacheBase<val_type, key_types...> super_t;
279  using ConcurrentCacheBase<val_type, key_types...>::ConcurrentCacheBase;
280 
281  typename super_t::value_type get_or_permute(
282  key_types... keys,
283  const std::function<typename super_t::value_type(
284  const typename super_t::key_tuple&
285  )>& compute_fxn,
286  const std::function<typename super_t::value_type(
287  const typename super_t::value_type&,
288  const typename super_t::key_tuple&
289  )>& permute_fxn
290  );
291 };
292 
296 template <typename val_type, typename... key_types>
297 class ConcurrentCacheWithSymmetry<
298  val_type,
299  KeySymmetry<IdentityKeyPermutation<sizeof...(key_types)>>,
300  key_types...
301 > : public ConcurrentCacheBase<val_type, key_types...>
302 {
303  public:
304  typedef ConcurrentCacheBase<val_type, key_types...> super_t;
305  using super_t::ConcurrentCacheBase;
306 
307  typename super_t::value_type get_or_permute(
308  key_types... keys,
309  const std::function<typename super_t::value_type(
310  const typename super_t::key_tuple&
311  )>& compute_fxn,
312  const std::function<typename super_t::value_type(
313  const typename super_t::value_type&,
314  const typename super_t::key_tuple&
315  )>& permute_fxn
316  )
317  {
318  return this->get(keys..., compute_fxn);
319  }
320 };
321 
325 template <typename val_type, int n_keys, int idx1, int idx2, typename... key_types>
326 class ConcurrentCacheWithSymmetry<
327  val_type,
328  KeySymmetry<
329  IdentityKeyPermutation<sizeof...(key_types)>,
330  KeyTransposition<n_keys, idx1, idx2>
331  >,
332  key_types...
333 > : public ConcurrentCacheBase<val_type, key_types...>
334 {
335  public:
336  typedef ConcurrentCacheBase<val_type, key_types...> super_t;
337 
338  using ConcurrentCacheBase<val_type, key_types...>::ConcurrentCacheBase;
339 
340  typedef KeyTransposition<n_keys, idx1, idx2> transposition_type;
341  typedef typename super_t::key_tuple key_tuple;
342  typedef typename super_t::value_type value_type;
343 
344  static_assert(
345  boost::is_convertible<
346  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx1>::type,
347  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx2>::type
348  >::value
349  and
350  boost::is_convertible<
351  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx2>::type,
352  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx1>::type
353  >::value
354  and
355  boost::has_less<
356  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx1>::type,
357  typename boost::mpl::at_c<boost::mpl::vector<key_types...>, idx2>::type
358  >::value
359  ,
360  "Types must be compatible to have symmetry in ConcurrentCacheWithSymmetry"
361  );
362 
363  inline value_type
364  get_or_permute(
365  key_types... keys,
366  const std::function<value_type(
367  const key_tuple&
368  )>& compute_fxn,
369  const std::function<value_type(
370  const value_type&,
371  const key_tuple&
372  )>& permute_fxn
373  )
374  {
375  key_tuple k(std::forward<key_types>(keys)...);
376 
377  if(not (boost::tuples::get<idx1>(k) < boost::tuples::get<idx2>(k))) {
378 
379  // regular case
380  typename super_t::future_map_accessor a;
381  if(this->cached_values_.insert(a, std::make_pair(k, typename super_t::future_value()))){
382  boost::promise<value_type> p;
383  p.set_value(
384  compute_fxn(k)
385  );
386  a->second = p.get_future().share();
387  }
388  return a->second.get();
389 
390  }
391  else {
392 
393  // permuted case
394  typename super_t::future_map_accessor a_perm, a_canon;
395  if(this->cached_values_.insert(a_perm, std::make_pair(k, typename super_t::future_value()))){
396 
397  key_tuple k_canon = make_permuted_key_tuple(k);
398 
399  // Now see if we need to comptue the canonical ordered value
400  if(this->cached_values_.insert(a_canon, std::make_pair(k_canon, typename super_t::future_value()))){
401 
402  boost::promise<value_type> p;
403  p.set_value(
404  compute_fxn(k_canon)
405  );
406  a_canon->second = p.get_future().share();
407 
408  }
409 
410  // Now call the permute function on the result
411  boost::promise<value_type> perm_p;
412  perm_p.set_value(
413  permute_fxn(a_canon->second.get(), k_canon)
414  );
415  a_perm->second = perm_p.get_future().share();
416 
417  }
418  return a_perm->second.get();
419 
420  }
421  }
422 
423  private:
424 
425  inline key_tuple
426  make_permuted_key_tuple(const key_tuple& orig) {
427  return make_permuted_key_tuple_recursive(
428  static_cast<typename key_tuple::inherited>(orig),
429  orig, boost::mpl::int_<0>()
430  );
431  }
432 
433  template<typename I, typename H, typename T>
434  inline typename boost::enable_if_c<
435  I::value == idx1,
436  boost::tuples::cons<H, T>
437  >::type
438  make_permuted_key_tuple_recursive(
439  const boost::tuples::cons<H, T>& kpart,
440  const key_tuple& orig, I not_used
441  )
442  {
443  return boost::tuples::cons<H, T>(
444  boost::tuples::get<idx2>(orig),
445  make_permuted_key_tuple_recursive(
446  kpart.get_tail(), orig,
447  typename boost::mpl::plus<I, boost::mpl::int_<1>>::type()
448  )
449  );
450  }
451 
452  template<typename I, typename H, typename T>
453  inline typename boost::enable_if_c<
454  I::value == idx2,
455  boost::tuples::cons<H, T>
456  >::type
457  make_permuted_key_tuple_recursive(
458  const boost::tuples::cons<H, T>& kpart,
459  const key_tuple& orig, I not_used
460  )
461  {
462  return boost::tuples::cons<H, T>(
463  boost::tuples::get<idx1>(orig),
464  make_permuted_key_tuple_recursive(
465  kpart.get_tail(), orig,
466  typename boost::mpl::plus<I, boost::mpl::int_<1>>::type()
467  )
468  );
469  }
470 
471  template<typename I, typename H, typename T>
472  inline typename boost::disable_if_c<
473  I::value == idx1 or I::value == idx2,
474  boost::tuples::cons<H, T>
475  >::type
476  make_permuted_key_tuple_recursive(
477  const boost::tuples::cons<H, T>& kpart,
478  const key_tuple& orig, I not_used
479  )
480  {
481  return boost::tuples::cons<H, T>(
482  kpart.get_head(),
483  make_permuted_key_tuple_recursive(
484  kpart.get_tail(), orig,
485  typename boost::mpl::plus<I, boost::mpl::int_<1>>::type()
486  )
487  );
488  }
489 
490  template<typename I>
491  inline const boost::tuples::null_type&
492  make_permuted_key_tuple_recursive(
493  const boost::tuples::null_type& nt,
494  const key_tuple& orig, I not_used
495  )
496  {
497  return nt;
498  }
499 
500 };
501 
502 
503 } // end namespace sc
504 #endif /* _util_container_conc_cache_h */
sc::KeyTransposition
Definition: conc_cache.h:132
sc::KeyPermutation
Definition: conc_cache.h:127
sc::ConcurrentCacheBase::value_type
ValueType value_type
types for map of values
Definition: conc_cache.h:197
sc::ConcurrentCacheBase::future_map_accessor
future_map::accessor future_map_accessor
The accessor type used by the madness ConcurrentHashMap.
Definition: conc_cache.h:203
sc::ConcurrentCacheBase::key_tuple
tuple_type< key_types... > key_tuple
The type used as a key into the map.
Definition: conc_cache.h:191
sc::ConcurrentCacheBase
Definition: conc_cache.h:182
sc::meta::splat_values
Definition: meta.h:84
sc::ConcurrentCacheWithSymmetry
A cache of objects that can be safely accessed concurrently by threads that share memory.
Definition: conc_cache.h:274
sc::KeySymmetry
Definition: conc_cache.h:173
sc::IdentityKeyPermutation
Definition: conc_cache.h:162
sc::ConcurrentCacheBase::future_map_const_accessor
future_map::const_accessor future_map_const_accessor
The const accessor used by the madness ConcurrentHashMap.
Definition: conc_cache.h:205
sc::ConcurrentCacheBase::future_value
boost::shared_future< value_type > future_value
A future of a value, used to prevent recomputation.
Definition: conc_cache.h:199
sc::ConcurrentCacheBase::future_map
madness::ConcurrentHashMap< key_tuple, future_value, _hash< key_tuple > > future_map
A map from keys to futures.
Definition: conc_cache.h:201
sc
Contains all MPQC code up to version 3.
Definition: mpqcin.h:14
sc::ConcurrentCacheBase::tuple_type
boost::tuple< Types... > tuple_type
types for keys
Definition: conc_cache.h:189
Generated at Sun Jan 26 2020 23:24:01 for MPQC 3.0.0-alpha using the documentation package Doxygen 1.8.16.