AztecProtocol / barretenberg

Apache License 2.0
132 stars 81 forks source link

Remove use of get_row() in hot loops #940

Open ledwards2225 opened 4 months ago

ledwards2225 commented 4 months ago

get_row() constructs an AllValues from a single row across a table of polynomials viewed as columns. When used in a hot loop, e.g. over the entire length of the circuit, this amounts to making a full copy of all polynomials (one row at a time which probably is even worse?). Its currently used in the log derivative library (used by ECCVM and AVM) and in PG. At last check the PG usage accounts for 1s x86. ECCVM usage appears negligible but could be relevant for AVM. (Edit: AVM has fixed this by introducing a version of get_row that returns const refs instead of copying data).

Note: method compute_grand_product() in grand_product_library.hpp uses a manual construction instead of get_row but I'm fairly sure that it's equivalent and should potentially be addressed.

fcarreiro commented 2 months ago

As we were discussing in the slack thread, get_row seems to amount for 80%+ of the work done for logderivatives in the AVM. Accessing the rows directly seems to massively improve proving a public token transfer from 60s to 15s. Luke and I will chat about how to get this fixed.

ledwards2225 commented 1 month ago

Update: The AVM team solved this by introducing a version of get_row that returns const refs instead of copying data. Apparently this was as good as the more involved solution of only extracting the exact data that was needed at each step. This a great solution except that it relies on some uncoupled duplication in the Flavors that would be very brittle. (Not such a problem for AVM since their Flavors are auto-generated). A half measure solution for the log-derivative inverse use case is to still use get_row but only when the relation in question is active. This results in only calling get_row as many times as the relation is active vs at every row. get_row is still used in a hot loop in PG: compute_full_honk_evaluations(). This case could use a const ref version of get_row if one existed. This would likely result in a significant speedup.