ConcurrentCache.hpp 8.23 KB
Newer Older
1
2
3
#pragma once

#include <mutex>
4
#include <shared_mutex>
5
6
7
8
#include <thread>
#include <tuple>
#include <unordered_map>

9
10
#include <dune/common/hash.hh>
#include <dune/common/std/type_traits.hh>
11
12
13

namespace AMDiS
{
14
15
16
17
  /// Store cache in instance.
  template <class Container>
  struct ConsecutivePolicy;

18
19
20
21
22
23
  /// Store cache thread local, requires no locking.
  template <class Container>
  struct ThreadLocalPolicy;

  /// Stores cache global static, requires locking on write access.
  template <class Container>
24
  struct StaticLockedPolicy;
25
26
27
28
29
30
31
32
33
34
35


  /// \brief The class template ConcurrentCache describes an associative static container that allows the
  /// concurrent access to the stored data.
  /**
   * Cache data of arbitray type that needs initialization on the first access. The data is thereby
   * initialized thread-wise or globally only once, and guarantees that you always get initialized data.
   *
   * \tparam Key        The type of key to access the data.
   * \tparam Data       The type of the data stored in the cache. The behaviur is undefined if Data is not
   *                    the same type as Container::mapped_type.
36
37
38
39
   * \tparam Policy     A policy class template implementing the method `get_or_init()`. Three implementations
   *                    are provided: \ref ConsecutivePolicy, \ref ThreadLocalPolicy and \ref StaticLockedPolicy.
   *                    By default, if no policy class template is specified, the `ThreadLocalPolicy` is used.
   *                    \see ConcurrentCachePolicy
40
41
42
43
44
45
46
47
48
   * \tparam Container  The type of the underlying associative container to use to store the data. The
   *                    container must satisfy the requirements of AssociativeContainer. The standard
   *                    containers `std::map` and `std::unordered_map` satisfie this requirement. By default,
   *                    if not container class is specified, the standard container `std::unordered_map<Key,Data>`
   *                    is used. Note, an unordered_map requires the key to be hashable.
   *
   * The `Policy` class template is a template parametrizable with the container type, that provides a static `get_or_init()`
   * method that is called with the key, and a functor for creation of new data elements.
   **/
49
50
  template <class Key,
            class Data,
51
52
53
54
55
56
57
58
59
60
61
            template <class> class Policy = ThreadLocalPolicy,
            class Container = std::unordered_map<Key, Data>>
  class ConcurrentCache;


#ifdef DOXYGEN
  /// \brief The class template ConcurrentCachePolicy describes a concrete policies for the use in \ref ConcurrentCache.
  /**
   * Provide a static cache and a `get_or_init()` static method that extracts the data from the cache if it exists or
   * creates a new extry by using an initialization functor.
   *
62
   * Realizations of this template are \ref ConsecutivePolicy, \ref ThreadLocalPolicy and \ref StaticLockedPolicy.
63
64
65
66
67
68
69
   *
   * \tparam Container  The Type of the associative container key->data to store the cached data.
   **/
  template <class Container>
  class ConcurrentCachePolicy;
#endif

70
71
72
73
74
75
76
77
78
79
80
  // implementation of the consecutive policy. Data is stored in instance variable.
  template <class Container>
  struct ConsecutivePolicy
  {
    using key_type = typename Container::key_type;
    using data_type = typename Container::mapped_type;
    using container_type = Container;

    template <class F, class... Args>
    data_type const& get_or_init(key_type const& key, F&& f, Args&&... args) const
    {
Praetorius, Simon's avatar
Praetorius, Simon committed
81
      return impl(std::is_default_constructible<data_type>{}, key, FWD(f), FWD(args)...);
82
83
84
85
86
87
88
89
90
91
    }

  private:
    // data_type is default_constructible
    template <class F, class... Args>
    data_type const& impl(std::true_type, key_type const& key, F&& f, Args&&... args) const
    {
      data_type empty;
      auto it = cachedData_.emplace(key, std::move(empty));
      if (it.second) {
Praetorius, Simon's avatar
Praetorius, Simon committed
92
        data_type data = f(key, FWD(args)...);
93
94
95
96
97
98
99
100
101
102
103
104
105
        it.first->second = std::move(data);
      }
      return it.first->second;
    }

    // data_type is not default_constructible
    template <class F, class... Args>
    data_type const& impl(std::false_type, key_type const& key, F&& f, Args&&... args) const
    {
      auto it = cachedData_.find(key);
      if (it != cachedData_.end())
        return it->second;
      else {
Praetorius, Simon's avatar
Praetorius, Simon committed
106
        data_type data = f(key, FWD(args)...);
107
108
109
110
111
112
113
114
115
116
        auto it = cachedData_.emplace(key, std::move(data));
        return it.first->second;
      }
    }

    mutable container_type cachedData_;
  };


  // implementation of the ThreadLocal policy. Data is stored in thread_local variable.
117
118
  template <class Container>
  struct ThreadLocalPolicy
119
  {
120
121
122
    using key_type = typename Container::key_type;
    using data_type = typename Container::mapped_type;
    using container_type = Container;
123

124
125
    template <class F, class... Args>
    static data_type const& get_or_init(key_type const& key, F&& f, Args&&... args)
126
    {
127
      return impl(std::is_default_constructible<data_type>{}, key, FWD(f), FWD(args)...);
128
129
130
131
132
133
    }

  private:
    // data_type is default_constructible
    template <class F, class... Args>
    static data_type const& impl(std::true_type, key_type const& key, F&& f, Args&&... args)
134
    {
135
136
137
      // Container to store the cached values
      thread_local container_type cached_data;

138
139
140
      data_type empty;
      auto it = cached_data.emplace(key, std::move(empty));
      if (it.second) {
141
        data_type data = f(key, FWD(args)...);
142
143
        it.first->second = std::move(data);
      }
144
      return it.first->second;
145
    }
146
147
148
149
150
151
152
153
154
155
156
157

    // data_type is not default_constructible
    template <class F, class... Args>
    static data_type const& impl(std::false_type, key_type const& key, F&& f, Args&&... args)
    {
      // Container to store the cached values
      thread_local container_type cached_data;

      auto it = cached_data.find(key);
      if (it != cached_data.end())
        return it->second;
      else {
158
        data_type data = f(key, FWD(args)...);
159
160
161
162
        auto it = cached_data.emplace(key, std::move(data));
        return it.first->second;
      }
    }
163
  };
164
165


166
  // implementation of the Shared policy. Data is stored in static variable.
167
  template <class Container>
168
  struct StaticLockedPolicy
169
170
171
172
  {
    using key_type = typename Container::key_type;
    using data_type = typename Container::mapped_type;
    using container_type = Container;
173

174
175
    template <class F, class... Args>
    static data_type const& get_or_init(key_type const& key, F&& f, Args&&... args)
176
    {
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
      // Container to store the cached values
      static container_type cached_data;

      // mutex used to access the data in the container, necessary since
      // access emplace is read-write.
      using mutex_type = std::shared_timed_mutex;
      static mutex_type access_mutex;

      // first try to lock for read-only, if an element for key is found, return it,
      // if not, obtain a unique_lock to insert a new element and initialize it.
      std::shared_lock<mutex_type> read_lock(access_mutex);
      auto it = cached_data.find(key);
      if (it != cached_data.end())
        return it->second;
      else {
        read_lock.unlock();
193
        data_type data = f(key, FWD(args)...);
194
195
196
197
        std::unique_lock<mutex_type> write_lock(access_mutex);
        auto new_it = cached_data.emplace(key, std::move(data));
        return new_it.first->second;
      }
198
    }
199
  };
200
201


202
203
  template <class Key, class Data, template <class> class Policy, class Container>
  class ConcurrentCache
204
      : protected Policy<Container>
205
206
207
  {
    using key_type = Key;
    using data_type = Data;
208

209
  public:
210

211
212
213
214
215
216
217
218
219
    /// \brief Return the data associated to the `key`.
    /**
     * Return the data associated to key. If no data is found, create a new entry in the container
     * with a value obtained from the functor, by calling `f(key, args...)`.
     *
     * \param f        A functor of signature data_type(key_type, Args...)
     * \param args...  Arguments passed additionally to the functor f
     **/
    template <class F, class... Args>
220
    data_type const& get(key_type const& key, F&& f, Args&&... args) const
221
    {
222
223
      static_assert(Dune::Std::is_callable<F(key_type, Args...), data_type>::value,
        "Functor F must have the signature data_type(key_type, Args...)");
224

225
      return ConcurrentCache::get_or_init(key, FWD(f), FWD(args)...);
226
    }
227
228
229
  };

} // end namespace AMDiS