clusterlin: rescale costs (preparation)
What the developer wrote
Authored by Pieter Wuille
clusterlin: rescale costs (preparation)
What changed, and why it matters
This commit is a non-security internal tuning change for Bitcoin Core's transaction mempool linearization logic. It multiplies several cost constants by 38 to prepare for future algorithm changes, and updates corresponding test/fuzz thresholds. There is no bug fix, no vulnerability, and no user-facing behavior change beyond slightly different internal cost budgets.
No security action required. Treat as routine refactoring/test-update in advance of a future cluster linearization improvement.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The patch rescales internal cost coefficients in the cluster linearization module: DepGraph::ActivateEnd/DeactivateEnd costs change from num_deps+1 to 38*num_deps+38; fuzz test masks and max_cost values are widened; a static lookup table of maximum optimal linearization costs is multiplied by ~38; and the mempool ACCEPTABLE_COST constant is raised from 1,700 to 75,000. The commit message explicitly labels this as ‘preparation’ for a subsequent change. No security defect is corrected or introduced in the diff.
Changed components
src/cluster_linearize.hsrc/test/fuzz/cluster_linearize.cppsrc/test/util/cluster_linearize.hsrc/txmempool.hInspect captured patch +13 / −13
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 57df4512..ea0d6bd8 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -486,9 +486,9 @@ public:
inline void StartOptimizingBegin() noexcept {}
inline void StartOptimizingEnd(int num_chunks) noexcept {}
inline void ActivateBegin() noexcept {}
- inline void ActivateEnd(int num_deps) noexcept { m_cost += num_deps + 1; }
+ inline void ActivateEnd(int num_deps) noexcept { m_cost += 38 * num_deps + 38; }
inline void DeactivateBegin() noexcept {}
- inline void DeactivateEnd(int num_deps) noexcept { m_cost += num_deps + 1; }
+ inline void DeactivateEnd(int num_deps) noexcept { m_cost += 38 * num_deps + 38; }
inline void MergeChunksBegin() noexcept {}
inline void MergeChunksMid(int num_txns) noexcept {}
inline void MergeChunksEnd(int num_steps) noexcept {}
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index adee8f2e..9b07bf00 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -1043,7 +1043,7 @@ FUZZ_TARGET(clusterlin_linearize)
}
// Invoke Linearize().
- max_cost &= 0x7ffff;
+ max_cost &= 0x3fffff;
auto [linearization, optimal, cost] = Linearize(
/*depgraph=*/depgraph,
/*max_cost=*/max_cost,
@@ -1242,7 +1242,7 @@ FUZZ_TARGET(clusterlin_postlinearize_tree)
// Try to find an even better linearization directly. This must not change the diagram for the
// same reason.
- auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 100000, rng_seed, IndexTxOrder{}, post_linearization);
+ auto [opt_linearization, _optimal, _cost] = Linearize(depgraph_tree, 1000000, rng_seed, IndexTxOrder{}, post_linearization);
auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
assert(cmp_opt == 0);
diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h
index f50a51bd..f8ffb5ea 100644
--- a/src/test/util/cluster_linearize.h
+++ b/src/test/util/cluster_linearize.h
@@ -402,14 +402,14 @@ inline uint64_t MaxOptimalLinearizationCost(DepGraphIndex cluster_count)
// *some* reasonable cost bound, optimal linearizations are always found.
static constexpr uint64_t COSTS[65] = {
0,
- 0, 4, 10, 34, 76, 156, 229, 380,
- 441, 517, 678, 933, 1037, 1366, 1464, 1711,
- 2111, 2542, 3068, 3116, 4029, 3467, 5324, 5402,
- 6481, 7161, 7441, 8183, 8843, 9353, 11104, 11455,
- 11791, 12570, 13480, 14259, 14525, 12426, 14477, 20201,
- 18737, 16581, 23622, 28486, 30652, 33021, 32942, 32745,
- 34046, 26227, 34662, 38019, 40814, 31113, 41448, 33968,
- 35024, 59207, 42872, 41277, 42365, 51833, 63410, 67035
+ 0, 176, 440, 1496, 3344, 6864, 10076, 16720,
+ 19404, 22748, 29832, 41052, 45628, 60104, 64416, 75284,
+ 92884, 111848, 134992, 137104, 177276, 152548, 234256, 237688,
+ 285164, 315084, 327404, 360052, 389092, 411532, 488576, 504020,
+ 518804, 553080, 593120, 627396, 639100, 546744, 636988, 888844,
+ 824428, 729564, 1039368, 1253384, 1348688, 1452924, 1449448, 1440780,
+ 1498024, 1153988, 1525128, 1672836, 1795816, 1368972, 1823712, 1494592,
+ 1541056, 2605108, 1886368, 1816188, 1864060, 2280652, 2790040, 2949540
};
assert(cluster_count < std::size(COSTS));
// Multiply the table number by two, to account for the fact that they are not absolutes.
diff --git a/src/txmempool.h b/src/txmempool.h
index 5a870f4c..d7b7de6e 100644
--- a/src/txmempool.h
+++ b/src/txmempool.h
@@ -51,7 +51,7 @@ static const uint32_t MEMPOOL_HEIGHT = 0x7FFFFFFF;
/** How much linearization cost required for TxGraph clusters to have
* "acceptable" quality, if they cannot be optimally linearized with less cost. */
-static constexpr uint64_t ACCEPTABLE_COST = 1'700;
+static constexpr uint64_t ACCEPTABLE_COST = 75'000;
/** How much work we ask TxGraph to do after a mempool change occurs (either
* due to a changeset being applied, a new block being found, or a reorg). */
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.