HomePhabricator

[mempool] use coins cache and iterate in topo order in check()

Description

[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

Details

Provenance
glozow <gloriajzhao@gmail.com>Authored on Sep 30 2021, 08:08
PiRKCommitted on Oct 7 2022, 13:38
PiRKPushed on Oct 7 2022, 13:39
Reviewer
Restricted Project
Differential Revision
D12170: [mempool] use coins cache and iterate in topo order in check()
Parents
rABC8a5d04de8890: [bench] Benchmark CTxMemPool::check()
Branches
Unknown
Tags
Unknown