Repository navigation
feat: Sorted execution trace - #5252
Conversation
Changes to circuit sizes
🧾 Summary (100% most significant diffs)
Full diff report 👇
|
Benchmark resultsNo metrics with a significant change found. Detailed resultsAll benchmarks are run on txs on the This benchmark source data is available in JSON format on S3 here. Values are compared against data from master at commit L2 block published to L1Each column represents the number of txs on an L2 block published to L1.
L2 chain processingEach column represents the number of blocks on the L2 chain where each block has 16 txs.
Circuits statsStats on running time and I/O sizes collected for every circuit run across all benchmarks.
Tree insertion statsThe duration to insert a fixed batch of leaves into each tree type.
MiscellaneousTransaction sizes based on how many contract classes are registered in the tx.
Transaction processing duration by data writes.
|
| bool result = true; | ||
| // TODO(https://github.com/AztecProtocol/barretenberg/issues/870): Currently we check all relations for each block. | ||
| // Once sorting is complete, is will be sufficient to check only the relevant relation(s) per block. | ||
| size_t block_idx = 0; |
There was a problem hiding this comment.
Previously I was only checking the main block (which contained all gates). Now I'm looping over all blocks and checking all relations on each one.
| // Determine number of times to execute the below operations that constitute the mock circuit logic. Note that | ||
| // the circuit size does not scale linearly with number of iterations due to e.g. amortization of lookup costs | ||
| const size_t NUM_ITERATIONS_LARGE = 13; // results in circuit size 2^19 (521327 gates) | ||
| const size_t NUM_ITERATIONS_LARGE = 12; // results in circuit size 2^19 (502238 gates) |
There was a problem hiding this comment.
Had to reduce this due to dummy gates increasing sizes of some circuits
| } | ||
| check_selector_length_consistency(); | ||
| ++this->num_gates; | ||
| create_dummy_gate(block, in.x2, in.x3, in.y3, in.y2); |
There was a problem hiding this comment.
Here I'm just using the create_dummy_gate method instead of doing it manually
| blocks.main.pad_additional(); | ||
| } | ||
| check_selector_length_consistency(); | ||
| create_add_gate({ variable_index[0], this->zero_idx, this->zero_idx, 1, 0, 0, -start }); |
There was a problem hiding this comment.
No change, just using create_add_gate instead of the manual thing
| 0, | ||
| -end }); | ||
| create_dummy_gate(block, variable_index[variable_index.size() - 1], this->zero_idx, this->zero_idx, this->zero_idx); | ||
| create_add_gate({ variable_index[variable_index.size() - 1], this->zero_idx, this->zero_idx, 1, 0, 0, -end }); |
There was a problem hiding this comment.
No actual change here, just using create_add_gate instead since there was no need for the "big add gate" functionality
| : CircuitBuilderBase<FF>(size_hint) | ||
| { | ||
| blocks.main.reserve(size_hint); | ||
| // TODO(https://github.com/AztecProtocol/barretenberg/issues/870): reserve space in blocks here somehow? |
There was a problem hiding this comment.
Leaving this as a TODO. I previously looked at how important this reserve was and it turns out the answer is that it's entirely negligible.
Rumata888
left a comment
There was a problem hiding this comment.
Chunky. Left very few comments. LGTM
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-package: 0.30.1</summary> ## [0.30.1](aztec-package-v0.30.0...aztec-package-v0.30.1) (2024-03-20) ### Miscellaneous * **aztec-package:** Synchronize aztec-packages versions </details> <details><summary>barretenberg.js: 0.30.1</summary> ## [0.30.1](barretenberg.js-v0.30.0...barretenberg.js-v0.30.1) (2024-03-20) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>aztec-cli: 0.30.1</summary> ## [0.30.1](aztec-cli-v0.30.0...aztec-cli-v0.30.1) (2024-03-20) ### Miscellaneous * **aztec-cli:** Synchronize aztec-packages versions </details> <details><summary>aztec-packages: 0.30.1</summary> ## [0.30.1](aztec-packages-v0.30.0...aztec-packages-v0.30.1) (2024-03-20) ### Features * Add CMOV instruction to brillig and brillig gen ([#5308](#5308)) ([208abbb](208abbb)) * **avm:** Indirect memory support for arithmetic/bitwise opcodes ([#5328](#5328)) ([d5ffa17](d5ffa17)), closes [#5273](#5273) * **avm:** Indirect memory support for MOV ([#5257](#5257)) ([10ef970](10ef970)), closes [#5205](#5205) * Merge SMT Terms in one class ([#5254](#5254)) ([f5c9b0f](f5c9b0f)) * Sorted execution trace ([#5252](#5252)) ([a216759](a216759)) ### Bug Fixes * Fix recursion tests and reinstate in CI ([#5300](#5300)) ([96c6f21](96c6f21)) * Skip uniswap l1 tests ([#5334](#5334)) ([7a56941](7a56941)) * Update smt_verification README.md ([#5332](#5332)) ([46b15e3](46b15e3)) ### Miscellaneous * Avm team as generated codeowners ([#5325](#5325)) ([06d2786](06d2786)) * No Translator composer ([#5202](#5202)) ([c8897ca](c8897ca)) * Remove toy vm files ([#5326](#5326)) ([d940356](d940356)) * Replace relative paths to noir-protocol-circuits ([ea2ac09](ea2ac09)) </details> <details><summary>barretenberg: 0.30.1</summary> ## [0.30.1](barretenberg-v0.30.0...barretenberg-v0.30.1) (2024-03-20) ### Features * Add CMOV instruction to brillig and brillig gen ([#5308](#5308)) ([208abbb](208abbb)) * **avm:** Indirect memory support for arithmetic/bitwise opcodes ([#5328](#5328)) ([d5ffa17](d5ffa17)), closes [#5273](#5273) * **avm:** Indirect memory support for MOV ([#5257](#5257)) ([10ef970](10ef970)), closes [#5205](#5205) * Merge SMT Terms in one class ([#5254](#5254)) ([f5c9b0f](f5c9b0f)) * Sorted execution trace ([#5252](#5252)) ([a216759](a216759)) ### Bug Fixes * Fix recursion tests and reinstate in CI ([#5300](#5300)) ([96c6f21](96c6f21)) * Update smt_verification README.md ([#5332](#5332)) ([46b15e3](46b15e3)) ### Miscellaneous * No Translator composer ([#5202](#5202)) ([c8897ca](c8897ca)) * Remove toy vm files ([#5326](#5326)) ([d940356](d940356)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
🤖 I have created a release *beep* *boop* --- <details><summary>aztec-package: 0.30.1</summary> ## [0.30.1](AztecProtocol/aztec-packages@aztec-package-v0.30.0...aztec-package-v0.30.1) (2024-03-20) ### Miscellaneous * **aztec-package:** Synchronize aztec-packages versions </details> <details><summary>barretenberg.js: 0.30.1</summary> ## [0.30.1](AztecProtocol/aztec-packages@barretenberg.js-v0.30.0...barretenberg.js-v0.30.1) (2024-03-20) ### Miscellaneous * **barretenberg.js:** Synchronize aztec-packages versions </details> <details><summary>aztec-cli: 0.30.1</summary> ## [0.30.1](AztecProtocol/aztec-packages@aztec-cli-v0.30.0...aztec-cli-v0.30.1) (2024-03-20) ### Miscellaneous * **aztec-cli:** Synchronize aztec-packages versions </details> <details><summary>aztec-packages: 0.30.1</summary> ## [0.30.1](AztecProtocol/aztec-packages@aztec-packages-v0.30.0...aztec-packages-v0.30.1) (2024-03-20) ### Features * Add CMOV instruction to brillig and brillig gen ([#5308](AztecProtocol/aztec-packages#5308)) ([208abbb](AztecProtocol/aztec-packages@208abbb)) * **avm:** Indirect memory support for arithmetic/bitwise opcodes ([#5328](AztecProtocol/aztec-packages#5328)) ([d5ffa17](AztecProtocol/aztec-packages@d5ffa17)), closes [#5273](AztecProtocol/aztec-packages#5273) * **avm:** Indirect memory support for MOV ([#5257](AztecProtocol/aztec-packages#5257)) ([10ef970](AztecProtocol/aztec-packages@10ef970)), closes [#5205](AztecProtocol/aztec-packages#5205) * Merge SMT Terms in one class ([#5254](AztecProtocol/aztec-packages#5254)) ([f5c9b0f](AztecProtocol/aztec-packages@f5c9b0f)) * Sorted execution trace ([#5252](AztecProtocol/aztec-packages#5252)) ([a216759](AztecProtocol/aztec-packages@a216759)) ### Bug Fixes * Fix recursion tests and reinstate in CI ([#5300](AztecProtocol/aztec-packages#5300)) ([96c6f21](AztecProtocol/aztec-packages@96c6f21)) * Skip uniswap l1 tests ([#5334](AztecProtocol/aztec-packages#5334)) ([7a56941](AztecProtocol/aztec-packages@7a56941)) * Update smt_verification README.md ([#5332](AztecProtocol/aztec-packages#5332)) ([46b15e3](AztecProtocol/aztec-packages@46b15e3)) ### Miscellaneous * Avm team as generated codeowners ([#5325](AztecProtocol/aztec-packages#5325)) ([06d2786](AztecProtocol/aztec-packages@06d2786)) * No Translator composer ([#5202](AztecProtocol/aztec-packages#5202)) ([c8897ca](AztecProtocol/aztec-packages@c8897ca)) * Remove toy vm files ([#5326](AztecProtocol/aztec-packages#5326)) ([d940356](AztecProtocol/aztec-packages@d940356)) * Replace relative paths to noir-protocol-circuits ([ea2ac09](AztecProtocol/aztec-packages@ea2ac09)) </details> <details><summary>barretenberg: 0.30.1</summary> ## [0.30.1](AztecProtocol/aztec-packages@barretenberg-v0.30.0...barretenberg-v0.30.1) (2024-03-20) ### Features * Add CMOV instruction to brillig and brillig gen ([#5308](AztecProtocol/aztec-packages#5308)) ([208abbb](AztecProtocol/aztec-packages@208abbb)) * **avm:** Indirect memory support for arithmetic/bitwise opcodes ([#5328](AztecProtocol/aztec-packages#5328)) ([d5ffa17](AztecProtocol/aztec-packages@d5ffa17)), closes [#5273](AztecProtocol/aztec-packages#5273) * **avm:** Indirect memory support for MOV ([#5257](AztecProtocol/aztec-packages#5257)) ([10ef970](AztecProtocol/aztec-packages@10ef970)), closes [#5205](AztecProtocol/aztec-packages#5205) * Merge SMT Terms in one class ([#5254](AztecProtocol/aztec-packages#5254)) ([f5c9b0f](AztecProtocol/aztec-packages@f5c9b0f)) * Sorted execution trace ([#5252](AztecProtocol/aztec-packages#5252)) ([a216759](AztecProtocol/aztec-packages@a216759)) ### Bug Fixes * Fix recursion tests and reinstate in CI ([#5300](AztecProtocol/aztec-packages#5300)) ([96c6f21](AztecProtocol/aztec-packages@96c6f21)) * Update smt_verification README.md ([#5332](AztecProtocol/aztec-packages#5332)) ([46b15e3](AztecProtocol/aztec-packages@46b15e3)) ### Miscellaneous * No Translator composer ([#5202](AztecProtocol/aztec-packages#5202)) ([c8897ca](AztecProtocol/aztec-packages@c8897ca)) * Remove toy vm files ([#5326](AztecProtocol/aztec-packages#5326)) ([d940356](AztecProtocol/aztec-packages@d940356)) </details> --- This PR was generated with [Release Please](https://github.com/googleapis/release-please). See [documentation](https://github.com/googleapis/release-please#release-please).
This work results in an execution trace fully sorted by gate type.
Prior to this PR, all of the infrastructure was added to construct and process a sorted execution trace. Each builder has a
blocksobject which essentially holds a {wires,selectors} pair for each gate type. Up until now, all gates were being added intoblocks.main, which is equivalent to what we've always done. This PR simply adds gates into their appropriate specialized block, e.g. arithmetic gates are added intoblocks.arithmeticand auxiliary gates are added intoblocks.aux. After being processed in theExecutionTraceclass, this results in an execution trace sorted by gate type.Note: This PR adds dummy gates in several new locations to account for the fact that some gates of a particular type were previously reading into a subsequent gate of different type, which breaks once the gates are sorted by type.
Note: This PR does not include any logic for taking advantage of the sorted structure.
Closes AztecProtocol/barretenberg#867 (gates are sorted)
Closes AztecProtocol/barretenberg#873 (no more gate interleaving assumptions, except ones now identified in more specific issues)
Closes AztecProtocol/barretenberg#910 (gate type summary via blocks.summarize())