Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Remove use of get_row() in hot loops #940

Open
ledwards2225 opened this issue Apr 12, 2024 · 2 comments
Open

Remove use of get_row() in hot loops #940

ledwards2225 opened this issue Apr 12, 2024 · 2 comments

Comments

@ledwards2225
Copy link
Collaborator

ledwards2225 commented Apr 12, 2024

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
Copy link
Contributor

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
Copy link
Collaborator Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants