Remove the txmempool <-> validation circular dependency by removing txmempool’s dependency on validation. There are two functions in txmempool that need validation right now: check() and removeForReorg(). This PR removes the dependencies in check().
This PR also improves the performance of CTxMemPool::check() by walking through the entries exactly once, in ascending ancestorcount order, which guarantees that we see parents before children.
bench results on master:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 8.34 | 119,851,301.59 | 0.0% | 0.01 | MempoolCheck |
results on top of this PR:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 2.13 | 468,844,203.61 | 0.0% | 0.01 | MempoolCheck |
(~4x faster)
Sorry for being off-topic, but just because I always twitch slightly when I see it: The bench output is already formatted in Markdown extended syntax, so if you just paste it into the comment box, without backticks around it (and without leading whitespace), it renders a bit nicer. And it’s easier to do, because less steps :-)
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 8.34 | 119,851,301.59 | 0.0% | 0.01 | MempoolCheck |
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 2.13 | 468,844,203.61 | 0.0% | 0.01 | MempoolCheck |
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
ChainstateManager::ProcessTransaction by jnewbery)If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
106+ int childTxs = 2000;
107+ if (bench.complexityN() > 1) {
108+ childTxs = static_cast<int>(bench.complexityN());
109+ }
110+ std::vector<CTransactionRef> ordered_coins = CreateOrderedCoins(det_rand, childTxs, /* min_ancestors */ 5);
111+ std::vector<size_t> random_index;
104+{
105+ FastRandomContext det_rand{true};
106+ int childTxs = 2000;
107+ if (bench.complexityN() > 1) {
108+ childTxs = static_cast<int>(bench.complexityN());
109+ }
Consider making const and using current variable naming style:
0 const int child_txs{bench.complexityN() > 1 ?
1 static_cast<int>(bench.complexityN()) :
2 2000};
105+ FastRandomContext det_rand{true};
106+ int childTxs = 2000;
107+ if (bench.complexityN() > 1) {
108+ childTxs = static_cast<int>(bench.complexityN());
109+ }
110+ std::vector<CTransactionRef> ordered_coins = CreateOrderedCoins(det_rand, childTxs, /* min_ancestors */ 5);
0 const std::vector<CTransactionRef> ordered_coins = CreateOrderedCoins(det_rand, childTxs, /* min_ancestors */ 5);
110+ std::vector<CTransactionRef> ordered_coins = CreateOrderedCoins(det_rand, childTxs, /* min_ancestors */ 5);
111+ std::vector<size_t> random_index;
112+ random_index.resize(ordered_coins.size());
113+ std::iota(random_index.begin(), random_index.end(), 0);
114+ Shuffle(random_index.begin(), random_index.end(), FastRandomContext());
115+ auto extra_args = {"-checkmempool=1"}; // Always check
0 const auto extra_args = {"-checkmempool=1"}; // Always check
115+ auto extra_args = {"-checkmempool=1"}; // Always check
116+ const auto testing_setup = MakeNoLogFileContext<const TestingSetup>(CBaseChainParams::MAIN, extra_args);
117+ CTxMemPool pool;
118+ LOCK2(cs_main, pool.cs);
119+ for (auto& tx : ordered_coins) AddTx(tx, pool);
120+ bench.run([&]() NO_THREAD_SAFETY_ANALYSIS {
I think it helps readability to have a linebreak between the setup and the bench run:
0 for (auto& tx : ordered_coins) AddTx(tx, pool);
1
2 bench.run([&]() NO_THREAD_SAFETY_ANALYSIS {
5@@ -6,7 +6,9 @@
6 #include <policy/policy.h>
7 #include <test/util/setup_common.h>
8 #include <txmempool.h>
9+#include <validation.h>
10
11+#include <numeric>
std::iota (https://github.com/bitcoin/bitcoin/pull/23157/files#r721193126)
744@@ -751,6 +745,10 @@ void CTxMemPool::check(CChainState& active_chainstate) const
745 assert(it->GetSizeWithAncestors() == nSizeCheck);
746 assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
747 assert(it->GetModFeesWithAncestors() == nFeesCheck);
748+ // Sanity check: we are walking in ascending ancestor count order. The non-contextual
749+ // check() will have ensured that this count is accurate.
708 indexed_transaction_set::const_iterator it2 = mapTx.find(txin.prevout.hash);
709 if (it2 != mapTx.end()) {
710 const CTransaction& tx2 = it2->GetTx();
711 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
712- fDependsWait = true;
713+ // Sanity check: all parents should have been checked before their children, which
678- CAmount txfee = 0;
679- bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee);
680- assert(fCheckResult);
681- UpdateCoins(tx, mempoolDuplicate, std::numeric_limits<int>::max());
682-}
683
710 const CTransaction& tx2 = it2->GetTx();
711 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
712- fDependsWait = true;
713+ // Sanity check: all parents should have been checked before their children, which
714+ // means its outputs must be available in the coins cache.
715+ assert(mempoolDuplicate.HaveCoin(txin.prevout));
Can this assert and the assert(active_coins_tip.HaveCoin(txin.prevout)); in the else branch below now be merged into a single assert(mempoolDuplicate.HaveCoin(txin.prevout));?
If I understand correctly, the mempoolDuplicate coins cache is a copy of the active_chains_tip cache, so should have all of the coins in the UTXO set. That means mempoolDuplicate should have all of the coins that are being spent by each transaction as we iterate through the entries in depth order.
0--- a/src/txmempool.cpp
1+++ b/src/txmempool.cpp
2@@ -706,13 +706,11 @@ void CTxMemPool::check(CChainState& active_chainstate) const
3 if (it2 != mapTx.end()) {
4 const CTransaction& tx2 = it2->GetTx();
5 assert(tx2.vout.size() > txin.prevout.n && !tx2.vout[txin.prevout.n].IsNull());
6- // Sanity check: all parents should have been checked before their children, which
7- // means its outputs must be available in the coins cache.
8- assert(mempoolDuplicate.HaveCoin(txin.prevout));
9 setParentCheck.insert(*it2);
10- } else {
11- assert(active_coins_tip.HaveCoin(txin.prevout));
12 }
13+ // Sanity check: all parents should have been checked before their children, which
14+ // means its outputs must be available in the coins cache.
15+ assert(mempoolDuplicate.HaveCoin(txin.prevout));
16 // Check whether its inputs are marked in mapNextTx.
17 auto it3 = mapNextTx.find(txin.prevout);
18 assert(it3 != mapNextTx.end());
785- CheckInputsAndUpdateCoins(entry->GetTx(), mempoolDuplicate, spendheight);
786- stepsSinceLastRemove = 0;
787- }
788+ TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
789+ CAmount txfee = 0;
790+ bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee);
I know you just moved this code, but I think we should remove tx.IsCoinBase() from here, and add an assert(!tx.IsCoinBase());. The mempool shouldn’t contain coinbase transactions.
No need to do it as part of this PR. Can be a follow-up.
utACK 4bc0c8066e79f0d95053bcc2449a7d354eaa9c25
I’ve left a few nitty style comments inline.
I found the ordering of the commits:
to be a little bit confusing. In the intermediate commits, you have things like:
0 assert(mempoolDuplicate.HaveCoin(txin.prevout));
1 if (!mempoolDuplicate.HaveCoin(txin.prevout)) fDependsWait = true;
which you then remove in the subsequent commit. It’s fine, but it’s a bit more mental overhead for reviewers.
I think a more intuitive progression of commits would be to squash those three commits into two:
GetSortedDepthAndScore() and adds the prev_ancestor_count sanity check.waitingOnDependants code since the iteration is now in depth order.Is the next step here to change check() to take a const CCoinsViewCache& and int64_t height and remove the dependency on validation entirely?
@flack good tip, fixed @theStack @jnewbery thanks for your reviews, I think I’ve incorporated all suggestions :)
Is the next step here to change check() to take a const CCoinsViewCache& and int64_t height and remove the dependency on validation entirely?
Yes I thought I had included that commit here but apparently I hadn’t - last push added it.
676-{
677- TxValidationState dummy_state; // Not used. CheckTxInputs() should always pass
678- CAmount txfee = 0;
679- bool fCheckResult = tx.IsCoinBase() || Consensus::CheckTxInputs(tx, dummy_state, mempoolDuplicate, spendheight, txfee);
680- assert(fCheckResult);
681- UpdateCoins(tx, mempoolDuplicate, std::numeric_limits<int>::max());
After this commit, UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, int nHeight) is no longer used:
0diff --git a/src/validation.cpp b/src/validation.cpp
1index 4504d2ca0a..c552577229 100644
2--- a/src/validation.cpp
3+++ b/src/validation.cpp
4@@ -1225,6 +1225,7 @@ void CChainState::InvalidBlockFound(CBlockIndex* pindex, const BlockValidationSt
5 }
6 }
7
8+/** Apply the effects of this transaction on the UTXO set represented by view */
9 void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, CTxUndo &txundo, int nHeight)
10 {
11 // mark inputs spent
12@@ -1240,12 +1241,6 @@ void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, CTxUndo &txund
13 AddCoins(inputs, tx, nHeight);
14 }
15
16-void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, int nHeight)
17-{
18- CTxUndo txundo;
19- UpdateCoins(tx, inputs, txundo, nHeight);
20-}
21-
22 bool CScriptCheck::operator()() {
23 const CScript &scriptSig = ptxTo->vin[nIn].scriptSig;
24 const CScriptWitness *witness = &ptxTo->vin[nIn].scriptWitness;
25diff --git a/src/validation.h b/src/validation.h
26index b2282828ce..caa0832dd3 100644
27--- a/src/validation.h
28+++ b/src/validation.h
29@@ -229,9 +229,6 @@ PackageMempoolAcceptResult ProcessNewPackage(CChainState& active_chainstate, CTx
30 const Package& txns, bool test_accept)
31 EXCLUSIVE_LOCKS_REQUIRED(cs_main);
32
33-/** Apply the effects of this transaction on the UTXO set represented by view */
34-void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, int nHeight);
35-
36 /** Transaction validation functions */
37
38 /**
Is the next step here to change check() to take a const CCoinsViewCache& and int64_t height and remove the dependency on validation entirely?
Yes I thought I had included that commit here but apparently I hadn’t - last push added it.
It might actually be better to defer that commit until after #23173 so fewer changes are needed to net_processing. Entirely up to you.
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.
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.
UpdateCoins is an unnecessary dependency on validation. All we need to
do is add and remove coins to check inputs. We don't need the extra
logic for checking coinbases and handling TxUndos.
Also remove the wrapper function in validation.h which constructs a
throwaway TxUndo object before calling UpdateCoins because it is now
unused.
No transaction in the mempool should ever be a coinbase.
Since mempoolDuplicate's backend is the chainstate coins view, it should
always contain the coins available.
Removes check's dependency on validation.h
83+{
84+ FastRandomContext det_rand{true};
85+ int childTxs = 800;
86+ if (bench.complexityN() > 1) {
87+ childTxs = static_cast<int>(bench.complexityN());
88+ }
Nit: This could be simplified to:
0int childTxs = bench.complexityN() > 1 ? static_cast<int>(bench.complexityN()) : 800;
as it is on line 105
tACK 082c5bf
Ran the bench a few times before and after the optimization:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 81.26 | 12,306,038.69 | 0.0% | 0.01 | MempoolCheck |
| 81.26 | 12,305,850.81 | 0.0% | 0.01 | MempoolCheck |
| 81.26 | 12,306,043.84 | 0.0% | 0.01 | MempoolCheck |
| 12,305,977.78 | Average |
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 10.72 | 93,324,244.07 | 0.0% | 0.01 | MempoolCheck |
| 10.72 | 93,323,975.05 | 0.0% | 0.01 | MempoolCheck |
| 10.72 | 93,323,120.41 | 0.0% | 0.01 | MempoolCheck |
| 93,323,779.84 | Average |
93,323,779.84 / 12,305,977.78 = 7.5836 (758.36%)
concept ACK
I’ll try to do a code review, but FWIW, my working clone is usually built with optimization disabled (-O0) to make debugging easier, and there’s an even bigger improvement that way (approximately 18x):
before:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 215.53 | 4,639,632.68 | 2.1% | 0.01 | MempoolCheck |
after:
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 12.12 | 82,495,736.15 | 3.8% | 0.01 | MempoolCheck |
tACK https://github.com/bitcoin/bitcoin/pull/23157/commits/082c5bf099c64e3d27abe9b68a71ce500b693e7e
Bench comparison
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 2.39 | 417,806,513.20 | 0.6% | 0.01 | MempoolCheck |
| 2.39 | 419,189,093.49 | 0.6% | 0.01 | MempoolCheck |
| 2.39 | 419,188,854.66 | 0.6% | 0.01 | MempoolCheck |
| 2.39 | 419,049,672.97 | 0.3% | 0.01 | MempoolCheck |
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 12.61 | 79,317,536.11 | 6.8% | 0.01 | MempoolCheck |
| 12.20 | 81,995,745.32 | 9.2% | 0.01 | MempoolCheck |
| 12.22 | 81,862,095.21 | 1.9% | 0.01 | MempoolCheck |
| 12.17 | 82,167,397.00 | 0.8% | 0.01 | MempoolCheck |
It seems I am observing only 6x speedup. But that’s probably my local benching issue.
Not sure what’s different or wrong on my system (running OpenBSD 6.9/amd64), but the benchmark doesn’t show any noticable difference after the optimization in CTxMemPool::check, it even seems to be worse.
at commit https://github.com/bitcoin/bitcoin/pull/23157/commits/30e240f65e69c6dffcd033afc63895345bd51f53 (with original check as on master branch):
0$ ./src/bench/bench_bitcoin -filter=MempoolCheck
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 100.66 | 9,934,356.36 | 1.6% | 0.01 | MempoolCheck |
at commit https://github.com/bitcoin/bitcoin/pull/23157/commits/54c6f3c1da01090aee9691a2c2bee0984a054ce8 (with optimized check):
0$ ./src/bench/bench_bitcoin -filter=MempoolCheck
| ns/op | op/s | err% | total | benchmark |
|---|---|---|---|---|
| 107.36 | 9,314,108.15 | 4.4% | 0.01 | MempoolCheck |
Will try on a Debian Linux machine later to compare.
// EDIT: It seems like the difference in benchmark results is almost only caused by the very last commit.
It seems like the difference in benchmark results is almost only caused by the very last commit.
That sounds strange to me, but I guess it’s plausible that the bench only sees a speedup because of the parameter change rather than ordered traversal. Even so, I’d want to remove all that unnecessary code…
That sounds strange to me, but I guess it’s plausible that the bench only sees a speedup because of the parameter change rather than ordered traversal. Even so, I’d want to remove all that unnecessary code…
Agree, removing unnecessary code is always a good thing! I didn’t intend to sound concept NACKy, this was just a hint that the posted benchmark results have to be taken with a grain of salt :) will likely code-review this PR within the next days.
751@@ -751,6 +752,9 @@ void CTxMemPool::check(CChainState& active_chainstate) const
752 assert(it->GetSizeWithAncestors() == nSizeCheck);
753 assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
754 assert(it->GetModFeesWithAncestors() == nFeesCheck);
755+ // Sanity check: we are walking in ascending ancestor count order.
Why is this sanity check necessary? It’s not like GetSortedDepthAndScore() is complicated or has non-deterministic behavior, right?
And why do we really need to fail if somehow we do encounter this case? The only down-side I see is marking this as a “check later” transaction which is just a minor performance hit?
Are there any race conditions where we could possibly see this assert throw?
Alright, I’m reviewing commit by commit, and now in e8639ec26aaf4de3fae280963434bf1cf2017b6f I am starting to understand why we have this assert.
But, I’m still wondering, why have this assert if assert(mempoolDuplicate.HaveCoin(txin.prevout)); will take care of the job should we run into any problems? I still don’t see why this is beneficial
Post merge ACK 082c5bf099c64e3d27abe9b68a71ce500b693e7e
Warming up to review some of your open PRs. Just one question / possible nit. You are KILLING it with these PRs, well done 💪