optimization: Switch CTxMemPool::CalculateDescendants from set to vector to reduce transaction hash calculations #30325

l0rinc commented at 4:19 PM on June 23, 2024: contributor

Profiling BlockAssemblerAddPackageTxns indicated excessive hash recalculations: <img src="https://github.com/bitcoin/bitcoin/assets/1841944/e1687162-30b5-47b6-83b3-d234cd156395">

The original implementation used a set to manage the stack of transactions for a depth-first traversal of its child transactions. However, since we're already filtering via setDescendants before adding them to stage, duplicates cannot exist anyway. Therefore, we can change it to a simple vector, providing efficient push and pop operations, eliminating the need for redundant duplicate checks and hash calculations.

Benchmarking BlockAssemblerAddPackageTxns locally an on CI reveals a significant speed increase - please validate it on your machine!

./src/bench/bench_bitcoin --filter='BlockAssemblerAddPackageTxns' --min-time=1000

before: | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 377,256,875.00 | 2.65 | 0.2% | 4.15 | BlockAssemblerAddPackageTxns

after: | ns/op | op/s | err% | total | benchmark |--------------------:|--------------------:|--------:|----------:|:---------- | 275,087,833.00 | 3.64 | 0.1% | 3.02 | BlockAssemblerAddPackageTxns

Replace early guard check with insert

This will unify the code in the next stage to simplify iteration

cae7deb4d7

DrahtBot commented at 4:19 PM on June 23, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process. A summary of reviews will appear here.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28676 ([WIP] Cluster mempool implementation by sdaftuar)

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.

l0rinc renamed this:
~~Optimization: Switch CTxMemPool::CalculateDescendants from set to deque to reduce transaction hash calculations~~
optimization: Switch CTxMemPool::CalculateDescendants from set to deque to reduce transaction hash calculations
on Jun 23, 2024

l0rinc force-pushed on Jun 23, 2024

l0rinc marked this as ready for review on Jun 23, 2024

l0rinc renamed this:
~~optimization: Switch CTxMemPool::CalculateDescendants from set to deque to reduce transaction hash calculations~~
optimization: Switch CTxMemPool::CalculateDescendants from set to vector to reduce transaction hash calculations
on Jun 24, 2024

l0rinc force-pushed on Jun 24, 2024

Switch CalculateDescendants from set to vector for stack management

The original implementation used a set (stage) to manage the stack of transactions for a depth-first traversal of its child transactions.
However, since we're already filtering by setDescendants count, duplicates cannot exist in stage anyway.
Therefore, we can change it to a vector, which provides amortized constant time push and pop operations without any hash calculations.

f37346e79c

Replace redundant count + insert with a single insert

We're already inserting before the iteration and adding the children during the iteration, making the counting redundant.

42b0500e5f

l0rinc force-pushed on Jun 24, 2024

l0rinc marked this as a draft on Jun 24, 2024

Simplify iterations, types

Many types can be `auto` and `const`.

> ./src/bench/bench_bitcoin --filter='BlockAssemblerAddPackageTxns' --min-time=1000

before:
|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|      377,256,875.00 |                2.65 |    0.2% |      4.15 | `BlockAssemblerAddPackageTxns`

after:
|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|      275,087,833.00 |                3.64 |    0.1% |      3.02 | `BlockAssemblerAddPackageTxns`

e0fd446845

l0rinc force-pushed on Jun 24, 2024

l0rinc marked this as ready for review on Jun 24, 2024

glozow commented at 7:31 AM on July 1, 2024: member

Seems like a reasonable thing to do, but this conflicts with / is already done in #28676. See the "Select transactions for blocks based on chunk feerate" commit there which gets rid of this call.

I think our current policy is to avoid making refactoring changes that would need to be redone or removed in cluster mempool.

l0rinc commented at 8:29 AM on July 1, 2024: contributor

Thanks for checking @glozow. Closing, invalidated by https://github.com/bitcoin/bitcoin/pull/28676/files#diff-c065d4cd2398ad0dbcef393c5dfc53f465bf44723348892395fffd2fb3bac522R377

l0rinc closed this on Jul 1, 2024

l0rinc deleted the branch on Jul 1, 2024

bitcoin locked this on Jul 1, 2025