The Optimization That Wasn't: How Profiling Revealed the True Bottleneck in Groth16 Synthesis

Introduction

In the world of zero-knowledge proof generation, the synthesis phase of Groth16 proving is where CPU time goes to die. For Filecoin's Proof-of-Replication (PoRep) protocol, the cuzk proving engine processes approximately 130 million constraints during a single synthesis run, consuming roughly 55 seconds of CPU time on a high-end AMD Zen4 workstation. When the assistant in this opencode session set out to optimize this phase, they embarked on a journey that would test every tenet of performance engineering: hypothesis formation, implementation, measurement, disappointment, deeper diagnosis, and a dramatic strategic pivot.

Segment 14 of the cuzk development saga captures this arc in full. It begins with the implementation of three carefully designed synthesis optimizations — a Vec recycling pool, interleaved A+B evaluation, and software prefetch intrinsics — each grounded in solid reasoning from earlier perf stat analysis. It continues through the crushing disappointment of a ~1% measured improvement against a baseline that should have yielded 15–25%. And it culminates in a masterful diagnostic pivot: deploying perf record and perf report to discover that the real bottleneck was hiding one level deeper than anyone had looked, inside temporary LinearCombination objects created by Boolean::lc() inside enforce closures. The assistant then pivoted to a new approach — adding add_to_lc and sub_from_lc methods to Boolean and add_lc to Num — and systematically patched every hot call site in the SHA-256 circuit.

This is a story about the discipline of measurement, the courage to abandon carefully implemented code when the data contradicts the hypothesis, and the power of profiling at the right granularity. It is also a case study in why intuition about performance bottlenecks is often wrong, and why the only reliable guide is the profiler.

The Three Optimizations: Design and Rationale

The optimization campaign began with a clear directive from the user at [msg 1122]: "Implement 1/2/3." This referred to three optimizations identified in the preceding perf stat analysis of the synthesis bottleneck ([msg 1121]). The assistant responded with a detailed planning message at [msg 1123], laying out the approach.

Optimization 1: The Vec Recycling Pool

The perf stat analysis had shown that jemalloc's alloc/dealloc cycle consumed approximately 34% of synthesis runtime. Each call to enforce — the hottest function in the entire proving pipeline — creates three LinearCombination objects (for the A, B, and C constraints), each backed by two Vec<Indexer> vectors (one for input variables, one for auxiliary variables). That's six heap-allocated Vecs per constraint. With ~130 million constraints, this translates to roughly 780 million malloc/free calls over the course of a single synthesis run.

The solution was a recycling pool: pre-allocate a set of Vecs inside ProvingAssignment, lend them out during each enforce call, and reclaim them after evaluation. This would eliminate all heap traffic in the hot path, replacing expensive malloc/free cycles with cheap Vec::clear() and Vec::pop()/Vec::push() operations.

The design reasoning, captured in [msg 1127] and [msg 1128], was careful. The assistant considered using bumpalo (a bump-allocating arena) but rejected it because it would "make the type generic over a lifetime and pollute the entire API." Instead, the assistant opted for a simpler approach: a VecPool inside ProvingAssignment that reuses six Vecs per enforce call — two for each of the three LinearCombination objects (A, B, C).

Optimization 2: Interleaved A+B Evaluation

The second optimization targeted instruction-level parallelism (ILP). The existing code evaluated the three constraint polynomials (A, B, C) sequentially: first all terms of A, then all terms of B, then all terms of C. Each evaluation loop read from the same input_assignment and aux_assignment arrays, but the sequential structure meant the CPU's execution pipeline could not overlap the independent arithmetic chains.

The assistant designed an eval_ab_interleaved function that processed A and B terms in a combined loop, alternating between the two LCs to keep the pipeline fuller. As the assistant explained in [msg 1144], the idea was to "process one term from each in round-robin to maximize ILP." The theory was sound: by interleaving independent arithmetic operations, the CPU's out-of-order execution engine could overlap the latency of the field arithmetic (multiplication, addition) across the two chains, improving overall throughput.

Optimization 3: Software Prefetch

The third optimization was the simplest: add _mm_prefetch intrinsics (PREFETCHT0 on x86_64) to the inner loops of eval and eval_with_trackers. This would hint to the CPU to bring the next cache line of assignment data into L1 before it was needed, reducing memory latency. The assistant implemented this in [msg 1140] and [msg 1142], adding prefetch to both the bellperson lc.rs and the bellpepper-core lc.rs.

The expected payoff for these three optimizations combined was substantial — the assistant anticipated a 15–25% improvement in synthesis time, which would translate to meaningful throughput gains in the overall proof generation pipeline.## The Implementation: From Design to Code

The implementation spanned multiple files across two crates, requiring careful coordination. The assistant worked methodically through the dependency chain, starting with the foundational data structures and building up to the hot loop integration.

Changes to bellpepper-core

In extern/bellpepper-core/src/lc.rs, the assistant added three new methods to LinearCombination: zero_recycled (which wraps pre-allocated Vecs instead of creating fresh ones), from_coeff_recycled (a variant of from_coeff that reuses buffers), and recycle (which returns the inner Vecs to the pool). These changes are documented in [msg 1131] and [msg 1132]. The assistant also added the input_terms_slice and aux_terms_slice accessor methods in [msg 1141] to support the interleaved eval.

Changes to bellperson

In extern/bellperson/src/groth16/prover/mod.rs, the assistant added a VecPool struct to ProvingAssignment and modified the enforce method to draw from and return to this pool. This was the critical integration point — the hot loop that had been spending 34% of its time in jemalloc would now operate entirely from pre-allocated buffers. The implementation is visible in [msg 1133] and [msg 1139].

However, adding a new field to ProvingAssignment had downstream consequences. The Debug and PartialEq implementations needed updating (see [msg 1134], [msg 1135], [msg 1136]) to account for the new lc_pool field while ensuring equality semantics remained correct. The assistant handled this carefully, ensuring that the pool was excluded from equality comparisons (since it's an implementation detail of the allocation strategy, not part of the assignment's logical state).

In extern/bellperson/src/lc.rs, the assistant implemented eval_ab_interleaved — the combined A+B evaluation function — in [msg 1144], and added software prefetch to both eval_with_trackers and the new interleaved function in [msg 1140]. The prefetch was a simple _mm_prefetch intrinsic call at the top of each iteration, targeting the next term's variable index.

Verification and Cleanup

Before benchmarking, the assistant verified the code compiled cleanly and checked that no stale references to eval_with_trackers remained. A grep at [msg 1147] confirmed that the old function was no longer called, and a build at [msg 1152] passed with only pre-existing warnings. The stage was set for measurement.

The Moment of Measurement: A 1% Disappointment

The benchmark was run at [msg 1154] using the synth-only microbenchmark with three iterations. The results were devastating:

The Diagnostic Pivot: What the Hardware Counters Revealed

The perf stat comparison at [msg 1156] told a nuanced story:

| Counter | Baseline | Optimized | Delta | |---|---|---|---| | Synthesis time | 55.5s | 54.9s | -1.1% | | Instructions | 593.8B | 569.6B | -4.1% | | Cycles | 228.4B | 225.5B | -1.3% | | IPC | 2.60 | 2.53 | -2.7% | | Branch instructions | 69.8B | 62.5B | -10.4% | | Branch misses | 188.0M | 181.6M | -3.4% | | L3/CCX fills | 122.5M | 133.4M | +8.9% |

The data was paradoxical. Instructions dropped by 4.1% — the recycling pool had indeed eliminated a significant number of jemalloc code paths. Branches dropped by 10.4%, confirming that the pool was working as designed. But IPC (instructions per cycle) dropped from 2.60 to 2.53, a 2.7% regression. The code was executing fewer instructions, but each instruction was taking relatively more cycles. The L3 cache fills also increased by 8.9%, suggesting worse cache behavior.

The assistant's diagnosis was precise: "The IPC regression suggests the interleaved A+B eval might be hurting rather than helping — the interleaved loop has more complex control flow (min/max calculations, two sets of prefetch, etc.) that could be confusing the branch predictor and defeating the CPU's ability to keep its pipeline full."

This was the critical insight. The interleaved eval, designed to improve ILP, was actually reducing it. The more complex control flow — alternating between two LCs with potentially different lengths, computing min/max to track progress, managing two sets of prefetch pointers — was creating branch prediction difficulties that outweighed any benefit from overlapping the arithmetic chains.

The Controlled Revert: Isolating the Variable

The assistant's response at [msg 1156] was a model of disciplined performance engineering: revert just the interleaved eval while keeping the recycling pool and prefetch, then measure again. This would isolate whether the interleaving was the cause of the IPC regression.

The revert was executed in two edits. At [msg 1157], the assistant modified prover/mod.rs to restore the original two-call pattern using separate eval_with_trackers calls for A and B. At [msg 1157], the assistant restored eval_with_trackers in bellperson's lc.rs. The interleaved function was kept in the codebase but no longer called from the hot path.

The chunk ends with a rebuild at [msg 1158] — a 15.89-second compilation that produced a clean binary with the recycling pool and prefetch intact but the interleaved eval removed. This set the stage for the next round of measurement: would the recycling pool and prefetch alone show the expected improvement once the IPC-regressing interleaving was removed?

The Second Disappointment: Pool Alone Is Flat

The microbenchmark results after reverting the interleaved eval were even more confounding. At [msg 1159], the assistant reported: "Hmm, 55.5s average — actually slightly worse than the Vec baseline (55.4s). The pool+prefetch alone isn't helping."

The recycling pool, which had seemed like such a clear win based on the perf stat data showing 34% alloc/dealloc overhead, was delivering zero improvement. Something was fundamentally wrong with the optimization model. The assistant hypothesized that perhaps the interleaved eval was masking a regression from the pool, or that the prefetch was causing cache pressure that offset the pool's gains. But the simplest explanation was that the bottleneck wasn't where the perf stat aggregate counters suggested.

It was time for deeper profiling.## The perf Revelation: Finding the Real Bottleneck

Rather than continuing to guess, the assistant deployed the heavy artillery: a full perf record with call-graph profiling, capturing 229,841 samples across the 55-second synthesis run ([msg 1165]). The resulting perf report output in message 1167 revealed the truth:

11.14%  ProvingAssignment::enforce
 8.52%  __mulx_mont_sparse_256
 6.82%  UInt32::addmany
 6.51%  Boolean::lc()

The critical finding was Boolean::lc() at 6.51% — a function that creates a fresh LinearCombination from a boolean variable. And critically, the recycling pool showed zero samples in the profile. The pool was sitting unused because the circuit code wasn't building on the recycled lc argument passed into each closure. Instead, it was creating fresh LinearCombination objects inside the closures via Boolean::lc().

A subagent investigation in message 1172 confirmed the pattern: 84% of closures do use the recycled lc argument, but they then call Boolean::lc() inside the closure body to create temporary LCs for individual bits. Each UInt32::addmany calls Boolean::lc() 32 times per operand. For SHA-256, this means thousands of temporary LC allocations inside a single enforce call. The recycling pool addressed the 6 Vecs per enforce, but the real bottleneck was the dozens of temporary LCs created per constraint inside the closures.

As the assistant articulated in message 1173: "The allocation overhead isn't in the 6 Vecs per enforce call — it's in the dozens of temporary LCs created by Boolean::lc() inside the circuit code."

This was the moment of truth. The perf stat aggregate counters showing 34% alloc/dealloc overhead were correct, but they led the assistant to optimize the wrong allocation site. The 34% was real, but it was coming from Boolean::lc() and its downstream callers (UInt32::addmany, SHA-256 gadgets, lookup closures), not from the 6 Vecs that enforce() itself manages. The recycling pool was fighting the wrong battle.

The Strategic Pivot: In-Place Operations

The assistant recognized that the recycling pool was fundamentally the wrong approach. Instead of recycling the 6 Vecs that enforce() itself manages, the optimization needed to target the temporary LCs created by Boolean::lc() inside the circuit code. The solution was to eliminate the allocations entirely by adding methods that operate directly on existing LinearCombination objects.

In message 1175, the assistant added two new methods to Boolean in bellpepper-core/src/gadgets/boolean.rs:

lc = lc + &bit.lc(one, coeff)  // allocates temp LC, adds, then drops

The patched code does:

bit.add_to_lc(one, coeff, &mut lc)  // directly inserts term into lc

This eliminates the Vec allocation, the insert_or_update call on a temporary object, and the subsequent deallocation — all of which were pure overhead. The difference is subtle in code but profound in execution: where the old pattern created a temporary LC, added it to the accumulator, and then dropped it (triggering a deallocation), the new pattern directly inserts the term into the existing LC's internal Vecs. No allocation, no deallocation, no temporary object.

Systematic Patching of Hot Call Sites

With the new methods implemented, the assistant began a systematic campaign to patch every hot call site where Boolean::lc() created temporary allocations inside enforce closures. The pattern was methodical and data-driven: start with the hottest site identified by perf, then work through the remaining targets.

UInt32::addmany (Message 1177)

This was the single hottest call site, accounting for 6.82% of synthesis time. The inner loop at line 352 of uint32.rs contained the pattern lc = lc + &bit.lc(CS::one(), coeff), called 32 times per operand. The fix was a one-line replacement: bit.add_to_lc(CS::one(), coeff, &mut lc). This single edit eliminated the most frequently executed temporary allocation in the entire synthesis pipeline.

Num::add_bool_with_coeff (Message 1183)

Used extensively in SHA-256 and lookup table constructions, this function had the same pattern of creating a temporary LC from a boolean and adding it to a Num's internal LC. Patched to use add_to_lc.

enforce_equal Closures (Message 1185)

The three variant closures in boolean.rs that implement equality constraints used patterns like |_| a.lc(...) that ignored the recycled lc entirely. These were rewritten to use add_to_lc and sub_from_lc on the passed-in lc.

SHA-256 Nonlinear Functions (Messages 1186–1192)

The core SHA-256 nonlinear functions — sha256_ch and sha256_maj — are among the most frequently invoked gadgets in the PoRep circuit. The sha256_ch closure at line 665-670 created up to four temporary LCs per enforce call. The sha256_maj closure at line 803-810 was even worse — all three closures used |_| (ignoring the recycled lc entirely) and built fresh LCs from scratch. These were rewritten to use add_to_lc and sub_from_lc on a single LC, eliminating the allocations entirely.

Lookup Gadget Closures (Messages 1193–1195)

The x-coordinate and y-coordinate lookup enforce closures in lookup.rs, which are part of the SHA-256 circuit hot path, used patterns like + &bits[i].lc::<Scalar>(one, x_coeffs[...]) that created temporary LCs for each bit lookup. Patched to use add_to_lc.

Completing the Coverage (Messages 1196–1199)

The assistant systematically checked for remaining call sites, reading lookup.rs to verify whether the second lookup function (lookup3_xy_with_conditional_negation) used direct .lc() calls or the already-patched add_bool_with_coeff. The multipack.rs call sites were also identified as potential targets. The assistant even caught an import issue — the sub_from_lc method needed to be imported in lookup.rs — demonstrating the attention to detail required for a successful multi-file refactoring.

The Build That Confirms

Message 1200 captures the moment when all these changes come together for compilation. The build succeeded in 16.20 seconds, producing only benign warnings about potential future Rust trait ambiguity. The assistant had made edits across multiple files in two repositories (bellpepper-core and bellperson), adding new methods and patching dozens of call sites. The successful build confirmed that the code was syntactically correct and ready for measurement.

The empty user message at 1201 — a silent acknowledgment — marks the boundary between implementation and measurement. The code is ready. The hypothesis is clear: eliminating temporary LinearCombination allocations at their source will yield a meaningful performance improvement, potentially recovering the 15–25% that the recycling pool failed to deliver.

Lessons in Performance Engineering

This segment of the cuzk development saga offers several enduring lessons for anyone engaged in performance optimization:

1. Profile at the Right Granularity

The perf stat aggregate counters showing 34% alloc/dealloc overhead were correct, but they were misleading. They pointed to "allocation" as the problem but didn't reveal which allocations. Only function-level profiling with perf record and perf report revealed that Boolean::lc() — a function invisible in the aggregate counters — was the true bottleneck. The lesson: aggregate counters are useful for identifying that a problem exists, but only detailed call-graph profiling can identify where the problem is.

2. Trust the Profiler, Not Your Intuition

The assistant's intuition said that the 6 Vecs per enforce call were the dominant allocation cost. This was a reasonable hypothesis based on the available data — the enforce function was the hottest function in the profile, and it created 6 Vecs per call. But the profiler said otherwise. The assistant trusted the data, abandoned the recycling pool (which had been carefully designed and implemented over multiple messages), and pivoted to a more targeted approach. This willingness to discard carefully implemented code when the data contradicts the hypothesis is the hallmark of effective engineering.

3. Eliminate Allocations, Don't Recycle Them

The recycling pool was a reactive approach — catch allocations after they happen and reuse the buffers. The add_to_lc/sub_from_lc approach is proactive — don't allocate in the first place. The latter is almost always more efficient, as it avoids not only the allocation itself but also the cache misses, TLB misses, and allocator bookkeeping that accompany heap operations. The recycling pool also had a fundamental limitation: it could only recycle allocations that enforce() itself controlled. The temporary LCs created inside closures were invisible to the pool and remained unoptimized.

4. Systematic Coverage Matters

After patching the hottest call site (UInt32::addmany), the assistant methodically worked through the remaining targets: Num::add_bool_with_coeff, enforce_equal, sha256_ch, sha256_maj, lookup closures, and the second lookup function. This systematic approach ensures that the optimization delivers its full potential rather than leaving performance on the table. A less disciplined engineer might have stopped after patching UInt32::addmany, leaving the SHA-256 closures unoptimized and missing a significant portion of the potential gain.

5. The Value of Controlled Experiments

When the initial benchmark disappointed, the assistant did not revert all three optimizations. Instead, the assistant used perf stat to identify which optimization was causing the IPC regression, then reverted only that component (the interleaved eval). This is the scientific method applied to software optimization: isolate variables, measure each independently, and draw conclusions from the controlled experiment.

Conclusion

Segment 14 of the cuzk development saga is a complete arc of profiling-driven optimization: hypothesize, implement, measure, reject hypothesis, profile deeper, discover true bottleneck, pivot, implement new approach, and systematically patch all hot call sites. The Vec recycling pool was a reasonable idea based on the available data, but only deeper profiling could reveal that the real bottleneck was hiding one level deeper — inside the closures that the pool could never reach.

The three optimizations that launched this segment — recycling pool, interleaved eval, software prefetch — were all carefully designed and correctly implemented. Yet they delivered at most 1% improvement. The add_to_lc/sub_from_lc approach that replaced them was a direct response to what the profiler revealed: temporary LinearCombination allocations inside closures, not the 6 Vecs per enforce call, were the true bottleneck.

The stage is now set for the next measurement. Whether the new approach delivers the expected improvement remains to be seen, but regardless of the outcome, the methodological lesson stands: in complex systems, intuition about where time is spent is often wrong. The only reliable guide is measurement — and the willingness to follow the data wherever it leads.

References

[1] When Theory Meets Practice: The Disappointing Benchmark That Reshaped a Synthesis Optimization Campaign — [chunk 14.0] [2] The Pivot: When Profiling Revealed the True Bottleneck in Groth16 Synthesis — [chunk 14.1]