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

pull l0rinc wants to merge 4 commits into bitcoin:master from l0rinc:paplorinc/CalculateDescendants changing 1 files +10 −17
  1. 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
  2. Replace early guard check with insert
    This will unify the code in the next stage to simplify iteration
    cae7deb4d7
  3. DrahtBot commented at 4:19 PM on June 23, 2024: contributor

    <!--e57a25ab6845829454e8d69fc972939a-->

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

    <!--006a51241073e994b41acfe9ec718e94-->

    Code Coverage

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

    <!--021abf342d371248e50ceaed478a90ca-->

    Reviews

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

    <!--174a7506f384e20aa4161008e828411d-->

    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.

  4. 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
  5. l0rinc force-pushed on Jun 23, 2024
  6. l0rinc marked this as ready for review on Jun 23, 2024
  7. 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
  8. l0rinc force-pushed on Jun 24, 2024
  9. l0rinc force-pushed on Jun 24, 2024
  10. l0rinc force-pushed on Jun 24, 2024
  11. 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
  12. 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
  13. l0rinc force-pushed on Jun 24, 2024
  14. l0rinc marked this as a draft on Jun 24, 2024
  15. 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
  16. l0rinc force-pushed on Jun 24, 2024
  17. l0rinc marked this as ready for review on Jun 24, 2024
  18. 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.

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

  20. l0rinc closed this on Jul 1, 2024
  21. l0rinc deleted the branch on Jul 1, 2024
  22. bitcoin locked this on Jul 1, 2025
Contributors
l0rincDrahtBotglozow
github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2026-07-09 06:47 UTC