Prover and verifier optimisation: tracking issue

[shreyas-londhe]

Optimisations found by profiling the prover and verifier. Each checklist item becomes its own issue. The list is open: add to it as profiling turns up more.

In scope:

Structure

• Avoid materialising the global R1CS matrix when the relation is one local circuit repeated over instances #42
• Parallelise bind_and_batch #43
• Replace the BTreeMap and BTreeSet accumulators in LinearCombination #44
• Hoist the modulus out of bigint_to_fq and parallelise the lowering pass #45

Forest GKR:

• GKR performance: tracking issue #52

Spartan

• Read the assignment as packed bits instead of a dense field MLE #46
• Defer Barrett reduction in the Spartan sumcheck round bodies #47
• Do not clone prove_spartan_piop arguments (products, assignments) #50

Virtual map, on #37

• Cache MaterializedMTranspose::digest instead of recomputing it per proof
• Stop allocating a full equality table in transpose_eq

Opening, on #38

• Parallelise build_batched_basis and defer reduction in accumulate_claim_block
• Optimize tensor_algebra_transpose #51
• Decide whether the weight binding is redundant in the virtual path

Machinery

• Size the rayon pool to the performance cores #48

Out of scope: witness generation. Also hand optimisation beyond porting what the profile already shows, which waits on these landing and a fresh profile.

Depends: #37, #38 and #40 for the items filed under them. The step-4 reduction and the profiling harness these came from are on exp/e2e, which has no PR.

Related: #8 covers the merged GKR forest #40 implements. #7 covers the opener #38 builds. #19 and #20 cover the Spartan PIOP and its sparse matrix core.

Done when: every item is closed or explicitly dropped, and a fresh profile turns up nothing worth adding.

[xrvdg]

Parallelise the layer sumcheck

This has already been implemented or do you mean something else?

Consume leaves lazily and parallelise the tree build

Currently being worked on.

Match the grouping convention and claim shape to the step-4 reduction

For GKR to parallelise effectively, the leaves need to be stored row-major. That layout lets the column bits be folded last without opening gaps, and it also helps the lazy lookup of the leaves. BitTable is currently column-major. If it were row-major instead, what breaks?

[shreyas-londhe]

This has already been implemented or do you mean something else?

I misread in my reading. This issue should be removed.

[shreyas-londhe]

For GKR to parallelise effectively, the leaves need to be stored row-major. That layout lets the column bits be folded last without opening gaps, and it also helps the lazy lookup of the leaves. BitTable is currently column-major. If it were row-major instead, what breaks?

The conversion costs is ~2ms (parallel) so I would keep the BitTable column-major for now, but we can convert at the GKR boundary so you can take advantage of row-major.

[frozenspider]

Attaching the profiler results from exp/e2e branch (f9b89b1), profiling run example (SHA256): e2e-608.json.gz
Commands that were used:

$ CARGO_PROFILE_RELEASE_DEBUG=line-tables-only RUSTFLAGS="-C target-cpu=native -C force-frame-pointers=yes" cargo build --release -p e2e --example run
$ samply record --save-only -o e2e-608.json.gz -- target/release/examples/run 608 1

Most of prover time, and perf optimization opportunities, come from GKR - which is not a real GKR by @xrvdg - for instance significant amount of prover time (20-30%) is taken by allocations, specifically by to_vec in prove_product_forest which won't be there. So much for the time wasted 😞

In addition to what @shreyas-londhe has logged, I'm adding the following tasks as a follow-up:

• Do not clone prove_spartan_piop arguments (products, assignments) #50
• Optimize tensor_algebra_transpose #51
• Added comment to Parallelise bind_and_batch #43

We also can optimize bind_and_batch $F_q$ multiplication by using Montgomery form, but expected gain is not high enough to bother.
The rest of my findings look negligible.

[xrvdg]

Made a separate tracking issue for GKR: #52. Updated the issue to include the link.