JBDD (Java Binary Decision Diagrams) is (yet another) native implementation of (Reduced Ordered) BDDs in Java. It is loosely inspired by JDD, but completely rewritten from scratch, since JDD contained some bugs and was missing features like, for example, substitution. The design goals are simplicity, performance, and no dependencies.
Internally, JBDD does not use any objects, only primitive arrays, and uses manual memory management.
JBDD also provides an object-oriented interface with automatic reference management through weak references (instead of finalize(), which has a hefty performance penalty).
The overhead incurred by the object-oriented interface largely depends on the number of referenced objects, but was hardly measurable in several synthetic benchmarks.
Compared to other libraries, JBDD beats most Java implementations and even is on-par or faster than established, C-based libraries such as BuDDy. (Measured on several synthetic benchmarks.)
- Reduced ordered BDDs with complement edges, over an
intAPI with manual reference counting, and an object layer (BddSet) with automatic reference management - MTBDDs over the same variables (
MtBdd, andBddMap<V>over caller-chosen value numberings), MDDs over n-valued variables (Mdd) - The usual operations plus domain-restricted (
xyIn) and simplifying (xySimplify) variants,compose,restrict, quantification and the relational product (andExists),constrain/simplify, satisfying counts and fractions, the influence of every variable in one pass, the literals a function implies and those implying it, unateness, implicants, prime implicants and irredundant covers of intervals (Minato-Morreale), solution and path cursors, registered operations with private caches - Dynamic variable reordering by sifting, over both diagrams of a context at once
- Primitive collections the API speaks, usable on their own (
de.tum.in.jbdd.collections):NatSet(sets of naturals as sorted arrays or words),Cursorandint-keyed hash maps
ZDDs are not implemented; for those, consider CUDD or Sylvan.
You can either build the jar using gradle (see below) or fetch it from maven central:
<dependency>
<groupId>de.tum.in</groupId>
<artifactId>jbdd</artifactId>
<version>0.7.0</version>
</dependency>and for gradle:
// https://mvnrepository.com/artifact/de.tum.in/jbdd
implementation("de.tum.in:jbdd:0.7.0")A few JVM flags worth trying out:
-Xss128mor similar high values, the implementation is very recursive- High values for
-Xmsand-XX:+AlwaysPreTouchto avoid repeated heap growth -XX:+UseParallelGC-- low latency is not required-XX:+UseTransparentHugePages-XX:TypeProfileLevel=222and-XX:TypeProfileWidth=4
Build the project using gradle, on JDK 21 or newer (the library itself targets Java 11). All dependencies are downloaded automatically.
$ ./gradlew build
Or, if you are on windows,
# gradlew.bat build
If you use JBDD for your experiments, I would appreciate a citation akin to the following.
@misc{jbdd,
author = {Tobias Meggendorfer},
title = {{JBDD}: A Java {BDD} Library},
howpublished = "\url{https://github.com/incaseoftrouble/jbdd}",
year = 2017
}