Clone wiki

JDD / Performance

JDD performance

JDD is written in Java, and top performance was not the main priority during the design.

Still, JDD is a very efficient BDD package. The computation speed is in some situations comparable to CUDD and BuDDy. Due to a new cache scheme, JDD sometimes even outperforms those two (this depends very much on the size and type of the problem being solved). The main disadvantage of using JDD is its memory usage. JDD uses less memory per node than BuDDy, however JVM craziness can result in higher overall memory usage.

If you still need a faster BDD package, check out JBDD, my Java interface to BuDDy and CUDD.

Benchmarks

Benchmarking is hard, specially when performance can vary greatly with the problem class. Still, many years ago when I was young and naive I did a quick test to show people JDD was fast enough for the 12-queens problem...

Package  Slow ratio N queens        Slow ratio, CNF SAT
            (12 x Queens)        (aim-100-6_0-yes1-2)
BuDDy           1.0                        1.6
CUDD            1.65                       ?
SableJBDD       > 10                       ?
JavaBDD         2.5                        5.15
JDD/BDD         1.55                       1.0
JDD/ZBDD        0.9                        N/A
JDD/ZBDD-CSP    0.29                       N/A
JDD/GSAT       N/A                        < 0.02

Notes:

  1. SableJBDD lacks garbage collection (!)
  2. at that time JavaBDD was in alpha and has improved since then

BDD Traces

A BDD-trace is a series of calls to a BDD library recorded at operation level. With a trace-driver, you can repeat these operations with another BDD package. This allows you to compare the performance of two BDD packages easily.

JDD distribution includes the following traces:

  • the original traces in Bwolen Yang's trace driver [1].
  • ISCAS85 traces (including the C6288 multiplier) by Yirng-An Chen.
  • Superscalar Suite 1.0 by Miroslav Velev.

See the profile.sh script for more information.

---

[1] some of these models are explained in the NuSMV manual here.

Updated