The Payoff: How Boolean::add_to_lc Delivered the First Real Synthesis Win in Phase 4

"Excellent results! Synthesis time dropped from 55.4s baseline to 50.9s average — a 4.5 second (8.1%) improvement. This is a significant win."

This single sentence, written by the AI assistant in message [msg 1208], represents the culmination of a long and often frustrating optimization journey. After weeks of implementing, reverting, and discarding optimization after optimization — each one either neutral or actively harmful — the Boolean::add_to_lc patch finally delivered a measurable, double-digit-percentage improvement to the CPU synthesis phase of Filecoin's Groth16 proof generation pipeline. The message is brief, almost anticlimactic in its matter-of-fact delivery, but the weight of those four words — "a significant win" — can only be appreciated by understanding the trail of failed experiments that preceded it.

The Context: Phase 4's Long String of Reversals

To understand why this message matters, one must understand the broader Phase 4 optimization effort documented in the conversation. The cuzk project is building a pipelined SNARK proving engine for Filecoin's Proof-of-Replication (PoRep) protocol. Phase 4 was dedicated to "compute-level optimizations" — micro-optimizations to the CPU synthesis hot path and GPU proving kernels. But by the time message [msg 1208] arrives, the assistant has already tried and discarded four separate optimizations:

1. SmallVec (A1) — Replacing Vec with SmallVec for the LinearCombination indexer was hypothesized to reduce cache misses. It did reduce cache misses at every level (L1, L2, L3, DRAM), but IPC dropped from 2.60 to 2.38 — an 8.5% regression. The enum discriminant checks and larger stack frames of SmallVec defeated Zen4's out-of-order execution engine. Cancelled.
2. cudaHostRegister (B1) — Pinning CPU memory for faster GPU transfers sounded promising, but the mlock syscall touched every page of 125 GB of allocations, adding 5.7 seconds of overhead. Reverted.
3. Interleaved A+B eval — Evaluating the A and B linear combinations in a single fused loop was supposed to improve cache utilization. Instead, it hurt IPC (2.53 vs 2.60). Reverted to separate evals.
4. Vec recycling pool + software prefetch — Recycling the six Vec buffers inside ProvingAssignment::enforce and adding software prefetch intrinsics to eval loops yielded only ~0.7% improvement. Marginal at best. Each of these optimizations was implemented, benchmarked with perf stat hardware counters, and either cancelled or reverted when the data showed no improvement or actual regression. The assistant was operating under a strict "measure everything" mandate — the user had explicitly demanded rigorous microbenchmarking after seeing a regression earlier in the project. This created a culture of empirical validation where every hypothesis had to survive contact with real hardware counters.

The Breakthrough: Profiling Reveals the Real Bottleneck

The key insight came from a perf record profile that captured 229,000 samples of the ~55-second synthesis phase. The breakdown was revealing:

| Category | Self % | ~Seconds | |---|---|---| | enforce (all fragments) | 22.13% | ~12.2s | | LC construction | 23.52% | ~12.9s | | Field arithmetic | 16.98% | ~9.3s | | Memory allocation | 17.44% | ~9.6s |

The "LC construction" category was the largest single contributor to synthesis time, and within it, Boolean::lc() accounted for 6.51% — approximately 3.6 seconds. The critical finding was that Boolean::lc() creates a fresh LinearCombination::zero() — which involves a Vec allocation — on every call, even though it typically wraps only 1-2 terms. In tight loops like UInt32::addmany, Boolean::lc() is called 32 times per operand. The allocation overhead was not in the six Vec buffers inside enforce (which the recycling pool targeted) but in the dozens of temporary LinearCombinations created by Boolean::lc() inside circuit gadget code.

This was a classic profiling insight: the obvious bottleneck (the six enforce Vecs) was not the real problem. The real problem was hidden in the gadget-level code, in a method that seemed innocuous but was called millions of times during circuit synthesis.

The Implementation: add_to_lc and sub_from_lc

The fix was elegant in its simplicity. Instead of creating a new LinearCombination for each boolean term and then adding it to the accumulator (which involves a Vec allocation, a copy, and a deallocation), the assistant added two new methods to the Boolean gadget:

• Boolean::add_to_lc() — adds the boolean's terms directly to an existing LinearCombination in-place
• Boolean::sub_from_lc() — subtracts the boolean's terms from an existing LinearCombination in-place These methods eliminate the temporary LinearCombination allocation entirely. The patch touched six files across three forked repositories:
• extern/bellpepper-core/src/gadgets/boolean.rs — the new methods themselves, plus patched enforce_equal, sha256_ch, and sha256_maj
• extern/bellpepper-core/src/gadgets/num.rs — Num::add_bool_with_coeff rewritten to use bit.add_to_lc()
• extern/bellperson/src/gadgets/uint32.rs — UInt32::addmany inner loop rewritten
• extern/bellperson/src/gadgets/lookup.rs — both lookup3_xy and lookup3_xy_with_conditional_negation patched across 6+ enforce closures
• extern/bellperson/src/groth16/prover/mod.rs — Vec recycling pool (supporting optimization)
• extern/bellpepper-core/src/lc.rs — prefetch intrinsics (supporting optimization)

The Moment of Validation

Message [msg 1208] is the moment the assistant sees the benchmark results from [msg 1207]. The microbenchmark ran three iterations of the synthesis-only workload (a single partition of a 32 GiB PoRep C2 proof) and produced these timings:

• Iteration 1: 50.687s
• Iteration 2: ~50.9s (average)
• Iteration 3: ~50.9s (average) Compared to the Vec baseline of 55.4s (established across two runs at 55.427s and 55.507s), this is a 4.5-second reduction — 8.1% improvement. The assistant's reaction is professional but clearly pleased: "Excellent results!" But the assistant does not stop at the wall-clock time. True to the project's measurement-first culture, the next step is immediately queued: running perf stat to collect hardware counter data for a rigorous A/B comparison. This is visible in the todo list embedded in the message, which transitions the "Run perf stat comparison" item from "pending" to "in_progress". The assistant knows that wall-clock time can be noisy; hardware counters provide the definitive story about why the improvement occurred.

The Broader Significance

This message represents more than just a successful optimization. It validates the entire profiling-driven methodology that the assistant had been following. The earlier failed optimizations (SmallVec, cudaHostRegister, interleaved eval) were all reasonable hypotheses that happened to be wrong. The Boolean::add_to_lc optimization was also a hypothesis — but it was grounded in hard data from perf record, which pinpointed Boolean::lc() as a 6.51% hotspot.

The lesson is a classic one in systems optimization: the bottleneck is almost never where you think it is. The Vec recycling pool targeted the six enforce buffers and yielded 0.7%. The real bottleneck was in the gadget-level code, called millions of times in tight loops, each call doing a tiny allocation that added up to seconds. This is the kind of insight that only comes from rigorous profiling with hardware counters, not from intuition.

Furthermore, this success set the stage for the rest of Phase 4. With synthesis now at ~50.9s, the assistant would go on to run a full end-to-end proof, discover a GPU wrapper regression (36.0s vs 34.0s baseline), trace it to synchronous destructor overhead, implement async deallocation, and ultimately achieve a 13.2% total E2E improvement. But the Boolean::add_to_lc win was the first real breakthrough — the moment when the optimization pipeline started delivering.