Describe the bug
get_chain_position for unconfirmed transactions is very inefficient if we have "nested conflicts". Since unconfirmed transactions that spend from evicted transactions are also evicted, we need to iterate over and check all unconfirmed descendants.
This problem is exacerbated in list_canonical_txs, filter_chain_txouts, etc. as these methods call get_chain_position for each transaction.
Worst case is O(n^2) for building the canonical tx history.
Proposed Solution
Let's pass an evicted_txs: &mut HashSet<Txid> input to get_chain_position which takes record of any tx that is deemed to be evicted from the canonical history. Note that descendants of evicted transactions are also evicted and should be included in evicted_txs. The logic to fill evicted_txs can stop when we insert an already-existing txid (since descendants of that txid will already be included in evicted_txs).
list_canonical_txs, filter_chain_txouts, etc. methods will construct an evicted_txs hashset which is passed to each internal call to try_get_chain_position.
Describe the bug
get_chain_positionfor unconfirmed transactions is very inefficient if we have "nested conflicts". Since unconfirmed transactions that spend from evicted transactions are also evicted, we need to iterate over and check all unconfirmed descendants.This problem is exacerbated in
list_canonical_txs,filter_chain_txouts, etc. as these methods callget_chain_positionfor each transaction.Worst case is
O(n^2)for building the canonical tx history.Proposed Solution
Let's pass an
evicted_txs: &mut HashSet<Txid>input toget_chain_positionwhich takes record of any tx that is deemed to be evicted from the canonical history. Note that descendants of evicted transactions are also evicted and should be included inevicted_txs. The logic to fillevicted_txscan stop when we insert an already-existingtxid(since descendants of thattxidwill already be included inevicted_txs).list_canonical_txs,filter_chain_txouts, etc. methods will construct anevicted_txshashset which is passed to each internal call totry_get_chain_position.