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

perf(continuations): linked list search should run in sublinear time #391

Open
Nashtare opened this issue Jul 12, 2024 · 0 comments
Open
Assignees
Labels
crate: evm_arithmetization Anything related to the evm_arithmetization crate. performance Performance improvement related changes

Comments

@Nashtare
Copy link
Collaborator

The current implementation of searching through the linked list is performing it naively, hence running in linear time, at the detriment of slower witness generation. This is particularly noticeable for payloads with a large number of accesses to storage or accounts.

We should have the search run in $O(\log n)$ time instead.

@Nashtare Nashtare added performance Performance improvement related changes crate: evm_arithmetization Anything related to the evm_arithmetization crate. labels Jul 12, 2024
@Nashtare Nashtare added this to the Performance Tuning milestone Jul 12, 2024
@Nashtare Nashtare changed the title linked list search should run in sublinear time perf(continuations): linked list search should run in sublinear time Jul 16, 2024
@Nashtare Nashtare self-assigned this Jul 16, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
crate: evm_arithmetization Anything related to the evm_arithmetization crate. performance Performance improvement related changes
Projects
Status: In Progress
Development

No branches or pull requests

1 participant