mirror of
https://github.com/powdr-labs/powdr.git
synced 2026-01-14 20:38:26 -05:00
e328eb90da
While working on #2306, @Schaeff came across several bugs in multiplicity witness generation. These were undetected, because we ignored multiplicities in the mock prover, which will be fixed by #2310. With this PR, #2310 will be green. The issue was that counting multiplicities inside `Machine::process_plookup()` fails if the caller actually discards the result. This happens in a few places, for example during our loop optimization in the "dynamic machine". With this PR, we instead have a centralized `MultiplicityColumnGenerator` that counts multiplicities after the fact, by going over each lookup, evaluating the two selected tuples on all rows, and counting how often each element in the LHS appears in the RHS. To measure the runtime of this, I ran: ```sh export TEST=keccak export POWDR_JIT_OPT_LEVEL=0 cargo run -r --bin powdr-rs compile riscv/tests/riscv_data/$TEST -o output --max-degree-log 18 cargo run -r --features plonky3,halo2 pil output/$TEST.asm -o output -f --field gl --linker-mode bus ``` I get the following profile on the server: ``` == Witgen profile (2554126 events) 32.4% ( 2.6s): Secondary machine 0: main_binary (BlockMachine) 23.1% ( 1.9s): Main machine (Dynamic) 12.7% ( 1.0s): Secondary machine 4: main_regs (DoubleSortedWitnesses32) 10.0% ( 809.9ms): FixedLookup 7.7% ( 621.1ms): Secondary machine 5: main_shift (BlockMachine) 5.6% ( 454.6ms): Secondary machine 2: main_poseidon_gl (BlockMachine) 3.8% ( 312.3ms): multiplicity witgen 3.8% ( 308.2ms): witgen (outer code) 0.6% ( 45.3ms): Secondary machine 1: main_memory (DoubleSortedWitnesses32) 0.4% ( 33.4ms): Secondary machine 6: main_split_gl (BlockMachine) 0.0% ( 8.0µs): Secondary machine 3: main_publics (WriteOnceMemory) --------------------------- ==> Total: 8.114630092s ``` So the cost is ~4%. I'm sure it can be optimized further but I would like to leave this to a future PR.
17 lines
432 B
TOML
17 lines
432 B
TOML
[package]
|
|
name = "powdr-executor-utils"
|
|
version.workspace = true
|
|
edition.workspace = true
|
|
license.workspace = true
|
|
homepage.workspace = true
|
|
repository.workspace = true
|
|
|
|
[dependencies]
|
|
powdr-number.workspace = true
|
|
powdr-ast.workspace = true
|
|
|
|
serde = { version = "1.0", default-features = false, features = ["alloc", "derive", "rc"] }
|
|
itertools = "0.13"
|
|
|
|
[lib]
|
|
bench = false # See https://github.com/bheisler/criterion.rs/issues/458 |