C++Memo  1.0-RC
Generic framework for memoization, providing automatic parallelization.
 All Classes Files Functions
cppmemo.hpp
Go to the documentation of this file.
1 
55 #ifndef CPPMEMO_H_
56 #define CPPMEMO_H_
57 
58 // The noexcept specifier is unsupported in Visual Studio
59 #ifndef _MSC_VER
60 #define CPPMEMO_NOEXCEPT noexcept
61 #else
62 #define CPPMEMO_NOEXCEPT
63 #endif
64 
65 #include <vector> // std::vector
66 #include <unordered_set> // std::unordered_set
67 #include <random> // std::minstd_rand
68 #include <thread> // std::thread
69 #include <algorithm> // std::shuffle
70 #include <cstddef> // std::nullptr_t
71 #include <stdexcept> // std::logic_error, std::runtime_error
72 
73 #include <fcmm/fcmm.hpp>
74 
75 namespace cppmemo {
76 
85 template<typename Key>
86 class CircularDependencyException : public std::exception {
87 
88  template<typename K, typename V, typename KH1, typename KH2, typename KE>
89  friend class CppMemo;
90 
91 private:
92 
93  std::vector<Key> keysStack;
94 
95  CircularDependencyException(const std::vector<Key>& keysStack) : keysStack(keysStack) {
96  }
97 
98 public:
99 
103  const char* what() const CPPMEMO_NOEXCEPT {
104  return "Circular dependency detected.";
105  }
106 
112  const std::vector<Key>& getKeysStack() const {
113  return keysStack;
114  }
115 
116 };
117 
137 template<
138  typename Key,
139  typename Value,
140  typename KeyHash1 = std::hash<Key>,
141  typename KeyHash2 = fcmm::DefaultKeyHash2<Key>,
142  typename KeyEqual = std::equal_to<Key>
143 >
144 class CppMemo {
145 
146 private:
147 
148  typedef fcmm::Fcmm<Key, Value, KeyHash1, KeyHash2, KeyEqual> Values;
149 
150  int defaultNumThreads;
151  Values values;
152  bool detectCircularDependencies;
153 
154  class ThreadItemsStack {
155 
156  public:
157 
158  struct Item {
159  Key key;
160  bool ready;
161  };
162 
163  private:
164 
165  int threadNo;
166  std::minstd_rand randGen;
167  std::size_t groupSize;
168  bool detectCircularDependencies;
169 
170  std::vector<Item> items;
171  std::unordered_set<Key, KeyHash1, KeyEqual> itemsSet;
172 
173  std::vector<Key> getKeysStack() const {
174  std::vector<Key> result;
175  result.reserve(items.size());
176  for (const Item& item : items) {
177  result.push_back(item.key);
178  }
179  return result;
180  }
181 
182  public:
183 
184  ThreadItemsStack(int threadNo, bool detectCircularDependencies) :
185  threadNo(threadNo), randGen(threadNo), groupSize(0),
186  detectCircularDependencies(detectCircularDependencies) {
187  }
188 
189  void push(const Key& key) {
190  items.push_back({ key, false });
191  if (detectCircularDependencies) {
192  if (itemsSet.find(key) != itemsSet.end()) {
193  throw CircularDependencyException<Key>(getKeysStack());
194  }
195  }
196  groupSize++;
197  }
198 
199  void pop() {
200  if (groupSize != 0) {
201  throw std::runtime_error("The current group is not finalized.");
202  }
203  if (detectCircularDependencies) {
204  const Item& item = items.back();
205  itemsSet.erase(item.key);
206  }
207  items.pop_back();
208  }
209 
210  void finalizeGroup() {
211  if (threadNo != 0 && groupSize > 1) {
212  if (threadNo == 1) {
213  // reverse the added prerequisites of improving parallel speedup
214  std::reverse(items.end() - groupSize, items.end());
215  } else {
216  // shuffle the added prerequisites of improving parallel speedup
217  std::shuffle(items.end() - groupSize, items.end(), randGen);
218  }
219  }
220  if (detectCircularDependencies) {
221  for (std::size_t i = 1; i <= groupSize; i++) {
222  const Item& addedItem = *(items.end() - i);
223  itemsSet.insert(addedItem.key);
224  }
225  }
226  groupSize = 0;
227  }
228 
229  bool empty() const {
230  return items.empty();
231  }
232 
233  const Item& back() const {
234  return items.back();
235  }
236 
237  Item& back() {
238  return items.back();
239  }
240 
241  std::size_t getGroupSize() const {
242  return groupSize;
243  }
244 
245  };
246 
247 public:
248 
254 
255  friend class CppMemo<Key, Value, KeyHash1, KeyHash2, KeyEqual>;
256 
257  private:
258 
259  enum Mode { NORMAL, DRY_RUN };
260 
261  const Values& values;
262  ThreadItemsStack& stack;
263  Mode mode;
264  Value dummyValue;
265 
266  PrerequisitesProvider(const Values& values, ThreadItemsStack& stack) :
267  values(values), stack(stack), mode(NORMAL), dummyValue() {
268  }
269 
270  void setMode(Mode mode) {
271  this->mode = mode;
272  }
273 
274  public:
275 
292  const Value& operator()(const Key& key) {
293  if (mode == NORMAL) {
294  return values[key];
295  } else { // dry running
296  const auto findIt = values.find(key);
297  if (findIt == values.end()) {
298  stack.push(key);
299  return dummyValue; // return an invalid value
300  } else {
301  return findIt->second; // return a valid value
302  }
303  }
304  }
305 
306  };
307 
313 
314  friend class CppMemo<Key, Value, KeyHash1, KeyHash2, KeyEqual>;
315 
316  private:
317 
318  const Values& values;
319  ThreadItemsStack& stack;
320 
321  PrerequisitesGatherer(const Values& values, ThreadItemsStack& stack) : values(values), stack(stack) {
322  }
323 
324  public:
325 
331  void operator()(const Key& key) {
332  if (values.find(key) == values.end()) {
333  stack.push(key);
334  }
335  }
336 
337  };
338 
339 private:
340 
341  template<typename Compute, typename DeclarePrerequisites>
342  void run(int threadNo, const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites,
343  bool providedDeclarePrerequisites) {
344 
345  ThreadItemsStack stack(threadNo, detectCircularDependencies);
346 
347  stack.push(key);
348  stack.finalizeGroup();
349 
350  PrerequisitesProvider prerequisitesProvider(values, stack);
351  PrerequisitesGatherer prerequisitesDeclarer(values, stack);
352 
353  while (!stack.empty()) {
354 
355  typename ThreadItemsStack::Item& item = stack.back();
356 
357  if (item.ready) {
358 
359  prerequisitesProvider.setMode(PrerequisitesProvider::NORMAL);
360  values.insert(item.key, [&](const Key& key) -> Value {
361  return compute(key, prerequisitesProvider);
362  });
363 
364  stack.pop();
365 
366  } else {
367 
368  item.ready = true;
369 
370  const Key itemKey = item.key; // copy item key
371 
372  if (values.find(itemKey) == values.end()) {
373 
374  if (providedDeclarePrerequisites) {
375 
376  // execute the declarePrerequisites function to get prerequisites
377 
378  declarePrerequisites(itemKey, prerequisitesDeclarer);
379 
380  } else {
381 
382  // dry-run the compute function to capture prerequisites
383 
384  prerequisitesProvider.setMode(PrerequisitesProvider::DRY_RUN);
385  const Value itemValue = compute(itemKey, prerequisitesProvider);
386 
387  if (stack.getGroupSize() == 0) { // the computed value is valid
388  values.emplace(itemKey, itemValue);
389  stack.pop();
390  }
391 
392  }
393 
394  stack.finalizeGroup();
395 
396  }
397 
398  }
399 
400  }
401 
402  }
403 
404  // This method serves as a workaround for a Visual Studio bug
405  template<typename Compute, typename DeclarePrerequisites>
406  static void runWrapper(CppMemo<Key, Value, KeyHash1, KeyHash2, KeyEqual>& instance, int threadNo, const Key& key, Compute compute,
407  DeclarePrerequisites declarePrerequisites, bool providedDeclarePrerequisites) {
408  instance.run(threadNo, key, compute, declarePrerequisites, providedDeclarePrerequisites);
409  }
410 
411  template<typename Compute, typename DeclarePrerequisites>
412  const Value& getValue(const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites, int numThreads,
413  bool providedDeclarePrerequisites) {
414 
415  const auto findIt = values.find(key);
416  if (findIt != values.end()) {
417  return findIt->second;
418  }
419 
420  if (numThreads > 1) { // multi-thread execution
421 
422  std::vector<std::thread> threads;
423  threads.reserve(numThreads);
424 
425  for (int threadNo = 0; threadNo < numThreads; threadNo++) {
426 
427  std::thread thread(&CppMemo<Key, Value, KeyHash1, KeyHash2, KeyEqual>::runWrapper<Compute, DeclarePrerequisites>,
428  std::ref(*this), threadNo, std::cref(key), compute, declarePrerequisites, providedDeclarePrerequisites);
429 
430  threads.push_back(std::move(thread));
431 
432  }
433 
434  for (std::thread& thread : threads) {
435  thread.join();
436  }
437 
438  } else { // single thread execution
439 
440  run(0, key, compute, declarePrerequisites, providedDeclarePrerequisites);
441 
442  }
443 
444  return values[key];
445 
446  }
447 
448 public:
449 
458  CppMemo(int defaultNumThreads = 1, std::size_t estimatedNumEntries = 0, bool detectCircularDependencies = false) :
459  values(estimatedNumEntries),
460  detectCircularDependencies(detectCircularDependencies) {
461  setDefaultNumThreads(defaultNumThreads);
462  }
463 
467  int getDefaultNumThreads() const {
468  return defaultNumThreads;
469  }
470 
474  void setDefaultNumThreads(int defaultNumThreads) {
475  if (defaultNumThreads < 1) {
476  throw std::logic_error("The default number of threads must be >= 1");
477  }
478  this->defaultNumThreads = defaultNumThreads;
479  }
480 
485  return detectCircularDependencies;
486  }
487 
493  void setDetectCircularDependencies(bool detectCircularDependencies) {
494  this->detectCircularDependencies = detectCircularDependencies;
495  }
496 
510  template<typename Compute, typename DeclarePrerequisites>
511  const Value& getValue(const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites, int numThreads) {
512  return getValue(key, compute, declarePrerequisites, numThreads, true);
513  }
514 
529  template<typename Compute, typename DeclarePrerequisites>
530  const Value& getValue(const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites) {
531  return getValue(key, compute, declarePrerequisites, defaultNumThreads, true);
532  }
533 
550  template<typename Compute>
551  const Value& getValue(const Key& key, Compute compute, int numThreads) {
552  const auto dummyDeclarePrerequisites = [](const Key&, PrerequisitesGatherer&) {};
553  return getValue(key, compute, dummyDeclarePrerequisites, numThreads, false);
554  }
555 
573  template<typename Compute>
574  const Value& getValue(const Key& key, Compute compute) {
575  return getValue(key, compute, defaultNumThreads);
576  }
577 
588  const Value& getValue(const Key& key) const {
589  const auto findIt = values.find(key);
590  if (findIt != values.end()) {
591  return findIt->second;
592  } else {
593  throw std::logic_error("The value is not memoized");
594  }
595  }
596 
600  template<typename Compute, typename DeclarePrerequisites>
601  const Value& operator()(const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites, int numThreads) {
602  return getValue(key, compute, declarePrerequisites, numThreads);
603  }
604 
608  template<typename Compute, typename DeclarePrerequisites>
609  const Value& operator()(const Key& key, Compute compute, DeclarePrerequisites declarePrerequisites) {
610  return getValue(key, compute, declarePrerequisites);
611  }
612 
616  template<typename Compute>
617  const Value& operator()(const Key& key, Compute compute, int numThreads) {
618  return getValue(key, compute, numThreads);
619  }
620 
624  template<typename Compute>
625  const Value& operator()(const Key& key, Compute compute) {
626  return getValue(key, compute);
627  }
628 
632  const Value& operator()(const Key& key) const {
633  return getValue(key);
634  }
635 
636  // the class shall not be copied or moved (because of fcmm)
637  CppMemo(const CppMemo&) = delete;
638  CppMemo(CppMemo&&) = delete;
639 
640 };
641 
642 } // namespace cppmemo
643 
644 #undef CPPMEMO_NOEXCEPT
645 
646 #endif // CPPMEMO_H_
const Value & operator()(const Key &key, Compute compute, int numThreads)
Alias for getValue(const Key&, Compute, int)
Definition: cppmemo.hpp:617
This class implements a generic framework for memoization supporting automatic parallel execution...
Definition: cppmemo.hpp:144
void setDetectCircularDependencies(bool detectCircularDependencies)
Enables or disables circular dependency detection.
Definition: cppmemo.hpp:493
const Value & getValue(const Key &key, Compute compute, int numThreads)
Returns the value corresponding to the requested key, computing (and memoizing) it as needed...
Definition: cppmemo.hpp:551
bool getDetectCircularDependencies() const
Returns true if circular dependency detection is enabled, false otherwise.
Definition: cppmemo.hpp:484
Definition: cppmemo.hpp:158
const Value & getValue(const Key &key) const
Returns the memoized value corresponding to the requested key. If no value is memoized, a std::logic_error exception is thrown.
Definition: cppmemo.hpp:588
const Value & getValue(const Key &key, Compute compute)
Returns the value corresponding to the requested key, computing (and memoizing) it as needed...
Definition: cppmemo.hpp:574
This exception is thrown when a circular dependency among the keys is detected.
Definition: cppmemo.hpp:86
const Value & getValue(const Key &key, Compute compute, DeclarePrerequisites declarePrerequisites, int numThreads)
Returns the value corresponding to the requested key, computing (and memoizing) it as needed...
Definition: cppmemo.hpp:511
CppMemo(int defaultNumThreads=1, std::size_t estimatedNumEntries=0, bool detectCircularDependencies=false)
Constructor.
Definition: cppmemo.hpp:458
void operator()(const Key &key)
Gathers a prerequisite.
Definition: cppmemo.hpp:331
const Value & operator()(const Key &key, Compute compute, DeclarePrerequisites declarePrerequisites, int numThreads)
Alias for getValue(const Key&, Compute, DeclarePrerequisites, int)
Definition: cppmemo.hpp:601
The function object gathering prerequisites from the DeclarePrerequisites function passed to an appro...
Definition: cppmemo.hpp:312
const std::vector< Key > & getKeysStack() const
Returns the keys stack at the time the circular dependency was detected.
Definition: cppmemo.hpp:112
const Value & operator()(const Key &key, Compute compute, DeclarePrerequisites declarePrerequisites)
Alias for getValue(const Key&, Compute, DeclarePrerequisites)
Definition: cppmemo.hpp:609
const Value & getValue(const Key &key, Compute compute, DeclarePrerequisites declarePrerequisites)
Returns the value corresponding to the requested key, computing (and memoizing) it as needed...
Definition: cppmemo.hpp:530
The function object providing prerequisites to the Compute function passed to an appropriate CppMemo:...
Definition: cppmemo.hpp:253
const Value & operator()(const Key &key, Compute compute)
Alias for getValue(const Key&, Compute)
Definition: cppmemo.hpp:625
void setDefaultNumThreads(int defaultNumThreads)
Sets the default number of threads to be started.
Definition: cppmemo.hpp:474
const Value & operator()(const Key &key)
Provides the value corresponding to the given key.
Definition: cppmemo.hpp:292
const char * what() const CPPMEMO_NOEXCEPT
Returns a C string identifying the exception.
Definition: cppmemo.hpp:103
const Value & operator()(const Key &key) const
Alias for getValue(const Key&)
Definition: cppmemo.hpp:632
int getDefaultNumThreads() const
Returns the default number of threads to be started.
Definition: cppmemo.hpp:467