ProvSQL C/C++ API
Adding support for provenance and uncertainty management to PostgreSQL databases
Loading...
Searching...
No Matches
ProbCache.h
Go to the documentation of this file.
1/**
2 * @file ProbCache.h
3 * @brief Cache of compiled d-DNNFs, and folding of independent parts.
4 *
5 * Two ways of not compiling the d-DNNF of a whole circuit, used by the
6 * tree-decomposition and compilation probability methods:
7 *
8 * - the *cache* keeps, for the session, the d-DNNFs compiled so far,
9 * under the canonical form of the circuit they were compiled for
10 * (@c CircuitCanonicalForm.h). A circuit is looked up island by
11 * island, then for its residual, so that a shape repeated inside a
12 * circuit or across circuits is compiled once; a hit evaluates the
13 * stored d-DNNF with the probabilities of the circuit at hand;
14 * - the *fold* groups the children of an AND or OR root by the inputs
15 * they share. Groups are independent, so their probabilities are
16 * multiplied (for an OR, through the complements); a group of one
17 * child is folded in turn and a larger one is handed to the method.
18 *
19 * Whether each applies is decided by the caller, from
20 * @c provsql.prob_cache and @c provsql.idp_fold.
21 */
22#ifndef PROB_CACHE_H
23#define PROB_CACHE_H
24
25#include <cstdint>
26#include <functional>
27#include <list>
28#include <string>
29#include <unordered_map>
30#include <vector>
31
33#include "dDNNF.h"
34
35namespace provsql {
36
37/// Counters of the cache since it was last emptied.
39 uint64_t hits = 0; ///< Lookups served from an entry
40 uint64_t misses = 0; ///< Lookups that found no usable entry
41 uint64_t inserts = 0; ///< Entries stored
42 uint64_t evictions = 0; ///< Entries dropped to stay under the size limit
43 uint64_t rejections = 0; ///< d-DNNFs too large to be stored
44 size_t entries = 0; ///< Entries held now
45 size_t bytes = 0; ///< Estimated size of the entries held now
46 size_t budget = 0; ///< Size the entries may reach before some are dropped
47};
48
49/**
50 * @brief The cache of compiled d-DNNFs of one backend.
51 *
52 * Entries are dropped least recently used first once their estimated
53 * total size passes the budget, and a d-DNNF larger than a quarter of
54 * the budget is not stored. The budget is @c provsql.prob_cache_size,
55 * lowered to a quarter of @c provsql.max_memory when that is smaller.
56 */
57class ProbCache {
58public:
59/// A compiled d-DNNF and how its inputs match the leaves of its form.
60struct Entry {
61 std::string form; ///< Canonical form the d-DNNF was compiled for
62 /// Method that compiled @c dd ("tree-decomposition", "compilation:d4"...).
63 std::string builder;
64 dDNNF dd; ///< The d-DNNF
65 std::vector<gate_t> leaf_gate; ///< Input of @c dd for each leaf of the form
66 std::vector<char> leaf_present; ///< Whether that leaf occurs in @c dd at all
67 size_t bytes = 0; ///< Estimated size of the entry
68};
69
70/// The cache of this backend.
71static ProbCache &instance();
72
73/// Looks @p key up. A non-empty @p builder restricts the hit to an entry
74/// compiled by that method; an entry of another builder counts as a miss.
75const Entry *find(const CanonicalForm &key,
76 const std::string &builder = std::string());
77
78/// Whether an entry of @p bytes is small enough to be stored; counts a
79/// rejection otherwise.
80bool admits(size_t bytes);
81
82/// Stores @p entry under @p key, replacing an entry already there.
83bool insert(const CanonicalForm &key, Entry entry);
84
85/// Drops the least recently used entries until the cache fits its budget
86/// (which the setting may have lowered since the last insertion).
87void trim();
88
89/// Empties the cache and its counters.
90void reset();
91
92/// The counters, with the current number and size of entries.
93ProbCacheStats stats() const;
94
95private:
96ProbCache() = default;
97
98std::list<Entry> lru_;
99std::unordered_map<std::string, std::list<Entry>::iterator> map_;
100size_t bytes_ = 0;
102};
103
104/// Compiles the circuit below a gate into a d-DNNF.
106 std::function<dDNNF(const BooleanCircuit &, gate_t)>;
107
108/// What a call to probCachedProbability actually did, so the caller can
109/// report it instead of the method it was asked for.
111 bool folded = false; ///< root split into independent groups
112 std::vector<std::string> built; ///< builders run on a miss
113 std::vector<std::string> cached; ///< builders of the entries served
114
115 /// Comma-separated label: "fold" if folded, the builders that ran, then
116 /// "cache:<builder>" for each builder whose entry was served.
117 std::string describe() const;
118};
119
120/// What probCachedProbability may do, and what it reports back.
122 bool use_cache = true; ///< Look compiled d-DNNFs up, and store new ones
123 bool fold = false; ///< Fold the independent groups of the root first
124 /// Non-empty: only an entry compiled by this builder is a hit (a call
125 /// naming its method must not be answered from another method's entry).
126 std::string required_builder;
127 /// Names the builder of the d-DNNF the compile callback last returned.
128 std::function<std::string()> last_builder;
130};
131
132/// How probFoldedProbability evaluates what it cannot fold.
134 /// Probability of a part, given as a circuit of its own and its root;
135 /// the flag tells a group of several children sharing inputs from a
136 /// single subcircuit.
137 std::function<double(BooleanCircuit &, gate_t, bool)> part;
138 /// Probability of the whole circuit, when its root has nothing to fold.
139 std::function<double()> whole;
140};
141
142/// Whether the circuit below @p root is one the cache and the fold handle:
143/// AND, OR and NOT gates over inputs that carry a UUID.
144bool probCacheEligible(const BooleanCircuit &c, gate_t root);
145
146/// Probability of the circuit below @p root, folding the independent
147/// groups of AND and OR gates from the root down and leaving the rest to
148/// @p eval.
149double probFoldedProbability(const BooleanCircuit &c, gate_t root,
150 const ProbFoldEval &eval);
151
152/**
153 * @brief Probability of the circuit below @p root through the fold and
154 * the cache.
155 * @param c The circuit.
156 * @param root Its root.
157 * @param compile Compiles what is neither folded nor served.
158 * @param ran_compiler If not null, set to whether @p compile was called.
159 * @param options What to use, and where to report what was done.
160 */
161double probCachedProbability(const BooleanCircuit &c, gate_t root,
162 const ProbCacheCompileFn &compile,
163 bool *ran_compiler = nullptr,
164 const ProbCacheOptions &options = ProbCacheOptions());
165
166}
167
168#endif
Canonical form of a Boolean circuit, and its split into islands.
gate_t
Strongly-typed gate identifier.
Definition Circuit.h:53
Boolean circuit for provenance formula evaluation.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
Definition dDNNF.h:71
std::unordered_map< std::string, std::list< Entry >::iterator > map_
Definition ProbCache.h:99
void trim()
Drops the least recently used entries until the cache fits its budget (which the setting may have low...
static ProbCache & instance()
The cache of this backend.
bool insert(const CanonicalForm &key, Entry entry)
Stores entry under key, replacing an entry already there.
std::list< Entry > lru_
Definition ProbCache.h:98
const Entry * find(const CanonicalForm &key, const std::string &builder=std::string())
Looks key up.
void reset()
Empties the cache and its counters.
ProbCacheStats stats() const
The counters, with the current number and size of entries.
ProbCacheStats stats_
Definition ProbCache.h:101
bool admits(size_t bytes)
Whether an entry of bytes is small enough to be stored; counts a rejection otherwise.
Decomposable Deterministic Negation Normal Form circuit.
double probFoldedProbability(const BooleanCircuit &c, gate_t root, const ProbFoldEval &eval)
Probability of the circuit below root, folding the independent groups of AND and OR gates from the ro...
std::function< dDNNF(const BooleanCircuit &, gate_t)> ProbCacheCompileFn
Compiles the circuit below a gate into a d-DNNF.
Definition ProbCache.h:105
double probCachedProbability(const BooleanCircuit &c, gate_t root, const ProbCacheCompileFn &compile, bool *ran_compiler, const ProbCacheOptions &options)
Probability of the circuit below root through the fold and the cache.
bool probCacheEligible(const BooleanCircuit &c, gate_t root)
Whether the circuit below root is one the cache and the fold handle: AND, OR and NOT gates over input...
Canonical form of a circuit below a root.
What probCachedProbability may do, and what it reports back.
Definition ProbCache.h:121
std::string required_builder
Non-empty: only an entry compiled by this builder is a hit (a call naming its method must not be answ...
Definition ProbCache.h:126
bool fold
Fold the independent groups of the root first.
Definition ProbCache.h:123
ProbCacheReport * report
Definition ProbCache.h:129
bool use_cache
Look compiled d-DNNFs up, and store new ones.
Definition ProbCache.h:122
std::function< std::string()> last_builder
Names the builder of the d-DNNF the compile callback last returned.
Definition ProbCache.h:128
What a call to probCachedProbability actually did, so the caller can report it instead of the method ...
Definition ProbCache.h:110
bool folded
root split into independent groups
Definition ProbCache.h:111
std::vector< std::string > built
builders run on a miss
Definition ProbCache.h:112
std::string describe() const
Comma-separated label: "fold" if folded, the builders that ran, then "cache:<builder>" for each build...
std::vector< std::string > cached
builders of the entries served
Definition ProbCache.h:113
Counters of the cache since it was last emptied.
Definition ProbCache.h:38
uint64_t evictions
Entries dropped to stay under the size limit.
Definition ProbCache.h:42
uint64_t inserts
Entries stored.
Definition ProbCache.h:41
uint64_t hits
Lookups served from an entry.
Definition ProbCache.h:39
size_t bytes
Estimated size of the entries held now.
Definition ProbCache.h:45
uint64_t misses
Lookups that found no usable entry.
Definition ProbCache.h:40
size_t budget
Size the entries may reach before some are dropped.
Definition ProbCache.h:46
size_t entries
Entries held now.
Definition ProbCache.h:44
uint64_t rejections
d-DNNFs too large to be stored
Definition ProbCache.h:43
A compiled d-DNNF and how its inputs match the leaves of its form.
Definition ProbCache.h:60
size_t bytes
Estimated size of the entry.
Definition ProbCache.h:67
std::string form
Canonical form the d-DNNF was compiled for.
Definition ProbCache.h:61
std::string builder
Method that compiled dd ("tree-decomposition", "compilation:d4"...).
Definition ProbCache.h:63
std::vector< gate_t > leaf_gate
Input of dd for each leaf of the form.
Definition ProbCache.h:65
std::vector< char > leaf_present
Whether that leaf occurs in dd at all.
Definition ProbCache.h:66
dDNNF dd
The d-DNNF.
Definition ProbCache.h:64
How probFoldedProbability evaluates what it cannot fold.
Definition ProbCache.h:133
std::function< double()> whole
Probability of the whole circuit, when its root has nothing to fold.
Definition ProbCache.h:139
std::function< double(BooleanCircuit &, gate_t, bool)> part
Probability of a part, given as a circuit of its own and its root; the flag tells a group of several ...
Definition ProbCache.h:137