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

No conflicts as of last run.

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

in src/policy/truc_policy.cpp:26 in 28addcb5b1

35-        // We assume the package is sorted, so that we don't need to continue
36-        // looking past the transaction itself.
37-        if (&(*tx) == &(*ptx)) break;
38-        if (possible_parents.count(tx->GetHash())) {
39-            in_package_parents.push_back(i);
40+        pindexes.clear();

l0rinc commented at 0:01 am on August 5, 2025:

what’s the reason for reusing the set here? This will just create a dependency between the loops. If you have some benchmarks, it would be good to double-check, but this might be simpler (and maybe even faster):

0        std::unordered_set<size_t> pindexes;
1        pindexes.reserve(tx->vin.size()); // TODO or whatever size you expect

in src/policy/truc_policy.cpp:31 in 28addcb5b1

40+        pindexes.clear();
41+        for (auto &input : tx->vin) {
42+            if (possible_parents.count(input.prevout.hash))
43+                pindexes.insert(possible_parents[input.prevout.hash]);
44         }
45+        std::copy(pindexes.begin(), pindexes.end(), std::back_inserter(relations[i]));

l0rinc commented at 0:02 am on August 5, 2025:

we could probably use the newer version here:

0        std::ranges::copy(pindexes, std::back_inserter(relations[i]));

I haven’t checked the usages, but why are we storing these in a vector in the first place if they have a uniqueness constraint?

in src/policy/truc_policy.cpp:29 in 28addcb5b1

38-        if (possible_parents.count(tx->GetHash())) {
39-            in_package_parents.push_back(i);
40+        pindexes.clear();
41+        for (auto &input : tx->vin) {
42+            if (possible_parents.count(input.prevout.hash))
43+                pindexes.insert(possible_parents[input.prevout.hash]);

l0rinc commented at 0:04 am on August 5, 2025:

C++20 allows ::contains (+ nit: braces):

0            if (possible_parents.contains(input.prevout.hash)) {
1                pindexes.insert(possible_parents[input.prevout.hash]);
2            }

Or even better, to avoid double hashing (via existence check first, and getting the value, second), we might as well:

0            if (const auto it{possible_parents.find(input.prevout.hash)}; it != possible_parents.end()) {
1                pindexes.insert(it->second);
2            }

in src/policy/truc_policy.cpp:40 in 28addcb5b1

50+    return relations;
51+}
52+
53+/** Helper for PackageTRUCChecks: Returns a vector containing the indices of transactions (within
54+ * package) that are direct parents of ptx. */
55+std::vector<size_t> FindInPackageParents(const size_t tx_index, const auto& relations)

l0rinc commented at 0:13 am on August 5, 2025:

we don’t usually auto parameters and not sure why we’re copying the result:

0inline const std::vector<size_t>& FindInPackageParents(size_t tx_index, const std::vector<std::vector<size_t>>& relations)
1{
2    return relations[tx_index];
3}

l0rinc changes_requested

l0rinc commented at 0:24 am on August 5, 2025: contributor

My understanding is that this isn’t a bottleneck, optimizing it without a benchmark or an easily reproducible usecase seems like it’s a solution begging for a problem - I speak from personal experience, that’s how I started as well :)

I left a few comments while reviewing anyway, but without a concept ack on the idea itself from those who are more familiar with it, it likely won’t get merged.

HowHsu commented at 5:15 am on August 5, 2025: none

My understanding is that this isn’t a bottleneck, optimizing it without a benchmark or an easily reproducible usecase seems like it’s a solution begging for a problem - I speak from personal experience, that’s how I started as well :)

I left a few comments while reviewing anyway, but without a concept ack on the idea itself from those who are more familiar with it, it likely won’t get merged.

Thanks, l0rinc. I’ll leave this patch alone for now.

fanquake marked this as a draft on Aug 6, 2025

truc: optimize the in package relation calculation #33062

Code Coverage & Benchmarks

Reviews

Conflicts