truc: optimize the in package relation calculation

HowHsu commented at 11:47 am on July 25, 2025: none

In PackageTRUCChecks(), we calculate the in-package-parents for an in package tx, which results in the total time complexisity being O(n^2), n is the number of Txs in the package. Let’s precompute the overall relationships between all transactions to make it be O(n).

DrahtBot commented at 11:47 am on July 25, 2025: contributor

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

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33062.

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:

#33094 (refactor: unify container presence checks by l0rinc)
#28676 (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.

fanquake requested review from glozow on Jul 25, 2025

in src/policy/truc_policy.cpp:72 in f268735ac4 outdated

66     // This function is specialized for these limits, and must be reimplemented if they ever change.
67     static_assert(TRUC_ANCESTOR_LIMIT == 2);
68     static_assert(TRUC_DESCENDANT_LIMIT == 2);
69 
70-    const auto in_package_parents{FindInPackageParents(package, ptx)};
71+    const auto in_package_parents{FindInPackageParents(tx_index, relations)};

glozow commented at 1:18 pm on July 25, 2025:

I think most of the benefits of precomputing this would be realized in the loop a few lines down looking for a package_tx sibling. As is, I’m not sure how much faster precomputation is: n=2 in normal cases, and we don’t need to continue computing parents once we’ve realized it’s oversize.

HowHsu commented at 8:06 am on July 26, 2025:

Hi glozow,

I think most of the benefits of precomputing this would be realized in the loop a few lines down looking for a package_tx sibling.

Could you elaborate on this? The parent may be from mempool, so the precomputing (build relationship of parent->vec<child>) doesn’t work in this case .

As is, I’m not sure how much faster precomputation is: n=2 in normal cases, and we don’t need to continue computing parents once we’ve realized it’s oversize.

Yep, for n=2, I think no much difference here.

glozow commented at 7:53 pm on July 28, 2025:

Ah right, it actually doesn’t help there. You can ignore that.

in src/policy/truc_policy.cpp:18 in f268735ac4 outdated

16 #include <vector>
17 
18-/** Helper for PackageTRUCChecks: Returns a vector containing the indices of transactions (within
19- * package) that are direct parents of ptx. */
20-std::vector<size_t> FindInPackageParents(const Package& package, const CTransactionRef& ptx)
21+std::vector<std::vector<size_t>> BuildInPackageRelations(const Package& package)

glozow commented at 1:20 pm on July 25, 2025:

Would you consider using DepGraph instead of a matrix of indices (it’s basically the same thing but more compact)?

HowHsu commented at 1:08 am on July 29, 2025:

Would you consider using DepGraph instead of a matrix of indices (it’s basically the same thing but more compact)?

Sure, I’ll look into it.

HowHsu commented at 8:41 am on July 30, 2025:

@glozow Hi glozow, seems DepGraph stores all ancestors of a tx, while here:

0if (mempool_ancestors.size() + in_package_parents.size() + 1 > TRUC_ANCESTOR_LIMIT)

shows PackageTRUCChecks() want the parent (the direct ancestor). Using DepGraph changes the semantics of this function. Any hints about the above code: Do we actually want mempool_ancestors.size() + in_package_parents.size() or mempool_ancestors.size + in_package_ancestors.size() here ? Using the Bitset directly is an alternative way.

glozow commented at 2:28 pm on July 30, 2025:

fwiw I don’t think this needs to be direct parents, it’s just implemented this way because the limit is 2.

As a more general note - thanks for working on this and I don’t want to be discouraging, but I’m not sure that a marginal improvement to this small function is worth this much effort. I see you have some other PRs that might be more impactful, so maybe focus on those? Maybe we can come back to this in the future if it helps with other things.

HowHsu commented at 2:47 pm on July 30, 2025:

fwiw I don’t think this needs to be direct parents, it’s just implemented this way because the limit is 2.

As a more general note - thanks for working on this and I don’t want to be discouraging, but I’m not sure that a marginal improvement to this small function is worth this much effort. I see you have some other PRs that might be more impactful, so maybe focus on those? Maybe we can come back to this in the future if it helps with other things.

Sure, thanks.

truc: optimize the in package relation calculation

In PackageTRUCChecks(), we calculate the in-package-parents for an
in package tx, which results in the total time complexisity being
O(n^2), n is the number of Txs in the package. Let's precompute the
overall relationships between all transactions to make it be O(n).

Signed-off-by: Hao Xu <hao.xu@linux.dev>

28addcb5b1

HowHsu force-pushed on Jul 25, 2025

DrahtBot added the label CI failed on Jul 25, 2025

glozow added the label Refactoring on Jul 25, 2025

DrahtBot removed the label CI failed on Jul 25, 2025

dr8931240-ux commented at 0:10 am on July 26, 2025: none

Thank you

dr8931240-ux commented at 0:40 am on July 26, 2025: none

Ok

truc: optimize the in package relation calculation #33062

Code Coverage & Benchmarks

Reviews

Conflicts