[mempool] use coins cache and iterate in topo order in check()
Summary:
[mempool] speed up check() by using coins cache and iterating in topo order
No behavior changes.
Before, we're always adding transactions to the "check later" queue if
they have any parents in the mempool. But there's no reason to do this
if all of its inputs are already available from mempoolDuplicate.
Instead, check for inputs, and only mark fDependsWait=true if the
parents haven't been processed yet.Reduce the amount of "check later" transactions by looking at
ancestors before descendants. Do this by iterating through them in
ascending order by ancestor count. This works because a child will
always have more in-mempool ancestors than its parent.We should never have any entries in the "check later" queue
after this commit.
https://github.com/bitcoin/bitcoin/pull/23157/commits/54c6f3c1da01090aee9691a2c2bee0984a054ce8
[mempool] remove now-unnecessary code
Remove variables used for keeping track of mempool transactions for
which we haven't processed the parents yet. Since we're iterating in
topological order now, they're always unused.
https://github.com/bitcoin/bitcoin/pull/23157/commits/e8639ec26aaf4de3fae280963434bf1cf2017b6f
This is a backport of core#23157 [3 & 4/8]
Depends on D12169
Test Plan:
ninja all check-all bench-bitcoin
Note that the benchmarks do not show any speed-up after this commit. The only significant change happensafter the last commit of the stack, when the ActiveChainState() pointer dereference is moved out of the benchmarked code.
I ran this in between the commits as well, to exercise all the assertions.
Reviewers: #bitcoin_abc, Fabien
Reviewed By: #bitcoin_abc, Fabien
Differential Revision: https://reviews.bitcoinabc.org/D12170