When Theory Meets Practice: The Disappointing Benchmark That Reshaped a Synthesis Optimization Campaign

Introduction

In the high-stakes world of cryptographic proof generation, a 15–25% performance improvement is the kind of number that makes engineers sit up straight. When the perf stat analysis of the cuzk proving engine's synthesis hot path revealed that roughly 34% of runtime was consumed by jemalloc allocation and deallocation in the enforce hot loop, the path forward seemed clear: eliminate those allocations, interleave the arithmetic for better instruction-level parallelism, and sprinkle in some software prefetch for good measure. The expected payoff was substantial.

What actually happened was something far more instructive. This chunk of the optimization session documents the implementation of three carefully designed synthesis optimizations, their disappointing ~1% measured improvement, and the diagnostic pivot that followed. It is a case study in the gap between theoretical optimization and empirical reality — and a testament to the discipline required to bridge that gap.

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 ~34% of synthesis runtime. Each call to enforce — the hottest function in the entire proving pipeline — created three LinearCombination objects, each containing two Vecs (one for input terms, one for auxiliary terms). These were immediately dropped after evaluation, generating a torrent of malloc/free calls. 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.

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."

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 Implementation: From Design to Code

The implementation spanned multiple files across two crates, requiring careful coordination. The assistant worked methodically through the dependency chain.

In bellpepper-core (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.

In bellperson (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]. The assistant also had to update the Debug and PartialEq implementations (see [msg 1134], [msg 1135], [msg 1136]) to account for the new lc_pool field while ensuring equality semantics remained correct.

In bellperson (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 Moment of Measurement: A 1% Disappointment

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

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?

Lessons in Performance Engineering

This chunk is a microcosm of the performance engineering discipline. Several lessons emerge:

1. Design is not prediction. The interleaved eval was a theoretically sound optimization — overlapping independent arithmetic chains should improve ILP. But theory must yield to measurement. The actual hardware behavior (branch mispredictions, cache pressure, pipeline utilization) can defy simple mental models.

2. The value of controlled experiments. The assistant did not revert all three optimizations when the benchmark disappointed. Instead, the assistant used perf stat to identify which optimization was causing the regression, then reverted only that component. This is the scientific method applied to software optimization: isolate variables, measure each independently.

3. Hardware counters are the microscope. Without perf stat, the assistant would have known only that the optimizations didn't work. With hardware counters, the assistant could see why: instructions dropped 4.1% (good), but IPC dropped 2.7% (bad). The counters revealed that the recycling pool was working as designed — it was the interleaving that was counterproductive.

4. The recycling pool was not wasted effort. The 4.1% instruction reduction and 10.4% branch reduction confirmed that the Vec recycling pool was eliminating jemalloc overhead. The fact that this didn't translate to a proportional speedup suggests that either (a) the jemalloc allocator was more efficient than expected (perhaps using thread-local caches), or (b) the bottleneck was elsewhere — perhaps in the LinearCombination arithmetic itself rather than the allocation overhead. The assistant's next steps would need to investigate this further.

Conclusion

The three-word directive "Implement 1/2/3" launched a complex optimization campaign that touched two crates, multiple files, and required careful design reasoning about memory management, CPU microarchitecture, and Rust's type system. The implementation was thorough and correct. The benchmark was honest. The diagnosis was precise.

The ~1% improvement was disappointing, but the real value of this chunk lies in what happened after the disappointment: the disciplined pivot from implementation to diagnosis, the use of hardware counters to understand the discrepancy, and the controlled revert to isolate the root cause. This is performance engineering at its most rigorous — not the triumph of a successful optimization, but the methodical unraveling of why an optimization didn't work as expected.

The story continues in the next chunk, where the assistant would measure the recycling-pool-only configuration and discover that the real bottleneck lay not in Vec allocation at all, but in temporary LinearCombination objects created inside closures via Boolean::lc() and similar methods — a finding that would redirect the entire optimization campaign toward a different approach entirely.