edr
edr copied to clipboard
Quadratic complexity in `mine_block`
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