The 3.2-Second Bottleneck: Diagnosing Parallelism in a 130M-Constraint R1CS MatVec

Introduction

In the high-stakes world of Filecoin proof-of-replication (PoRep) proving, every millisecond counts. The proving pipeline processes circuits with 130 million constraints and 722 million non-zero entries — numbers that would make most database administrators blanche. When the Pre-Compiled Constraint Evaluator (PCE), a carefully architected optimization designed to deliver 3–5× speedups, was actually running slower than the baseline (61.1 seconds versus 50.4 seconds), something had gone fundamentally wrong. Message 1444 of this coding session captures the moment of diagnosis: a deep-dive into why the PCE's matrix-vector (MatVec) evaluation was underperforming, and the critical decision about whether and how to parallelize it.

This message is a masterclass in systems-level performance debugging. It demonstrates how a developer, armed with precise measurements and a deep understanding of hardware characteristics, can reason about performance at the level of CPU cycles, memory bandwidth, and cache behavior — all before writing a single line of changed code.

Context: The PCE Pipeline and the Performance Mystery

To understand message 1444, we must first understand what the PCE does and why it was expected to be faster. The Pre-Compiled Constraint Evaluator is the centerpiece of Phase 5 of the cuzk proving engine optimization project. Its core insight is that the R1CS constraint structure — the A, B, and C matrices that define the circuit — is purely a function of circuit topology, not of any particular witness assignment. This means the constraint matrices can be extracted once, serialized to disk, and reused for every subsequent proof of the same circuit type. The old path had to re-derive this structure during each proof, paying the cost of constraint evaluation inside the bellperson framework's ProvingAssignment::enforce() method.

The PCE replaces this with a two-phase approach: first, a lightweight WitnessCS synthesis that only computes witness values (26.7 seconds for 10 circuits in parallel), followed by a CSR (Compressed Sparse Row) MatVec multiplication that applies the pre-computed constraint matrices to the witness vector (34.3 seconds for 10 circuits sequentially). The total: 61.1 seconds, compared to 50.4 seconds for the old path.

The previous message ([msg 1443]) had already identified the structural problem: the MatVec evaluation was running each of the 10 partition circuits sequentially via .into_iter().map(...), despite a comment in the code claiming it was "parallel across circuits." Message 1444 picks up this thread and dives into the performance characteristics to determine the right fix.

The Diagnostic Journey

The message opens with a direct observation of the code:

Found it — line 404-409: witnesses.into_iter().map(...) — that's a sequential iterator, not a parallel one. The comment says "parallel across circuits" but it uses .into_iter() not .into_par_iter().

This is the classic "comment lies" problem — the code's intent (parallel execution) was documented but never implemented. However, the assistant immediately recognizes that simply swapping .into_iter() for .into_par_iter() is not a trivial decision:

However, there's a subtlety: each evaluate_pce call internally uses rayon::join for A/B/C parallelism, which already saturates all cores. Running 10 circuits in parallel with rayon inside each would cause oversubscription.

This is the critical insight. The assistant understands that rayon, Rust's popular data-parallelism library, uses a global thread pool. If each evaluate_pce call already uses rayon::join to parallelize the A, B, and C matrix evaluations across all available cores, then launching 10 such evaluations simultaneously would create 10× the number of tasks competing for the same 96 CPU cores. The result would be thread oversubscription, context-switching overhead, and potentially worse performance.

This reasoning shows a sophisticated understanding of how work-stealing thread pools behave under nested parallelism. The assistant correctly identifies that the naive fix — just making the outer loop parallel — could backfire.

The Back-of-the-Envelope Calculation

What follows is perhaps the most impressive section of the message: a full back-of-the-envelope performance model of the MatVec kernel, computed from first principles:

Let me think about this differently. The total work is 722M nnz × ~55 cycles/nnz = 39.7 billion cycles. At 3.5 GHz × 96 cores = 336 GFLOP/s theoretical, that's 0.12s compute. But we're getting 3.2s — 26x slower than compute-bound. This is clearly memory-bandwidth-bound.

This calculation reveals several assumptions and insights:

  1. The ~55 cycles/nnz estimate: This is an assumption about the cost of processing each non-zero entry. It includes the column index lookup, the coefficient multiplication, the addition to the accumulator, and the loop overhead. This number comes from the assistant's understanding of the generated code and typical CPU pipeline behavior for sparse linear algebra kernels.
  2. The 3.5 GHz clock rate: This is an assumption about the CPU frequency of the target machine (likely an AMD Threadripper or EPYC processor based on the 96-core count mentioned elsewhere).
  3. The conclusion that it's memory-bandwidth-bound: The 26× gap between theoretical compute throughput and actual performance is a classic signature of a memory-bound kernel. The assistant correctly identifies that the bottleneck is not computation but data movement. The assistant then refines the model:
For bandwidth: reading 722M nnz × (4B col + 32B val) = 26 GB of matrix data + 722M random 32-byte witness lookups. At ~200 GB/s DRAM bandwidth on this Threadripper, the matrix scan alone is ~0.13s. The random witness accesses are the bottleneck.

This is where the analysis gets really interesting. The assistant breaks down the data access pattern:

The Decision: Sequential or Parallel?

After this analysis, the assistant arrives at a nuanced conclusion:

Running circuits in parallel won't help — they'd just compete for memory bandwidth. But running the 10 MatVecs sequentially when the witness data is all in DRAM means we're paying the full random-access penalty each time.

Wait — this seems contradictory. If parallel execution would compete for bandwidth, why would it help? The assistant catches this and refines the reasoning:

If I make the 10 MatVecs truly parallel using rayon's par_iter (not nested rayon), the memory bandwidth sharing would still be better than sequential since different circuits access different witness vectors (different cache lines).

This is the key insight: different circuits have different witness vectors. When circuit 0 is running, it accesses witness vector 0, which is 4.2 GB of data. When circuit 1 runs next, it accesses witness vector 1 — a completely different 4.2 GB of data. The cache is effectively cold for each sequential circuit. But if all 10 circuits run simultaneously, each CPU core works on a different circuit's witness data, and the combined working set is 42 GB spread across all cores' cache hierarchies. The memory bandwidth is shared, but the cache utilization is better because each core repeatedly accesses the same small portion of its circuit's witness vector.

This is a subtle point that many developers would miss. The assistant correctly reasons that parallel execution across circuits is beneficial not because it increases compute throughput (which is already saturated), but because it improves cache utilization by interleaving accesses to different data sets.

The Decision to Try Parallel Execution

The message concludes with a decisive action:

Let me try it: [edit] /home/theuser/curio/extern/cuzk/cuzk-core/src/pipeline.rs

The assistant changes the sequential iterator to a parallel one, but importantly, the edit is described as a trial — "let me try it" — indicating an awareness that the performance model needs empirical validation. The assistant has reasoned through the trade-offs and arrived at a hypothesis, but is humble enough to know that real hardware doesn't always follow the model.

Assumptions and Potential Mistakes

Several assumptions underpin this analysis:

  1. The ~55 cycles/nnz estimate: This is an educated guess, not a measurement. If the actual cost per non-zero is significantly different, the compute-bound calculation changes.
  2. The 200 GB/s DRAM bandwidth: This is a theoretical peak for the Threadripper platform. Real-world bandwidth is typically lower due to memory controller overhead, NUMA effects, and the mixed read/write pattern.
  3. The random-access pattern is the bottleneck: The assistant assumes that the witness vector accesses are uniformly random and fully latency-bound. If there's any spatial locality in the column indices (which is common in R1CS circuits due to how constraints are generated), the actual cache behavior could be better than modeled.
  4. Rayon's nested parallelism behavior: The assistant assumes that rayon::join inside each evaluate_pce call would oversubscribe the thread pool if 10 circuits run in parallel. This depends on the specific rayon configuration and how join interacts with the work-stealing scheduler. In practice, rayon's join is designed to handle nested parallelism efficiently through work stealing — it doesn't necessarily create new threads, it just splits the current task. The oversubscription concern may be less severe than assumed.
  5. The memory bandwidth sharing model: The assistant assumes that parallel execution across circuits improves cache utilization. This is plausible but depends on the cache hierarchy (L2/L3 sizes, associativity, replacement policy) and the access pattern of each circuit's MatVec.

Input Knowledge Required

To fully understand this message, a reader needs:

  1. R1CS and Groth16 basics: Understanding that a constraint system has A, B, C matrices and a witness vector, and that proving involves evaluating these matrices against the witness.
  2. CSR sparse matrix format: Understanding how Compressed Sparse Row stores matrix data (column indices and values in contiguous arrays, row pointers).
  3. Rayon and work-stealing parallelism: Understanding that rayon uses a global thread pool and that join splits work within the current thread rather than spawning new threads.
  4. Memory hierarchy fundamentals: Understanding cache lines, DRAM bandwidth, random-access vs sequential-access performance, and how they interact with sparse linear algebra.
  5. The cuzk project architecture: Understanding the PCE pipeline, the role of synthesize_with_pce, and how evaluate_pce works internally.
  6. The Threadripper/EPYC platform: Understanding that these CPUs have high core counts (96), high memory bandwidth (~200 GB/s), and large caches.

Output Knowledge Created

This message produces several valuable outputs:

  1. A performance model of the MatVec kernel: The back-of-the-envelope calculation provides a framework for understanding where the time goes in sparse matrix-vector multiplication at this scale.
  2. A decision about parallelism strategy: The assistant decides to try parallel execution across circuits, with the understanding that it may or may not work and needs empirical validation.
  3. A code change: The edit to pipeline.rs changes the sequential iterator to a parallel one, which will be tested in subsequent messages.
  4. A deeper understanding of the bottleneck: The analysis reveals that the MatVec is memory-bandwidth-bound, not compute-bound, which has implications for future optimization strategies (e.g., compression, blocking, or GPU offloading).

The Thinking Process

The thinking process visible in this message is remarkable for its structure:

  1. Observation: The code has a sequential iterator where a parallel one was intended.
  2. Recognition of subtlety: Simply making it parallel could cause oversubscription due to nested rayon parallelism.
  3. Quantitative analysis: Building a performance model from first principles to understand where the time goes.
  4. Refinement: Breaking down the data access patterns (sequential scan vs random access) to identify the true bottleneck.
  5. Hypothesis formation: Concluding that parallel execution across circuits could improve cache utilization despite bandwidth sharing.
  6. Action: Making the change and planning to measure the result. This is a textbook example of the "measure, model, hypothesize, test" cycle of performance engineering. The assistant doesn't blindly make the code parallel — it reasons about why parallelism might help, quantifies the expected benefit, and identifies the risks.

Conclusion

Message 1444 is a pivotal moment in the cuzk optimization project. It captures the transition from "the PCE is slower than expected" to "we understand why and have a plan to fix it." The analysis demonstrates that performance debugging at this scale requires not just knowledge of the code, but a deep understanding of hardware characteristics, parallel programming models, and sparse linear algebra.

The 3.2-second MatVec per circuit — 26× slower than compute-bound — is a reminder that in large-scale proving systems, memory bandwidth is often the true bottleneck, not CPU cycles. The decision to try parallel execution across circuits, despite the risk of oversubscription, reflects a nuanced understanding of how cache utilization interacts with parallelism.

This message also highlights the importance of the "comment lies" problem in software engineering. The code claimed to be parallel but wasn't — a bug that would have been caught by any code review that took comments seriously. The fix, once validated, would not only improve performance but also align the code with its documentation.

The next messages in the session would reveal whether the parallel MatVec achieved the expected speedup. But regardless of the outcome, the diagnostic process itself — the reasoning, the quantitative modeling, the careful consideration of trade-offs — is a model worth studying.