use hashmap instead of BTreeMap for faster lookup

[malik672]

Describe the feature

I'm not entirely sure but in the but in the pending file under transaction_pool crate we can already order using the the sequential structure of the submission id hence we do not need to use it properties again and we can just switch to a hashmap instead and enable faster lookup constant time than logarithmic time

Additional context

pub struct PendingPool<T: TransactionOrdering> {
    /// How to order transactions.
    ordering: T,
    /// Keeps track of transactions inserted in the pool.
    ///
    /// This way we can determine when transactions were submitted to the pool.
    submission_id: u64,
    /// _All_ Transactions that are currently inside the pool grouped by their identifier.
    by_id: BTreeMap<TransactionId, PendingTransaction<T>>,
    /// _All_ transactions sorted by priority
    all: BTreeSet<PendingTransaction<T>>,
    /// The highest nonce transactions for each sender - like the `independent` set, but the
    /// highest instead of lowest nonce.
    ///
    /// Sorted by their scoring value.
    highest_nonces: BTreeSet<PendingTransaction<T>>,
    /// Independent transactions that can be included directly and don't require other
    /// transactions.
    ///
    /// Sorted by their scoring value.
    independent_transactions: BTreeSet<PendingTransaction<T>>,
    /// Keeps track of the size of this pool.
    ///
    /// See also [`PoolTransaction::size`](crate::traits::PoolTransaction::size).
    size_of: SizeTracker,
    /// Used to broadcast new transactions that have been added to the `PendingPool` to existing
    /// `static_files` of this pool.
    new_transaction_notifier: broadcast::Sender<PendingTransaction<T>>,
}

No response

[mattsse]

hmm, looks like we can do this for the by_id map at least because this function is not a hot path and we can simply iterate over the entire map for this

reth/crates/transaction-pool/src/pool/pending.rs

Lines 519 to 524 in 0da914e

	pub(crate) fn get_txs_by_sender(&self, sender: SenderId) -> Vec<TransactionId> {
	self.by_id
	.range((sender.start_bound(), Unbounded))
	.take_while(move |(other, _)| sender == other.sender)
	.map(|(tx_id, _)| *tx_id)
	.collect()

[malik672]

Agreed, since by_id is also used for direct lookups which are more frequent, we can optimize those to O(1) with HashMap while accepting the O(n) scan for get_txs_by_sender

[malik672]

I should benchmark this tbh

[malik672]

@mattsse i want to remove BTreeSet<PendingTransaction<T>>, I feel it's redundant and not needed since it mirrors by_id, if we want all, we can simply create a helper function over by_id and get all

the best part, we save memory, and reduce unnecessary writes