러스트에서 10만 개 이상의 게이트 디지털 로직 시뮬레이터 구축: 계층 구조를 평평하게 만들고 L1 캐시를 극대화한 방법

Like many people, I was incredibly inspired by Sebastian Lague’s digital logic simulator videos. I had this “fragile dream” of building a visual, node-based sandbox where you could wire up primitive NAND gates, package them into custom sub-chips, and stack them recursively all the way up to a fully functioning 16-bit or 32-bit CPU running in real-time.

But if you’ve ever tried scaling up traditional visual logic simulators, you know you hit a brutal performance wall incredibly fast. Classic Object-Oriented patterns—where every logic gate is a heap-allocated node, wires are pointers, and nested sub-chips require recursive tree-walks or virtual dispatch—will tank the engine to 4 FPS the moment your circuit crosses a few thousand gates.

I wanted raw simulation throughput. Built from scratch using Rust, Macroquad, and egui, my simulator now comfortably processes over 100,000+ primitive gates in real-time on standard laptop hardware.

Here is how I used Data-Oriented Design, dynamic parallel execution, and topological cache defragmentation to make hardware scale.

1. Making Deep Nesting Free (The Flattening Compiler)

In a naive simulator, if you nest a NAND gate inside an XOR gate, inside a Full Adder, inside an ALU, inside a CPU, your runtime pays a massive pointer-chasing traversal penalty at every single nesting level just to find out what a wire is doing.

To fix this, I built a synchronous flattening compiler.

[User View: Nested Hierarchy]
CPU ➔ ALU ➔ Full Adder ➔ NAND

[Simulation Layer: Flattened Array]
[ NAND #0, NAND #1, NAND #2, NAND #3, ... ]  <-- One flat, contiguous Slab

Enter fullscreen mode Exit fullscreen mode

Before the simulation loop ever starts, the engine recursively resolves the entire nested-chip layout and flattens it down to a single, contiguous array of raw primitive primitives (NAND, Input, Output, Clock).

At runtime, the concept of a “sub-chip” completely ceases to exist. Nesting depth becomes a zero-cost abstraction used strictly for UI organization. A CPU built out of 10,000 deeply nested custom chip instances evaluates exactly as fast as 10,000 raw NAND gates laid out flat on a single canvas.

2. Navigating the “Wide vs. Narrow” Pipeline Safely with Rayon

To push past 100k gates, I needed to leverage multi-core processors. However, parallel event processing is notorious for introducing non-deterministic data races.

The Safety Net

I used Tarjan’s Strongly Connected Components (SCC) algorithm to calculate an $O(V+E)$ topological depth scheduling layout. By grouping independent gates into explicit depth layers, I could guarantee that all nodes within the exact same depth layer can be evaluated in parallel with 100% thread safety without locks.

The Bottleneck: Thread-Pool Overhead

The problem with a pure event-driven simulation loop is that it is highly unpredictable. The workload might be incredibly “wide” on one step (e.g., a 32-bit clock line triggering 32 separate registers simultaneously), but turn entirely “narrow” on the very next step (e.g., a single ALU flag toggling).

If you unconditionally throw Rayon’s .par_iter() at small event queues or narrow steps, the overhead of spinning up and waking up worker threads takes longer than just processing the math sequentially on a single core.

The Solution: An Intelligent Hardware Profiler

Instead of guessing a hardcoded threshold (which fails spectacularly depending on whether the app runs on a high-end desktop or an Android phone), the simulator runs a quick calibration routine on startup. It benchmarks dummy gate arrays of varying sizes using both single-threaded .iter() and parallel .par_iter() to find the exact crossover threshold where multi-threading becomes beneficial on the host machine.

The simulator then dynamically routes execution mid-cycle depending on the size of the current evaluation queue:

let queue_size = current_queue.len();
let updates: Vec<(usize, u8)> = if queue_size >= self.dynamic_threshold {
    // Hardware profiler determined parallel is faster for this batch size
    current_queue.par_iter().filter_map(compute_state).collect()
} else {
    // Single-thread is faster for small queues
    current_queue.iter().filter_map(compute_state).collect()
};

// Centralized, sequential lock-free write-back
for (idx, new_state) in updates {
    self.nodes[idx].state = new_state;
    next_enqueues.push(idx);
}

Enter fullscreen mode Exit fullscreen mode

By passing an immutable copy of the state array to the parallel closure, compute_state remains completely read-only. We accumulate the updates into a standard Vec via .collect(), and then apply them sequentially on a single thread.

Because the parallel phase never writes to shared memory, the engine is completely immune to False Sharing and requires zero performance-killing Mutex or RwLock wrappers inside the simulation loop.

3. Smashing the Cache Locality Wall

Even with a flattened array, random memory allocation is a silent killer. In a large project, users constantly place, delete, and re-wire gates. This leaves structural gaps in the underlying Slab memory allocator. If Gate #5 reads its input from Gate #95,000, the CPU suffers an L1/L2 cache miss, stalling the processor while it fetches data from main RAM.

To optimize strictly for the silicon, I implemented an L1/L2 Cache Defragmentation pass directly inside the synchronous compilation pipeline.

Directly after depth calculation, the engine performs the following:

1. Extracts all valid nodes out of the current sparse allocation layout.
2. Sorts them primarily by topological depth ascending.
3. Packs them tightly into a fresh, non-sparse Slab.
4. Generates an old_to_new translation mapping vector (using usize::MAX as a safe sentinel).
5. Iterates over the new layout and rewrites all internal source references and active event queues to point to the new packed indices.

Because topologically connected gates are now packed right next to each other in physical RAM, the CPU’s hardware prefetcher keeps the L1 cache perfectly saturated. When Rayon grabs chunks of the queue, it processes dense, contiguous memory blocks with minimal cache misses.

4. Bypassing the $O(N)$ UI Rendering Bottleneck

While the simulation backend was running at near bare-metal speeds, drawing a massive circuit was crushing the visual rendering engine. Originally, the editor ran an Axis-Aligned Bounding Box (AABB) frustum check sequentially across the entire component vector. Even if you zoomed all the way in on a single gate, the CPU had to loop through 100,000 items every single frame just to realize they were off-screen.

To solve this, I leveraged the project’s existing Spatial Hash Grid (which was originally engineered for $O(1)$ wire deduplication) to instantly query visible canvas boundaries in $O(K)$ time.

let top_left = self.to_world_space(vec2(0.0, 0.0));
let bottom_right = self.to_world_space(vec2(screen_width(), screen_height()));
let viewport_rect = Rect::new(top_left.x, top_left.y, bottom_right.x - top_left.x, bottom_right.y - top_left.y);

// Grab only visible components instantly
let mut visible_comp_ids = self.canvas.spatial_grid.query_rect(viewport_rect);

Enter fullscreen mode Exit fullscreen mode

Avoiding the Visual Traps

• Defeating Z-Fighting Flicker: A spatial hash query returns a HashSet, which has a non-deterministic iteration order. If you draw straight from the set, overlapping components will randomly flicker over and under each other every single frame. Dumping the IDs into a Vec and executing a microsecond .sort_unstable() before rendering completely stabilizes the layer layout.
• The Long Wire Phantom: Wires are mathematically derived on the fly from a global map (self.circuit.connections) by looking up source and target coordinates. By completely separating the wire rendering phase from the culled component drawing phase, a long bus wire that stretches completely across the screen from an off-screen ALU to an off-screen RAM block never clips out or vanishes when you zoom into the empty space between them.

Current Status & What’s Next

By separating core simulation into isolated parallel-read and sequential-write loops, defragmenting RAM for cache line alignment, and trading immediate-mode UI iterations for spatial grid queries, the engine is fully capable of running complex hardware architectures.

The application features full cross-platform compilation via the same codebase (including a touch-native UI layout for Android alongside native desktop binaries for Windows, Linux, and macOS) and tracks full 4-state logic (Floating, Low, High, Contention) so you can actually debug physical bus conflicts.

The codebase is fully open-source. If you want to dig into the compilation tracing logic, the spatial grid implementation, or compile it yourself, check out the repository here:

👉 Sayanthegamer/digital_logic

I’d love to hear your thoughts on the architecture. How do you handle graph parallelization, memory layout, or cache defragmentation in your own performance-critical Rust projects?