The Pivot Point: Benchmarking Boolean::add_to_lc in the Phase 4 Optimization Pipeline

Introduction

In the middle of a deep optimization session for the cuzk SNARK proving engine — part of Filecoin's proof-of-replication (PoRep) pipeline — there comes a moment that exemplifies the discipline of performance engineering. Message <msg id=1204> is deceptively brief. The assistant writes:

Based on the context, the immediate next step is clear: benchmark the Boolean::add_to_lc optimizations that were implemented but never tested. Let me proceed.

That's it. Two sentences, followed by a structured todo list. But this short message sits at a critical juncture: it is the transition from implementation to measurement — the moment where weeks of code changes, profiling sessions, and failed experiments converge into a single, decisive test. The Boolean::add_to_lc optimization, if it works, would be the payoff for an entire sub-phase of work. If it fails, the team would need to reconsider their entire approach to synthesis optimization.

The Context: A Long Road of Failed Optimizations

To understand why this message matters, we must understand what led to it. The Phase 4 optimization effort had been a story of well-intentioned ideas meeting the unforgiving reality of hardware counters.

The assistant's previous message ([msg 1202]) is a sprawling 2,000+ word document that reads like a battle report. It catalogs everything that had been tried and rejected:

• SmallVec (A1): The hypothesis was that replacing Vec with SmallVec for small linear combinations would reduce cache misses. The perf stat data showed the opposite: SmallVec did reduce cache misses at every level (L1, L2, L3, DRAM), but it crashed IPC from 2.60 to 2.38 — an 8.5% regression. The enum discriminant checks and larger stack frames defeated Zen4's out-of-order execution engine. Vec's simpler instruction stream won.
• cudaHostRegister (B1): Pinning host memory for GPU transfers seemed like a standard optimization. But for 10 circuits × 3 arrays × 4.17 GB, the mlock syscall touched every page of 125 GB of memory, adding 5.7 seconds of overhead. Cancelled.
• Interleaved A+B eval: Merging two evaluation loops into one to improve cache behavior actually hurt IPC (2.53 vs 2.60). Reverted.
• Vec recycling pool: Reusing allocation buffers in ProvingAssignment::enforce yielded only ~0.7% improvement — barely measurable. The profiling had revealed that the dominant allocation cost wasn't in the six enforce Vecs, but in the dozens of temporary LinearCombination objects created inside circuit gadget closures.
• Software prefetch: Added _mm_prefetch intrinsics to eval loops. Marginal benefit. Each of these was a rational hypothesis, backed by profiling data, implemented cleanly, and then rigorously measured. Each failed to deliver meaningful improvement. This pattern — hypothesis, implementation, measurement, rejection — is the essence of data-driven optimization, but it is also emotionally taxing. After the fourth or fifth dead end, the temptation to declare victory with marginal gains or to move on to a different subsystem must be strong.

The Boolean::add_to_lc Optimization

The one optimization that remained untested was Boolean::add_to_lc(). The insight came from the perf record profile, which sampled 229,000 call stacks during the ~55-second synthesis phase. The breakdown showed that Boolean::lc() consumed 6.51% of synthesis time — approximately 3.6 seconds. This function creates a fresh LinearCombination::zero() — a heap allocation — on every call, even though it typically wraps only one or two terms.

In tight loops like UInt32::addmany, Boolean::lc() is called 32 times per operand. In SHA-256 gadget code, it is called inside every enforce closure. The pattern is everywhere:

lc = lc + &bit.lc(CS::one(), coeff)

This expression creates a temporary LinearCombination (allocating a Vec), adds it to lc (allocating another Vec for the result), and then drops the temporary (freeing the first Vec). The allocation and deallocation happen for every boolean term in every constraint.

The fix was elegantly simple: add methods add_to_lc() and sub_from_lc() to the Boolean type that mutate an existing LinearCombination in place, eliminating the temporary entirely. The new usage looks like:

lc = bit.add_to_lc(lc, CS::one(), coeff)

This bypasses the allocation entirely. The Boolean writes its terms directly into the target LinearCombination's internal vectors.

The implementation touched seven files across three crates (bellpepper-core, bellperson, and their gadget modules). Every call site that used bit.lc() inside a closure was patched: UInt32::addmany, Num::add_bool_with_coeff, Boolean::enforce_equal (three variants), Boolean::sha256_ch, Boolean::sha256_maj, lookup3_xy, and lookup3_xy_with_conditional_negation. In total, dozens of individual call sites were converted.

The Message as Decision Artifact

Message <msg id=1204> is interesting precisely because of what it doesn't say. It doesn't re-argue the case for the optimization. It doesn't hedge with caveats about potential downsides. It doesn't propose alternative approaches. It simply states that the next step is clear and proceeds.

The todo list embedded in the message reveals the assistant's mental model of the validation pipeline:

1. Build synth-bench (status: in_progress) — verify the code compiles
2. Run synth-only microbenchmark (3 iterations) — measure synthesis time in isolation
3. Run perf stat comparison — collect hardware counter data for A/B comparison
4. If significant improvement, run full E2E test — validate that synthesis gains translate to end-to-end throughput
5. Investigate GPU wrapper regression — a separate 3-second regression in the bellperson GPU wrapper time (37s vs 34s baseline) that appeared alongside the Phase 4 changes
6. Consider patching remaining call sites — multipack.rs and num.rs conditionally_reverse still use the old pattern
7. Commit Phase 4 changes — checkpoint the working state This sequence embodies a crucial engineering principle: measure at every level of abstraction. The synth-only microbenchmark isolates the CPU synthesis cost from GPU variability. The perf stat comparison validates that the improvement comes from the expected mechanism (fewer instructions, fewer allocations) rather than from measurement noise. The full E2E test confirms that the synthesis improvement isn't masked by GPU bottlenecks or synchronization overhead. Each layer of measurement builds confidence.

Assumptions Embedded in the Plan

The plan makes several assumptions worth examining:

That Boolean::lc() is the dominant allocation cost. The profiling data supported this — 6.51% of synthesis time in Boolean::lc() itself, plus additional time in LC::add (5.61%) and LC::sub_unsimplified (1.70%) that would be bypassed by in-place mutation. But the 17.44% of time attributed to "Memory allocation" (libc internals) might have other sources that this optimization wouldn't touch.

That the synth-only microbenchmark is a valid proxy. The microbenchmark runs a single partition's synthesis in isolation, without the GPU proving phase. If the optimization has side effects that only manifest in the full pipeline — for example, if it changes memory layout in ways that affect GPU transfer performance — the microbenchmark would miss them.

That the GPU wrapper regression is independent. The 3-second regression in bellperson GPU wrapper time (from 34.0s to 37.2s) appeared alongside the Phase 4 CUDA changes (A4 parallel B_G2, D4 per-MSM window tuning). The assistant assumes this is a separate issue from the synthesis optimization, but it's possible that changes to memory allocation patterns in synthesis could affect GPU transfer scheduling.

That 3 iterations are sufficient for statistical significance. On a 96-core Zen4 system with aggressive turbo boost and NUMA effects, single-threaded synthesis time can vary by several percent between runs. Three iterations provides a rough estimate but may not capture the full distribution.

The Broader Narrative: Optimization as Iterative Hypothesis Testing

This message sits within a larger pattern that defines the entire Phase 4 effort. Each optimization follows the same cycle:

1. Profile: Use perf record to identify hotspots with precise self-time attribution
2. Hypothesize: Form a theory about why the hotspot exists and how to eliminate it
3. Implement: Write the code change, often touching multiple files and crates
4. Measure: Run microbenchmarks and collect hardware counters
5. Decide: Accept, reject, or modify based on data What makes this cycle notable is the rigor of the measurement step. The assistant doesn't just measure wall-clock time — it collects perf stat data showing instructions retired, branch mispredictions, cache misses at every level, and IPC. This allows the assistant to understand why an optimization works or fails, not just that it works or fails. The SmallVec case is the clearest example. SmallVec reduced cache misses (the hypothesized mechanism) but hurt IPC (an unexpected side effect). Without the hardware counter data, the assistant might have concluded that SmallVec was a net positive based on wall-clock time alone, or might have attributed the regression to the wrong cause. The perf stat data revealed the true mechanism: SmallVec's enum discriminant checks and larger stack frames introduced instruction-level dependencies that Zen4's out-of-order engine couldn't hide.

What Happened Next

The chunk summary reveals the outcome of this pivotal test. The Boolean::add_to_lc optimization succeeded: synthesis time dropped from ~55.4s to ~50.9s — an 8.3% improvement. The perf stat data confirmed 91 billion fewer instructions (-15.3%) and 18.6 billion fewer branches (-26.7%). The optimization worked exactly as hypothesized.

But the story didn't end there. The full E2E test revealed a new problem: the GPU wrapper time was 36.0s vs 34.0s baseline, despite identical CUDA internal timing (~26s). This led to a deeper investigation that uncovered synchronous destructor overhead from freeing ~37 GB of C++ vectors and ~130 GB of Rust Vecs after GPU proving. The fix — moving deallocation into detached threads — dropped the GPU wrapper time to 26.2s and the total E2E time to 77.2s, a 13.2% reduction from the 88.9s baseline.

This is the deeper lesson of message <msg id=1204>: the assistant committed to measuring before declaring victory, and that commitment uncovered a second, larger optimization opportunity that had been hidden by the measurement methodology. If the assistant had simply declared "Boolean::add_to_lc works, synthesis is 8% faster, done," the 13.2% total improvement would never have been realized. The GPU destructor bottleneck would have remained invisible, masked by the synthesis improvement.

Conclusion

Message <msg id=1204> is a study in disciplined execution. It is the moment when the assistant transitions from implementation to validation, from hypothesis to measurement. The brevity of the message belies the weight of the decision: after weeks of failed optimizations, this is the test that could either validate the entire approach or send the team back to the drawing board.

The todo list embedded in the message encodes a sophisticated understanding of performance validation — the need to measure at multiple levels, to collect hardware counter data, to isolate variables, and to investigate regressions rather than ignoring them. This methodology, applied consistently, is what turned a promising but unproven optimization into a 13.2% end-to-end improvement.

In the end, the Boolean::add_to_lc optimization was not the biggest win of Phase 4 — the async deallocation fix was larger. But it was the catalyst. Without the discipline to measure and investigate, the GPU destructor bottleneck would have remained hidden, and the full potential of the optimization pipeline would have been left unrealized.