29#include <unordered_map>
76 const std::string &builder = std::string());
99std::unordered_map<std::string, std::list<Entry>::iterator>
map_;
163 bool *ran_compiler =
nullptr,
gate_t
Strongly-typed gate identifier.
Boolean circuit for provenance formula evaluation.
A d-DNNF circuit supporting exact probabilistic and game-theoretic evaluation.
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.
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.
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...
What probCachedProbability may do, and what it reports back.
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...
bool fold
Fold the independent groups of the root first.
bool use_cache
Look compiled d-DNNFs up, and store new ones.
std::function< std::string()> last_builder
Names the builder of the d-DNNF the compile callback last returned.
What a call to probCachedProbability actually did, so the caller can report it instead of the method ...
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.
uint64_t evictions
Entries dropped to stay under the size limit.
uint64_t inserts
Entries stored.
uint64_t hits
Lookups served from an entry.
size_t bytes
Estimated size of the entries held now.
uint64_t misses
Lookups that found no usable entry.
size_t budget
Size the entries may reach before some are dropped.
size_t entries
Entries held now.
uint64_t rejections
d-DNNFs too large to be stored
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.
std::string builder
Method that compiled dd ("tree-decomposition", "compilation:d4"...).
std::vector< gate_t > leaf_gate
Input of dd for each leaf of the form.
std::vector< char > leaf_present
Whether that leaf occurs in dd at all.
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 ...