chore: parallelise inverse polynomial construction for lookup relations

[maramihali]

Benchmark were showing that oink is the second most expensive round in PG after combiner. On top of that one component where we see discrepancies when increasing the ambient trace size is logderivative inverses construction. A step towards improving this is parallelising the construction of inverse polynomials (which is linear). Also the inverses can be committed to with commit_sparse which shows a slight improvement as well.
BEFORE

CLIENT_IVC_BENCH_STRUCTURE(2^19)

ClientIVCBench/Full/6      29146 ms        27299 ms
ProtogalaxyProver::prove(t)            16265    58.29%
ProtogalaxyProver_::run_oink_prover_on_each_incomplete_key(t)    5624    34.58%


EXAMPLE_20(2^20)

ClientIVCBench/Full/6      37145 ms        34235 ms
ProtogalaxyProver::prove(t)            21283    60.75%
ProtogalaxyProver_::run_oink_prover_on_each_incomplete_key(t)    8818    41.43%
COMMIT::lookup_inverses(t)        406     9.82%

AFTER

CLIENT_IVC_BENCH_STRUCTURE(2^19)

ClientIVCBench/Full/6      27351 ms        25477 ms 
ProtogalaxyProver::prove(t)            14627    55.72%
ProtogalaxyProver_::run_oink_prover_on_each_incomplete_key(t)    4030    27.55%


EXAMPLE_20(2^20)
ClientIVCBench/Full/6      33852 ms        30893 ms   
ProtogalaxyProver::prove(t)            18250    56.97%
ProtogalaxyProver_::run_oink_prover_on_each_incomplete_key(t)    5526    30.28%
COMMIT::lookup_inverses(t)        301     7.43%

[iakovenkos]

are they really (going to be) sparse in practice?

[iakovenkos]

lgtm

[fcarreiro]

Just a comment because I see a lot of microoptimisation going on: have you guys profiled where the time is going?

IIRC when I did some profiling for the AVM (which luckily does not use this relation, since we already parallelize) a lot of time was spent in

• Using get_row which (according to some comments) "was only meant for debugging"
• (related to the above) Visiting all rows of the trace and finding out if you actually need to compute the inverse or not.

If this is still true, you'd benefit far more if you could save which rows need an inverse, and only act on those (therefore O(needs_inverse) vs O(rows)). I think this is true for the AVM (where the cost of get_row is really big) and I have some ideas on how to implement this. However, for general bb, the problem is that the whole proving system is stateless in terms of relations. That is, everything uses Relation::method, and not relation_instance.method.

[maramihali]

I actually looked into the issue here AztecProtocol/barretenberg#940 and we indeed only use get_row for those that need an inverse (achieved by checking q_lookup and lookup_read_target polynomial). I'm optimising with the scope of reducing the impact of using a larger trace structure when keeping the same circuit content (so introducing more sparsity in the trace). I did indeed profiled get_row and the time spent doing it is not getting worse because we avoid calling it when not needed. We still are spending around 3.5s calling get_row but as Luke noted in the issue moving to a different pattern requires more involved work and we want to eliminate the existing low hanging fruits first.