GKR performance: tracking issue

[xrvdg]

General

Scope gkr_reduce in prover.rs and verifier.rs

Benchmarking & Profiling setup

• Divan
• Bin for samply/intstruments profiling
• AI comparison benchmark

Optimisations

Prove layer (66%)

• Remove deallocations (19.4%)
• Dequeu with capacity (19.4%)

Suffix Table (8.3%)

• Pre-allocate table
• Split table

Sumcheck

• LUT

verifier messages (19.9%)

• Spongefish

Circuit Evaluator / Witness Builder (33%)

• leaf construction (11%)
  • tranposed bit table
  • branchless
• evaluator (22.5%)
  • allocation free intermediate layers (18.5%)
  • no clone (3.5%)
• lazy
  • level d (leafs)
  • level d-1
  • level d-2

Inner product claim transformation / mtable (5.2%)

• branchless
• bytemuck zeroed_vec
  • zereod_vec had some positive affect, but has messed up the frame/stack pointer attribution
• Add assign (4%)
• column bit enumerator (1%)

Miscellaneous optimisations

• Scan Binius64 (prodcheck, intmul)
• Scan f2z-pcs

Remarks

Multithreading will be done after these optimisations.

[xrvdg]

#55

┌───────────────────────────┬──────────┬──────────┬─────────┐
│                           │  before  │  after   │ speedup │
├───────────────────────────┼──────────┼──────────┼─────────┤
│ parallel (default)        │ 363.4 ms │ 166.1 ms │ 2.19x   │
├───────────────────────────┼──────────┼──────────┼─────────┤
│ single-threaded (patched) │ 480.3 ms │ 283.4 ms │ 1.70x   │
└───────────────────────────┴──────────┴──────────┴─────────┘

pprof stats

Arithmetic work (64.1%)

• 40% vmull_p64
• 13.4% veor1
• 10.7% add assign

Allocations (23.5%)

• 10% push / vec allocs
• 6.9% vec with capacity
• 3.9% memmove
• 2.5% bzero