edr icon indicating copy to clipboard operation
edr copied to clipboard

Quadratic complexity in `mine_block`

Open agostbiro opened this issue 10 months ago • 0 comments

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

agostbiro avatar Apr 12 '24 09:04 agostbiro