truc: optimize the in package relation calculation #33062

HowHsu · 2025-07-25T11:47:14Z

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 · 2025-07-25T11:47:18Z

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.

src/policy/truc_policy.cpp

glozow · 2025-07-25T13:20:59Z

src/policy/truc_policy.cpp

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


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

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.

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

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

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.

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.

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>

l0rinc

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.

l0rinc · 2025-08-05T00:01:56Z

src/policy/truc_policy.cpp

-        if (&(*tx) == &(*ptx)) break;
-        if (possible_parents.count(tx->GetHash())) {
-            in_package_parents.push_back(i);
+        pindexes.clear();


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):

Suggested change

pindexes.clear();

std::unordered_set<size_t> pindexes;

pindexes.reserve(tx->vin.size()); // TODO or whatever size you expect

l0rinc · 2025-08-05T00:02:16Z

src/policy/truc_policy.cpp

        }
+        std::copy(pindexes.begin(), pindexes.end(), std::back_inserter(relations[i]));


we could probably use the newer version here:

Suggested change

std::copy(pindexes.begin(), pindexes.end(), std::back_inserter(relations[i]));

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?

l0rinc · 2025-08-05T00:04:28Z

src/policy/truc_policy.cpp

+            if (possible_parents.count(input.prevout.hash))
+                pindexes.insert(possible_parents[input.prevout.hash]);


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

Suggested change

if (possible_parents.count(input.prevout.hash))

pindexes.insert(possible_parents[input.prevout.hash]);

if (possible_parents.contains(input.prevout.hash)) {

pindexes.insert(possible_parents[input.prevout.hash]);

}

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

Suggested change

if (possible_parents.count(input.prevout.hash))

pindexes.insert(possible_parents[input.prevout.hash]);

if (const auto it{possible_parents.find(input.prevout.hash)}; it != possible_parents.end()) {

pindexes.insert(it->second);

}

l0rinc · 2025-08-05T00:13:54Z

src/policy/truc_policy.cpp

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


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

Suggested change

std::vector<size_t> FindInPackageParents(const size_t tx_index, const auto& relations)

inline const std::vector<size_t>& FindInPackageParents(size_t tx_index, const std::vector<std::vector<size_t>>& relations)

{

return relations[tx_index];

}

HowHsu · 2025-08-05T05:15:44Z

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 requested a review from glozow July 25, 2025 12:22

glozow reviewed Jul 25, 2025

View reviewed changes

HowHsu force-pushed the truc branch from f268735 to 28addcb Compare July 25, 2025 14:08

DrahtBot added the CI failed label Jul 25, 2025

glozow added the Refactoring label Jul 25, 2025

DrahtBot removed the CI failed label Jul 25, 2025

This comment was marked as spam.

Sign in to view

This was referenced Jul 29, 2025

Cluster mempool implementation #28676

Open

refactor: unify container presence checks #33094

Closed

l0rinc suggested changes Aug 5, 2025

View reviewed changes

fanquake marked this pull request as draft August 6, 2025 13:49

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

truc: optimize the in package relation calculation #33062

truc: optimize the in package relation calculation #33062

HowHsu commented Jul 25, 2025

Uh oh!

DrahtBot commented Jul 25, 2025 •

edited

Loading

Uh oh!

Uh oh!

glozow Jul 25, 2025

Uh oh!

HowHsu Jul 29, 2025

Uh oh!

HowHsu Jul 30, 2025

Uh oh!

glozow Jul 30, 2025

Uh oh!

HowHsu Jul 30, 2025

Uh oh!

This comment was marked as spam.

Uh oh!

This comment was marked as spam.

Uh oh!

l0rinc left a comment

Uh oh!

l0rinc Aug 5, 2025 •

edited

Loading

Uh oh!

l0rinc Aug 5, 2025

Uh oh!

l0rinc Aug 5, 2025

Uh oh!

l0rinc Aug 5, 2025

Uh oh!

HowHsu commented Aug 5, 2025

Uh oh!

Uh oh!

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

		}
		std::copy(pindexes.begin(), pindexes.end(), std::back_inserter(relations[i]));

	std::copy(pindexes.begin(), pindexes.end(), std::back_inserter(relations[i]));
	std::ranges::copy(pindexes, std::back_inserter(relations[i]));

		if (possible_parents.count(input.prevout.hash))
		pindexes.insert(possible_parents[input.prevout.hash]);

-std::vector<size_t> FindInPackageParents(const size_t tx_index, const auto& relations)
+inline const std::vector<size_t>& FindInPackageParents(size_t tx_index, const std::vector<std::vector<size_t>>& relations)
+{
+    return relations[tx_index];
+}

truc: optimize the in package relation calculation #33062

Are you sure you want to change the base?

truc: optimize the in package relation calculation #33062

Conversation

HowHsu commented Jul 25, 2025

Uh oh!

DrahtBot commented Jul 25, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage & Benchmarks

Reviews

Conflicts

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

This comment was marked as spam.

Uh oh!

This comment was marked as spam.

Uh oh!

l0rinc left a comment

Choose a reason for hiding this comment

Uh oh!

l0rinc Aug 5, 2025 • 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!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

HowHsu commented Aug 5, 2025

Uh oh!

Uh oh!

DrahtBot commented Jul 25, 2025 •

edited

Loading

l0rinc Aug 5, 2025 •

edited

Loading