Design Notes

Design Notes

This page gives the implementation-level rationale behind the optimized branch.

It is meant for readers who already understand what NDD is and want to know how this repository's array-backed implementation is organized internally.

Overview

The optimized branch keeps the same conceptual model:

• one NDD node corresponds to one field
• each outgoing edge is guarded by a BDD-based label
• logical operations recurse over fields and labels

What changes is the storage and execution strategy used to implement that model efficiently in Java.

1. Array-Backed Node Table

The original implementation represented each node as an object with nested edge structures. In this branch, NodeTable.java stores node state in parallel arrays.

That means:

• node metadata lives in dense primitive arrays
• edge payloads are stored in shared arrays
• canonical nodes reference edge blocks by index rather than owning separate edge containers

This is the main memory-layout change behind the name NDD-Array.

2. Global Edge Collection

During recursive logical operations, the implementation accumulates candidate edges in one shared stack-like structure instead of allocating temporary maps inside each call.

Important helper concepts in NDD.java:

• edgeCollect(...)
• edgeFlush(...)
• safe-point maintenance after recursion unwinds

The point of this design is to reduce transient allocation without losing canonical ordering.

3. Deferred Field Materialization

declareField(...) and generateFields() are deliberately separate.

Why:

• the implementation needs to know every field width before laying out shared BDD variables
• that global view is what makes right-aligned reuse possible
• it also keeps the field model explicit for packet-processing applications

This is why the library expects users to commit to a field partition early.

4. Safe-Point Recycling

The array-backed layout introduces a constraint that the implementation must respect: recursive operations may still hold raw edge-array positions while the recursion stack is active.

Because of that, edge compaction and retired-slot reuse happen only at safe points after recursion unwinds. Relevant methods include:

• NDD.runSafePointMaintenance()
• NodeTable.compactEdgesIfNeeded()
• NodeTable.compactEdgesAtSafePoint()

5. API Shape

JNDD

The low-level API uses integer node IDs. This matches the array-backed representation and avoids wrapper allocation on the hot path.

JavaNDD

The NDDFactory layer keeps a BDDFactory-style API for compatibility with codebases built around JavaBDD.

That compatibility layer is especially relevant for the Batfish-style integration documented in Network Verification Applications.

6. Interpreting The Benchmark Variants

When reading the result pages:

• ndd is the baseline implementation
• ndd-reuse isolates the effect of shared-BDD-variable reuse
• ndd-array adds the array-backed node table and stack-based edge collection

That split is useful because it shows which gains come from better symbolic structure and which come from the new runtime representation.