txmempool -/-> validation 1/2: improve performance of check() and remove dependency on validation #23157

glozow · 2021-10-01T16:06:21Z

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.

glozow · 2021-10-01T16:07:01Z

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)

flack · 2021-10-01T17:19:19Z

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`

DrahtBot · 2021-10-01T17:29:49Z

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#23173 (Add ChainstateManager::ProcessTransaction by jnewbery)
#22677 (cut the validation <-> txmempool circular dependency 2/2 by glozow)
#21527 (net_processing: lock clean up by ajtowns)
#17786 (refactor: Nuke policy/fees->mempool circular dependencies by hebasto)

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.

theStack

Concept ACK

src/bench/mempool_stress.cpp

jnewbery

utACK 4bc0c8066e79f0d95053bcc2449a7d354eaa9c25

I've left a few nitty style comments inline.

I found the ordering of the commits:

[mempool] speed up check by using coins cache and iterating in topo order
[mempool] assert that check() always goes in topological order
[mempool] remove code needed for unsorted mempool checking

to be a little bit confusing. In the intermediate commits, you have things like:

                assert(mempoolDuplicate.HaveCoin(txin.prevout));
                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:

the first commit just changes the for loop to use GetSortedDepthAndScore() and adds the prev_ancestor_count sanity check.
the second commit removes the 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?

src/bench/mempool_stress.cpp

src/txmempool.cpp

glozow · 2021-10-04T12:41:55Z

@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.

src/txmempool.cpp

jnewbery · 2021-10-04T13:27:35Z

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.

… 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.

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

jnewbery · 2021-10-04T15:45:40Z

reACK 082c5bf

SachinMeier · 2021-10-06T00:45:29Z

src/bench/mempool_stress.cpp

+    int childTxs = 800;
+    if (bench.complexityN() > 1) {
+        childTxs = static_cast<int>(bench.complexityN());
+    }


Nit: This could be simplified to:

int childTxs = bench.complexityN() > 1 ? static_cast<int>(bench.complexityN()) : 800;

as it is on line 105

GeneFerneau · 2021-10-06T03:00:44Z

tACK 082c5bf

Ran the bench a few times before and after the optimization:

Before optimization refactor

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

After optimization refactor

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

Optimization increase in op/s

93,323,779.84 / 12,305,977.78 = 7.5836 (758.36%)

LarryRuane · 2021-10-06T16:43:21Z

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`

rajarshimaitra

tACK 082c5bf

Bench comparison

Optimized

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`

Non-Optimized

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.

theStack

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 30e240f (with original check as on master branch):

$ ./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 54c6f3c (with optimized check):

$ ./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.

glozow · 2021-10-20T09:16:11Z

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...

theStack · 2021-10-20T14:18:30Z

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.

theStack

Code-review ACK 082c5bf

…ce of c…

mjdietzx

Post merge ACK 082c5bf

Warming up to review some of your open PRs. Just one question / possible nit. You are KILLING it with these PRs, well done 💪

mjdietzx · 2021-10-28T22:04:40Z

src/txmempool.cpp

        assert(it->GetSizeWithAncestors() == nSizeCheck);
        assert(it->GetSigOpCostWithAncestors() == nSigOpCheck);
        assert(it->GetModFeesWithAncestors() == nFeesCheck);
+        // 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 e8639ec 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

It's not strictly necessary, no. It's just a relatively cheap-to-run sanity check. It can make things easier to debug if we have any problems, but yes it can be removed and this code would still be checking the same things.

Summary: This is a backport of [[bitcoin/bitcoin#23157 | core#23157]] [1 & 2/8] bitcoin/bitcoin@cb14071 bitcoin/bitcoin@30e240f Test Plan: `ninja bench-bitcoin` | ns/op | op/s | err% | total | benchmark |--------------------|--------------------|--------|----------|---------- | 172,478,220.00 | 5.80 | 0.1% | 1.90 | `ComplexMemPool` | ... | ... | ... | ... | ... | 8.07 | 123,977,164.61 | 0.0% | 0.00 | `MempoolCheck` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Subscribers: Fabien Differential Revision: https://reviews.bitcoinabc.org/D12169

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. bitcoin/bitcoin@54c6f3c > [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. bitcoin/bitcoin@e8639ec This is a backport of [[bitcoin/bitcoin#23157 | 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

Summary: 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. This is a backport of [[bitcoin/bitcoin#23157 | core#23157]] [6/8] bitcoin/bitcoin@9e8d7ad Notes: - there was another occurence of the removed `UpdateCoins` function in the unit test added in rABC880d847f076f7b38c849ce3f31120f2f582a0ba0 . For that case, as the tx is a coinbase transaction (without inputs), `UpdateCoins` was just calling `AddCoins`. - the removed `UpdateCoins` function was slighlty modified in D1479 to avoid building an uneccessary `CTxUndo` Depends on D12171 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D12172

Summary: 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. This is a backport of [[bitcoin/bitcoin#23157 | core#23157]] [7/8] bitcoin/bitcoin@ed6115f Depends on D12172 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Differential Revision: https://reviews.bitcoinabc.org/D12173

Summary: Removes check's dependency on validation.h. This is a step towards removing the `txmempool --> validation` circular dependency. From the PR's description: > There are two functions in txmempool that need validation right now: check() and removeForReorg(). This PR removes the dependencies in check(). This concludes backport of [[bitcoin/bitcoin#23157 | core#23157]] [8/8] bitcoin/bitcoin@082c5bf#diff-6875de769e90cec84d2e8a9c1b962cdbcda44d870d42e4215827e599e11e90e3 Depends on D12173 The fuzzer change is not applicable due to missing backports. Test Plan: `ninja all check-all bench-bitcoin` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Subscribers: Fabien Differential Revision: https://reviews.bitcoinabc.org/D12174

[refactor/bench] make mempool_stress bench reusable and parameterizable

cb14071

glozow mentioned this pull request Oct 1, 2021

cut the validation <-> txmempool circular dependency 2/2 #22677

Merged

DrahtBot added the Mempool label Oct 1, 2021

This was referenced Oct 1, 2021

Deprecate main and test -chain params #23090

Closed

refactor: Nuke policy/fees->mempool circular dependencies #17786

Merged

theStack reviewed Oct 3, 2021

View reviewed changes

src/bench/mempool_stress.cpp Outdated Show resolved Hide resolved

jnewbery reviewed Oct 4, 2021

View reviewed changes

glozow force-pushed the 2021-09-speed-mempool-check branch from 4bc0c80 to a420bcb Compare October 4, 2021 12:31

jnewbery reviewed Oct 4, 2021

View reviewed changes

src/txmempool.cpp Outdated Show resolved Hide resolved

glozow force-pushed the 2021-09-speed-mempool-check branch from a420bcb to 6bb6ee4 Compare October 4, 2021 12:50

glozow added 7 commits October 4, 2021 15:00

[bench] Benchmark CTxMemPool::check()

30e240f

[mempool] remove now-unnecessary code

e8639ec

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.

MOVEONLY: remove single-use helper func CheckInputsAndUpdateCoins

09d1891

[mempool] simplify some check() logic

ed6115f

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.

[refactor] pass coinsview and height to check()

082c5bf

Removes check's dependency on validation.h

glozow force-pushed the 2021-09-speed-mempool-check branch from 6bb6ee4 to 082c5bf Compare October 4, 2021 14:02

DrahtBot mentioned this pull request Oct 4, 2021

Add ChainstateManager::ProcessTransaction #23173

Merged

DrahtBot mentioned this pull request Oct 5, 2021

net_processing: lock clean up #21527

Closed

SachinMeier reviewed Oct 6, 2021

View reviewed changes

rajarshimaitra reviewed Oct 6, 2021

View reviewed changes

theStack reviewed Oct 10, 2021

View reviewed changes

theStack approved these changes Oct 23, 2021

View reviewed changes

maflcko merged commit 1847ce2 into bitcoin:master Oct 25, 2021

glozow deleted the 2021-09-speed-mempool-check branch October 25, 2021 13:26

maflcko added the Refactoring label Oct 25, 2021

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Oct 25, 2021

Merge bitcoin#23157: txmempool -/-> validation 1/2: improve performan…

ff642d7

…ce of c…

mjdietzx reviewed Oct 28, 2021

View reviewed changes

bitcoin locked and limited conversation to collaborators Oct 30, 2022

txmempool -/-> validation 1/2: improve performance of check() and remove dependency on validation #23157

txmempool -/-> validation 1/2: improve performance of check() and remove dependency on validation #23157

Uh oh!

Conversation

glozow commented Oct 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

glozow commented Oct 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

flack commented Oct 1, 2021

Uh oh!

DrahtBot commented Oct 1, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

jnewbery left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

glozow commented Oct 4, 2021

Uh oh!

Uh oh!

jnewbery commented Oct 4, 2021

Uh oh!

jnewbery commented Oct 4, 2021

Uh oh!

SachinMeier Oct 6, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

GeneFerneau commented Oct 6, 2021

Before optimization refactor

After optimization refactor

Optimization increase in op/s

Uh oh!

LarryRuane commented Oct 6, 2021

Uh oh!

rajarshimaitra left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Optimized

Non-Optimized

Uh oh!

theStack left a comment • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

glozow commented Oct 20, 2021

Uh oh!

theStack commented Oct 20, 2021

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

mjdietzx left a comment

Choose a reason for hiding this comment

Uh oh!

mjdietzx Oct 28, 2021

Choose a reason for hiding this comment

Uh oh!

mjdietzx Oct 28, 2021

Choose a reason for hiding this comment

Uh oh!

glozow Oct 29, 2021

Choose a reason for hiding this comment

Uh oh!

glozow commented Oct 1, 2021 •

edited

Loading

glozow commented Oct 1, 2021 •

edited

Loading

DrahtBot commented Oct 1, 2021 •

edited

Loading

SachinMeier Oct 6, 2021 •

edited

Loading

rajarshimaitra left a comment •

edited

Loading

theStack left a comment •

edited

Loading