Repository navigation
Investigate: is single-threaded bucket accumulation in Pippenger a bottleneck? #1656
Description
There is a TODO in scalar_multiplication.cpp questioning whether the single-threaded bucket accumulation loop is a performance concern for large MSMs with many threads:
// Accumulate results. This part needs to be single threaded, but amount of work done here should be small
// TODO(@zac-williamson) check this? E.g. if we are doing a 2^16 MSM with 256 threads this single-threaded part
// will be painful.Action items:
- Benchmark the bucket accumulation phase relative to the overall MSM for representative sizes (2^16, 2^20) to determine if this is actually a bottleneck.
- If it is, explore parallelization options. Note that
BitVector::set()inbitvector.hppperforms a non-atomic read-modify-write, so any parallelization of the bucket loop must keepBucketAccumulatorsper-thread or use atomic operations.
Activity
peter941221 commentedon Mar 23, 2026
I put together a small PR that makes this TODO measurable and (on my machine) suggests the single-threaded final reduction is not a bottleneck, even in the
2^16/256 threadsregime mentioned in the issue.What the PR adds
BB_BENCHphase breakdown insideMSM::batch_multi_scalar_mul(...):evaluate_work_unitsaccumulate_results(the TODO loop)batch_normalizescalars_to_montgomeryPippengerBench/BatchMSM_1656/256/{msm_size}msm_size ∈ {2^16, 2^20}num_polys = 1)Quick numbers (4 vCPU laptop;
BB_BENCHtime counters are nanoseconds)2^16, 256 threads:accumulate_results ≈ 139k ns(~0.139 ms) vs total≈ 521 ms(~0.027%)2^20, 256 threads:accumulate_results ≈ 141k ns(~0.141 ms) vs total≈ 3457 ms(~0.004%)So the reduction loop stays in the sub-millisecond range and is drowned out by
evaluate_work_unitson this setup.If this matches what you see on a 64+ core box, we can probably keep it single-threaded and just leave the benchmark + breakdown in place to prevent guesswork going forward.
PR link: AztecProtocol/aztec-packages#21885
chore: bench phase breakdown + thread sweep for MSM reduction (#21885)
AztecBot commentedon Mar 31, 2026
This issue was automatically closed because it was referenced in AztecProtocol/aztec-packages PR #21885 which has been merged to the default branch.
View workflow run