perf: avoid needless clones in permutation trace commit #69
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This was referenced Apr 14, 2025
16204ec to
00b88ed
Compare
leonardoalt
pushed a commit
to powdr-labs/stark-backend
that referenced
this pull request
Jun 3, 2025
* perf: cpu `TraceCommitter` should reserve capacity for LDE (openvm-org#68) * perf: avoid needless clones in permutation trace commit (openvm-org#69) * perf: `transmute_to_base` to avoid needless clones * chore: add note about p3 PR * chore: add debug asserts for safety * feat!: drop main trace earlier for lower peak memory (openvm-org#71) * feat: drop main trace earlier for lower peak memory * fix: trace_metrics * chore: log quotient poly cells (openvm-org#72) * feat: reserve capacity for perm & quotient LDE; avoid copy for quotient split (openvm-org#73) * chore: log quotient poly cells * feat: perm trace reserve extra capacity * feat: quotient no-resize and no-copy * fix: small trace heights * fix: misunderstanding of vertical striding * chore: clarify comment * chore: bump workspace version to `1.0.1` (openvm-org#74) * release: v1.1.0 (openvm-org#76) * feat: update security parameters (openvm-org#20) * chore: update status in readme (openvm-org#21) closes INT-4015 * fix: account for poles in log up security calculation (openvm-org#22) * chore: update readme * fix(plonky3): update plonky3 commit for security fix --------- Co-authored-by: Zach Langley <zblangley@gmail.com> * perf: optimize `compute_quotient_values` (openvm-org#75) * chore: rename keccak example to keccakf * feat: add example to bench compute_quotient and readme * chore: add bench script * chore: update profile script to use perf on linux * feat: `parallelize_chunks` * feat: allocate once per thread * feat: share alpha_powers and avoid `Vec::push` * chore: bump workspace version * feat: Export metrics to Prometheus server (openvm-org#70) * Add metrics exporter * Add tracing context * Fix tokio * Revert "Fix tokio" This reverts commit fdd16a8. * Install crypto provider * Increase interval length * Feature gate * Small fixes * chore: remove unused modules (openvm-org#77) --------- Co-authored-by: Jonathan Wang <31040440+jonathanpwang@users.noreply.github.com> Co-authored-by: Zach Langley <zblangley@gmail.com> Co-authored-by: Manh Dinh <manh9203@gmail.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
PR targeting #68
I noticed that permutation trace commitment is doing TWO needless clones: first
RowMajorMatrix::flatten_to_basecreates a whole new vector by collecting individual flatten to base when the extension field matrix can just be transmuted. Secondly, the permutation trace is never used after it is committed, so we should not useTraceCommitter(which clones) but instead usepcs.commitdirectly.I have add a
transmute_to_basefunction to replaceflatten_to_base. There doesn't seem a good way to have the compiler check the required safety assumptions, so I just document it. (TheBinomialExtensionFieldimplementation ofExtensionFieldsatisfies the assumptions.)The quotient polynomial matrices also saves clones by using
transmute_to_base.Note that since the backend is the one who constructs both perm and quotient matrices, we should be able to reserve extra capacity to avoid a vector re-alloc using the same idea as in #68. I didn't do this yet because there's a lot of traits that make it kind of messy.
before: https://github.com/axiom-crypto/openvm-reth-benchmark/blob/gh-pages/benchmarks-dispatch/refs/heads/main/reth-1c30506ef50e081fa0dceae8244b6dc6311f9584-0d99ea9777b49a7f2c889dc36dd5470ef77a099408c22e824b413132e03e9b83.md
after: https://github.com/axiom-crypto/openvm-reth-benchmark/blob/gh-pages/benchmarks-dispatch/refs/heads/main/reth-8fba5a1c8d9a53527b463292f1569f6087404deb-b9ae348d0275e83a4b3237713f3850bb3c858b14294348e4fe7dbe0d07096e71.md