|0.1.3||Sep 25, 2019|
|0.1.2||Dec 17, 2018|
|0.1.1||Dec 17, 2018|
|0.1.0||Nov 30, 2018|
#262 in Data structures
50 downloads per month
A rust library for working with boolean expressions (expression trees, decision diagrams, etc.)
This crate lets you build a complicated abstract syntax tree (or logic circuit schematic, if you prefer) by working with individual Bit structs, or vectors that act like integers. You can also solve these AST structures by converting them into reduced, ordered, binary decision diagrams (ROBDDs) - a normal form consisting of if-then-else triples that essentially act like compressed truth tables. You can also construct and manipulate BDDs directly.
I got most this working back in December and then put it all aside for a while. It's still pretty messy, but I'm starting to work on it again, so I figured I would ship what I have, and then aim for more frequent, small releases as I continue to tinker with it.
bddso that the
BddStateis now owned by a
BddWorker. Further, both
BddWorkerare now traits.
- Provided multiple implementations for
BddState-- (so far, one with and one without array bounds checking).
- Added a multi-core bdd worker:
BddSwarm. Between threading and an out-of-order execution model that results in potential short circuiting,
ite()calls that once took 30 or more seconds on my low-end 2-core laptop now run in 0 seconds!
solve::sort_by_costwhich optimizes the ast→bdd conversion to take only one
bdd_refine_onestep per AST node (improved my still-external benchmark script by an order of magnitude).
ite_normnow constructs hi/lo nodes directly from input rather than calling
when_xx. This resulted in about a 23% speedup.
(rudimentary) example programs
examples/bdd-solve.rsdemonstrates one method of using bex to solve arbitrary problems. (Albeit very very slowly, still...)
examples/bex-shell.rsis a tiny forth-like interpreter for manipulating expressions interactively.
- See exaples/README.md for more details.
solve::ProgressReportcan now simply save the final result instead of showing it (as
dotcan take a very long time to render it into a png). It also now shows progress as a percentage (though only currently accurate when
Cargo.tomldocumentation link to docs.rs/bex
- added this changelog
bex::int, used macros to generalize number of bits, added
bex::solvefor converting between ast and bdd representations.
- Added distinction between
virtual(intermediate) variables in
- Added graphviz (
*.dot) output for
base::Baseand improved formatting for
- Various performance enhancements for
bex::bdd. Most notably:
- switched caches to use the
hashbrowncrate (for about a 40% speedup!)
- added inlining hints for many functions
- re-ordered logic in bottleneck functions (
ite_norm) to minimize work
bdd::NIDis now a single u64 with redundant information packed into the NID itself. This way, decisions can be made looking at the NID directly, without fetching the actual node.
- Disabled bounds checking for internal node lookups. (unsafe)
- switched caches to use the
bex::bddin preparation for multi-threading.
- Grouped the internal node lists and the caches by branching variable (VID). This isn't actually an optimization, but I expect(ed?) it to make concurrent solving easier in the future.
- moved all the unsafe, data-mutating operations into a handful of
isolated functions on a single source page. These will likely be
factored out into a new
Initial public version. Work-in-progress code imported from a private repo.