Skip to content

Results NQueens

Jump to bottom
TelosCheney edited this page Aug 5, 2026 · 4 revisions

Results: NQueens

The ndd-zdd rows on this page are archived results from the removed finite-domain ZDD backend. That backend used a one-of-w domain and is not the current set-family ZDD implementation, whose width-w domain contains 2^w Boolean bit vectors. New backend comparisons must rerun the benchmark; the legacy rows below are retained only as experiment history.

This page preserves the detailed NQueens benchmark table from results/nqueens_metrics.csv.

For the dedicated NQueens benchmarking repository, including the broader cross-library harness and related implementations, see https://github.com/XJTU-NetVerify/nqueensBenchmarkDDs.

NQueens is the easiest benchmark in this repository to understand and rerun, so it is also the clearest place to see what the current NDD implementation changes in practice.

What This Page Shows

  • cross-library comparisons across C, Java, and C# implementations
  • the gap between NDD-Origin, NDD-Reuse, and the current NDD implementation
  • not just runtime, but also memory footprint and node counts
  • a snapshot of the NQueens evaluation that complements the standalone benchmark repository

Main Takeaways

  • NDD preserves the same solution counts as the other exact DD implementations.
  • The biggest gains over the NDD-Origin baseline show up from size 10 onward.
  • The reduced BDD-node counts of NDD-Reuse and NDD show that the variable-reuse optimization matters even before the array-backed execution changes are considered.
  • The gap between NDD-Reuse and NDD isolates the additional gain from the structure-of-arrays node table and shared edge stack.
  • The archived backend comparison exercised an older finite-domain ZDD experiment. Its relative timings do not characterize the current ZDD backend.

Highlight Table

Size NDD-Origin time (s) NDD time (s) Speedup NDD-Origin RSS (KB) NDD RSS (KB) RSS reduction
8 0.078 0.040 1.95x 71392 63376 11.2%
9 0.188 0.070 2.67x 127104 65436 48.5%
10 0.498 0.164 3.03x 193236 85568 55.7%
11 1.922 0.559 3.44x 587552 165616 71.8%
12 10.229 3.439 2.97x 1830248 483056 73.6%
13 66.710 23.662 2.82x 6828624 2492744 63.5%

Label Backend Comparison

These results compare plain decision diagram baselines and NDD using different edge-label backends.

Targets:

  • bdd: plain BDD baseline
  • zdd: plain ZDD baseline
  • bcdd: plain complemented-edge BDD baseline
  • ndd: NDD with standard BDD edge labels
  • ndd-zdd: retired finite-domain ZDD edge labels (legacy rows only)
  • ndd-bcdd: NDD with complemented-edge BDD edge labels

N = 8

target solutions time (s) memory (MB) nodes created nodes alive
bdd 92 0.0330 58.9 52,474 2,451
zdd 92 0.0125 50.2 21,107 373
bcdd 92 0.0878 83.2 52,412 2,450
ndd 92 0.0377 61.3 10,797 600
ndd-zdd 92 0.0342 64.9 9,067 451
ndd-bcdd 92 0.0363 60.8 10,823 1,312

N = 9

target solutions time (s) memory (MB) nodes created nodes alive
bdd 352 0.1009 62.4 216,443 9,557
zdd 352 0.0483 61.3 81,984 1,309
bcdd 352 0.3326 210.6 216,215 9,556
ndd 352 0.0696 71.4 29,451 1,364
ndd-zdd 352 0.0632 65.8 26,578 1,178
ndd-bcdd 352 0.0699 77.5 29,485 2,773

N = 10

target solutions time (s) memory (MB) nodes created nodes alive
bdd 724 0.3264 68.5 955,575 25,945
zdd 724 0.1636 68.2 343,536 3,120
bcdd 724 1.4544 690.3 953,944 25,944
ndd 724 0.1847 93.5 97,595 2,905
ndd-zdd 724 0.1651 97.5 92,654 2,680
ndd-bcdd 724 0.1847 101.7 97,638 5,675

N = 11

target solutions time (s) memory (MB) nodes created nodes alive
bdd 2,680 2.3780 94.4 4,691,834 94,822
zdd 2,680 0.7121 80.9 1,552,727 10,503
bcdd 2,680 8.6851 3133.5 4,685,028 94,821
ndd 2,680 0.5399 196.3 398,650 8,579
ndd-zdd 2,680 0.5556 207.9 388,606 8,310
ndd-bcdd 2,680 0.6840 202.1 398,703 14,023

N = 12

target solutions time (s) memory (MB) nodes created nodes alive
bdd 14,200 16.9083 218.2 24,717,257 435,170
zdd 14,200 5.2012 115.6 7,592,039 45,833
bcdd 14,200 20.4717 315.5 24,717,255 435,169
ndd 14,200 3.0199 567.2 1,859,828 33,638
ndd-zdd 14,200 2.8683 559.4 1,831,431 33,561
ndd-bcdd 14,200 3.0480 742.1 1,859,892 33,637

N = 13

target solutions time (s) memory (MB) nodes created nodes alive
bdd 73,712 138.8387 2127.1 136,722,638 2,044,394
zdd 73,712 42.8324 212.6 39,087,758 204,781
bcdd 73,712 139.4397 2188.9 136,587,014 2,044,393
ndd 73,712 22.3243 2460.7 9,378,160 145,368
ndd-zdd 73,712 20.9622 2446.8 9,267,948 145,278
ndd-bcdd 73,712 22.3683 3212.9 9,378,236 145,367

Full Results Table

Note: JSylvan is a parallel BDD library and was run with 48 worker threads. All other implementations in the table are single-threaded.

Implementation Lang Size Time (s) Max RSS (KB) Nodes Created Nodes Alive NDD Nodes Alive BDD Nodes Alive Solutions
BuDDy C 8 0.077764 33976 53611 2451 0 2451 92
CUDD C 8 0.019701 1556 52385 2451 0 2451 92
JDD Java 8 0.101363 47628 53083 2451 0 2451 92
JSylvan Java 8 0.199862 100548 54140 2451 0 2451 92
NDD-Origin Java 8 0.077586 71392 18813 2980 1274 1706 92
NDD-Reuse Java 8 0.075226 70052 10950 1501 1274 227 92
NDD Java 8 0.039729 63376 10797 600 415 185 92
DD-BDD C# 8 0.105951 30060 52181 2458 0 2458 92
DD-CBDD C# 8 0.102576 29972 46171 772 0 772 92
BuDDy C 9 0.055283 916 218386 9557 0 9557 352
CUDD C 9 0.084736 18248 216602 9557 0 9557 352
JDD Java 9 0.169698 52604 217230 9557 0 9557 352
JSylvan Java 9 0.169024 97144 219050 9557 0 9557 352
NDD-Origin Java 9 0.188159 127104 50686 4838 2360 2478 352
NDD-Reuse Java 9 0.178204 119348 29679 2652 2360 292 352
NDD Java 9 0.070447 65436 29451 1364 1133 231 352
DD-BDD C# 9 0.251876 33960 215883 9565 0 9565 352
DD-CBDD C# 9 0.237059 33848 185654 2795 0 2795 352
BuDDy C 10 0.273222 12272 958740 25945 0 25945 724
CUDD C 10 0.470678 38032 954767 25945 0 25945 724
JDD Java 10 0.401075 64156 956019 25945 0 25945 724
JSylvan Java 10 0.221022 113608 958344 25945 0 25945 724
NDD-Origin Java 10 0.497630 193236 146705 7747 4310 3437 724
NDD-Reuse Java 10 0.437430 184724 97924 4674 4310 364 724
NDD Java 10 0.164244 85568 97595 2905 2625 280 724
DD-BDD C# 10 0.543737 64908 77081 25954 0 25954 724
DD-CBDD C# 10 0.433853 61044 793143 6601 0 6601 724
BuDDy C 11 3.292847 33044 4699647 94822 0 94822 2680
CUDD C 11 3.544228 165496 4687448 94822 0 94822 2680
JDD Java 11 2.561767 86824 4691203 94822 0 94822 2680
JSylvan Java 11 1.237607 210944 4693318 94822 0 94822 2680
NDD-Origin Java 11 1.921927 587552 549703 15116 10487 4629 2680
NDD-Reuse Java 11 1.898573 594184 399085 10932 10487 445 2680
NDD Java 11 0.558676 165616 398650 8579 8244 335 2680
DD-BDD C# 11 2.559011 282948 3808918 94832 0 94832 2680
DD-CBDD C# 11 1.760857 147488 1374411 22455 0 22455 2680
BuDDy C 12 41.097934 132060 24741296 435170 0 435170 14200
CUDD C 12 28.662674 290152 24740519 435170 0 435170 14200
JDD Java 12 19.010857 208500 24719128 435170 0 435170 14200
JSylvan Java 12 4.815930 1189512 24702052 435170 0 435170 14200
NDD-Origin Java 12 10.228945 1830248 2481745 42799 36749 6050 14200
NDD-Reuse Java 12 9.958038 1887984 1860431 37282 36749 533 14200
NDD Java 12 3.439133 483056 1859828 34230 33837 393 14200
DD-BDD C# 12 13.930812 1031892 12943122 435181 0 435181 14200
DD-CBDD C# 12 9.730087 707192 2190375 98900 0 98900 14200
BuDDy C 13 500.000000 559724 0 0 0 0 0
CUDD C 13 194.928463 1249180 136780708 2044394 0 2044394 73712
JDD Java 13 148.970034 2153312 136725331 2044394 0 2044394 73712
JSylvan Java 13 42.856795 1426140 136752306 2044394 0 2044394 73712
NDD-Origin Java 13 66.710407 6828624 12178662 157061 149303 7758 73712
NDD-Reuse Java 13 61.887740 6756196 9378951 149933 149303 630 73712
NDD Java 13 23.661821 2492744 9378160 146060 145603 457 73712
DD-BDD C# 13 81.584208 8151360 101810366 2044406 0 2044406 73712
DD-CBDD C# 13 55.487488 2475704 24376279 445755 0 445755 73712

Plots

Time

NQueens time

Memory

NQueens max RSS

Node Counts

NQueens nodes created

NQueens nodes alive

Clone this wiki locally