-
Notifications
You must be signed in to change notification settings - Fork 2
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
Quadratic complexity in mine_block
#382
Comments
This was referenced Apr 12, 2024
agostbiro
changed the title
Worst-case quadratic complexity in
Quadratic complexity in Apr 18, 2024
mine_block
mine_block
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
mine_block
has quadratic complexity in the number of callers as it reruns the comparator function on all transactions for each transaction:https://github.com/NomicFoundation/hardhat/blob/b267db8d1f2acb6f5611e82b74b9d9e555024c84/crates/edr_evm/src/mempool.rs#L54-L59
Note that we're doing order preserving removal from
IndexMap
as well in the loop in certain cases which has linear complexity:https://github.com/NomicFoundation/hardhat/blob/69e340761ce52812fe720689bcec972345fc8df7/crates/edr_evm/src/miner.rs#L134-L157
The text was updated successfully, but these errors were encountered: