27 budget = std::min(budget,
36 return maxCacheBytes() / 4;
39constexpr unsigned MAX_FOLD_DEPTH = 64;
43 size_t wires = 0, uuid_bytes = 0;
46 uuid_bytes += dd.
getUUID(g).size();
49 return 2 * e.form.size()
53 + e.leaf_gate.size() * (
sizeof(
gate_t) + 1)
57std::string islandLeafUuid(
size_t i)
59 return "provsql:island:" + std::to_string(i);
63 const std::vector<double> &leaf_probs)
65 assert(leaf_probs.size() == e.leaf_gate.size());
67 for(
size_t i = 0; i < leaf_probs.size(); ++i)
69 dd.
setProb(e.leaf_gate[i], leaf_probs[i]);
73void noteOnce(std::vector<std::string> &names,
const std::string &name)
75 if(std::find(names.begin(), names.end(), name) == names.end())
76 names.push_back(name);
81 const std::string &builder,
82 const std::function<std::string(
const CanonicalLeaf &)> &leaf_uuid)
87 e.leaf_gate.assign(key.leaves.size(),
gate_t{0});
88 e.leaf_present.assign(key.leaves.size(), 0);
91 for(
size_t i = 0; i < key.leaves.size(); ++i) {
92 const std::string u = leaf_uuid(key.leaves[i]);
101 e.leaf_present[i] = 1;
106 std::vector<gate_t> stack{dd.
getRoot()};
108 while(!stack.empty()) {
114 if(seen.insert(ch).second)
119 e.bytes=estimateEntryBytes(dd, e);
120 if(!
cache.admits(e.bytes))
126gate_t materialiseComponent(
127 const BooleanCircuit &c,
gate_t root,
const GateSet *frontier,
128 const std::unordered_map<gate_t, size_t, hash_gate_t> &island_index,
129 const std::unordered_map<gate_t, double, hash_gate_t> &island_prob,
133 std::unordered_map<gate_t, gate_t, hash_gate_t> old2new;
134 old2new.reserve(nodes.size());
136 auto isAbstract =[&](
gate_t g) {
137 return g != root && frontier && frontier->count(g) != 0;
142 old2new[g] = out.
setGate(islandLeafUuid(island_index.at(g)),
153 out.
addWire(old2new.at(g), old2new.at(u));
155 return old2new.at(root);
167 const std::string &builder)
171 || (!builder.empty() && it->second->builder != builder)) {
182 if(bytes <= maxEntryBytes())
191 if(it !=
map_.end()) {
192 bytes_ -= it->second->bytes;
193 lru_.erase(it->second);
197 lru_.push_front(std::move(entry));
206 while(
bytes_ > maxCacheBytes() && !
lru_.empty()) {
227 s.
budget = maxCacheBytes();
255 const ProbCacheOptions &options, std::string &builder)
258 *ran_compiler =
true;
259 dDNNF dd = compile(c, root);
260 builder = options.last_builder ? options.last_builder() : std::string();
262 noteOnce(options.report->built, builder);
266double cachedComponent(
const BooleanCircuit &c,
gate_t root,
274 if(e && options.report)
275 noteOnce(options.report->cached, e->builder);
281 std::unordered_map<gate_t, size_t, hash_gate_t> island_index;
282 for(
size_t i = 0; i < key.island_roots.size(); ++i)
283 island_index[key.island_roots[i]] = i;
285 std::unordered_map<gate_t, double, hash_gate_t> island_prob;
286 for(
size_t i = 0; i < key.islands.size(); ++i) {
288 const gate_t g = key.island_roots[i];
290 if(
const auto *e = lookup(icf)) {
291 std::vector<double> probs;
292 probs.reserve(icf.leaves.size());
294 probs.push_back(c.
getProb(leaf.gate));
295 p = instantiateAndEvaluate(*e, probs);
297 BooleanCircuit island;
298 gate_t island_root = materialiseComponent(c, g,
nullptr, {}, {}, island);
299 dDNNF dd = compileNoted(island, island_root, compile, ran_compiler,
304 p = dd.probabilityEvaluation();
310 std::vector<double> probs;
311 probs.reserve(rcf.leaves.size());
313 probs.push_back(leaf.is_abstract ? island_prob.at(leaf.gate)
316 if(
const auto *e = lookup(rcf))
317 return instantiateAndEvaluate(*e, probs);
320 return leaf.is_abstract ? islandLeafUuid(island_index.at(leaf.gate))
321 : c.getUUID(leaf.gate);
324 if(key.island_roots.empty()) {
325 dDNNF dd = compileNoted(c, root, compile, ran_compiler, options, builder);
326 tryCacheCompiled(
cache, rcf, dd, builder, residualLeafUuid);
330 GateSet frontier(key.island_roots.begin(), key.island_roots.end());
332 gate_t res_root = materialiseComponent(c, root, &frontier, island_index,
334 dDNNF dd = compileNoted(res, res_root, compile, ran_compiler, options,
336 tryCacheCompiled(
cache, rcf, dd, builder, residualLeafUuid);
340double evaluateComponent(
const BooleanCircuit &c,
gate_t root,
344 if(options.use_cache)
345 return cachedComponent(c, root, compile, ran_compiler, options);
347 return compileNoted(c, root, compile, ran_compiler, options, builder)
348 .probabilityEvaluation();
351std::vector<std::vector<gate_t> > independentGroups(
352 const BooleanCircuit &c,
const std::vector<gate_t> &children)
354 std::vector<size_t> parent(children.size());
355 std::iota(parent.begin(), parent.end(),
size_t{0});
356 auto find = [&parent](
size_t x) {
357 while(parent[x] != x) {
358 parent[x] = parent[parent[x]];
364 std::unordered_map<gate_t, size_t, CanonicalGateHash> owner;
365 std::vector<gate_t> stack;
366 for(
size_t i = 0; i < children.size(); ++i) {
367 stack.push_back(children[i]);
368 while(!stack.empty()) {
369 const gate_t g = stack.back();
374 const auto entry = owner.emplace(g, i);
376 parent[find(i)] = find(entry.first->second);
379 stack.insert(stack.end(), wires.begin(), wires.end());
383 std::unordered_map<size_t, size_t> position;
384 std::vector<std::vector<gate_t> > groups;
385 for(
size_t i = 0; i < children.size(); ++i) {
386 const auto entry = position.emplace(find(i), groups.size());
388 groups.emplace_back();
389 groups[entry.first->second].push_back(children[i]);
395 const std::vector<gate_t> &children,
398 std::unordered_map<gate_t, gate_t, CanonicalGateHash> old2new;
399 std::vector<gate_t> nodes;
400 std::vector<gate_t> stack(children.begin(), children.end());
401 while(!stack.empty()) {
402 const gate_t g = stack.back();
404 if(!old2new.emplace(g,
gate_t{0}).second)
408 stack.insert(stack.end(), wires.begin(), wires.end());
410 std::sort(nodes.begin(), nodes.end());
419 out.
addWire(old2new.at(g), old2new.at(u));
422 for(
gate_t child : children)
423 out.
addWire(root, old2new.at(child));
427double foldedProbability(
const BooleanCircuit &c,
gate_t g,
434 if(depth < MAX_FOLD_DEPTH
436 std::vector<gate_t> children;
439 if(seen.insert(w).second)
440 children.push_back(w);
442 const auto groups = independentGroups(c, children);
443 if(groups.size() != 1 || groups.front().size() == 1) {
445 for(
const auto &group : groups) {
447 if(group.size() == 1) {
448 p = foldedProbability(c, group.front(), eval, depth + 1);
451 const gate_t part_root = materialiseGroup(c, type, group, part);
452 p = eval.part(part, part_root,
true);
464 const gate_t part_root = materialiseComponent(c, g,
nullptr, {}, {}, part);
465 return eval.part(part, part_root,
false);
473 return foldedProbability(c, root, eval, 0);
482 *ran_compiler =
false;
487 return evaluateComponent(part, part_root, compile, ran_compiler,
492 return evaluateComponent(c, root, compile, ran_compiler, options);
494 const double p = foldedProbability(c, root, eval, 0);
499 return evaluateComponent(c, root, compile, ran_compiler, options);
505 const auto add = [&label](
const std::string &name) {
512 for(
const std::string &b :
built)
515 for(
const std::string &b :
cached)
516 add(b.empty() ?
"cache" :
"cache:" + b);
BooleanGate
Gate types for a Boolean provenance circuit.
@ NOT
Logical negation of a single child gate.
@ OR
Logical disjunction of child gates.
@ AND
Logical conjunction of child gates.
@ IN
Input (variable) gate representing a base tuple.
static CircuitCache cache
Process-local singleton circuit gate cache.
gate_t
Strongly-typed gate identifier.
Cache of compiled d-DNNFs, and folding of independent parts.
Boolean circuit for provenance formula evaluation.
void setProb(gate_t g, double p)
Set the probability for gate g and mark the circuit as probabilistic.
gate_t setGate(BooleanGate type) override
Allocate a new gate with type type and no UUID.
double getProb(gate_t g) const
Return the probability stored for gate g.
bool insert(const CircuitCacheInfos &infos)
Insert a new gate into the cache, evicting the oldest if necessary.
std::vector< gate_t > & getWires(gate_t g)
Return a mutable reference to the child-wire list of gate g.
gateType getGateType(gate_t g) const
Return the type of gate g.
void addWire(gate_t f, gate_t t)
Add a directed wire from gate f (parent) to gate t (child).
uuid getUUID(gate_t g) const
Return the UUID string associated with gate g.
gate_t getGate(const uuid &u)
Return (or create) the gate associated with UUID u.
bool hasGate(const uuid &u) const
Test whether a gate with UUID u exists.
std::vector< gate_t >::size_type getNbGates() const
Return the total number of gates in the circuit.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
double probabilityEvaluation() const
Compute the exact probability of the d-DNNF being true.
gate_t getRoot() const
Return the root gate of this d-DNNF.
The cache of compiled d-DNNFs of one backend.
std::unordered_map< std::string, std::list< Entry >::iterator > map_
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.
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.
bool admits(size_t bytes)
Whether an entry of bytes is small enough to be stored; counts a rejection otherwise.
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.
GateSet reachableNodes(const BooleanCircuit &c, gate_t root, const GateSet *abstract_leaves)
Gates reachable from root.
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.
IslandKey computeIslandKey(const BooleanCircuit &c, gate_t root)
Splits the circuit below root into its outermost islands and the residual.
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...
std::unordered_set< gate_t, CanonicalGateHash > GateSet
Set of gates of one circuit.
int provsql_prob_cache_size
Byte budget, in kB, of the per-backend cache of compiled d-DNNFs; provsql.prob_cache_size GUC.
int provsql_max_memory
Memory, in MB, that the evaluations of a statement may add to the backend's resident set,...
Core types, constants, and utilities shared across ProvSQL.
A leaf of a canonical form, in the order the form meets it.
A circuit split into its outermost islands and what remains.
What probCachedProbability may do, and what it reports back.
bool fold
Fold the independent groups of the root first.
bool folded
root split into independent groups
std::vector< std::string > built
builders run on a miss
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
Counters of the cache since it was last emptied.
size_t bytes
Estimated size of the entries held now.
size_t budget
Size the entries may reach before some are dropped.
size_t entries
Entries held now.
A compiled d-DNNF and how its inputs match the leaves of its form.
size_t bytes
Estimated size of the entry.
std::string form
Canonical form the d-DNNF was compiled for.
How probFoldedProbability evaluates what it cannot fold.
std::function< double()> whole
Probability of the whole circuit, when its root has nothing to fold.
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 ...