Skip to content

feat(avm): set avm circuit subgroup size#8537

Merged
fcarreiro merged 1 commit into
masterfrom
fc/avm-fixed-circuit-size
Sep 18, 2024
Merged

feat(avm): set avm circuit subgroup size#8537
fcarreiro merged 1 commit into
masterfrom
fc/avm-fixed-circuit-size

Conversation

@fcarreiro

@fcarreiro fcarreiro commented Sep 13, 2024

Copy link
Copy Markdown
Contributor

I had to make a few changes in this PR, so bear with me.

Inside you there are two wolves:

  • The size of the generated trace (which I'll call the "trace"): e.g., you run a loop from 1 to 1000 and get a trace with size 1000 (or, if you will, ~2^18 if you add the precomputed columns)
  • The size of the polynomials used for proving: aka circuit subgroup size. We need to set this to some number, since the VK and other things depend on it.

In this PR I'm setting the latter to 2^21. Is that all? No, because this still needs to work with traces < 2^21. Can't you just resize the trace to 2^21 and call it a day? You can, but then your memory and time will suck.

This PR therefore does the following: Suppose your trace has size 1000 and you know already our subgroup size is set to 2^21. The polynomials will be initialized with a real size of 1000 rows, and a virtual size of 2^21. Then the values will be set from our generated trace.

  • This is far better in terms of memory because you only "pay for what you use"*.
  • This is also far better in terms of time, because resizing the trace to 2^21 takes forever (like 20s+). This is because we currently use std::vector which forces the initialization of every field, even if you previously reserved memory (which btw is fast).

Extra: I also did some cleanups, in particular I try to rely less on environment variables and have a clear flow separation between "prod" and tests.

  • bb avm_prove only runs check circuit if you really ask for it.
  • bb avm_prove uses full proving by default (all range checks and precomputed tables). This will in particular help with a more realistic devnet/testnet.
  • tests manually set the above options
  • check-circuit only checks rows up to the "trace" size; this should make it faster and still sound.
  • the 2^21 size does not (effectively) affect check-circuit

Results: I'm running this program, which at 2^22 rows took 6 minutes and 280GB ram. Let's then suppose that for 2^21 it would've taken 3 minutes and 140GB ram.

  • After this PR, proving takes 49 seconds, and 31GB ram. (note that the time gains include as well the last few PRs)

*that is, if you use 1000 rows, you allocate 1000 rows. Sparcity is not yet taken into account. We need some more changes for that.

Loading
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

Successfully merging this pull request may close these issues.

4 participants