clusterlin: remove unused MergeLinearizations (cleanup)
What changed, and why it matters
This commit simply removes an unused helper function called MergeLinearizations, along with its benchmark and fuzz test. It is a routine code cleanup with no security relevance.
No security action needed; this is a benign cleanup commit.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The patch deletes the MergeLinearizations template function from src/cluster_linearize.h and removes all associated benchmark entries in src/bench/cluster_linearize.cpp and the fuzz target clusterlin_merge in src/test/fuzz/cluster_linearize.cpp. The commit message explicitly states the function ‘ended up never being used in txgraph.’ No functional behavior of Bitcoin Core changes; this is dead-code elimination.
Changed components
src/cluster_linearize.hsrc/bench/cluster_linearize.cppsrc/test/fuzz/cluster_linearize.cppInspect captured patch +0 / −105
diff --git a/src/bench/cluster_linearize.cpp b/src/bench/cluster_linearize.cpp
index 4c320380..a856d247 100644
--- a/src/bench/cluster_linearize.cpp
+++ b/src/bench/cluster_linearize.cpp
@@ -44,27 +44,6 @@ void BenchPostLinearizeWorstCase(DepGraphIndex ntx, benchmark::Bench& bench)
});
}
-template<typename SetType>
-void BenchMergeLinearizationsWorstCase(DepGraphIndex ntx, benchmark::Bench& bench)
-{
- DepGraph<SetType> depgraph;
- for (DepGraphIndex i = 0; i < ntx; ++i) {
- depgraph.AddTransaction({i, 1});
- if (i) depgraph.AddDependencies(SetType::Singleton(0), i);
- }
- std::vector<DepGraphIndex> lin1;
- std::vector<DepGraphIndex> lin2;
- lin1.push_back(0);
- lin2.push_back(0);
- for (DepGraphIndex i = 1; i < ntx; ++i) {
- lin1.push_back(i);
- lin2.push_back(ntx - i);
- }
- bench.run([&] {
- MergeLinearizations(depgraph, lin1, lin2);
- });
-}
-
void BenchLinearizeOptimallyTotal(benchmark::Bench& bench, const std::string& name, const std::vector<std::vector<uint8_t>>& serializeds)
{
for (const auto& serialized : serializeds) {
@@ -119,13 +98,6 @@ static void PostLinearize64TxWorstCase(benchmark::Bench& bench) { BenchPostLinea
static void PostLinearize75TxWorstCase(benchmark::Bench& bench) { BenchPostLinearizeWorstCase<BitSet<75>>(75, bench); }
static void PostLinearize99TxWorstCase(benchmark::Bench& bench) { BenchPostLinearizeWorstCase<BitSet<99>>(99, bench); }
-static void MergeLinearizations16TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<16>>(16, bench); }
-static void MergeLinearizations32TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<32>>(32, bench); }
-static void MergeLinearizations48TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<48>>(48, bench); }
-static void MergeLinearizations64TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<64>>(64, bench); }
-static void MergeLinearizations75TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<75>>(75, bench); }
-static void MergeLinearizations99TxWorstCase(benchmark::Bench& bench) { BenchMergeLinearizationsWorstCase<BitSet<99>>(99, bench); }
-
// Constructed from replayed historical mempool activity, selecting for clusters that are slow
// to linearize from scratch, with increasing number of transactions (9 to 63).
static const std::vector<std::vector<uint8_t>> CLUSTERS_HISTORICAL = {
@@ -185,12 +157,5 @@ BENCHMARK(PostLinearize64TxWorstCase, benchmark::PriorityLevel::HIGH);
BENCHMARK(PostLinearize75TxWorstCase, benchmark::PriorityLevel::HIGH);
BENCHMARK(PostLinearize99TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations16TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations32TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations48TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations64TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations75TxWorstCase, benchmark::PriorityLevel::HIGH);
-BENCHMARK(MergeLinearizations99TxWorstCase, benchmark::PriorityLevel::HIGH);
-
BENCHMARK(LinearizeOptimallyTotal, benchmark::PriorityLevel::HIGH);
BENCHMARK(LinearizeOptimallyPerCost, benchmark::PriorityLevel::HIGH);
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 8b4d0d22..120bc527 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -1681,48 +1681,6 @@ void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> l
}
}
-/** Merge two linearizations for the same cluster into one that is as good as both.
- *
- * Complexity: O(N^2) where N=depgraph.TxCount(); O(N) if both inputs are identical.
- */
-template<typename SetType>
-std::vector<DepGraphIndex> MergeLinearizations(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> lin1, std::span<const DepGraphIndex> lin2)
-{
- Assume(lin1.size() == depgraph.TxCount());
- Assume(lin2.size() == depgraph.TxCount());
-
- /** Chunkings of what remains of both input linearizations. */
- LinearizationChunking chunking1(depgraph, lin1), chunking2(depgraph, lin2);
- /** Output linearization. */
- std::vector<DepGraphIndex> ret;
- if (depgraph.TxCount() == 0) return ret;
- ret.reserve(depgraph.TxCount());
-
- while (true) {
- // As long as we are not done, both linearizations must have chunks left.
- Assume(chunking1.NumChunksLeft() > 0);
- Assume(chunking2.NumChunksLeft() > 0);
- // Find the set to output by taking the best remaining chunk, and then intersecting it with
- // prefixes of remaining chunks of the other linearization.
- SetInfo<SetType> best;
- const auto& lin1_firstchunk = chunking1.GetChunk(0);
- const auto& lin2_firstchunk = chunking2.GetChunk(0);
- if (lin2_firstchunk.feerate >> lin1_firstchunk.feerate) {
- best = chunking1.IntersectPrefixes(lin2_firstchunk);
- } else {
- best = chunking2.IntersectPrefixes(lin1_firstchunk);
- }
- // Append the result to the output and mark it as done.
- depgraph.AppendTopo(ret, best.transactions);
- chunking1.MarkDone(best.transactions);
- if (chunking1.NumChunksLeft() == 0) break;
- chunking2.MarkDone(best.transactions);
- }
-
- Assume(ret.size() == depgraph.TxCount());
- return ret;
-}
-
/** Make linearization topological, retaining its ordering where possible. */
template<typename SetType>
void FixLinearization(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization) noexcept
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index a32fc169..32848179 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -59,8 +59,6 @@
* - clusterlin_postlinearize
* - clusterlin_postlinearize_tree
* - clusterlin_postlinearize_moved_leaf
- * - MergeLinearization tests:
- * - clusterlin_merge
* - FixLinearization tests:
* - clusterlin_fix_linearization
* - MakeConnected tests (a test-only function):
@@ -1308,32 +1306,6 @@ FUZZ_TARGET(clusterlin_postlinearize_moved_leaf)
assert(cmp >= 0);
}
-FUZZ_TARGET(clusterlin_merge)
-{
- // Construct an arbitrary graph from the fuzz input.
- SpanReader reader(buffer);
- DepGraph<TestBitSet> depgraph;
- try {
- reader >> Using<DepGraphFormatter>(depgraph);
- } catch (const std::ios_base::failure&) {}
-
- // Retrieve two linearizations from the fuzz input.
- auto lin1 = ReadLinearization(depgraph, reader);
- auto lin2 = ReadLinearization(depgraph, reader);
-
- // Merge the two.
- auto lin_merged = MergeLinearizations(depgraph, lin1, lin2);
-
- // Compute chunkings and compare.
- auto chunking1 = ChunkLinearization(depgraph, lin1);
- auto chunking2 = ChunkLinearization(depgraph, lin2);
- auto chunking_merged = ChunkLinearization(depgraph, lin_merged);
- auto cmp1 = CompareChunks(chunking_merged, chunking1);
- assert(cmp1 >= 0);
- auto cmp2 = CompareChunks(chunking_merged, chunking2);
- assert(cmp2 >= 0);
-}
-
FUZZ_TARGET(clusterlin_fix_linearization)
{
// Verify expected properties of FixLinearization() on arbitrary linearizations.
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.