OILS / vendor / souffle / datastructure / ConcurrentCache.h View on Github | oilshell.org

83 lines, 33 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2021, The Souffle Developers. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8#pragma once
9
10#include "ConcurrentInsertOnlyHashMap.h"
11#include "souffle/utility/ParallelUtil.h"
12
13namespace souffle {
14/**
15 * A simple implementation of a cache that can be used during interation and compilation
16 * to store frequently used values or values that are expensive to compute (e.g., regex).
17 */
18template <class Key, class Value, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>,
19 class KeyFactory = details::Factory<Key>>
20struct ConcurrentCache {
21#ifdef _OPENMP
22 using CacheImpl = ConcurrentInsertOnlyHashMap<ConcurrentLanes, Key, Value, Hash, KeyEqual, KeyFactory>;
23#else
24 using CacheImpl = ConcurrentInsertOnlyHashMap<SeqConcurrentLanes, Key, Value, Hash, KeyEqual, KeyFactory>;
25#endif
26
27 ConcurrentCache(const std::size_t LaneCount = 1) : lanes(LaneCount), cache(LaneCount, 8) {}
28 ~ConcurrentCache() = default;
29
30 void setNumLanes(const std::size_t NumLanes) {
31 lanes.setNumLanes(NumLanes);
32 cache.setNumLanes(NumLanes);
33 }
34
35 /**
36 * @brief Lookup the specified key in the cache.
37 *
38 * If the key is in the cache, then the associated value is returned. Otherwise,
39 * if the key, is not in the cache, the supplied function is invoked to construct
40 * the value from the key.
41 *
42 * The cache is not modified if the constructor function throws an exception.
43 * @param key the key for caching
44 * @param constructor a functor that takes a key and produces a value
45 * @return the cached value that is associated with the key
46 */
47 template <class CTOR>
48 const Value& getOrCreate(const Key& key, const CTOR& constructor) {
49 typename CacheImpl::lane_id lane = lanes.threadLane();
50 auto entry = cache.weakFind(lane, key);
51 if (entry == nullptr) {
52 auto node = cache.node(constructor(key));
53 auto result = cache.get(lane, node, key);
54 if (!result.second) {
55 // we need to delete the temporary node, since someone else
56 // already created the same node concurrently
57 delete node;
58 }
59 entry = result.first;
60 }
61 return entry->second;
62 }
63
64 /**
65 * @brief Lookup the value associated with the specified key.
66 *
67 * If the key does not exist, constructs a value using
68 * the key.
69 *
70 * This function forwards to getOrCreate
71 * @param key the key to lookup
72 * @return the cached value that is associated with the key
73 */
74 inline const Value& getOrCreate(const Key& key) {
75 return getOrCreate(key, [](auto p) { return Value(p); });
76 }
77
78 ConcurrentLanes lanes;
79
80 CacheImpl cache;
81};
82
83} // namespace souffle