The Counterintuitive Case of SmallVec: When Fewer Instructions and Fewer Cache Misses Still Lose

Introduction

In the high-stakes world of Filecoin proof generation optimization, every millisecond counts. The cuzk proving engine, a pipelined Groth16 prover for Filecoin's Proof-of-Replication (PoRep) protocol, had already undergone three phases of optimization—batch-mode synthesis, async overlap between CPU and GPU, and cross-sector batching—each delivering measurable throughput improvements. Phase 4 was supposed to be the compute-level optimization wave, targeting the hottest CPU paths in the constraint synthesis pipeline.

But optimization is never straightforward. In message 1078 of this coding session, the assistant presents a perf stat comparison that tells a deeply counterintuitive story: an optimization that reduces instructions by 7%, reduces L3 cache misses by 27.5%, and reduces L1D fills from L3 by 58.6% still ends up making the code slower. This message is a masterclass in why hardware counter analysis matters, why intuition about "fewer cache misses = faster" is dangerously incomplete, and how Zen4's out-of-order execution engine punishes complex control flow regardless of memory hierarchy improvements.

The Subject Message: A perf stat Showdown

The message at the center of this analysis is a concise but data-rich report. The assistant had been investigating why the SmallVec optimization (codenamed A1) was performing worse than the original Vec implementation, despite the intuitive expectation that inline storage would reduce cache misses and improve performance. The message presents the evidence:

Here's the perf stat comparison — SmallVec cap=2 vs Vec (original):

>

### perf stat Results: SmallVec cap=2 vs Vec

>

| Counter | SmallVec cap=2 (avg of 2) | Vec (avg of 2) | Delta | |---|---|---|---| | Synthesis time | 56.5s | 55.5s | +1.8% slower | | Instructions | 552.0B | 593.8B | -7.0% (fewer!) | | Cycles | 232.1B | 228.4B | +1.6% | | IPC | 2.38 | 2.60 | -8.5% worse | | Branch instructions | 69.8B | 69.8B | ~same | | Branch misses | 184.6M | 188.0M | -1.8% (trivial) | | cache-references (LLC) | 6.58B | 6.93B | -5.0% | | cache-misses (LLC) | 107.6M | 148.4M | -27.5% | | L2 DC accesses | 4.93B | 4.98B | -0.9% | | L2 DC hits | 4.84B | 4.85B | ~same | | L1D fills from L2 | 1.37B | 2.23B | -38.4% | | L1D fills from L3/CCX | 50.7M | 122.5M | -58.6% | | DRAM fills | 5.2M | 6.4M | -17.5% |

>

### Analysis

>

The data tells a counterintuitive but clear story:

>

1. SmallVec has FEWER cache misses at every level — L2, L3, and DRAM fills are all lower. The inline storage does keep data closer to the core. 2. But SmallVec executes 7% fewer instructions while taking 1.6% more cycles. This means IPC dropped from 2.60 to 2.38 — a massive 8.5% IPC regression. 3. Branch misses are essentially identical (~184-188M), so that's not the cause. 4. The root cause is instruction-level parallelism degradation, not cache misses. SmallVec's enum discriminant checks, size-dependent branching, and larger stack frames defeat Zen4's out-of-order execution window. Vec's simple pointer-chasing code is highly predictable and the OOO engine handles the resulting cache misses efficiently by overlapping them.

>

Bottom line: On Zen4 with jemalloc, Vec's simpler instruction stream yields higher IPC that more than compensates for its extra cache misses. SmallVec is the wrong optimization for this workload. A1 is definitively cancelled.

>

The revert to Vec is already done (both lc.rs and Cargo.toml). Now let's run the final E2E test with only the beneficial changes (A4 parallel B_G2, D4 per-MSM window, max_num_circuits=30).

The Context: Why This Message Was Written

To understand why message 1078 exists, we need to trace the arc of Phase 4 optimization. The cuzk proving engine had been built through three successful phases. Phase 1 implemented batch-mode PoRep C2 synthesis. Phase 2 added async overlap between CPU synthesis and GPU proving, achieving a 1.27x throughput improvement. Phase 3 implemented cross-sector batching with a BatchCollector, achieving a 1.46x throughput improvement.

Phase 4 was the compute-level optimization wave, targeting the hottest paths identified through profiling. The team had created a detailed optimization proposal document (c2-optimization-proposal-4.md) that outlined several candidate optimizations. Four were implemented in rapid succession:

The Reasoning and Motivation

The assistant's motivation in writing this message is threefold. First, and most immediately, the message serves as a decision document. After days of investigation—building microbenchmarks, reverting changes, collecting data—the assistant needed to definitively answer whether A1 should be included in the final Phase 4 commit. The perf stat data provides an unambiguous answer: no.

Second, the message is a knowledge artifact for the broader project. The cuzk proving engine is a complex system spanning Go, Rust, C++, and CUDA code. Understanding how microarchitectural decisions interact with the workload is critical for future optimization work. The message explicitly documents the counterintuitive finding that "Vec's simpler instruction stream yields higher IPC that more than compensates for its extra cache misses." This is not just a data point—it's a reusable insight that will inform future optimization decisions across the entire codebase.

Third, the message serves as a transition point in the workflow. The assistant had a todo list with four items: (1) collect perf stat data, (2) revert A1, (3) run final E2E test, (4) commit Phase 4. Messages 1055–1077 completed items 1 and 2. Message 1078 presents the results of item 1, confirms item 2 is done, and kicks off item 3. The todo list embedded in the message shows the status update: items 1 and 2 are completed, item 3 is now in progress.

The Decisions Made in This Message

Several decisions are made or confirmed within message 1078 itself:

  1. A1 is definitively cancelled. This is the primary decision. The assistant states it unequivocally: "A1 is definitively cancelled." This decision is backed by the perf stat data showing that SmallVec is 1.8% slower than Vec, despite reducing instructions and cache misses.
  2. The revert to Vec is confirmed complete. The assistant notes that the revert has already been applied to both lc.rs and Cargo.toml. This was done in messages 1067–1073, and message 1078 confirms the state.
  3. The next step is the final E2E test. The assistant transitions from the A1 investigation to running the end-to-end GPU test with only the beneficial changes (A4, D4, max_num_circuits=30). This is the validation step before committing Phase 4.
  4. The root cause explanation is accepted. The assistant proposes that SmallVec's "enum discriminant checks, size-dependent branching, and larger stack frames defeat Zen4's out-of-order execution window." This is not proven with additional data in this message, but it's the working hypothesis that explains the observed IPC regression.

Assumptions and Potential Mistakes

The message contains several assumptions worth examining:

Assumption 1: The IPC regression is caused by control flow complexity. The assistant attributes the IPC drop from 2.60 to 2.38 to SmallVec's "enum discriminant checks, size-dependent branching, and larger stack frames." While this is a plausible explanation, the message doesn't include additional data to confirm it. A deeper analysis using perf annotate or instruction-level profiling would be needed to pinpoint exactly which instructions are stalling the pipeline. The branch miss count is essentially identical between the two configurations, which rules out branch mispredictions as the cause, but doesn't directly confirm the control flow complexity hypothesis.

Assumption 2: The two runs per configuration are sufficient for statistical significance. The assistant ran two perf stat runs for each configuration. While the results are consistent (55.8s and 57.1s for SmallVec, 55.4s and 55.5s for Vec), there's notable variance in the SmallVec runs (1.3s difference). A larger sample size would strengthen the conclusion, though the perf stat hardware counters are typically very stable across runs.

Assumption 3: The synth-only microbenchmark is representative of the full pipeline. The assistant uses --partition 0 -i 1 which runs a single partition for one iteration. This is a small slice of the full proof generation (which has 10 partitions). The assumption is that the per-partition behavior is representative of the whole. This is reasonable for CPU synthesis optimization, but it's worth noting that the full pipeline includes GPU work, SRS loading, and other phases that might interact differently with the memory subsystem.

Assumption 4: Zen4 behavior generalizes to other architectures. The analysis is specific to AMD Zen4 (the test machine's CPU). The conclusion that "SmallVec is the wrong optimization for this workload" is qualified by "On Zen4 with jemalloc." On Intel architectures with different cache hierarchies and OOO execution engines, or with different allocators, the results could differ. The message implicitly acknowledges this by specifying the platform.

Potential mistake: The IPC comparison may conflate multiple effects. The SmallVec configuration executes 7% fewer instructions but takes 1.6% more cycles. The IPC drop from 2.60 to 2.38 is calculated from these aggregate numbers. However, IPC is a complex metric that can be affected by many factors simultaneously. The reduction in instructions might come from different parts of the code than the increase in cycles. Without instruction-level breakdowns, it's possible that the instruction reduction is in fast paths while the cycle increase is in slow paths, making the IPC comparison less informative than it appears.

Input Knowledge Required

To fully understand message 1078, several pieces of context are necessary:

What is SmallVec? SmallVec is a Rust crate that provides a SmallVec type—a Vec-like container that stores elements inline (on the stack) up to a configurable capacity, falling back to heap allocation only when that capacity is exceeded. The cap=2 variant stores up to 2 elements inline. For the LinearCombination type in bellpepper-core, which typically holds 1–3 terms, SmallVec should eliminate most heap allocations.

What is LinearCombination? In the bellperson constraint system, a LinearCombination represents a weighted sum of variables: a₁·v₁ + a₂·v₂ + ... + aₙ·vₙ. It's stored as a Vec<(Variable, Fr)> where Fr is a field element. During synthesis, thousands of LinearCombinations are created and manipulated, making their memory layout and allocation patterns critical for performance.

What is IPC? Instructions Per Cycle is a measure of how many CPU instructions are executed per clock cycle. Modern out-of-order processors can sustain IPC > 1 by executing multiple instructions in parallel when they have no data dependencies. Zen4 has a wide OOO engine capable of high IPC on well-optimized code. The drop from 2.60 to 2.38 represents an 8.5% reduction in execution efficiency.

What is jemalloc? jemalloc is a memory allocator optimized for multi-threaded workloads. It's commonly used in Rust projects as an alternative to the system allocator. The fact that the code uses jemalloc is relevant because SmallVec's primary benefit—reducing heap allocations—may be less impactful when jemalloc already handles small allocations efficiently.

What are L1D fills from L2 vs L3/CCX? These are AMD-specific perf events that track where data is coming from when it fills the L1 data cache. "L1D fills from L2" means the data was found in the L2 cache (a relatively fast hit). "L1D fills from L3/CCX" means the data came from the L3 cache or another CCX (Core Complex), which is slower. The dramatic reduction in L3/CCX fills (58.6%) with SmallVec suggests that inline storage keeps data in closer caches.

Output Knowledge Created

Message 1078 creates several important pieces of knowledge:

  1. A validated negative result: SmallVec is slower than Vec for this workload on Zen4. This is valuable because negative results are often underreported but critical for guiding future work. Future optimizers on this project won't waste time re-evaluating SmallVec.
  2. A methodology for optimization evaluation: The message demonstrates a rigorous approach: use a synth-only microbenchmark to isolate the variable, collect hardware counter data with perf stat, compare multiple runs for consistency, and analyze the root cause rather than just the surface-level timing.
  3. A reusable insight about IPC vs cache misses: The finding that "Vec's simpler instruction stream yields higher IPC that more than compensates for its extra cache misses" is a general principle that applies beyond this specific optimization. It suggests that on Zen4, code clarity and predictability can be more important than memory hierarchy optimization.
  4. A documented decision point: The message serves as a permanent record that A1 was evaluated, found to be detrimental, and cancelled. This prevents future confusion about why SmallVec isn't used in the codebase.
  5. Hardware counter baselines: The perf stat numbers provide reference points for future optimization work. If someone later proposes a different memory layout optimization, they can compare against these baselines.

The Thinking Process

The assistant's reasoning in message 1078 is structured and methodical. Let me trace the thinking:

Step 1: Present the data. The assistant leads with the perf stat comparison table, organizing 12 metrics across two configurations. The table is carefully structured with the counter name, both values, and the delta. The use of bold for key deltas (1.8% slower, 7.0% fewer instructions, 8.5% IPC regression, etc.) guides the reader's attention to the most important numbers.

Step 2: Identify the paradox. The assistant explicitly notes the counterintuitive nature of the finding: "SmallVec has FEWER cache misses at every level" but is still slower. This framing acknowledges that the result defies conventional wisdom, which makes the analysis more credible.

Step 3: Eliminate obvious explanations. The assistant checks branch misses and finds them essentially identical, ruling out branch misprediction as the cause. This is good detective work—eliminating the easy explanations before diving into the complex ones.

Step 4: Propose the root cause. The assistant attributes the IPC regression to SmallVec's "enum discriminant checks, size-dependent branching, and larger stack frames." This is a hypothesis about why the control flow is more complex. The reasoning is that SmallVec is implemented as an enum (either inline or heap-backed), and every access requires checking which variant is active. This adds conditional branches and reduces the effective size of the out-of-order execution window.

Step 5: Draw the conclusion. The bottom line is stated clearly: "Vec's simpler instruction stream yields higher IPC that more than compensates for its extra cache misses." This is the key insight—it's not about cache misses, it's about instruction-level parallelism.

Step 6: Confirm the action taken. The assistant notes that the revert is already done, demonstrating that analysis has already been translated into action.

Step 7: Transition to the next step. The message ends by kicking off the final E2E test, keeping the workflow moving.

Broader Implications

The lesson of message 1078 extends far beyond this specific optimization. It's a reminder that performance optimization is not about applying generic rules ("inline storage is faster") but about understanding the specific interaction between the workload, the microarchitecture, and the software stack.

On Zen4, the out-of-order execution engine is extraordinarily powerful. It can hide memory latency by overlapping independent cache misses, execute multiple instructions per cycle from a wide instruction window, and speculate past branches with high accuracy. But this power comes with a vulnerability: complex control flow with unpredictable data-dependent branches can collapse the instruction window, reducing the OOO engine's ability to find parallel work.

Vec, for all its pointer chasing and cache misses, has a simple, predictable instruction stream. The load instructions that miss cache don't stall the pipeline because the OOO engine can execute other instructions around them. SmallVec, by contrast, has a more complex instruction stream with discriminant checks and size-dependent paths that fragment the instruction window, reducing the OOO engine's reach.

This is a profound insight that applies to many optimization scenarios. It explains why "obvious" optimizations like custom allocators, inline storage, or manual unrolling can backfire on modern CPUs. The message's true value is not in proving that SmallVec is bad for this one workload, but in demonstrating a mindset: measure at the hardware level, question your assumptions, and understand why before you decide what.

Conclusion

Message 1078 is a small but perfect example of data-driven optimization. It presents a clear paradox, eliminates obvious explanations, proposes a root cause, and makes a definitive decision. The perf stat data is presented cleanly, the analysis is logical, and the conclusion is unambiguous. The message also serves as a workflow transition point, keeping the project moving forward.

The counterintuitive finding—that fewer cache misses and fewer instructions can still result in slower execution—is a valuable contribution to the project's collective knowledge. It will inform future optimization decisions and prevent wasted effort on similar approaches. And it demonstrates that in the complex world of modern CPU microarchitecture, the simplest code is often the fastest code.