The Allocation Hypothesis: When a 250 GB Optimization Delivered Zero Impact

Introduction

In performance engineering, the most humbling moments are not when your optimization fails to improve things — they are when your optimization succeeds in theory but delivers nothing in practice. This is the story of such a moment in the SUPRASEAL_C2 Groth16 proof generation pipeline for Filecoin's Proof-of-Replication (PoRep), where a meticulously traced hypothesis about memory allocation overhead led to a beautifully engineered fix that benchmarked at exactly zero impact.

The investigation unfolded across two major phases. First, the team completed Phase 4 synthesis hot path optimizations — including Boolean::add_to_lc micro-optimization and a novel async deallocation fix for GPU wrapper destructor overhead — achieving a 13.2% end-to-end improvement from 88.9 seconds to 77.2 seconds. Then, emboldened by that success, the team turned to investigate whether allocation overhead during circuit synthesis might mirror the previously fixed deallocation bottleneck. What followed was a deep-dive into bellperson's ProvingAssignment memory allocation patterns that uncovered a dormant optimization infrastructure, a theoretical 250 GB of wasted memory copy, and ultimately, the sobering lesson that not all bottlenecks are created equal.

Phase 4: The Synthesis Hot Path Optimizations

The story begins with the completion of Phase 4, a round of micro-optimizations targeting the CPU synthesis hot path. The team had identified that the Boolean::add_to_lc and Boolean::sub_from_lc methods — which handle adding boolean constraints to linear combinations — were on the critical path. Microbenchmarks showed that optimizing these methods dropped synthesis time from ~55.4 seconds to ~50.9 seconds, an 8.3% improvement [1]. The perf stat counters confirmed the win: 91 billion fewer instructions (-15.3%) and 18.6 billion fewer branches (-26.7%).

But the real prize came from an unexpected direction. When the team ran a full end-to-end proof to validate the synthesis improvements, they discovered a GPU wrapper regression: the GPU phase had gone from 34.0 seconds to 36.0 seconds, despite identical CUDA kernel internal timing (~26 seconds). This 10-second gap was a mystery — the C++ wrapper was somehow adding 10 seconds of overhead that didn't exist before.

The root cause, traced through careful instrumentation of the C++ code, was synchronous destructor overhead. When the GPU proving phase completed, the C++ wrapper freed approximately 37 GB of C++ vectors (split_vectors, tail_msm bases) and ~130 GB of Rust Vecs (ProvingAssignment a, b, c) — all in the destructor of the wrapper function. This synchronous deallocation blocked the calling thread for seconds, inflating the apparent GPU time.

The fix was elegant: move these large deallocations into detached threads on both the C++ and Rust sides, allowing the function to return immediately while deallocation happens in the background. After this fix, the GPU wrapper time dropped to 26.2 seconds — matching the CUDA internal timing exactly. The total end-to-end time improved to 77.2 seconds, a 13.2% reduction from the 88.9-second baseline. All Phase 4 changes, including Boolean::add_to_lc, async deallocation, a Vec recycling pool, software prefetch, and A4/D4 CUDA changes, were committed as 2da2a901.

The story begins with the completion of Phase 4, a round of micro-optimizations targeting the CPU synthesis hot path. The team had identified that the Boolean::add_to_lc and Boolean::sub_from_lc methods — which handle adding boolean constraints to linear combinations — were on the critical path. Microbenchmarks showed that optimizing these methods dropped synthesis time from ~55.4 seconds to ~50.9 seconds, an 8.3% improvement. The perf stat counters confirmed the win: 91 billion fewer instructions (-15.3%) and 18.6 billion fewer branches (-26.7%).

The Allocation Hypothesis: A Natural Next Step

The async deallocation fix had been a triumph of identifying hidden overhead. The team had found that freeing multi-gigabyte buffers synchronously was a bottleneck, and moving that work to background threads unlocked a significant win. The natural question followed: if deallocation was a bottleneck, could allocation be one too?

The hypothesis was compelling. During circuit synthesis, bellperson's ProvingAssignment accumulates constraint evaluations into five main Vecs: a, b, c, input_assignment, and aux_assignment. For a 32 GiB PoRep C2 proof with ~130 million constraints across 10 partitions, each of the a, b, c Vecs grows to ~4.17 GB (130 million 32-byte Scalars). If these Vecs grow organically via Rust's standard doubling strategy, each would undergo approximately 27 reallocations, each time allocating a new buffer, copying the old data, and freeing the old buffer. The total wasted copy work across all 10 partitions: approximately 250 GB.

A subagent was dispatched with a focused mission: "Investigate synthesis allocation (agent: explore)." The user's question was surgically precise — exact code with line numbers showing how each Vec is initialized and grown, and whether capacity is pre-allocated or not.

The Investigation: Tracing the Call Chain

The subagent's investigation unfolded systematically across multiple rounds of tool calls ([msg 1] through [msg 18]). It began by reading the three key source files: bellperson/src/groth16/prover/mod.rs (the ProvingAssignment struct), bellperson/src/groth16/prover/supraseal.rs (the CUDA-accelerated prover wrapper), and cuzk/cuzk-core/src/pipeline.rs (the Curio orchestration layer).

The first discovery was that ProvingAssignment has two constructors. The default new() method (lines 160-172 of mod.rs) initializes all Vecs with vec![] — zero capacity. But there is also new_with_capacity() (lines 125-155 of mod.rs) which accepts num_constraints, num_aux, and num_inputs parameters and pre-allocates all Vecs and DensityTracker BitVecs to their final sizes. The infrastructure for pre-allocation exists.

The second discovery was the SynthesisCapacityHint struct (line 134 of supraseal.rs), which carries the expected constraint and variable counts. The function synthesize_circuits_batch_with_hint() (lines 164-235 of supraseal.rs) accepts an Option<SynthesisCapacityHint> and branches: if a hint is provided, it calls new_with_capacity(); if None, it falls back to new().

The critical question was: does any caller actually pass a hint? The subagent traced the call chain from pipeline.rs downward. Every call site — at lines 396, 596, 737, 940, 1135, and 1313 — uses synthesize_circuits_batch(), the non-hint variant. This function (line 159 of supraseal.rs) simply delegates to _with_hint(circuits, None). The hint is always None.

A grep for _with_hint and SynthesisCapacityHint across the entire codebase returned "No files found" ([msg 11]). The infrastructure was entirely dormant — a fully functional pre-allocation mechanism that had never been wired up.

Implementing the Fix

With the diagnosis confirmed, the assistant implemented a global hint cache and modified all six synthesis call sites in pipeline.rs to use synthesize_circuits_batch_with_hint, passing the known constraint and variable counts. The fix was clean: the constraint counts are deterministic for a given sector size, so the hints could be computed once and cached. The infrastructure was committed as a defensive optimization — theoretically eliminating ~265 GB of redundant memory copies across 10 parallel circuits.

The Benchmark: Zero Impact

Then came the moment of truth. Rigorous benchmarking was performed — single-partition synth-only tests and full end-to-end proofs with the daemon. The result: synthesis time was 50.65 seconds with and without the capacity hints. Zero measurable impact.

How could eliminating ~27 reallocations per Vec, saving ~250 GB of memcpy work, have no effect? The answer lies in the fundamental asymmetry of allocation versus deallocation in Rust. The geometric doubling strategy of Vec::push() amortizes the cost of reallocation across the lifetime of the vector. Each element is copied approximately twice on average (the sum of the geometric series 1 + 1/2 + 1/4 + ... ≈ 2). For 130 million 32-byte Scalars, that's about 8.34 GB of copying per Vec — but this copying happens incrementally, interleaved with the actual computation of constraint evaluations. The memory bandwidth is already saturated by the synthesis computation itself, so the reallocations overlap with useful work and add no measurable wall-clock time.

The previous deallocation win was different. When the GPU phase completed, the destructors ran synchronously, freeing ~37 GB of C++ vectors and ~130 GB of Rust Vecs in a single blocking call. This was not amortized — it was a concentrated burst of munmap system calls that stalled the thread for seconds. The fix (async deallocation) worked because it removed a synchronous bottleneck, not because it reduced the total amount of memory work.

The Deeper Lesson

This investigation delivered a profound lesson about performance optimization: not all theoretically wasteful operations are actual bottlenecks. The ~250 GB of memcpy from Vec reallocation is real — the CPU does copy that data — but it is hidden beneath the computational cost of synthesis. The synthesis bottleneck is purely computational: evaluating 130 million constraints, each requiring SHA-256 bit manipulation, Fr field arithmetic, and linear combination evaluation. The memory allocation overhead is a rounding error against this compute cost.

The finding also validated the team's optimization strategy. Phase 4's wins came from reducing computational work (Boolean::add_to_lc saved 91 billion instructions) and eliminating synchronous blocking (async deallocation). Phase 5 would need to target the computational hotpath itself — perhaps through Parallel Circuit Evaluation (PCE) or other techniques that reduce the raw instruction count.

The allocation infrastructure — SynthesisCapacityHint, new_with_capacity, and the global hint cache — remains committed as a defensive optimization. It costs nothing to maintain and could become relevant if the computational bottleneck is ever reduced to the point where allocation overhead matters. But for now, the team knows exactly where the real bottleneck lies.

Conclusion

The SUPRASEAL_C2 allocation investigation is a case study in the importance of measurement over intuition. A compelling hypothesis — that Vec reallocation overhead mirrors the previously fixed deallocation bottleneck — was systematically investigated, found to have a theoretical basis, and tested with a clean implementation. The benchmark results were unambiguous: zero impact. The synthesis bottleneck is computational, not allocational.

This outcome is not a failure. It is knowledge. The team now knows that they can stop worrying about Vec pre-allocation and focus their optimization efforts where they will actually matter: the computational hotpath of circuit synthesis. The defensive optimization is in place for future scenarios where the balance might shift. And the methodology — trace the call chain, quantify the theoretical cost, implement the fix, benchmark rigorously — is a template for future investigations.

In the broader narrative of the SUPRASEAL_C2 optimization effort, this chapter closes with a clear direction: Phase 5 must target the computational kernel. The allocation hypothesis has been tested and found wanting. The real work lies ahead.## References

[1] "Opening the Black Box: The First Probe into Bellperson's Memory Allocation" — [chunk 15.1] article analyzing the initial file reads that began the allocation investigation.

[2] "The Hunt for Capacity Hints: A Targeted Grep Investigation into Bellperson's Memory Allocation" — [chunk 15.1] article documenting the grep search that revealed the dormant SynthesisCapacityHint infrastructure.

[3] "The Missing Hint: How a Single Grep Confirmed 250 GB of Wasted Memory Copy" — [chunk 15.1] article capturing the moment when the grep for _with_hint returned "No files found."

[4] "Confirming the Absence of Capacity Pre-allocation: A Critical Verification in the SUPRASEAL_C2 Pipeline Investigation" — [chunk 15.1] article on the verification that pipeline.rs uses the non-hint variant.

[5] "The Hidden Cost of Growth: How Vec Reallocation Shapes Memory in Groth16 Proof Synthesis" — [chunk 15.1] article quantifying the ~27 reallocations per Vec and ~250 GB wasted copy work.

[6] "The Moment the Lens Shifted: Tracing LC Pooling in bellperson's Synthesis Pipeline" — [chunk 15.1] article on the discovery of the LinearCombination buffer recycling mechanism.

[7] "Peering into the DensityTracker: A Pivotal Bash Command in the Memory Allocation Investigation" — [chunk 15.1] article documenting the DensityTracker::new() implementation with zero-capacity BitVec.

[8] "The Recycled Buffer: Tracing Memory Allocation in Bellperson's Groth16 Synthesis Pipeline" — [chunk 15.1] article on the from_recycled and recycle methods for LC buffer pooling.

[9] "The Allocation Question: Tracing Memory Growth in Bellperson's ProvingAssignment" — [chunk 15.1] article analyzing the user's precise query about Vec pre-allocation.

[10] "The Confirmation and Pivot: Tracing Memory Allocation in Bellperson's Groth16 Synthesis Pipeline" — [chunk 15.1] article on the confirmation that all pipeline callers use the non-hint variant.