Every gate the circuit emits builds a LinearCombination, which keeps its terms in a BTreeMap<usize, BigInt>, and a BoolLinearCombination, which keeps its witness indices in a BTreeSet<usize>. Both allocate a tree node for every term, and the map allocates a BigInt for every coefficient.
The coefficients do not need that. The widest one in C is 34359738368, which is 2^35 and fits in 36 bits, so every coefficient in the whole matrix fits in an i64. BigInt heap-allocates to hold numbers that fit in eight bytes.
The ordered map is not obviously needed either. Rows are emitted in increasing column order and read back the same way.
What it could win: a flat vector of (u32, i64) pairs would allocate once per row rather than once per term, and hold twelve bytes per entry rather than a tree node plus a heap number. The generator's peak should fall towards the size of the matrices it produces instead of sitting several times above it.
This is generation cost. Neither our benchmarks nor BitZ's count it as proving time. It matters because it decides how large a statement we can build at all.
Effort M.
Every gate the circuit emits builds a
LinearCombination, which keeps its terms in aBTreeMap<usize, BigInt>, and aBoolLinearCombination, which keeps its witness indices in aBTreeSet<usize>. Both allocate a tree node for every term, and the map allocates aBigIntfor every coefficient.The coefficients do not need that. The widest one in
Cis 34359738368, which is 2^35 and fits in 36 bits, so every coefficient in the whole matrix fits in ani64.BigIntheap-allocates to hold numbers that fit in eight bytes.The ordered map is not obviously needed either. Rows are emitted in increasing column order and read back the same way.
What it could win: a flat vector of
(u32, i64)pairs would allocate once per row rather than once per term, and hold twelve bytes per entry rather than a tree node plus a heap number. The generator's peak should fall towards the size of the matrices it produces instead of sitting several times above it.This is generation cost. Neither our benchmarks nor BitZ's count it as proving time. It matters because it decides how large a statement we can build at all.
Effort M.