Page MenuHomePhabricator

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

Authored by PiRK on Oct 7 2022, 09:18.

Details

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.

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

PiRK requested review of this revision.Oct 7 2022, 09:18
PiRK retitled this revision from [mempool] using coins cache and iterate in topo order in check() to [mempool] use coins cache and iterate in topo order in check().Oct 7 2022, 09:18

Tail of the build log:

[412/470] Running utility command for check-bitcoin-checkqueue_tests
[413/470] Running utility command for check-bitcoin-getarg_tests
[414/470] bitcoin: testing fs_tests
[415/470] Running utility command for check-bitcoin-fs_tests
[416/470] bitcoin: testing inv_tests
[417/470] bitcoin: testing checkpoints_tests
[418/470] bitcoin: testing sigencoding_tests
[419/470] Running utility command for check-bitcoin-inv_tests
[420/470] Running utility command for check-bitcoin-checkpoints_tests
[421/470] Running utility command for check-bitcoin-sigencoding_tests
[422/470] bitcoin: testing script_tests
[423/470] bitcoin: testing coinstatsindex_tests
[424/470] bitcoin: testing blockfilter_tests
[425/470] bitcoin: testing key_io_tests
[426/470] bitcoin: testing scheduler_tests
[427/470] Running utility command for check-bitcoin-coinstatsindex_tests
[428/470] Running utility command for check-bitcoin-script_tests
[429/470] bitcoin: testing cuckoocache_tests
[430/470] Running utility command for check-bitcoin-blockfilter_tests
[431/470] Running utility command for check-bitcoin-key_io_tests
[432/470] Running utility command for check-bitcoin-scheduler_tests
[433/470] Running utility command for check-bitcoin-cuckoocache_tests
[434/470] bitcoin: testing blockindex_tests
[435/470] bitcoin: testing walletdb_tests
[436/470] Running utility command for check-bitcoin-blockindex_tests
[437/470] Running utility command for check-bitcoin-walletdb_tests
[438/470] bitcoin: testing crypto_tests
[439/470] Running utility command for check-bitcoin-crypto_tests
[440/470] bitcoin: testing denialofservice_tests
[441/470] bitcoin: testing txvalidationcache_tests
[442/470] bitcoin: testing miner_tests
[443/470] Running utility command for check-bitcoin-denialofservice_tests
[444/470] Running utility command for check-bitcoin-txvalidationcache_tests
[445/470] Running utility command for check-bitcoin-miner_tests
[446/470] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/addressbooktests.cpp.o
[447/470] bitcoin: testing init_tests
[448/470] bitcoin: testing uint256_tests
[449/470] Running utility command for check-bitcoin-init_tests
[450/470] Running utility command for check-bitcoin-uint256_tests
[451/470] Building CXX object src/qt/test/CMakeFiles/test_bitcoin-qt.dir/wallettests.cpp.o
[452/470] bitcoin: testing merkle_tests
[453/470] bitcoin: testing rcu_tests
[454/470] Running utility command for check-bitcoin-merkle_tests
[455/470] Running utility command for check-bitcoin-rcu_tests
[456/470] Linking CXX executable src/qt/test/test_bitcoin-qt
[457/470] bitcoin: testing wallet_crypto_tests
[458/470] Running utility command for check-bitcoin-wallet_crypto_tests
[459/470] bitcoin-qt: testing test_bitcoin-qt
[460/470] Running bitcoin-qt test suite
PASSED: bitcoin-qt test suite
[461/470] bitcoin: testing coinselector_tests
[462/470] bitcoin: testing blockcheck_tests
[463/470] Running utility command for check-bitcoin-coinselector_tests
[464/470] Running utility command for check-bitcoin-blockcheck_tests
[465/470] bitcoin: testing transaction_tests
[466/470] Running utility command for check-bitcoin-transaction_tests
[467/470] bitcoin: testing coins_tests
[468/470] Running utility command for check-bitcoin-coins_tests
ninja: build stopped: cannot make progress due to previous errors.
Build build-clang-tidy failed with exit code 1

rebase for unrelated test failure (can be "fixed" by backporting core#21689)

This revision is now accepted and ready to land.Oct 7 2022, 10:06