cluster mempool: control/optimize TxGraph memory usage

sipa commented at 2:21 pm on August 8, 2025: member

Part of #30289.

This adds a few optimizations to reduce TxGraph’s memory usage, and makes sure that dynamic memory it uses doesn’t linger after shrinking clusters. Finally, it exposes a function GetMainMemoryUsage() to compute TxGraph’s approximate memory usage.

It makes the Cluster type abstract, with two instances (SingletonClusterImpl for 1-transaction clusters, and GenericClusterImpl for others).

On my 64-bit system, I obtain the following numbers:

SingletonClusterImpl: 48 bytes, plus 16 bytes malloc overhead in its unique_ptr, plus 8-byte pointer in m_clusters
GenericClusterImpl: 104 bytes, plus 16 bytes malloc overhead in its unique_ptr, plus 8-byte pointer in m_clusters, plus 72 bytes malloc overhead inside its vectors and DepGraph, plus 40 bytes per transaction in those.
TxGraphImpl::Entry: 72 bytes per transaction
TxGraphImpl::ChunkData: 8 bytes, plus 56 bytes in std::set overhead + malloc overhead, all per chunk.
TxGraph::Ref: 16 bytes per transaction

This overall amounts to 200 bytes per cluster, plus 64 bytes per chunk, plus 128 bytes per transaction, but only 224 bytes overall per singleton cluster.

DrahtBot commented at 2:21 pm on August 8, 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/33157.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	l0rinc, instagibbs, ismaelsadeeq, glozow

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#33591 (Cluster mempool followups by sdaftuar)
#33469 (TxGraph: change m_excluded_clusters by instagibbs)
#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.

LLM Linter (✨ experimental)

Possible typos and grammar issues:

/ -> (remove) [Trailing “/” after a // comment produces a mismatched comment terminator and is confusing / invalid in the comment “Cannot move or copy (would invalidate Cluster* in Locator and ClusterSet). */”.]

drahtbot_id_5_m

sipa force-pushed on Aug 8, 2025

DrahtBot added the label CI failed on Aug 8, 2025

DrahtBot commented at 2:31 pm on August 8, 2025: contributor

🚧 At least one of the CI tasks failed. Task macOS-cross, gui, no tests: https://github.com/bitcoin/bitcoin/runs/47684523262 LLM reason (✨ experimental): The CI failure is caused by a compilation error due to ambiguous call to ‘DynamicUsage’ in txgraph.cpp.

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

DrahtBot removed the label CI failed on Aug 8, 2025

ismaelsadeeq commented at 8:14 pm on September 2, 2025: member

Concept ACK to have control over memory usage, also not suprised by the numbers because of the added complexity of cluster mempool v master.

in src/txgraph.cpp:3415 in 754775357b outdated

2981+    SplitAll(0);
2982+    ApplyDependencies(0);
2983+    // Compute memory usage
2984+    auto& clusterset = GetClusterSet(0);
2985+    size_t usage = /* From clusters */
2986+                   clusterset.m_cluster_usage +

glozow commented at 7:56 pm on September 3, 2025:

Note to self/reviewers: since we’ve done ApplyDependencies, ClusterSet.m_group_data, m_deps_to_add, and m_to_remove are all empty so we don’t need to add their dynamic memory usage. We also aren’t counting m_removed since that’d be at staging level or an m_unlinked entry.

sipa commented at 5:54 pm on October 9, 2025:

Indeed!

sipa commented at 5:43 pm on September 4, 2025: member

I had missed a few sources of memory usage in the numbers posted in the PR description before. I’ve redone the derivation, and explained it in more detail. Thanks @glozow for trying to make sense of my incorrect numbers.

in src/txgraph.cpp:488 in 15277c05a1 outdated

484@@ -484,12 +485,13 @@ class TxGraphImpl final : public TxGraph
485     /** Swap the Entry referred to by a and the one referred to by b. */
486     void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
487     /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
488-    *   removed), return the Cluster it is in. Otherwise, return nullptr. */
489-    Cluster* FindCluster(GraphIndex idx, int level) const noexcept;
490+    *   removed), return the Cluster it is in and the level it has. Otherwise, return

instagibbs commented at 7:09 pm on September 4, 2025:

0    *   removed), return the Cluster it is in and the level the Cluster has. Otherwise, return

sipa commented at 8:35 pm on September 5, 2025:

Done.

in src/txgraph.cpp:1006 in c638faec3a outdated

1000@@ -1001,8 +1001,9 @@ bool Cluster::Split(TxGraphImpl& graph, int level) noexcept
1001     while (todo.Any()) {
1002         auto component = m_depgraph.FindConnectedComponent(todo);
1003         auto split_quality = component.Count() <= 2 ? QualityLevel::OPTIMAL : new_quality;
1004-        if (first && component == todo) {
1005-            // The existing Cluster is an entire component. Leave it be, but update its quality.
1006+        if (first && component == todo && SetType::Fill(component.Count()) == component) {
1007+            // The existing Cluster is an entire component, without holes. Leave it be, but update
1008+            // its quality.

instagibbs commented at 7:50 pm on September 4, 2025:

probably should be explicit in comments that this is a memory optimization, letting hole-having clusters be reconstructed without holes

sipa commented at 8:35 pm on September 5, 2025:

Added a comment to explain that.

in src/test/fuzz/cluster_linearize.cpp:510 in 614eefb7df outdated

506@@ -507,6 +507,11 @@ FUZZ_TARGET(clusterlin_depgraph_sim)
507             }
508             continue;
509         }
510+        if (command <= 3) {

instagibbs commented at 7:56 pm on September 4, 2025:

this in unconditionally called I think

sipa commented at 8:35 pm on September 5, 2025:

I’ve rewritten this using the “loop of comand– approach”.

in src/test/fuzz/cluster_linearize.cpp:457 in 614eefb7df outdated

452@@ -453,8 +453,8 @@ FUZZ_TARGET(clusterlin_depgraph_sim)
453     };
454 
455     LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
456-        uint8_t command = provider.ConsumeIntegral<uint8_t>();
457-        if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
458+        uint8_t command = provider.ConsumeIntegral<uint8_t>() % 4;
459+        if ((command <= 2 && num_tx_sim == 0) || (command <= 0 && num_tx_sim < TestBitSet::Size())) {

instagibbs commented at 8:03 pm on September 4, 2025:

not sure I track why the command values are being mapped to specific series of actions. Writing it out in case it ends up helpful:

0: a. AddTransaction if txns below set limit b. AddDependency if any txns exist c. RemoveTransactions if any txns exist d. Compact 1: a. AddTransaction if no transaction exists b. AddDependency (transaction will exist) c. RemoveTransactions (transaction will exist) d. Compact

2: a. AddTransaction if no transaction exists b. RemoveTransactions (transaction will exist) c. Compact

3. a. Compact

sipa commented at 8:35 pm on September 5, 2025:

I have rewritten this.

instagibbs commented at 8:20 pm on September 4, 2025: member

concept ACK, I refuse to do math

sipa force-pushed on Sep 5, 2025

sipa commented at 8:39 pm on September 5, 2025: member

I have implemented the “abstract Cluster” approach anyway, as special-casing singletons outside of the Cluster logic was too cumbersome.

Old numbers:

384 bytes per singleton cluster
512 or 576 bytes per pair cluster

New numbers:

224 bytes per singleton cluster
520 or 584 bytes per pair cluster

sipa force-pushed on Sep 5, 2025

sipa commented at 1:02 pm on September 6, 2025: member

And with the addition of SingletonClusterImpl, overall mempool usage (determined by loading a mempool.dat from a long-running node into both (1) master and (2) #28676 + this PR), the mempool memusage/vsize ratio seems to have dropped ~4.5%, meaning cluster mempool will effectively increase mempool size by that much for a constant -maxmempool setting.

Master (6.09 membyte/vbyte):

0  "size": 58610,
1  "bytes": 28502050,
2  "usage": 173585008,
3  "total_fee": 0.05257629,
4  "maxmempool": 300000000,

Cluster mempool + this PR (5.83 membyte/vbyte):

0  "size": 58348,
1  "bytes": 28461800,
2  "usage": 165896648,
3  "total_fee": 0.05210373,
4  "maxmempool": 300000000,

sipa force-pushed on Sep 7, 2025

sipa force-pushed on Sep 8, 2025

sipa force-pushed on Sep 9, 2025

DrahtBot added the label Needs rebase on Sep 11, 2025

sipa force-pushed on Sep 11, 2025

sipa commented at 5:07 pm on September 11, 2025: member

Rebased after #33354 merge.

DrahtBot removed the label Needs rebase on Sep 11, 2025

in src/txgraph.cpp:107 in 22f5fe833f outdated

112@@ -113,8 +113,6 @@ class Cluster
113     QualityLevel m_quality{QualityLevel::NONE};

ismaelsadeeq commented at 12:31 pm on September 16, 2025:

In “txgraph: Make level of Cluster implicit (optimization)” 22f5fe833fcf3da6a4180d181ff68d6da34f40db

Should also add coverage for GetLevel

 0diff --git a/src/txgraph.cpp b/src/txgraph.cpp
 1index ef7b6568107..0e7e5d22947 100644
 2--- a/src/txgraph.cpp
 3+++ b/src/txgraph.cpp
 4@@ -2421,6 +2421,8 @@ void TxGraphImpl::SanityCheck() const
 5                 if (cluster.GetTxCount() != 0) {
 6                     actual_clusters.insert(&cluster);
 7                 }
 8+
 9+                assert(cluster.GetLevel(*this) == level);
10                 // Sanity check the cluster, according to the Cluster's internal rules.
11                 cluster.SanityCheck(*this, level);
12                 // Check that the cluster's quality and setindex matches its position in the quality list

sipa commented at 2:57 pm on September 17, 2025:

Done. I’ve also refactored these asserts a bit, moving some of them from *ClusterImpl::SanityCheck to TxGraphImpl::SanityCheck, so duplication across the two implementations can be avoided.

in src/txgraph.cpp:146 in 7974ed311c outdated

141+               // Dynamic memory usage inside m_depgraph.
142+               m_depgraph.DynamicMemoryUsage() +
143+               // Memory usage of the allocated Cluster itself.
144+               memusage::MallocUsage(sizeof(Cluster)) +
145+               // Memory usage of the ClusterSet::m_clusters entry.
146+               sizeof(std::unique_ptr<Cluster>);

ismaelsadeeq commented at 1:22 pm on September 16, 2025:

In “txgraph: keep track of Cluster memory usage (preparation)” 7974ed311c1843d548d98e9eae8fed71a42a1026

Should also count the sequence number of the cluster?

0               // Memory usage of the cluster m_sequence.
1               + sizeof(uint64_t);

sipa commented at 11:42 am on September 17, 2025:

No, that’s included in sizeof(Cluster) above.

in src/txgraph.cpp:168 in 22f5fe833f outdated

164+    int GetLevel(const TxGraphImpl& graph) const noexcept;
165     /** Only called by Graph::SwapIndexes. */
166     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept { m_mapping[cluster_idx] = graph_idx; }
167     /** Push changes to Cluster and its linearization to the TxGraphImpl Entry objects. */
168-    void Updated(TxGraphImpl& graph) noexcept;
169+    void Updated(TxGraphImpl& graph, int level) noexcept;

ismaelsadeeq commented at 1:58 pm on September 16, 2025:

In “txgraph: Make level of Cluster implicit (optimization)” https://github.com/bitcoin/bitcoin/commit/22f5fe833fcf3da6a4180d181ff68d6da34f40db

Instead of using an int for level here, should we relax the Level enum from a scoped enum to an unscoped one to allow implicit conversion and unified input? This would also apply in cases where we want to pass a specific enum value, e.g. in e.g CopyToStaging

sipa commented at 11:45 am on September 17, 2025:

I’d rather keep the external selector (Level level) and internal identifier (int level) separate, as it may allow adding more external ones later if need be (e.g. a Level::SINGLE which requires there to be only the main level and asserts otherwise, or a Level::STAGING which requires a staging level to exist). Also, if we’d add a third level (which may be needed to implement testmempoolaccept with package RBF) there may be even more level selectors to add.

ismaelsadeeq commented at 6:51 pm on September 17, 2025:

Thanks for the context. For anyone that wants to dig in, the testmempoolaccept third level was discussed here https://github.com/bitcoin/bitcoin/issues/32160

l0rinc commented at 7:27 pm on October 6, 2025:

I also find the int levels to be quite error-prone, if enums are off the table, could we at least use some MISSING and STAGING and MAIN constants throughout?

sipa force-pushed on Sep 17, 2025

in src/txgraph.cpp:1246 in fdcb5f17bd outdated

1245     // Copy the Cluster from main to staging, if it's not already there.
1246     if (level == 0) {
1247         // Make the Cluster Acceptable before copying. This isn't strictly necessary, but doing it
1248         // now avoids doing double work later.
1249-        MakeAcceptable(*cluster);
1250+        MakeAcceptable(*cluster, 0);

instagibbs commented at 1:38 pm on September 18, 2025:

fdcb5f17bd100eb2c1765c13bbb8367d03fc7ea5

micro-nit for readability

0        MakeAcceptable(*cluster, level);

sipa commented at 1:26 pm on September 23, 2025:

Done.

ismaelsadeeq commented at 1:54 pm on September 18, 2025: member

Code Review ACK 66401148ddcba04c27751e39e53fc41e6deb5d14

I shutdown a long-running node at height 915249.

0.rw------- 128M ismaelsadeeq 18 Sep 14:46 mempool.dat

Restarted the node on master 1444ed855f4 with:

0build/bin/bitcoind -connect=0 -debug

After loading the mempool, getmempoolinfo returned:

0{
1  "loaded": true,
2  "size": 104944,
3  "bytes": 43254588,
4  "usage": 260130384,
5  "total_fee": 0.10523099,
6  "maxmempool": 300000000
7}

I restarted the node on full cluster mempool implementation 57f929d with the same config. getmempoolinfo returned:

0{
1  "loaded": true,
2  "size": 104944,
3  "bytes": 43254588,
4  "usage": 244614928,
5  "total_fee": 0.10523099,
6  "maxmempool": 300000000
7}

The mempool size and fee data are identical across runs, but usage differ with cluster mempool having slightly less usage at 6%.

DrahtBot requested review from instagibbs on Sep 18, 2025

in src/txgraph.cpp:2290 in fdcb5f17bd outdated

2287@@ -2275,7 +2288,7 @@ void Cluster::SanityCheck(const TxGraphImpl& graph, int level) const
2288     // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
2289     assert(m_linearization.size() <= graph.m_max_cluster_count);
2290     // The level must match the level the Cluster occurs in.

instagibbs commented at 2:01 pm on September 18, 2025:

0    // The level must match the level the Cluster occurs in (call only valid with non-empty cluster).

sipa commented at 1:26 pm on September 23, 2025:

Done something like this.

in src/txgraph.cpp:3437 in a940e46bb0 outdated

2977@@ -2976,6 +2978,22 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
2978     return ret;
2979 }
2980 
2981+size_t TxGraphImpl::GetMainMemoryUsage() noexcept

instagibbs commented at 2:32 pm on September 18, 2025:

a940e46bb06cf40f65772516d67f78cbd87c6b52

noting we aren’t tracking BlockBuilderImpl memory usage which only has growth in m_excluded_clusters

(N.B. I don’t think we need ordered set for m_excluded_clusters)

sipa commented at 1:28 pm on September 23, 2025:

Added a comment that BlockBuilders are excluded from the memory usage.

Agreed w.r.t ordered_set, but will leave for a follow-up.

in src/txgraph.cpp:889 in 89b7997e74 outdated

790@@ -779,6 +791,30 @@ uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
791     return ret;
792 }
793 
794+DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept

instagibbs commented at 4:28 pm on September 18, 2025:

89b7997e7414074da3b0a35a17d86a2dfe24f378

For these functions(and the later singleton ones) can we Assume(graph_idx >= 0)

sipa commented at 1:15 pm on September 23, 2025:

GraphIndex is unsigned, so that would literally always be true?

instagibbs commented at 1:20 pm on September 23, 2025:

huh, huge reading comprehension issues. I distinctly recall checking, sad!

sipa commented at 1:28 pm on September 23, 2025:

Added an Assume(graph_idx != GraphIndex(-1)); here for extra safety.

in src/txgraph.cpp:1996 in 66401148dd

1992@@ -1745,18 +1993,33 @@ void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int in_level) noexcept
1993     // moves.
1994     size_t max_size_pos{0};
1995     DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1996+    DepGraphIndex tot_size = max_size;

instagibbs commented at 4:40 pm on September 18, 2025:

66401148ddcba04c27751e39e53fc41e6deb5d14

micro-nit: couldn’t figure out what tot meant for a second… “to t…. size?”

0    DepGraphIndex total_size = max_size;

sipa commented at 1:29 pm on September 23, 2025:

Done.

instagibbs approved

instagibbs commented at 5:00 pm on September 18, 2025: member

ACK 66401148ddcba04c27751e39e53fc41e6deb5d14

Did not validate the numbers, non-blocking comments only

sipa force-pushed on Sep 23, 2025

instagibbs commented at 1:55 pm on September 23, 2025: member

reACK 99e144778eeffc1074d5a1c193896bea335db8af

via git range-diff master 66401148ddcba04c27751e39e53fc41e6deb5d14 99e144778eeffc1074d5a1c193896bea335db8af

DrahtBot requested review from ismaelsadeeq on Sep 23, 2025

sipa force-pushed on Sep 23, 2025

instagibbs commented at 2:58 pm on September 23, 2025: member

reACK 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354

just a rebase

ismaelsadeeq commented at 9:58 am on September 25, 2025: member

reACK 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354

Changes since last ACK are nits fixes.

in src/txgraph.cpp:239 in 5ac32aa441 outdated

258+    virtual void SanityCheck(const TxGraphImpl& graph, int level) const = 0;
259 };
260 
261+/** An implementation of Cluster that uses a DepGraph and vectors, to support arbitrary numbers of
262+ *  transactions up to MAX_CLUSTER_COUNT_LIMIT. */
263+class GenericClusterImpl final : public Cluster

l0rinc commented at 5:35 pm on October 3, 2025:

I wonder if the new vtable pointer that was introduced by polymorphism is worth it or we could make a fake-inheritance by templates or macros or code generation instead or std::variant<SingletonCluste, GenericCluster> parameter types? For the std::variant we would likely need some tricks to save memory (grouping vectors or more pointers to reduce size of generic, not sure yet) and it would likely be a big refactor and not sure it would be smaller or more readable, just thinking out loud. I will experiment with regrouping things to see if we can get some additional savings. (edited)

sipa commented at 8:58 pm on October 8, 2025:

A variant has the same overhead as a vtable pointer (by adding a variant tag), but has the additional downside that the allocated memory will always have space for the larger of the member types. So in this case, that would boil down to always allocating as much memory as vtable-bearing GenericClusterImpl, even for singletons.

l0rinc commented at 10:07 pm on October 8, 2025:

yes, with current versions it would use the max size, it’s why I wrote “we would likely need some tricks to save memory”. I don’t have a concrete better idea yet but will try to come up with something better.

sipa commented at 6:50 pm on October 9, 2025:

There are certainly possibilities, like storing the clusters in two vectors (one for each implementation), and using positions within that vector + some marker to identify the implementation as “identifier” for the cluster. The difficulty is that you now need to deal with holes in those vectors, or swapping to compact them, meaning you need to go find and update all places where those cluster identifiers are used.

Absent something like that, I think the current approach is close to ideal. It incurs a per-Cluster allocation cost, but in return gets a stable Cluster* to use as identifier. And given that cost already, the polymorphism is nearly free (a single vtable pointer per object).

in src/txgraph.cpp:951 in 5ac32aa441 outdated

925+        if (entry.m_locator[level].cluster == this) return level;
926+    }
927+    // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
928+    // point back to it.
929+    assert(false);
930+    return -1;

l0rinc commented at 5:48 pm on October 3, 2025:

Given that we’d already be failing in the parent call’s Assume(level <= to_level) (and that std::unreachable() is not yet available in C++20) could we maybe use our own NONFATAL_UNREACHABLE here?

sipa commented at 9:01 pm on October 8, 2025:

I think this should be fatal (as it will crash anyway later when the caller tries to access level -1).

l0rinc commented at 4:04 am on October 11, 2025:

And we’re not throwing because of noexcept? What about a single std::abort() instead of the two?

in src/txgraph.cpp:1986 in 5ac32aa441

1982@@ -1586,7 +1983,7 @@ void TxGraphImpl::GroupClusters(int level) noexcept
1983     Compact();
1984 }
1985 
1986-void TxGraphImpl::Merge(std::span<Cluster*> to_merge) noexcept
1987+void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int in_level) noexcept

l0rinc commented at 6:29 pm on October 3, 2025:

nit: what’s the difference between an int level and the int in_level here? It doesn’t seem to be shadowing anything.

sipa commented at 6:50 pm on October 9, 2025:

Fixed.

in src/txgraph.cpp:946 in 5ac32aa441 outdated

920+
921+    // Pick an arbitrary Entry that occurs in this Cluster.
922+    const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];
923+    // See if there is a level whose Locator matches this Cluster, if so return that level.
924+    for (int level = 0; level < MAX_LEVELS; ++level) {
925+        if (entry.m_locator[level].cluster == this) return level;

l0rinc commented at 6:50 pm on October 3, 2025:

nit: I noticed m_locator is a raw C-style array, was std::array<Locator, MAX_LEVELS> considered as a slightly safer alternative that may avoid pointer decay - given its tiny size we want to make sure we’re not misindexing and it might make the iterations slightly more descriptive:

0for (int level{0}; level < entry.m_locator.size(); ++level) {

sipa commented at 9:24 pm on October 8, 2025:

The code here is new, but the lay-out of m_locator predates this PR. Going to leave it for a follow-up if anyone cares.

in src/txgraph.cpp:1288 in 5ac32aa441 outdated

1265+
1266+void GenericClusterImpl::Compact() noexcept
1267+{
1268+    m_linearization.shrink_to_fit();
1269+    m_mapping.shrink_to_fit();
1270+    m_depgraph.Compact();

glozow commented at 7:11 pm on October 3, 2025:

Note to self/reviewers: Depgraph::Compact() also calls shrink_to_fit(), meaning positions do not change and the mapping is not invalidated.

sipa commented at 9:07 pm on October 9, 2025:

Right.

in src/txgraph.cpp:630 in 5ac32aa441

628+    std::pair<Cluster*, int> FindCluster(GraphIndex idx, int level) const noexcept;
629     /** Extract a Cluster from its ClusterSet. */
630     std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
631     /** Delete a Cluster. */
632-    void DeleteCluster(Cluster& cluster) noexcept;
633+    void DeleteCluster(int level, Cluster& cluster) noexcept;

l0rinc commented at 8:29 pm on October 3, 2025:

nit: in other cases the parameters are in a different order, e.g. void Split(Cluster& cluster, int level) noexcept;

sipa commented at 9:24 pm on October 8, 2025:

I’m not going to change that now.

l0rinc commented at 5:27 pm on October 11, 2025:

Thanks for doing it anyway :)

in src/txgraph.cpp:1900 in 5ac32aa441

1895@@ -1499,8 +1896,8 @@ void TxGraphImpl::GroupClusters(int level) noexcept
1896         PartitionData* last_partition{nullptr};
1897         for (const auto& [dep, _] : an_deps) {
1898             auto [par, chl] = dep;
1899-            auto par_cluster = FindCluster(par, level);
1900-            auto chl_cluster = FindCluster(chl, level);
1901+            auto [par_cluster, _par_level] = FindCluster(par, level);
1902+            auto [chl_cluster, _chl_level] = FindCluster(chl, level);

l0rinc commented at 8:35 pm on October 3, 2025:

nit: we could minimize the diff slightly with:

0            auto par_cluster = FindCluster(par, level).first;
1            auto chl_cluster = FindCluster(chl, level).first;

sipa commented at 6:51 pm on October 9, 2025:

Addressed by creating separate FindCluster and FindClusterAndLevel functions. In most call sites, FindCluster can remain unchanged.

in src/txgraph.cpp:2224 in cd6dadf53a outdated

2219@@ -2207,8 +2220,8 @@ std::strong_ordering TxGraphImpl::CompareMainOrder(const Ref& a, const Ref& b) n
2220     const auto& locator_b = entry_b.m_locator[0];
2221     Assume(locator_a.IsPresent());
2222     Assume(locator_b.IsPresent());
2223-    MakeAcceptable(*locator_a.cluster);
2224-    MakeAcceptable(*locator_b.cluster);
2225+    MakeAcceptable(*locator_a.cluster, 0);
2226+    MakeAcceptable(*locator_b.cluster, 0);

l0rinc commented at 9:01 pm on October 3, 2025:

I find these new unnamed and unbounded primitive arguments quite confusing now

sipa commented at 6:52 pm on October 9, 2025:

I have added a few /*level=*/0 etc. as arguments. Does that help?

in src/txgraph.cpp:1138 in fcf5e788d9 outdated

1133@@ -1123,8 +1134,9 @@ bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
1134     // Iterate over the connected components of this Cluster's m_depgraph.
1135     while (todo.Any()) {
1136         auto component = m_depgraph.FindConnectedComponent(todo);
1137+        auto component_size = component.Count();
1138         auto split_quality = component.Count() <= 2 ? QualityLevel::OPTIMAL : new_quality;

l0rinc commented at 9:14 pm on October 3, 2025:

fcf5e788d912cc465ad84ec75dabaf9941044314: Now that we have component_size deduplicated in follow-ups, consider using it for the split quality as well:

0        auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality;

question: doesn’t this change the definition of QualityLevel::NEEDS_SPLIT, since not all components are necessarily NEEDS_RELINEARIZE (but I might have misunderstood what this means)

sipa commented at 9:32 pm on October 8, 2025:

I don’t understand the question. What change would affect the definition?

l0rinc commented at 11:34 pm on October 8, 2025:

The question was referring to the documentation of NEEDS_SPLIT

0/** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */

and was asking if this still holds in every case (even for small clusters)

sipa commented at 3:46 am on October 9, 2025:

Maybe it could say “which will all be made NEEDS_RELINEARIZE”. It’s always possible (even for non-tiny clusters) that nothing really needs to be done with it anymore.

in src/test/fuzz/cluster_linearize.cpp:514 in 7084d5faf1 outdated

554                     }
555                 }
556+                break;
557+            } else if (command-- == 0) {
558+                // Compact.
559+                real.Compact();

l0rinc commented at 9:53 pm on October 3, 2025:

Based on https://en.cppreference.com/w/cpp/container/vector/shrink_to_fit this is just a hint, not guranteed to change anything

It depends on the implementation whether the request is fulfilled.

But maybe we could still test that the that after deletion the DynamicMemoryUsage is the same, but after calling compaction the memory shrinks?

Something like:

0auto last_compaction_pos{real.PositionRange()};

…

0const size_t mem_before{real.DynamicMemoryUsage()};
1real.Compact();
2const size_t mem_after{real.DynamicMemoryUsage()};
3
4assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
5last_compaction_pos = real.PositionRange();
6break;

Which fails for me if we remove entries.shrink_to_fit() in Compact, and passes with the current implementation.

sipa commented at 6:53 pm on October 9, 2025:

I have incorporated this, and added you as co-author.

in src/txgraph.cpp:1004 in d9dbbf41b6 outdated

1000@@ -1001,8 +1001,10 @@ bool Cluster::Split(TxGraphImpl& graph, int level) noexcept
1001     while (todo.Any()) {
1002         auto component = m_depgraph.FindConnectedComponent(todo);
1003         auto split_quality = component.Count() <= 2 ? QualityLevel::OPTIMAL : new_quality;
1004-        if (first && component == todo) {
1005-            // The existing Cluster is an entire component. Leave it be, but update its quality.
1006+        if (first && component == todo && SetType::Fill(component.Count()) == component) {

l0rinc commented at 9:55 pm on October 3, 2025:

for the record, the SanityCheck below doesn’t seem to fail without this change (i.e. build without fuzz passed if I have reverted this line for commit d9dbbf41b6458b11d9225fb436fc749bd30f9588). Not sure that’s expected, it surprised me.

sipa commented at 9:37 pm on October 8, 2025:

This entire if branch is an optimization which could be commented out without breaking anything. It just avoids creating a new cluster when the old one could be reused.

in src/test/fuzz/cluster_linearize.cpp:511 in 7084d5faf1 outdated

552+                            sim[i]->second -= del;
553+                        }
554                     }
555                 }
556+                break;
557+            } else if (command-- == 0) {

l0rinc commented at 9:59 pm on October 3, 2025:

This is just for consistency over } else {, right?

sipa commented at 9:38 pm on October 8, 2025:

And extensibility, yes.

in src/cluster_linearize.h:338 in 7084d5faf1 outdated

332@@ -332,6 +333,17 @@ class DepGraph
333         }
334         return true;
335     }
336+
337+    /** Reduce memory usage if possible. No observable effect. */
338+    void Compact() noexcept

l0rinc commented at 8:53 pm on October 5, 2025:

my understanding is that shrinking can throw on allocation error. Since the reallocation is optional in this case, we could catch it and ignore it, but we would likely fail on the very next allocation anyway, so it may not help a lot…

sipa commented at 9:39 pm on October 8, 2025:

We always treat allocation errors as fatal.

in src/cluster_linearize.h:340 in 7084d5faf1 outdated

332@@ -332,6 +333,17 @@ class DepGraph
333         }
334         return true;
335     }
336+
337+    /** Reduce memory usage if possible. No observable effect. */
338+    void Compact() noexcept
339+    {
340+        entries.shrink_to_fit();

l0rinc commented at 8:54 pm on October 5, 2025:

would it make sense to add some minimal buffer to avoid shrinking if the capacity is very close to size - and to avoid having to realloc on the very next addition?

sipa commented at 9:39 pm on October 8, 2025:

We could experiment with that in a follow-up.

in src/txgraph.cpp:1211 in 0f3331f8cb outdated

910@@ -909,6 +911,7 @@ void Cluster::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>
911             [&](auto pos) { return todo[pos]; }), m_linearization.end());
912         quality = QualityLevel::NEEDS_SPLIT;
913     }
914+    Compact();
915     graph.SetClusterQuality(level, m_quality, m_setindex, quality);
916     Updated(graph, level);

l0rinc commented at 5:06 pm on October 6, 2025:

0f3331f8cb215b5b45e6a369ea989fe27d7a04af I mostly understand why we’re calling Compact after the Updated in GenericClusterImpl::Split but wasn’t sure why we’re compacting before possible changes here in GenericClusterImpl::ApplyRemovals.

But adding:

0auto mem_before{TotalMemoryUsage()};
1Updated(graph, level);
2Compact();
3assert(mem_before == TotalMemoryUsage());

revealed that there’s no difference, since the txgrap fuzz always passes here - just want to confirm if it’s deliberate.

sipa commented at 10:01 pm on October 8, 2025:

I do see fuzz failure if I remove the Compact; as for example it’s possible that m_linearization is shrunk above, which will need to be accounted for.

Now, it is true that we technically don’t really care about minimizing memory usage here, as we’ll always have a Split() that follows, which will either create new Clusters, or update the existing one. The Compact() and corresponding updating of memory usage could be moved there, but I find that a bit harder to reason about.

in src/txgraph.cpp:942 in 0f3331f8cb outdated

938@@ -936,6 +939,13 @@ void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
939     Updated(graph, 0);
940 }
941 
942+void Cluster::Compact() noexcept

l0rinc commented at 5:14 pm on October 6, 2025:

what if the compactions returned a boolean of whether they did any work, maybe that can help with testing Compact based on TotalMemoryUsage (or vice-versa), something like if (c.Compact()) assert(mem_after < mem_before);

sipa commented at 10:01 pm on October 8, 2025:

Seems overkill.

in src/txgraph.cpp:1103 in f891b3aff3 outdated

1098@@ -1071,6 +1099,8 @@ void Cluster::Merge(TxGraphImpl& graph, int level, Cluster& other) noexcept
1099 {
1100     /** Vector to store the positions in this Cluster for each position in other. */
1101     std::vector<DepGraphIndex> remap(other.m_depgraph.PositionRange());
1102+    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1103+    graph.GetClusterSet(level).m_cluster_usage -= other.TotalMemoryUsage();

l0rinc commented at 5:28 pm on October 6, 2025:

nit: maybe we could reduce duplication here:

0    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage() + other.TotalMemoryUsage();

glozow commented at 5:51 pm on October 7, 2025:

fwiw, I think the existing code is clearer.

l0rinc commented at 7:25 pm on October 7, 2025:

I’m also fine with other ways of deduplication - or to leave as is.

sipa commented at 10:01 pm on October 8, 2025:

I will leave as-is.

in src/txgraph.cpp:2150 in f891b3aff3 outdated

2145@@ -2114,6 +2146,7 @@ void TxGraphImpl::StartStaging() noexcept
2146     m_staging_clusterset->m_deps_to_add = m_main_clusterset.m_deps_to_add;
2147     m_staging_clusterset->m_group_data = m_main_clusterset.m_group_data;
2148     m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2149+    m_staging_clusterset->m_cluster_usage = 0;
2150     Assume(m_staging_clusterset->m_oversized.has_value());

l0rinc commented at 5:32 pm on October 6, 2025:

The oversized Assume refers to a previous line and we’re assigning the default value to a freshly created field. To group the oversized references and allow implicit values, maybe we could do:

0    m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
1    Assume(m_staging_clusterset->m_oversized.has_value());
2    Assume(m_staging_clusterset->m_cluster_usage == 0);

or

0    Assume(m_main_clusterset.m_oversized.has_value());
1    m_staging_clusterset->m_oversized = m_main_clusterset.m_oversized;
2    Assume(m_staging_clusterset->m_cluster_usage == 0);
3    Assume(m_staging_clusterset->m_removed.empty());
4    Assume(m_staging_clusterset->m_to_remove.empty());

sipa commented at 6:54 pm on October 9, 2025:

I have reordered the statements.

in src/txgraph.cpp:1275 in f891b3aff3 outdated

956@@ -934,8 +957,10 @@ void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
957         entry.m_locator[1].SetMissing();
958     }
959     auto quality = m_quality;
960+    graph.GetClusterSet(1).m_cluster_usage -= TotalMemoryUsage();

l0rinc commented at 5:36 pm on October 6, 2025:

While the method name hints at it, maybe a comment could be added to draw attention that we’re removing from staging and adding to main. I have checked and SanityCheck via fuzzing correctly catches if we would have had a main cluster usage deduction here 👍

sipa commented at 6:55 pm on October 9, 2025:

I have reordered these statements and added comments.

in src/txgraph.cpp:2985 in 437e29cd8d outdated

2978@@ -2977,6 +2979,22 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
2979     return ret;
2980 }
2981 
2982+size_t TxGraphImpl::GetMainMemoryUsage() noexcept
2983+{
2984+    // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
2985+    SplitAll(0);

l0rinc commented at 5:40 pm on October 6, 2025:

I find these side-effects here to be very confusing in an apparent memory getter method (same for Exists)

sipa commented at 10:06 pm on October 8, 2025:

They are unobservable side-effects (from the perspective of a TxGraph interface user). The implementation is lazy, which means that at times it needs to apply queued-up mutations.

l0rinc commented at 5:31 pm on October 11, 2025:

Now that you’ve added the stability fuzz tests, I’m fine with the side-effects, thanks

in src/txgraph.cpp:2988 in 437e29cd8d outdated

2983+{
2984+    // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
2985+    SplitAll(0);
2986+    ApplyDependencies(0);
2987+    // Compute memory usage
2988+    auto& clusterset = GetClusterSet(0);

l0rinc commented at 5:41 pm on October 6, 2025:

The method name already claims it’s main, so we might as well use m_main_clusterset here directly + inline return value:

0    return /* From clusters */
1           m_main_clusterset.m_cluster_usage +
2           /* From Entry objects. */
3           sizeof(Entry) * m_main_clusterset.m_txcount +
4           /* From the chunk index. */
5           memusage::DynamicUsage(m_main_chunkindex);

sipa commented at 6:55 pm on October 9, 2025:

Done.

in src/txgraph.h:208 in 437e29cd8d outdated

201@@ -202,6 +202,12 @@ class TxGraph
202      *  graph must not be oversized. If the graph is empty, {{}, FeePerWeight{}} is returned. */
203     virtual std::pair<std::vector<Ref*>, FeePerWeight> GetWorstMainChunk() noexcept = 0;
204 
205+    /** Get the approximate memory usage for this object, just counting the main graph. If a
206+     *  staging graph is present, return a number corresponding to memory usage after
207+     *  AbortStaging() would be called. BlockBuilders' memory usage is not included here. Can
208+     *  always be called. */

l0rinc commented at 5:42 pm on October 6, 2025:

what does “can always be called” refer to here? That it can be called even if the graph is oversized?

sipa commented at 10:12 pm on October 8, 2025:

Yes, or when BlockBuilder objects exist. All functions in the TxGraph interface declare when they’re allowed to be called.

in src/txgraph.cpp:98 in a9eeb70759 outdated

93@@ -94,21 +94,16 @@ struct TrimTxData
94     uint64_t m_uf_size;
95 };
96 
97+class Cluster;
98+class GenericClusterImpl;

l0rinc commented at 5:45 pm on October 6, 2025:

I’m surprised by these forward declarations, a parent shouldn’t have to know about the children (at least in programming) - but it seems we don’t actually need these

sipa commented at 6:55 pm on October 9, 2025:

Done.

in src/txgraph.cpp:104 in a9eeb70759 outdated

 99+
100 /** A grouping of connected transactions inside a TxGraphImpl::ClusterSet. */
101 class Cluster
102 {
103     friend class TxGraphImpl;
104     using GraphIndex = TxGraph::GraphIndex;

l0rinc commented at 5:46 pm on October 6, 2025:

can we make this protected to avoid having to redefine it in every child class?

sipa commented at 6:55 pm on October 9, 2025:

Done.

in src/txgraph.cpp:231 in a9eeb70759 outdated

252+ *  transactions up to MAX_CLUSTER_COUNT_LIMIT. */
253+class GenericClusterImpl final : public Cluster
254+{
255+    friend class TxGraphImpl;
256+    using GraphIndex = TxGraph::GraphIndex;
257+    using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;

l0rinc commented at 5:49 pm on October 6, 2025:

nit: This tripped me up a bit on first review, seeing the usages it made me think it’s setter method for an internal type - maybe BitsetType or ClusterPositions or something similar could be more descriptive

sipa commented at 10:14 pm on October 8, 2025:

We’re using the name SetType in many places in the cluster linearization code.

in src/txgraph.cpp:262 in a9eeb70759 outdated

271+    explicit GenericClusterImpl(uint64_t sequence) noexcept;
272+    /** Construct a singleton GenericClusterImpl. */
273+    explicit GenericClusterImpl(uint64_t sequence, TxGraphImpl& graph, const FeePerWeight& feerate, GraphIndex graph_index) noexcept;
274+
275+
276+    size_t TotalMemoryUsage() const noexcept final

l0rinc commented at 5:50 pm on October 6, 2025:

On a final class, C.128 says either override or final can be used on virtual functions with no semantic difference. The current use of final is correct, but the guideline notes to ‘use final on functions sparingly’, so override might be descriptive here:

0    size_t TotalMemoryUsage() const noexcept override

sipa commented at 10:16 pm on October 8, 2025:

The code already uses final on all of the TxGraphImpl functions. Will leave for a follow-up.

in src/txgraph.cpp:1119 in a9eeb70759 outdated

1114@@ -1066,7 +1115,8 @@ bool Cluster::Split(TxGraphImpl& graph, int level) noexcept
1115     // Redistribute the transactions.
1116     for (auto i : m_linearization) {
1117         /** The cluster which transaction originally in position i is moved to. */
1118-        Cluster* new_cluster = remap[i].first;
1119+        Cluster* new_abstract_cluster = remap[i].first;
1120+        GenericClusterImpl* new_cluster = static_cast<GenericClusterImpl*>(new_abstract_cluster);

l0rinc commented at 5:59 pm on October 6, 2025:

These casts bother me a bit, I think we could avoid these by adding the abstraction commit before the specialization commit, e.g.

 0diff --git a/src/txgraph.cpp b/src/txgraph.cpp
 1--- a/src/txgraph.cpp	(revision 2ab1b802ad070853777a3c207a4fe49ef32bc978)
 2+++ b/src/txgraph.cpp	(date 1759773463470)
 3@@ -104,6 +104,7 @@
 4     using GraphIndex = TxGraph::GraphIndex;
 5 
 6 protected:
 7+    using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
 8     /** The quality level of m_linearization. */
 9     QualityLevel m_quality{QualityLevel::NONE};
10     /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */
11@@ -157,6 +158,8 @@
12     virtual uint64_t GetTotalTxSize() const noexcept = 0;
13     /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */
14     virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0;
15+    /** Add dependencies to a given child in this cluster. */
16+    virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;
17     /** Figure out what level this Cluster exists at in Graph::m_clustersets. In most cases this
18      *  is known by the caller already (see all "int level" arguments below), but not always. */
19     virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0;
20@@ -262,6 +265,10 @@
21     LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
22     uint64_t GetTotalTxSize() const noexcept final;
23     GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }
24+    void AddDependencies(SetType parent, DepGraphIndex child) noexcept
25+    {
26+        m_depgraph.AddDependencies(parent, child);
27+    }
28     int GetLevel(const TxGraphImpl& graph) const noexcept final;
29     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }
30     void Updated(TxGraphImpl& graph, int level) noexcept final;
31@@ -1128,12 +1135,11 @@
32     // Redistribute the dependencies.
33     for (auto i : m_linearization) {
34         /** The cluster transaction in position i is moved to. */
35-        Cluster* new_abstract_cluster = remap[i].first;
36-        GenericClusterImpl* new_cluster = static_cast<GenericClusterImpl*>(new_abstract_cluster);
37+        Cluster* new_cluster = remap[i].first;
38         // Copy its parents, translating positions.
39         SetType new_parents;
40         for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
41-        new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
42+        new_cluster->AddDependencies(new_parents, remap[i].second);
43     }
44     // Update all the Locators of moved transactions, and memory usage.
45     for (Cluster* new_cluster : new_clusters) {

The difficulty of extracting it revealed a lack of abstraction that we could fix before doing the abstraction itself.

sipa commented at 6:56 pm on October 9, 2025:

Fixed by doing the introduction of abstraction functions first, before making Cluster an abstract class.

l0rinc commented at 5:32 pm on October 11, 2025:

Thanks, it’s a lot cleaner this way

in src/txgraph.cpp:156 in a9eeb70759 outdated

144@@ -167,75 +145,145 @@ class Cluster
145         return m_quality == QualityLevel::NEEDS_SPLIT ||
146                m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
147     }
148+
149+    // Generic helper functions
150+
151+    /** Total memory usage currently for this Cluster, including all its dynamic memory, plus Cluster
152+     *  structure itself, and ClusterSet::m_clusters entry. */
153+    virtual size_t TotalMemoryUsage() const noexcept = 0;

l0rinc commented at 6:19 pm on October 6, 2025:

a9eeb7075954adaf74731160fbaa0ac9e4704c34 nit: we’re moving this method that we’ve introduced in a different commit. If you touch again, consider placing it here to minimize the diff

sipa commented at 8:57 pm on October 9, 2025:

I’ve moved the implementation out of the class definition, so that it doesn’t need to move when the abstraction is added.

in src/txgraph.cpp:1 in a9eeb70759 outdated

l0rinc commented at 6:19 pm on October 6, 2025:

a9eeb7075954adaf74731160fbaa0ac9e4704c34 I have manually inlined the new class to see if it was abstracted correctly and I got very minimal diff 👍

l0rinc commented at 7:36 pm on October 6, 2025:

Doing a single final sanity check ignores situations when we get temporarily out of sync - I know it can be expensive, but could we add it after each change? I tried and it did pass for me.

l0rinc commented at 1:45 am on October 7, 2025:

Another surprise for me here is that a sanity check removes transactions

l0rinc commented at 2:04 am on October 7, 2025:

when do we expect this to be the case? My understand was that if the “no holes” invariant holds this should never be true. Adding a throw "" here for debugging indicates that this is never called.

sipa commented at 4:08 pm on October 9, 2025:

I don’t think that’s worth the slowdown.

My thinking around this is that whenever the fuzzer hits a particular level of complication, it’s reasonable to assume it has already explored most less-complicated cases too, through other runs of the harness. That applies to prefixes of the same seed too.

sipa commented at 5:22 pm on October 9, 2025:

It only modifies the linchunking object, which is local inside SanityCheck().

l0rinc commented at 5:53 pm on October 9, 2025:

you’re right, my mistake

sipa commented at 9:05 pm on October 9, 2025:

Nice. I’ve replaced it with an Assume that the adding always happens at the end.

This made me realize that there is probably a more efficient GenericClusterImpl::Merge implementation possible (which just translates the indices in the old cluster to the new one by appending an offset to all). It’s pretty nontrivial to do, so I’m leaving that for a potential follow-up if anyone cares.

l0rinc commented at 5:24 pm on October 11, 2025:

Mostly unrelated, but I have checked the fuzz coverage of these files, there are a few missing areas that we might want to follow-up on later:

l0rinc commented at 5:27 pm on October 11, 2025:

Is there anything trivial from that idea that we could already do now, without making the code more complicated? Merge is quite complicated currently, seems there may be a few independent operations lurking inside. But I admit I don’t fully understand it yet, so ignore if not relevant.

l0rinc commented at 5:35 pm on October 11, 2025:

I have tested with them added and the fuzzers are passing

sipa commented at 10:01 pm on October 11, 2025:

The first two here are sort of expected, as they’re only in instantiations with the MultiIntBitSet as set type. There is another fuzz test that verifies the behavior of that instance as correct, and specifically, equivalent to IntBitSet. At higher levels IntBitSet is the only one used in actual production code, while MultiIntBitSet is only used in tests (for example, in the txgraph fuzz simulation).

sipa commented at 10:04 pm on October 11, 2025:

I don’t think so; it needs a different approach.

The current approach copies in linearization order. A faster approach (which would need additional logic in DepGraph too) would return the DepGraphIndex order of transactions, and applies offsets.

I’ll consider this in my (not yet pushed) updates to #32545, which introduce a substantial change: allowing linearizations to be non-topological. That currently requires merging in two phases (first copy all transactions, then all dependencies). An offset approach may be simpler there.

l0rinc commented at 8:41 pm on October 20, 2025:

The latest https://maflcko.github.io/b-c-cov/fuzz.coverage/src/txgraph.cpp.gcov.html#L1446 indicates that SingletonClusterImpl::Split may not be covered fully.

l0rinc commented at 11:20 am on November 3, 2025:

pushed a follow-up to https://github.com/bitcoin/bitcoin/pull/33768

in src/txgraph.cpp:153 in e8355b2169 outdated

149@@ -148,6 +150,8 @@ class Cluster
150 
151     // Generic helper functions
152 
153+    /** Determine the maximum number of transactions this cluster can hold. */
154+    virtual DepGraphIndex GetMaxTxCount() const noexcept = 0;

l0rinc commented at 6:22 pm on October 6, 2025:

e8355b2169555fbd66daba055a727fdb2dee390b as mentioned, I would do these changes before the abstraction attempt to make that cleaner (avoiding downcasts directly)

sipa commented at 6:57 pm on October 9, 2025:

Done.

in src/txgraph.cpp:241 in e8355b2169 outdated

237@@ -227,8 +238,8 @@ class Cluster
238 class GenericClusterImpl final : public Cluster
239 {
240     friend class TxGraphImpl;
241+    using SetType = Cluster::SetType;

l0rinc commented at 6:22 pm on October 6, 2025:

This seems unused

glozow commented at 3:08 pm on October 7, 2025:

m_depgraph is a DepGraph<SetType>

l0rinc commented at 7:24 pm on October 7, 2025:

We’re in Cluster so SetType should be available here, so I think it’s redundant

sipa commented at 6:57 pm on October 9, 2025:

Indeed, fixed.

in src/txgraph.cpp:891 in e8355b2169 outdated

790@@ -779,6 +791,31 @@ uint64_t GenericClusterImpl::GetTotalTxSize() const noexcept
791     return ret;
792 }
793 
794+DepGraphIndex GenericClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
795+{
796+    Assume(graph_idx != GraphIndex(-1));

l0rinc commented at 6:25 pm on October 6, 2025:

There are a lot of these sentinels spread around the code after the split. Could we document if slightly better with something like:

0class Cluster
1...
2public:
3    static constexpr auto INVALID{GraphIndex(-1)};

and

0    Assume(graph_idx != Cluster::INVALID);

glozow commented at 6:30 pm on October 7, 2025:

Alternatively, both classes could implement an IsEmpty() function.

sipa commented at 6:58 pm on October 9, 2025:

Instead of adding an IsEmpty(), I ended up using the added GetTxCount() virtual function in many places.

in src/txgraph.cpp:808 in e8355b2169 outdated

803+void GenericClusterImpl::AddDependencies(SetType parent, DepGraphIndex child) noexcept
804+{
805+    m_depgraph.AddDependencies(parent, child);
806+}
807+
808+void GenericClusterImpl::ExtractTransactions(std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)> visit_fn) noexcept

l0rinc commented at 6:34 pm on October 6, 2025:

This seems like a non-trivial lambda, given that it’s called from a loop, please consider if it would make sense to avoid the copy:

0virtual void ExtractTransactions(const std::function<void (...)>& visit_fn) noexcept = 0;

sipa commented at 6:58 pm on October 9, 2025:

Done.

in src/txgraph.cpp:319 in 5ac32aa441 outdated

322+               // Memory usage of the ClusterSet::m_clusters entry.
323+               sizeof(std::unique_ptr<Cluster>);
324+    }
325+
326+    DepGraphIndex GetMaxTxCount() const noexcept final { return 1; }
327+    LinearizationIndex GetTxCount() const noexcept final { return m_graph_index != GraphIndex(-1); }

l0rinc commented at 6:39 pm on October 6, 2025:

Now that this is extracted to a dedicated method, there are a few places we could reuse it:

0    uint64_t GetTotalTxSize() const noexcept override { return GetTxCount() ? m_feerate.size : 0; }
1    GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept override
2    { Assume(index == 0); Assume(GetTxCount()); return m_graph_index; }

and

0DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
1{
2    Assume(!GetTxCount());
3    ...

0void SingletonClusterImpl::ExtractTransactions(std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)> visit_fn) noexcept
1{
2    if (GetTxCount()) {

etc

sipa commented at 6:58 pm on October 9, 2025:

Done.

in src/txgraph.cpp:662 in 5ac32aa441

653@@ -598,10 +654,16 @@ class TxGraphImpl final : public TxGraph
654     {
655         return std::make_unique<GenericClusterImpl>(m_next_sequence_counter++);
656     }
657+    /** Create an empty SingletonClusterImpl object. */
658+    std::unique_ptr<SingletonClusterImpl> CreateEmptySingletonCluster() noexcept
659+    {
660+        return std::make_unique<SingletonClusterImpl>(m_next_sequence_counter++);
661+    }
662     /** Create an empty Cluster object of the appropriate size. */

l0rinc commented at 6:43 pm on October 6, 2025:

The comment may need some clarification how an empty object can have a non-empty size

0    /** Create an empty Cluster of the appropriate implementation. */

sipa commented at 6:59 pm on October 9, 2025:

Did rephrase a bit more elaborately.

in src/txgraph.cpp:2017 in 5ac32aa441 outdated

1993@@ -1746,18 +1994,33 @@ void TxGraphImpl::Merge(std::span<Cluster*> to_merge, int in_level) noexcept
1994     // moves.
1995     size_t max_size_pos{0};
1996     DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
1997+    DepGraphIndex total_size = max_size;

l0rinc commented at 6:46 pm on October 6, 2025:

Is this strictly related to SingletonClusterImpl changes? If you modify again, could it be split out to a separate commit since that one is already quite complicated, maybe we can split it into two commits? But only if you need to touch again.

sipa commented at 7:00 pm on October 9, 2025:

I have moved these changes to a separate commit, introducing the notion of intended ranges of transaction counts for each Cluster implementation.

in src/txgraph.cpp:2640 in 5ac32aa441

2633@@ -2318,6 +2634,14 @@ void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx
2634     Updated(graph, level);
2635 }
2636 
2637+void SingletonClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx, int64_t fee) noexcept
2638+{
2639+    Assume(m_graph_index != GraphIndex(-1));
2640+    Assume(idx == 0);

l0rinc commented at 6:50 pm on October 6, 2025:

nit: when is it index and when idx?

sipa commented at 3:17 pm on October 9, 2025:

I think I’ve mostly used “idx” in function arguments, and “index” in member/local variable names, but it’s probably not entirely consistent.

in src/test/fuzz/txgraph.cpp:1019 in 5ac32aa441

1011@@ -1012,6 +1012,15 @@ FUZZ_TARGET(txgraph)
1012                 }
1013                 assert(!top_sim.IsOversized());
1014                 break;
1015+            } else if (command-- == 0) {
1016+                // GetMainMemoryUsage().
1017+                real->GetMainMemoryUsage();
1018+                // There is nothing to test about this function, as it's very
1019+                // implementation-specific, and can go up (even when transactions are removed) and

l0rinc commented at 7:17 pm on October 6, 2025:

maybe we could check that calling it is stable and idempotent, something like:

0assert(real->GetMainMemoryUsage() == real->GetMainMemoryUsage());
1
2if (real->GetTransactionCount(TxGraph::Level::MAIN) == 0) {
3    assert(real->GetMainMemoryUsage() == 0);
4} else {
5    assert(real->GetMainMemoryUsage() > 0);
6}
7
8real->SanityCheck();

And given that GetMainMemoryUsage has some surprising side-effects (SplitAll & ApplyDependencies), we could also check that it’s not changing counts or staging presence.

sipa commented at 8:59 pm on October 9, 2025:

Good idea, I’ve done something like this (with the repetition made optional).

And given that GetMainMemoryUsage has some surprising side-effects (SplitAll & ApplyDependencies), we could also check that it’s not changing counts or staging presence.

There is no need for that; comparing with the simulation will catch that as those are well-defined properties we check (either when invoking inspector methods in the simulation, or in the full comparison at the end).

in src/txgraph.cpp:1341 in 5ac32aa441 outdated

1312@@ -957,7 +1313,17 @@ uint64_t Cluster::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::
1313     return size;
1314 }
1315 
1316-bool Cluster::Split(TxGraphImpl& graph) noexcept
1317+uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1318+{
1319+    if (m_graph_index  == GraphIndex(-1)) return 0;

l0rinc commented at 7:41 pm on October 6, 2025:

super-nit: formatting and repeated GraphIndex(-1) references

sipa commented at 9:00 pm on October 9, 2025:

I have removed some of them through use of GetTxCount() as suggested elsewhere.

l0rinc commented at 5:40 pm on October 11, 2025:

Except this one

in src/txgraph.cpp:1415 in 5ac32aa441

1411+{
1412+    Assume(NeedsSplitting());
1413+    if (m_graph_index == GraphIndex(-1)) {
1414+        // The cluster is now empty.
1415+        graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1416+        Updated(graph, level);

l0rinc commented at 7:41 pm on October 6, 2025:

Is this necessary here? Seems like a noop

sipa commented at 9:00 pm on October 9, 2025:

Nice catch. Removed.

in src/txgraph.cpp:1593 in 5ac32aa441

1589@@ -1193,15 +1590,15 @@ void TxGraphImpl::SetClusterQuality(int level, QualityLevel old_quality, Cluster
1590     InsertCluster(level, std::move(cluster_ptr), new_quality);
1591 }
1592 
1593-void TxGraphImpl::DeleteCluster(Cluster& cluster) noexcept
1594+void TxGraphImpl::DeleteCluster(int level, Cluster& cluster) noexcept

l0rinc commented at 7:42 pm on October 6, 2025:

nit: in other cases the level param is after the cluster one (reduces some diffs if we’re consistent)

sipa commented at 9:00 pm on October 9, 2025:

Moved it.

in src/txgraph.cpp:943 in cd6dadf53a outdated

713+{
714+    // GetLevel() does not work for empty Clusters.
715+    Assume(!m_linearization.empty());
716+
717+    // Pick an arbitrary Entry that occurs in this Cluster.
718+    const auto& entry = graph.m_entries[m_mapping[m_linearization.front()]];

glozow commented at 8:32 pm on October 6, 2025:

If the cluster is empty, then L718 will call front() on an empty vector. Should we assert instead of Assume that it’s not empty?

Alternatively, if (!Assume(!m_linearization.empty()) return -1;?

sipa commented at 9:07 pm on October 9, 2025:

Done.

instagibbs commented at 12:36 pm on October 10, 2025:

not going to nag any but until now in TxGraph we haven’t been using conditionals to “save” us in release builds when these assumptions are violated

GrayHatGuy commented at 12:43 pm on October 10, 2025:

A proper risk analysis would have vetted this

in src/txgraph.cpp:130 in 5ac32aa441

145 
146-    // Generic helper functions.
147-
148     /** Whether the linearization of this Cluster can be exposed. */
149     bool IsAcceptable(bool after_split = false) const noexcept
150     {

l0rinc commented at 11:36 pm on October 6, 2025:

super-nit: IsOptimal could be used inside IsAcceptable (though it wouldn’t be symmetric in that case)

sipa commented at 4:20 pm on October 9, 2025:

Seems unrelated to this PR.

in src/txgraph.cpp:172 in 5ac32aa441

170+    virtual DepGraphIndex AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept = 0;
171+    /** Add dependencies to a given child in this cluster. */
172+    virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;
173+    /** Invoke visitor_fn for each transaction in the cluster, in linearization order, then wipe this Cluster. */
174+    virtual void ExtractTransactions(std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)> visit_fn) noexcept = 0;
175+    /** Figure out what level this Cluster exists at in Graph::m_clustersets. In most cases this

l0rinc commented at 11:41 pm on October 6, 2025:

I can’t find Graph::m_clustersets

sipa commented at 9:00 pm on October 9, 2025:

Added a commit that fixes some outdated comments.

in src/txgraph.cpp:112 in 5ac32aa441

116-    /** The current linearization of the cluster. m_linearization.size() equals
117-     *  m_depgraph.TxCount(). This is always kept topological. */
118-    std::vector<DepGraphIndex> m_linearization;
119     /** The quality level of m_linearization. */
120     QualityLevel m_quality{QualityLevel::NONE};
121     /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */

l0rinc commented at 11:44 pm on October 6, 2025:

the Graph:: references seem to be leftovers, so maybe they can be updated to TxGraphImpl::ClusterSet::m_clusters

sipa commented at 9:01 pm on October 9, 2025:

Fixed in a commit that fixes some outdated comments.

in src/txgraph.cpp:1088 in 5ac32aa441

1084@@ -814,38 +1085,58 @@ std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
1085             cluster->GetConflicts(*this, ret);
1086         }
1087     }
1088-    // Deduplicate the result (the same Cluster may appear multiple times).
1089+    // Deduplicate the result (the same GenericClusterImpl may appear multiple times).

l0rinc commented at 11:52 pm on October 6, 2025:

Hmm, but SingletonClusterImpl can also be in the duplicates:

0assert(std::ranges::all_of(ret, [](auto* c){ return c->GetMaxTxCount() > 1; }));

fails the txgraph fuzzer, indicating that this should likely remain:

0    // Deduplicate the result (the same Cluster may appear multiple times).

sipa commented at 9:01 pm on October 9, 2025:

Indeed, fixed.

in src/txgraph.cpp:1225 in 5ac32aa441

1225 
1226-void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
1227+void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1228+{
1229+    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
1230+    if (m_graph_index == GraphIndex(-1)) return;

l0rinc commented at 0:35 am on October 7, 2025:

nit: there is likely no difference in accounting, but if we’re already returning on the second line, we could avoid a noop usage call:

0    if (m_graph_index == GraphIndex(-1)) return;
1    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();

sipa commented at 9:02 pm on October 9, 2025:

Nice catch.

Even better: the fact that this was possible indicated that the function was never called on empty clusters (because TotalMemoryUsage() is not 0, even for empty clusters). I’ve thus changed it to an Assume() for non-emptiness.

in src/txgraph.cpp:1260 in 5ac32aa441 outdated

1238     for (auto i : m_linearization) {
1239         GraphIndex idx = m_mapping[i];
1240         auto& entry = graph.m_entries[idx];
1241         entry.m_locator[1].SetMissing();
1242     }
1243     auto quality = m_quality;

l0rinc commented at 0:40 am on October 7, 2025:

This innocent looking assignment also revealed that ExtractCluster modifies the object’s m_quality - which I found surprising.

Inlined it to validate the above claim, fuzzing fails with: txgraph.cpp:1566 InsertCluster: Assertion 'quality != QualityLevel::NONE' failed.

sipa commented at 4:47 pm on October 9, 2025:

Yeah, extracting is seen as moving to the “none” quality level.

in src/txgraph.cpp:1390 in 5ac32aa441

1399     }
1400     // Redistribute the dependencies.
1401     for (auto i : m_linearization) {
1402         /** The cluster transaction in position i is moved to. */
1403-        Cluster* new_cluster = remap[i].first;
1404+        Cluster* new_abstract_cluster = remap[i].first;

l0rinc commented at 0:43 am on October 7, 2025:

Are we deliberately keeping the new name here (new_cluster -> new_abstract_cluster) or is this just a leftover from the temporary casting?

sipa commented at 9:02 pm on October 9, 2025:

This was a leftover, gone.

in src/txgraph.cpp:2174 in 5ac32aa441

2170@@ -1756,7 +2171,7 @@ void TxGraphImpl::RemoveTransaction(const Ref& arg) noexcept
2171     Assume(m_main_chunkindex_observers == 0 || GetTopLevel() != 0);
2172     // Find the Cluster the transaction is in, and stop if it isn't in any.
2173     int level = GetTopLevel();
2174-    auto cluster = FindCluster(GetRefIndex(arg), level);
2175+    auto [cluster, cluster_level] = FindCluster(GetRefIndex(arg), level);

l0rinc commented at 0:52 am on October 7, 2025:

we don’t seem to be using the new cluster_level value, to avoid confusion and minimize the diff, please consider:

0    auto [cluster, _] = FindCluster(GetRefIndex(arg), level);

or

0    auto cluster = FindCluster(GetRefIndex(arg), level).first;

or even:

0    if (!FindCluster(GetRefIndex(arg), level).first) return;

sipa commented at 9:02 pm on October 9, 2025:

Addressed by introducing a separate FindCluster and FindClusterAndLevel function.

in src/txgraph.cpp:2263 in 5ac32aa441 outdated

2234@@ -1820,7 +2235,19 @@ void Cluster::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Clus
2235     }
2236 }
2237 
2238-void Cluster::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2239+void SingletonClusterImpl::GetAncestorRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2240+{
2241+    Assume(m_graph_index != GraphIndex(-1));
2242+    while (!args.empty()) {
2243+        if (args.front().first != this) break;

l0rinc commented at 1:10 am on October 7, 2025:

similarly to:

https://github.com/bitcoin/bitcoin/blob/86eaa4d6cd5c428f6635a8d44fa6b5a9545ea909/src/cluster_linearize.h#L440-L442

0    while (!args.empty() && args.front().first == this) {

sipa commented at 4:48 pm on October 9, 2025:

This matches the code that’s already in GenericClusterImpl.

in src/txgraph.cpp:627 in 5ac32aa441

620@@ -484,12 +621,13 @@ class TxGraphImpl final : public TxGraph
621     /** Swap the Entry referred to by a and the one referred to by b. */
622     void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
623     /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
624-    *   removed), return the Cluster it is in. Otherwise, return nullptr. */
625-    Cluster* FindCluster(GraphIndex idx, int level) const noexcept;
626+    *   removed), return the Cluster it is in and the level the Cluster has. Otherwise, return
627+    *   {nullptr, -1}. */
628+    std::pair<Cluster*, int> FindCluster(GraphIndex idx, int level) const noexcept;
629     /** Extract a Cluster from its ClusterSet. */

l0rinc commented at 1:34 am on October 7, 2025:

Could we document here that its quality is also changed?

0    /** Extract a Cluster from its ClusterSet and set its quality to NONE. */

sipa commented at 9:03 pm on October 9, 2025:

Done, in a new comment-fixing commit.

in src/txgraph.cpp:913 in 5ac32aa441 outdated

887+    m_depgraph.AddDependencies(parent, child);
888+}
889+
890+void SingletonClusterImpl::AddDependencies(SetType parent, DepGraphIndex child) noexcept
891+{
892+    // Singletons cannot have any dependencies.

l0rinc commented at 1:40 am on October 7, 2025:

if that’s the case, shouldn’t this be an error instead?

sipa commented at 5:07 pm on October 9, 2025:

Adding a dependency from a transaction to itself is a no-op. I don’t think we rely on that, but it doesn’t hurt to support.

in src/txgraph.cpp:2293 in 5ac32aa441 outdated

2265@@ -1839,7 +2266,12 @@ void Cluster::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cl
2266     }
2267 }
2268 
2269-bool Cluster::GetClusterRefs(TxGraphImpl& graph, std::span<TxGraph::Ref*> range, LinearizationIndex start_pos) noexcept
2270+void SingletonClusterImpl::GetDescendantRefs(const TxGraphImpl& graph, std::span<std::pair<Cluster*, DepGraphIndex>>& args, std::vector<TxGraph::Ref*>& output) noexcept
2271+{
2272+    GetAncestorRefs(graph, args, output);

l0rinc commented at 1:58 am on October 7, 2025:

Could we add a comment here explaining why a descendant is the same as an ancestor in this case? I’m not familiar enough with cluster mempool to understand that instantly - if you think it’s trivial, ignore my comment

sipa commented at 9:03 pm on October 9, 2025:

Done.

It’s simply that in a singleton cluster, the ancestors of a transaction, the descendants of a transaction, and in fact the entire cluster are always just the same single element.

l0rinc commented at 5:43 pm on October 11, 2025:

Thank you

in src/txgraph.cpp:160 in 5ac32aa441 outdated

156+    /** Total memory usage currently for this Cluster, including all its dynamic memory, plus Cluster
157+     *  structure itself, and ClusterSet::m_clusters entry. */
158+    virtual size_t TotalMemoryUsage() const noexcept = 0;
159     /** Get the number of transactions in this Cluster. */
160-    LinearizationIndex GetTxCount() const noexcept { return m_linearization.size(); }
161+    virtual LinearizationIndex GetTxCount() const noexcept = 0;

l0rinc commented at 2:10 am on October 7, 2025:

the comment states we’re calculating the “number of transactions” but the return type claims it’s a position within a Cluster::m_linearization. Given the calculations in TxGraphImpl::Merge I find this confusing.

sipa commented at 5:53 pm on October 9, 2025:

Every transaction in a cluster will end up in its linearization, so the transaction count can at most be 1 more than the largest possible linearization index. This makes it fairly appropriate as a type, I think.

DepGraphIndex could work too (and I use that elsewhere for transaction counts in a cluster), do you think that’s more clear? It’s a bit misleading too, because not every cluster actually uses a depgraph internally (singletons don’t).

l0rinc commented at 5:45 pm on October 11, 2025:

Not sure, will let you decide, feel free to resolve the comment

sipa commented at 10:05 pm on October 11, 2025:

Ok, resolving.

in src/txgraph.cpp:1354 in 5ac32aa441

1348@@ -983,52 +1349,55 @@ bool Cluster::Split(TxGraphImpl& graph) noexcept
1349     // Iterate over the connected components of this Cluster's m_depgraph.
1350     while (todo.Any()) {
1351         auto component = m_depgraph.FindConnectedComponent(todo);
1352+        auto component_size = component.Count();
1353         auto split_quality = component.Count() <= 2 ? QualityLevel::OPTIMAL : new_quality;
1354-        if (first && component == todo) {
1355-            // The existing Cluster is an entire component. Leave it be, but update its quality.
1356+        if (first && component == todo && component_size >= 2 && SetType::Fill(component_size) == component) {

l0rinc commented at 2:32 am on October 7, 2025:

The component_size >= 2 is basically what converts GenericClusterImpl back into a SingletonClusterImpl, right? And the opposite is TxGraphImpl::Merge in total_size > into_cluster->GetMaxTxCount(), right? The component_size >= 2 was a bit hidden here, if I understood it correctly, it might need some comment or refactoring.

sipa commented at 9:06 pm on October 9, 2025:

This is now dealt with more consistently in a new commit that introduces a range of valid transaction counts for each Cluster implementation.

in src/txgraph.cpp:2907 in 5ac32aa441 outdated

2880@@ -2401,6 +2881,19 @@ void TxGraphImpl::SanityCheck() const
2881             // ... for all clusters in them ...
2882             for (ClusterSetIndex setindex = 0; setindex < quality_clusters.size(); ++setindex) {
2883                 const auto& cluster = *quality_clusters[setindex];
2884+                // The number of transactions in a Cluster cannot exceed m_max_cluster_count.
2885+                assert(cluster.GetTxCount() <= m_max_cluster_count);

l0rinc commented at 2:41 am on October 7, 2025:

We could test the implementation-specific capacity as well here:

0                assert(cluster.GetTxCount() <= cluster.GetMaxTxCount());

sipa commented at 9:07 pm on October 9, 2025:

Why not both?

They’re independent notions: one is a policy-configurable per-TxGraph maximum cluster count, and the other is a Cluster-implementation dependent limit.

Done.

l0rinc commented at 3:11 am on October 7, 2025: contributor

It’s my first time diving into cluster mempool, and it seems like a solid implementation. I like the polymorphic split between SingletonClusterImpl and GenericClusterImpl.

I’ve documented my review journey and left many comments. Some are tiny nits, but others appear to be leftovers from previous refactorings that should be corrected - I’m fine with doing them in a follow-up PR as well. If you decide to apply any suggestions here, I’ve included a few commit reorganization tips that could make the changes clearer.

Key suggestions include:

Fuzz test enhancements for more thorough coverage
Documentation fixes for stale references from previous refactorings
Dead code removal after recent memory compaction changes
Comments highlighting surprising side-effects in certain methods

I don’t yet feel confident enough to fully approve, but this is definitely a strong Concept ACK for the change.

in src/txgraph.cpp:938 in 5ac32aa441

933+int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
934+{
935+    // GetLevel() does not work for empty Clusters.
936+    Assume(m_graph_index != GraphIndex(-1));
937+
938+    // Pick an arbitrary Entry that occurs in this Cluster.

glozow commented at 6:32 pm on October 7, 2025:

nit: In the SingletonClusterImpl case, there is only 1 Entry

sipa commented at 9:07 pm on October 9, 2025:

Fixed.

in src/txgraph.cpp:1063 in 5ac32aa441 outdated

1036+    // If this is for the main graph (level = 0), compute its chunking and store its information in
1037+    // the Entry's m_main_lin_index and m_main_chunk_feerate.
1038+    if (level == 0) {
1039+        entry.m_main_lin_index = 0;
1040+        entry.m_main_chunk_feerate = m_feerate;
1041+        graph.CreateChunkData(m_graph_index, LinearizationIndex(-1));

glozow commented at 6:40 pm on October 7, 2025:

nit: perhaps worth a comment that the special “singleton at the end of the cluster” LinearizationIndex(-1) is used here

sipa commented at 9:07 pm on October 9, 2025:

Good idea, done.

in src/txgraph.cpp:1037 in 5ac32aa441

1033+    // invalidate its ordering).
1034+    if (level == 0) graph.ClearChunkData(entry);
1035+    entry.m_locator[level].SetPresent(this, 0);
1036+    // If this is for the main graph (level = 0), compute its chunking and store its information in
1037+    // the Entry's m_main_lin_index and m_main_chunk_feerate.
1038+    if (level == 0) {

glozow commented at 6:54 pm on October 7, 2025:

Hm, should we be checking m_quality before adding to chunk index? Singletons are always “linearized” optimally of course, but QualityLevel::OVERSIZED_SINGLETON is also possible here (probably only theoretically).

sipa commented at 9:08 pm on October 9, 2025:

Fair point, done.

in src/txgraph.cpp:2122 in 5ac32aa441 outdated

2098+    Updated(graph, level);
2099     return {cost, improved};
2100 }
2101 
2102-void TxGraphImpl::MakeAcceptable(Cluster& cluster) noexcept
2103+std::pair<uint64_t, bool> SingletonClusterImpl::Relinearize(TxGraphImpl& graph, int level, uint64_t max_iters) noexcept

glozow commented at 7:08 pm on October 7, 2025:

As far as I can tell, this function should never be called?

sipa commented at 9:08 pm on October 9, 2025:

Indeed. Changed into an assert(false);, plus a comment explaining why, and a SingletonClusterImpl::SanityCheck() check to verify that claim.

glozow commented at 7:16 pm on October 7, 2025: member

code review ACK 5ac32aa441b

I focused on checking that all the dynamic memory is accounted for, places where m_cluster_usage is updated, and correctness of the SingletonCluster implementation. Feel free to ignore my nits.

DrahtBot requested review from l0rinc on Oct 7, 2025

sipa force-pushed on Oct 9, 2025

sipa commented at 6:23 pm on October 9, 2025: member

Addressed many comments, and made some bigger changes:

Restructured the commits to first make all abstractions, and then do the abstract class Cluster change cleanly.
Use GetTxCount() in more places, instead of m_graph_index != GraphIndex(-1)
Made Compact() and memory accounting work at the TxGraphImpl::Merge level rather than Cluster::Merge: the old code could be compacting O(n) times when merging n clusters together simultaneously.
Made the dealing with which implementations are valid for which ranges of transaction counts much cleaner.
Improved comments.

sipa force-pushed on Oct 9, 2025

in src/txgraph.cpp:1425 in de8ebdd795 outdated

1059@@ -1050,6 +1060,7 @@ bool Cluster::Split(TxGraphImpl& graph, int level) noexcept
1060     // Update all the Locators of moved transactions.
1061     for (Cluster* new_cluster : new_clusters) {
1062         new_cluster->Updated(graph, level);
1063+        new_cluster->Compact();

instagibbs commented at 1:05 pm on October 10, 2025:

de8ebdd795e35644435c7b68b2c2bc5f54ea9d7c

Not immediately clear this is necessary. These are all freshly generated, and shouldn’t have holes, and capacities should be proportional?

sipa commented at 1:50 pm on October 10, 2025:

No holes, indeed. But the capacities may be higher than needed, because transactions have been added one by one through vector::push_back in m_mapping, m_linearization, and m_depgraph.entries. When vector addition causes capacity to be exceeded, most C++ stdlibs use some exponential growing (e.g. doubling the capacity every time).

instagibbs commented at 1:56 pm on October 10, 2025:

yep, just noting

sipa commented at 2:19 pm on October 10, 2025:

I just noticed you said “proportional”. Indeed, they are, but still off by a factor of up to 2, and 1.5 on average.

instagibbs approved

instagibbs commented at 1:43 pm on October 10, 2025: member

reACK 7421e58dee402ee8b5b58a18684953a89ad350d7

git range-diff master 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354 7421e58dee402ee8b5b58a18684953a89ad350d7

DrahtBot requested review from glozow on Oct 10, 2025

in src/txgraph.cpp:1641 in 7421e58dee

1639 Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
1640 {
1641     int to_level = GetTopLevel();
1642     Assume(to_level == 1);
1643-    int level = cluster->m_level;
1644+    int level = cluster->GetLevel(*this);

l0rinc commented at 0:57 am on October 11, 2025:

This method is called from two places, one of which is dropping the pre-cacululated cluster level that we could access through FindClusterAndLevel - the other call doesn’t seem to, I guess that’s why you decided to always recalculate. It seems to me it wouldn’t complicate much to provide it when it’s available and recalculate when it’s not, something like:

 0diff --git a/src/txgraph.cpp b/src/txgraph.cpp
 1--- a/src/txgraph.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
 2+++ b/src/txgraph.cpp	(date 1760144001634)
 3@@ -722,7 +722,7 @@
 4     /** If cluster is not in staging, copy it there, and return a pointer to it.
 5     *   Staging must exist, and this modifies the locators of its
 6     *   transactions from inherited (P,M) to explicit (P,P). */
 7-    Cluster* PullIn(Cluster* cluster) noexcept;
 8+    Cluster* PullIn(Cluster* cluster, int level) noexcept;
 9     /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
10      *  NEEDS_SPLIT* QualityLevel) up to the specified level. */
11     void ApplyRemovals(int up_to_level) noexcept;
12@@ -1634,11 +1634,12 @@
13     return {nullptr, -1};
14 }
15 
16-Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
17+Cluster* TxGraphImpl::PullIn(Cluster* cluster, int cluster_level) noexcept
18 {
19     int to_level = GetTopLevel();
20     Assume(to_level == 1);
21     int level = cluster->GetLevel(*this);
22+    Assert(level == cluster_level); // TODO use parent call calculations instead
23     Assume(level <= to_level);
24     // Copy the Cluster from main to staging, if it's not already there.
25     if (level == 0) {
26@@ -1661,8 +1662,8 @@
27         // Pull in all Clusters that are not in staging.
28         if (level == 1) {
29             for (GraphIndex index : to_remove) {
30-                auto cluster = FindCluster(index, level);
31-                if (cluster != nullptr) PullIn(cluster);
32+                auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
33+                if (cluster != nullptr) PullIn(cluster, cluster_level);
34             }
35         }
36         // Group the set of to-be-removed entries by Cluster::m_sequence.
37@@ -2067,7 +2068,7 @@
38         // Pull in all the Clusters that contain dependencies.
39         if (level == 1) {
40             for (Cluster*& cluster : cluster_span) {
41-                cluster = PullIn(cluster);
42+                cluster = PullIn(cluster, cluster->GetLevel(*this));
43             }
44         }
45         // Invoke Merge() to merge them into a single Cluster.

Note that this would move the only remaing non-sanity-check call of GetLevel higher up.

sipa commented at 10:12 pm on October 11, 2025:

Done.

in src/txgraph.cpp:3442 in 7421e58dee outdated

3432@@ -2906,6 +3433,21 @@ std::vector<TxGraph::Ref*> TxGraphImpl::Trim() noexcept
3433     return ret;
3434 }
3435 
3436+size_t TxGraphImpl::GetMainMemoryUsage() noexcept
3437+{
3438+    // Make sure splits/merges are applied, as memory usage may not be representative otherwise.
3439+    SplitAll(/*up_to_level=*/0);
3440+    ApplyDependencies(/*level=*/0);
3441+    // Compute memory usage

l0rinc commented at 1:32 am on October 11, 2025:

This might have been mentioned before, but I couldn’t find the comment.

I noticed m_main_chunkindex_discarded isn’t included in the GetMainMemoryUsage calculation. Is my understanding correct that this was intentionally skipped because it’s not part of the stable state being measured or that it would pollute the measurements?

To check if it was simply empty at this point (like the other vectors mentioned by @glozow), I tried

0diff --git a/src/txgraph.cpp b/src/txgraph.cpp
1--- a/src/txgraph.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
2+++ b/src/txgraph.cpp	(date 1760146686230)
3@@ -3445,6 +3445,7 @@
4                    sizeof(Entry) * m_main_clusterset.m_txcount +
5                    /* From the chunk index. */
6                    memusage::DynamicUsage(m_main_chunkindex);
7+    assert(m_main_chunkindex_discarded.empty());
8     return usage;
9 }

but it fails fuzz testing with

Assertion failed: (m_main_chunkindex_discarded.empty()), function GetMainMemoryUsage, file txgraph.cpp, line 3449.

Maybe a brief comment explaining why this cache is not included would be helpful.

sipa commented at 10:13 pm on October 11, 2025:

Added a comment in the txgraph.h definition of the function.

in src/txgraph.cpp:899 in 7421e58dee

894+}
895+
896+
897+DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
898+{
899+    Assume(m_graph_index == GraphIndex(-1));

l0rinc commented at 2:03 am on October 11, 2025:

nit: for consistency:

0    Assume(!GetTxCount());

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:1341 in 7421e58dee

1335@@ -957,7 +1336,17 @@ uint64_t Cluster::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::
1336     return size;
1337 }
1338 
1339-bool Cluster::Split(TxGraphImpl& graph) noexcept
1340+uint64_t SingletonClusterImpl::AppendTrimData(std::vector<TrimTxData>& ret, std::vector<std::pair<GraphIndex, GraphIndex>>& deps) const noexcept
1341+{
1342+    if (m_graph_index  == GraphIndex(-1)) return 0;

l0rinc commented at 2:04 am on October 11, 2025:

nit: likely missed because of the extra space

0    if (!GetTxCount()) return 0;

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:1460 in 7421e58dee outdated

1464-        } else {
1465-            m_mapping[new_pos] = idx;
1466-        }
1467+        // Since this cluster must have been made hole-free before being merged into, all added
1468+        // transactions should appear at the end.
1469+        Assume(new_pos == m_mapping.size());

l0rinc commented at 2:12 am on October 11, 2025:

nit: I’d put the assume before the first usage of the validated value

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:1145 in 7421e58dee

1144+    ptr->m_feerate = m_feerate;
1145+    // Insert the new Cluster into the graph.
1146     graph.InsertCluster(1, std::move(ret), m_quality);
1147     // Update its Locators.
1148-    ptr->Updated(graph);
1149+    ptr->Updated(graph, 1);

l0rinc commented at 3:54 am on October 11, 2025:

nit: for consistency we could add the name hints here as well

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:905 in 7421e58dee

900+    m_graph_index = graph_idx;
901+    m_feerate = feerate;
902+    return 0;
903+}
904+
905+void GenericClusterImpl::AddDependencies(SetType parent, DepGraphIndex child) noexcept

l0rinc commented at 3:57 am on October 11, 2025:

nit:

0void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:380 in 7421e58dee outdated

372@@ -248,6 +373,8 @@ class Cluster
373 class TxGraphImpl final : public TxGraph
374 {
375     friend class Cluster;
376+    friend class SingletonClusterImpl;
377+    friend class GenericClusterImpl;
378     friend class BlockBuilderImpl;

l0rinc commented at 4:08 am on October 11, 2025:

nit: kinda’ unrelated but my linter is complaining here that Member 'm_known_end_of_cluster' is not initialized in this constructor.

sipa commented at 9:40 pm on October 11, 2025:

Indeed unrelated.

in src/txgraph.cpp:619 in 7421e58dee

614@@ -485,11 +615,13 @@ class TxGraphImpl final : public TxGraph
615     void SwapIndexes(GraphIndex a, GraphIndex b) noexcept;
616     /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
617     *   removed), return the Cluster it is in. Otherwise, return nullptr. */
618-    Cluster* FindCluster(GraphIndex idx, int level) const noexcept;
619-    /** Extract a Cluster from its ClusterSet. */
620+    Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }
621+    /** Like FindClusterAndLevel, but also return what level the match was found in (-1 if not found). */

l0rinc commented at 4:16 am on October 11, 2025:

0    /** Like FindCluster, but also return what level the match was found in (-1 if not found). */

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:2929 in 7421e58dee outdated

2923+                    assert(cluster.GetTxCount() >= cluster.GetMinIntendedTxCount());
2924+                }
2925+
2926                 // Check the sequence number.
2927                 assert(cluster.m_sequence < m_next_sequence_counter);
2928                 assert(sequences.count(cluster.m_sequence) == 0);

l0rinc commented at 2:09 pm on October 11, 2025:

nit: in a follow-up we could make this: assert(!sequences.contains(cluster.m_sequence));

in src/txgraph.cpp:112 in 7421e58dee outdated

119     ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
120-    /** Which level this Cluster is at in the graph (-1=not inserted, 0=main, 1=staging). */
121-    int m_level{-1};
122     /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
123         transactions in distinct clusters). */
124     uint64_t m_sequence;

l0rinc commented at 2:11 pm on October 11, 2025:

nit: it seems to me this can now be private

sipa commented at 9:45 pm on October 11, 2025:

Without m_quality and m_setindex private, I think this would be confusing. They feel like they belong together.

in src/txgraph.cpp:1618 in 7421e58dee outdated

1613 {
1614     // Extract the cluster from where it currently resides.
1615-    auto cluster_ptr = ExtractCluster(cluster.m_level, cluster.m_quality, cluster.m_setindex);
1616+    auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
1617     // And throw it away.
1618     cluster_ptr.reset();

l0rinc commented at 2:16 pm on October 11, 2025:

Is the explicit reset meant for clarity here instead of

0void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
1{
2    // Extract the cluster from where it currently resides and throw it away.
3    ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
4}

sipa commented at 9:37 pm on October 11, 2025:

Yes.

in src/txgraph.cpp:1247 in 7421e58dee outdated

1245 }
1246 
1247-void Cluster::MoveToMain(TxGraphImpl& graph) noexcept
1248+void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
1249+{
1250+    Assume(GetTxCount());

l0rinc commented at 2:24 pm on October 11, 2025:

The doc states /** Remove all transactions from a (non-empty) Cluster. */ but we’re only asserting that here - I know it might not matter much, but for symmetry consider adding the assuption to GenericClusterImpl::Clear as well

sipa commented at 10:13 pm on October 11, 2025:

Done.

in src/txgraph.cpp:1261 in 7421e58dee outdated

1260         GraphIndex idx = m_mapping[i];
1261         auto& entry = graph.m_entries[idx];
1262         entry.m_locator[1].SetMissing();
1263     }
1264     auto quality = m_quality;
1265+    // Subtract memory usage from staging and add it to main.

l0rinc commented at 2:26 pm on October 11, 2025:

I find this a lot more intuitive, thanks

in src/test/fuzz/cluster_linearize.cpp:498 in 7421e58dee outdated

541+                // intermediary transactions may be deleted which impact connectivity).
542+                anc_update_fn();
543+                // Compare the state of the transactions being deleted.
544+                for (auto i : del) check_fn(i);
545+                // Apply to DepGraph.
546+                real.RemoveTransactions(del);

l0rinc commented at 2:33 pm on October 11, 2025:

slightly unrelated nit: it seems to me that RemoveTransactions iterates over unused positions as well.

0assert(entries.size() > m_used.Count()); // TODO fails fuzzing, indicating that entries can have holes
1for (auto& entry : entries) {

In a follow-up maybe we could check how many sparse graphs we have and whether iterating over the valid positions only would perform better.

0assert(entries.size() >= m_used.Count()); // TODO m_used is never worse
1for (auto idx : m_used) {
2    entries[idx].ancestors &= m_used;
3    entries[idx].descendants &= m_used;
4}

sipa commented at 9:51 pm on October 11, 2025:

Unrelated, indeed.

Also, I wouldn’t be surprised if the cost of a CTZ to find the next set bit, and the less predictable access pattern, is greater than the cost of performing two ANDs on unused positions. In either case, I don’t think this matters.

in src/txgraph.cpp:662 in 7421e58dee outdated

655+    }
656+    /** Create an empty Cluster of the appropriate implementation for the specified (maximum) tx
657+     *  count. */
658+    std::unique_ptr<Cluster> CreateEmptyCluster(DepGraphIndex tx_count) noexcept
659+    {
660+        if (tx_count >= SingletonClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= SingletonClusterImpl::MAX_TX_COUNT) {

l0rinc commented at 3:02 pm on October 11, 2025:

nit: this feels a bit like a lack of abstraction, especially since now we have multiple ways of getting the min and max. If a few places we can use the getter methods, but here maybe we could add a higher-level abstraction to the impls, maybe something like

0static bool IsIntendedFor(DepGraphIndex tx_count) noexcept {
1    return MIN_INTENDED_TX_COUNT <= tx_count && tx_count <= MAX_TX_COUNT
2}

or maybe even

0static bool IsIntendedFor(DepGraphIndex tx_count) noexcept {
1    return std::clamp(tx_count, MIN_INTENDED_TX_COUNT, MAX_TX_COUNT) == tx_count;
2}

so that here we’re not leaking internals:

0std::unique_ptr<Cluster> TxGraphImpl::CreateEmptyCluster(DepGraphIndex tx_count) noexcept
1{
2    if (SingletonClusterImpl::IsIntendedFor(tx_count)) return CreateEmptySingletonCluster();
3    Assert(GenericClusterImpl::IsIntendedFor(tx_count));
4    return CreateEmptyGenericCluster();
5}

ni2: the format min <= value && value <= max may be more intuitive to signal a strict ordering relation

sipa commented at 9:56 pm on October 11, 2025:

I think of the MIN_INTENDED_TX_COUNT and MAX_TX_COUNT as the best emulation of having static versions of MinIntendedTxCount() and MaxTxCount() (because in C++, class methods cannot be virtual, so they can’t be made part of the Cluster formal interface). So we’re stuck with two versions: a polymorphic instance member function, and a non-polymorphic class member variable.

l0rinc commented at 6:03 pm on October 11, 2025: contributor

Thank you for considering the suggestions, I find the new layout a lot easier to follow.

I have left a few more nits, but I’m fine doing them in a follow-up. I like these memory optimizations, my only concern is that we’re likely doing a lot heavier copying because of the regular compactions (especially since most move constructors seem unused based on previous fuzzing reports). As mentioned, in a follow-up we can experiment with leaving a tiny buffer.

I have also added a few redundant assertions locally and ran a fuzzer for FUZZ=clusterlin_depgraph_sim and FUZZ=txgraph overnight (without sanitizers which I can’t get to work on a Mac anyway) and they both passed 👍

  0diff --git a/src/txgraph.cpp b/src/txgraph.cpp
  1--- a/src/txgraph.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
  2+++ b/src/txgraph.cpp	(date 1760202864002)
  3@@ -99,6 +99,9 @@
  4 class Cluster
  5 {
  6     friend class TxGraphImpl;
  7+    /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
  8+        transactions in distinct clusters). */
  9+    uint64_t m_sequence;
 10 
 11 protected:
 12     using GraphIndex = TxGraph::GraphIndex;
 13@@ -107,9 +110,6 @@
 14     QualityLevel m_quality{QualityLevel::NONE};
 15     /** Which position this Cluster has in TxGraphImpl::ClusterSet::m_clusters[m_quality]. */
 16     ClusterSetIndex m_setindex{ClusterSetIndex(-1)};
 17-    /** Sequence number for this Cluster (for tie-breaking comparison between equal-chunk-feerate
 18-        transactions in distinct clusters). */
 19-    uint64_t m_sequence;
 20 
 21     explicit Cluster(uint64_t sequence) noexcept : m_sequence(sequence) {}
 22 
 23@@ -616,7 +616,7 @@
 24     /** If idx exists in the specified level ClusterSet (explicitly, or in the level below and not
 25     *   removed), return the Cluster it is in. Otherwise, return nullptr. */
 26     Cluster* FindCluster(GraphIndex idx, int level) const noexcept { return FindClusterAndLevel(idx, level).first; }
 27-    /** Like FindClusterAndLevel, but also return what level the match was found in (-1 if not found). */
 28+    /** Like FindCluster, but also return what level the match was found in (-1 if not found). */
 29     std::pair<Cluster*, int> FindClusterAndLevel(GraphIndex idx, int level) const noexcept;
 30     /** Extract a Cluster from its ClusterSet, and set its quality to QualityLevel::NONE. */
 31     std::unique_ptr<Cluster> ExtractCluster(int level, QualityLevel quality, ClusterSetIndex setindex) noexcept;
 32@@ -663,8 +663,7 @@
 33         if (tx_count >= GenericClusterImpl::MIN_INTENDED_TX_COUNT && tx_count <= GenericClusterImpl::MAX_TX_COUNT) {
 34             return CreateEmptyGenericCluster();
 35         }
 36-        assert(false);
 37-        return {};
 38+        std::abort();
 39     }
 40 
 41     // Functions for handling Refs.
 42@@ -722,7 +721,7 @@
 43     /** If cluster is not in staging, copy it there, and return a pointer to it.
 44     *   Staging must exist, and this modifies the locators of its
 45     *   transactions from inherited (P,M) to explicit (P,P). */
 46-    Cluster* PullIn(Cluster* cluster) noexcept;
 47+    Cluster* PullIn(Cluster* cluster, int level) noexcept;
 48     /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
 49      *  NEEDS_SPLIT* QualityLevel) up to the specified level. */
 50     void ApplyRemovals(int up_to_level) noexcept;
 51@@ -896,22 +895,22 @@
 52 
 53 DepGraphIndex SingletonClusterImpl::AppendTransaction(GraphIndex graph_idx, FeePerWeight feerate) noexcept
 54 {
 55-    Assume(m_graph_index == GraphIndex(-1));
 56+    Assume(!GetTxCount());
 57     m_graph_index = graph_idx;
 58     m_feerate = feerate;
 59     return 0;
 60 }
 61 
 62-void GenericClusterImpl::AddDependencies(SetType parent, DepGraphIndex child) noexcept
 63+void GenericClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
 64 {
 65-    m_depgraph.AddDependencies(parent, child);
 66+    m_depgraph.AddDependencies(parents, child);
 67 }
 68 
 69-void SingletonClusterImpl::AddDependencies(SetType parent, DepGraphIndex child) noexcept
 70+void SingletonClusterImpl::AddDependencies(SetType parents, DepGraphIndex child) noexcept
 71 {
 72     // Singletons cannot have any dependencies.
 73     Assume(child == 0);
 74-    Assume(parent == SetType{} || parent == SetType::Fill(0));
 75+    Assume(parents == SetType{} || parents == SetType::Fill(0));
 76 }
 77 
 78 void GenericClusterImpl::ExtractTransactions(const std::function<void (DepGraphIndex, GraphIndex, FeePerWeight, SetType)>& visit_fn) noexcept
 79@@ -946,8 +945,7 @@
 80     }
 81     // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
 82     // point back to it.
 83-    assert(false);
 84-    return -1;
 85+    std::abort();
 86 }
 87 
 88 int SingletonClusterImpl::GetLevel(const TxGraphImpl& graph) const noexcept
 89@@ -963,8 +961,7 @@
 90     }
 91     // Given that we started with an Entry that occurs in this Cluster, one of its Locators must
 92     // point back to it.
 93-    assert(false);
 94-    return -1;
 95+    std::abort();
 96 }
 97 
 98 void TxGraphImpl::ClearLocator(int level, GraphIndex idx, bool oversized_tx) noexcept
 99@@ -981,6 +978,7 @@
100     }
101     // Update the transaction count.
102     --clusterset.m_txcount;
103+    Assert(clusterset.m_txcount_oversized >= oversized_tx);
104     clusterset.m_txcount_oversized -= oversized_tx;
105     // If clearing main, adjust the status of Locators of this transaction in staging, if it exists.
106     if (level == 0 && GetTopLevel() == 1) {
107@@ -988,6 +986,7 @@
108             entry.m_locator[1].SetMissing();
109         } else if (!entry.m_locator[1].IsPresent()) {
110             --m_staging_clusterset->m_txcount;
111+            Assert(m_staging_clusterset->m_txcount_oversized >= oversized_tx);
112             m_staging_clusterset->m_txcount_oversized -= oversized_tx;
113         }
114     }
115@@ -1091,7 +1090,7 @@
116 std::vector<Cluster*> TxGraphImpl::GetConflicts() const noexcept
117 {
118     Assume(GetTopLevel() == 1);
119-    auto& clusterset = GetClusterSet(1);
120+    auto& clusterset = GetClusterSet(/*level=*/1);
121     std::vector<Cluster*> ret;
122     // All main Clusters containing transactions in m_removed (so (P,R) ones) are conflicts.
123     for (auto i : clusterset.m_removed) {
124@@ -1140,11 +1139,11 @@
125     ptr->m_graph_index = m_graph_index;
126     ptr->m_feerate = m_feerate;
127     // Insert the new Cluster into the graph.
128-    graph.InsertCluster(1, std::move(ret), m_quality);
129+    graph.InsertCluster(/*level=*/1, std::move(ret), m_quality);
130     // Update its Locators.
131-    ptr->Updated(graph, 1);
132+    ptr->Updated(graph, /*level=*/1);
133     // Update memory usage.
134-    graph.GetClusterSet(1).m_cluster_usage += ptr->TotalMemoryUsage();
135+    graph.GetClusterSet(/*level=*/1).m_cluster_usage += ptr->TotalMemoryUsage();
136     return ptr;
137 }
138 
139@@ -1153,6 +1152,7 @@
140     // Iterate over the prefix of to_remove that applies to this cluster.
141     Assume(!to_remove.empty());
142     SetType todo;
143+    Assert(graph.GetClusterSet(level).m_cluster_usage >= TotalMemoryUsage());
144     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
145     do {
146         GraphIndex idx = to_remove.front();
147@@ -1231,6 +1231,8 @@
148 
149 void GenericClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
150 {
151+    Assume(GetTxCount());
152+    Assert(graph.GetClusterSet(level).m_cluster_usage >= TotalMemoryUsage());
153     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
154     for (auto i : m_linearization) {
155         graph.ClearLocator(level, m_mapping[i], m_quality == QualityLevel::OVERSIZED_SINGLETON);
156@@ -1243,6 +1245,7 @@
157 void SingletonClusterImpl::Clear(TxGraphImpl& graph, int level) noexcept
158 {
159     Assume(GetTxCount());
160+    Assert(graph.GetClusterSet(level).m_cluster_usage >= TotalMemoryUsage());
161     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
162     graph.ClearLocator(level, m_graph_index, m_quality == QualityLevel::OVERSIZED_SINGLETON);
163     m_graph_index = GraphIndex(-1);
164@@ -1257,10 +1260,11 @@
165     }
166     auto quality = m_quality;
167     // Subtract memory usage from staging and add it to main.
168+    Assert(graph.GetClusterSet(/*level=*/1).m_cluster_usage >= TotalMemoryUsage());
169     graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
170     graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
171     // Remove cluster itself from staging and add it to main.
172-    auto cluster = graph.ExtractCluster(1, quality, m_setindex);
173+    auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
174     graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
175     Updated(graph, /*level=*/0);
176 }
177@@ -1272,10 +1276,11 @@
178         entry.m_locator[1].SetMissing();
179     }
180     auto quality = m_quality;
181-    graph.GetClusterSet(1).m_cluster_usage -= TotalMemoryUsage();
182-    auto cluster = graph.ExtractCluster(1, quality, m_setindex);
183-    graph.InsertCluster(0, std::move(cluster), quality);
184-    graph.GetClusterSet(0).m_cluster_usage += TotalMemoryUsage();
185+    Assert(graph.GetClusterSet(/*level=*/1).m_cluster_usage >= TotalMemoryUsage());
186+    graph.GetClusterSet(/*level=*/1).m_cluster_usage -= TotalMemoryUsage();
187+    auto cluster = graph.ExtractCluster(/*level=*/1, quality, m_setindex);
188+    graph.InsertCluster(/*level=*/0, std::move(cluster), quality);
189+    graph.GetClusterSet(/*level=*/0).m_cluster_usage += TotalMemoryUsage();
190     Updated(graph, 0);
191 }
192 
193@@ -1374,7 +1379,7 @@
194         auto component = m_depgraph.FindConnectedComponent(todo);
195         auto component_size = component.Count();
196         auto split_quality = component_size <= 2 ? QualityLevel::OPTIMAL : new_quality;
197-        if (first && component == todo && SetType::Fill(component_size) == component && component_size >= MIN_INTENDED_TX_COUNT) {
198+        if (first && component == todo && SetType::Fill(component_size) == component && component_size >= GetMinIntendedTxCount()) {
199             // The existing Cluster is an entire component, without holes. Leave it be, but update
200             // its quality. If there are holes, we continue, so that the Cluster is reconstructed
201             // without holes, reducing memory usage. If the component's size is below the intended
202@@ -1400,6 +1405,7 @@
203         todo -= component;
204     }
205     // We have to split the Cluster up. Remove accounting for the existing one first.
206+    Assert(graph.GetClusterSet(level).m_cluster_usage >= TotalMemoryUsage());
207     graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
208     // Redistribute the transactions.
209     for (auto i : m_linearization) {
210@@ -1435,6 +1441,7 @@
211     Assume(NeedsSplitting());
212     if (GetTxCount() == 0) {
213         // The cluster is now empty.
214+        Assert(graph.GetClusterSet(level).m_cluster_usage >= TotalMemoryUsage());
215         graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
216         return true;
217     } else {
218@@ -1453,10 +1460,10 @@
219     other.ExtractTransactions([&](DepGraphIndex pos, GraphIndex idx, FeePerWeight feerate, SetType other_parents) noexcept {
220         // Copy the transaction into this Cluster, and remember its position.
221         auto new_pos = m_depgraph.AddTransaction(feerate);
222-        remap[pos] = new_pos;
223         // Since this cluster must have been made hole-free before being merged into, all added
224         // transactions should appear at the end.
225         Assume(new_pos == m_mapping.size());
226+        remap[pos] = new_pos;
227         m_mapping.push_back(idx);
228         m_linearization.push_back(new_pos);
229         // Copy the transaction's dependencies, translating them using remap. Note that since
230@@ -1610,10 +1617,8 @@
231 
232 void TxGraphImpl::DeleteCluster(Cluster& cluster, int level) noexcept
233 {
234-    // Extract the cluster from where it currently resides.
235-    auto cluster_ptr = ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
236-    // And throw it away.
237-    cluster_ptr.reset();
238+    // Extract the cluster from where it currently resides and throw it away.
239+    ExtractCluster(level, cluster.m_quality, cluster.m_setindex);
240 }
241 
242 std::pair<Cluster*, int> TxGraphImpl::FindClusterAndLevel(GraphIndex idx, int level) const noexcept
243@@ -1634,11 +1639,12 @@
244     return {nullptr, -1};
245 }
246 
247-Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
248+Cluster* TxGraphImpl::PullIn(Cluster* cluster, int cluster_level) noexcept
249 {
250     int to_level = GetTopLevel();
251     Assume(to_level == 1);
252     int level = cluster->GetLevel(*this);
253+    Assert(level == cluster_level); // TODO use parent call calculations instead
254     Assume(level <= to_level);
255     // Copy the Cluster from main to staging, if it's not already there.
256     if (level == 0) {
257@@ -1661,8 +1667,8 @@
258         // Pull in all Clusters that are not in staging.
259         if (level == 1) {
260             for (GraphIndex index : to_remove) {
261-                auto cluster = FindCluster(index, level);
262-                if (cluster != nullptr) PullIn(cluster);
263+                auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
264+                if (cluster != nullptr) PullIn(cluster, cluster_level);
265             }
266         }
267         // Group the set of to-be-removed entries by Cluster::m_sequence.
268@@ -2012,9 +2018,11 @@
269     // moves.
270     size_t max_size_pos{0};
271     DepGraphIndex max_size = to_merge[max_size_pos]->GetTxCount();
272+    Assert(GetClusterSet(level).m_cluster_usage >= to_merge[max_size_pos]->TotalMemoryUsage());
273     GetClusterSet(level).m_cluster_usage -= to_merge[max_size_pos]->TotalMemoryUsage();
274     DepGraphIndex total_size = max_size;
275     for (size_t i = 1; i < to_merge.size(); ++i) {
276+        Assert(GetClusterSet(level).m_cluster_usage >= to_merge[i]->TotalMemoryUsage());
277         GetClusterSet(level).m_cluster_usage -= to_merge[i]->TotalMemoryUsage();
278         DepGraphIndex size = to_merge[i]->GetTxCount();
279         total_size += size;
280@@ -2067,7 +2075,7 @@
281         // Pull in all the Clusters that contain dependencies.
282         if (level == 1) {
283             for (Cluster*& cluster : cluster_span) {
284-                cluster = PullIn(cluster);
285+                cluster = PullIn(cluster, cluster->GetLevel(*this));
286             }
287         }
288         // Invoke Merge() to merge them into a single Cluster.
289@@ -2925,7 +2933,7 @@
290 
291                 // Check the sequence number.
292                 assert(cluster.m_sequence < m_next_sequence_counter);
293-                assert(sequences.count(cluster.m_sequence) == 0);
294+                assert(!sequences.contains(cluster.m_sequence));
295                 sequences.insert(cluster.m_sequence);
296                 // Remember we saw this Cluster (only if it is non-empty; empty Clusters aren't
297                 // expected to be referenced by the Entry vector).
298diff --git a/src/test/fuzz/txgraph.cpp b/src/test/fuzz/txgraph.cpp
299--- a/src/test/fuzz/txgraph.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
300+++ b/src/test/fuzz/txgraph.cpp	(date 1760204180327)
301@@ -462,6 +462,7 @@
302                 auto ref_loc = top_sim.AddTransaction(feerate);
303                 // Move it in place.
304                 *ref_loc = std::move(ref);
305+                real->SanityCheck();
306                 break;
307             } else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 && command-- == 0) {
308                 // AddDependency.
309@@ -477,6 +478,7 @@
310                 top_sim.AddDependency(par, chl);
311                 top_sim.real_is_optimal = false;
312                 real->AddDependency(*par, *chl);
313+                real->SanityCheck();
314                 break;
315             } else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 && command-- == 0) {
316                 // RemoveTransaction. Either all its ancestors or all its descendants are also
317@@ -492,6 +494,7 @@
318                     real->RemoveTransaction(*ptr);
319                     top_sim.RemoveTransaction(ptr);
320                 }
321+                real->SanityCheck();
322                 break;
323             } else if (sel_sim.removed.size() > 0 && command-- == 0) {
324                 // ~Ref (of an already-removed transaction). Destroying a TxGraph::Ref has an
325@@ -507,6 +510,7 @@
326                     std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
327                 }
328                 sel_sim.removed.pop_back();
329+                real->SanityCheck();
330                 break;
331             } else if (block_builders.empty() && command-- == 0) {
332                 // ~Ref (of any transaction).
333@@ -529,6 +533,7 @@
334                         sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
335                     }
336                 }
337+                real->SanityCheck();
338                 break;
339             } else if (block_builders.empty() && command-- == 0) {
340                 // SetTransactionFee.
341@@ -543,10 +548,12 @@
342                 for (auto& sim : sims) {
343                     sim.SetTransactionFee(ref, fee);
344                 }
345+                real->SanityCheck();
346                 break;
347             } else if (command-- == 0) {
348                 // GetTransactionCount.
349                 assert(real->GetTransactionCount(level_select) == sel_sim.GetTransactionCount());
350+                real->SanityCheck();
351                 break;
352             } else if (command-- == 0) {
353                 // Exists.
354@@ -554,10 +561,12 @@
355                 bool exists = real->Exists(*ref, level_select);
356                 bool should_exist = sel_sim.Find(ref) != SimTxGraph::MISSING;
357                 assert(exists == should_exist);
358+                real->SanityCheck();
359                 break;
360             } else if (command-- == 0) {
361                 // IsOversized.
362                 assert(sel_sim.IsOversized() == real->IsOversized(level_select));
363+                real->SanityCheck();
364                 break;
365             } else if (command-- == 0) {
366                 // GetIndividualFeerate.
367@@ -572,6 +581,7 @@
368                     }
369                 }
370                 if (!found) assert(feerate.IsEmpty());
371+                real->SanityCheck();
372                 break;
373             } else if (!main_sim.IsOversized() && command-- == 0) {
374                 // GetMainChunkFeerate.
375@@ -586,6 +596,7 @@
376                     assert(feerate.size >= main_sim.graph.FeeRate(simpos).size);
377                     assert(feerate.size <= main_sim.SumAll().size);
378                 }
379+                real->SanityCheck();
380                 break;
381             } else if (!sel_sim.IsOversized() && command-- == 0) {
382                 // GetAncestors/GetDescendants.
383@@ -597,6 +608,7 @@
384                 assert(result.size() == result_set.Count());
385                 auto expect_set = sel_sim.GetAncDesc(ref, alt);
386                 assert(result_set == expect_set);
387+                real->SanityCheck();
388                 break;
389             } else if (!sel_sim.IsOversized() && command-- == 0) {
390                 // GetAncestorsUnion/GetDescendantsUnion.
391@@ -619,6 +631,7 @@
392                 for (TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
393                 // Compare.
394                 assert(result_set == expect_set);
395+                real->SanityCheck();
396                 break;
397             } else if (!sel_sim.IsOversized() && command-- == 0) {
398                 // GetCluster.
399@@ -654,16 +667,19 @@
400                     assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
401                     assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
402                 }
403+                real->SanityCheck();
404                 break;
405             } else if (command-- == 0) {
406                 // HaveStaging.
407                 assert((sims.size() == 2) == real->HaveStaging());
408+                real->SanityCheck();
409                 break;
410             } else if (sims.size() < 2 && command-- == 0) {
411                 // StartStaging.
412                 sims.emplace_back(sims.back());
413                 sims.back().modified = SimTxGraph::SetType{};
414                 real->StartStaging();
415+                real->SanityCheck();
416                 break;
417             } else if (block_builders.empty() && sims.size() > 1 && command-- == 0) {
418                 // CommitStaging.
419@@ -672,6 +688,7 @@
420                 const bool main_optimal = std::all_of(sims.cbegin(), sims.cend(), [](const auto &sim) { return sim.real_is_optimal; });
421                 sims.erase(sims.begin());
422                 sims.front().real_is_optimal = main_optimal;
423+                real->SanityCheck();
424                 break;
425             } else if (sims.size() > 1 && command-- == 0) {
426                 // AbortStaging.
427@@ -681,6 +698,7 @@
428                 // removals of main transactions while staging was active, then aborting will
429                 // cause it to be re-evaluated in TxGraph).
430                 sims.back().oversized = std::nullopt;
431+                real->SanityCheck();
432                 break;
433             } else if (!main_sim.IsOversized() && command-- == 0) {
434                 // CompareMainOrder.
435@@ -699,6 +717,7 @@
436                 // Do not verify consistency with chunk feerates, as we cannot easily determine
437                 // these here without making more calls to real, which could affect its internal
438                 // state. A full comparison is done at the end.
439+                real->SanityCheck();
440                 break;
441             } else if (!sel_sim.IsOversized() && command-- == 0) {
442                 // CountDistinctClusters.
443@@ -730,6 +749,7 @@
444                 // Compare the number of deduplicated representatives with the value returned by
445                 // the real function.
446                 assert(result == sim_reps.Count());
447+                real->SanityCheck();
448                 break;
449             } else if (command-- == 0) {
450                 // DoWork.
451@@ -767,6 +787,7 @@
452                     // allowed to touch.
453                     assert(iters <= iters_for_optimal);
454                 }
455+                real->SanityCheck();
456                 break;
457             } else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() && command-- == 0) {
458                 // GetMainStagingDiagrams()
459@@ -786,14 +807,17 @@
460                 for (size_t i = 1; i < real_staged_diagram.size(); ++i) {
461                     assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
462                 }
463+                real->SanityCheck();
464                 break;
465             } else if (block_builders.size() < 4 && !main_sim.IsOversized() && command-- == 0) {
466                 // GetBlockBuilder.
467                 block_builders.emplace_back(real->GetBlockBuilder());
468+                real->SanityCheck();
469                 break;
470             } else if (!block_builders.empty() && command-- == 0) {
471                 // ~BlockBuilder.
472                 block_builders.erase(block_builders.begin() + builder_idx);
473+                real->SanityCheck();
474                 break;
475             } else if (!block_builders.empty() && command-- == 0) {
476                 // BlockBuilder::GetCurrentChunk, followed by Include/Skip.
477@@ -845,6 +869,7 @@
478                     builder_data.included = new_included;
479                 }
480                 builder_data.done = new_done;
481+                real->SanityCheck();
482                 break;
483             } else if (!main_sim.IsOversized() && command-- == 0) {
484                 // GetWorstMainChunk.
485@@ -871,6 +896,7 @@
486                     }
487                     assert(sum == worst_chunk_feerate);
488                 }
489+                real->SanityCheck();
490                 break;
491             } else if ((block_builders.empty() || sims.size() > 1) && command-- == 0) {
492                 // Trim.
493@@ -895,6 +921,7 @@
494                     top_sim.RemoveTransaction(top_sim.GetRef(simpos));
495                 }
496                 assert(!top_sim.IsOversized());
497+                real->SanityCheck();
498                 break;
499             } else if ((block_builders.empty() || sims.size() > 1) &&
500                        top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() && command-- == 0) {
501@@ -932,6 +959,7 @@
502                         for (auto j : clusters[par_cl]) {
503                             if (par_idx == 0) {
504                                 par_pos = j;
505+                                real->SanityCheck();
506                                 break;
507                             }
508                             --par_idx;
509@@ -942,6 +970,7 @@
510                         for (auto j : clusters[chl_cl]) {
511                             if (chl_idx == 0) {
512                                 chl_pos = j;
513+                                real->SanityCheck();
514                                 break;
515                             }
516                             --chl_idx;
517@@ -1011,6 +1040,7 @@
518                     top_sim.RemoveTransaction(top_sim.GetRef(simpos));
519                 }
520                 assert(!top_sim.IsOversized());
521+                real->SanityCheck();
522                 break;
523             } else if (command-- == 0) {
524                 // GetMainMemoryUsage().
525@@ -1026,6 +1056,7 @@
526                 } else {
527                     assert(usage > 0);
528                 }
529+                real->SanityCheck();
530                 break;
531             }
532         }
533diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
534--- a/src/test/fuzz/cluster_linearize.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
535+++ b/src/test/fuzz/cluster_linearize.cpp	(date 1760155666348)
536@@ -453,7 +453,6 @@
537     };
538 
539     auto last_compaction_pos{real.PositionRange()};
540-
541     LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) {
542         int command = provider.ConsumeIntegral<uint8_t>() % 4;
543         while (true) {
544@@ -476,6 +475,7 @@
545                 // Update sim.
546                 sim[idx] = {feerate, TestBitSet::Singleton(idx)};
547                 ++num_tx_sim;
548+                SanityCheck(real);
549                 break;
550             } else if (num_tx_sim > 0 && command-- == 0) {
551                 // AddDependencies.
552@@ -485,6 +485,7 @@
553                 real.AddDependencies(parents, child);
554                 // Apply to sim.
555                 sim[child]->second |= parents;
556+                SanityCheck(real);
557                 break;
558             } else if (num_tx_sim > 0 && command-- == 0) {
559                 // Remove transactions.
560@@ -507,6 +508,7 @@
561                         }
562                     }
563                 }
564+                SanityCheck(real);
565                 break;
566             } else if (command-- == 0) {
567                 // Compact.
568@@ -515,6 +517,7 @@
569                 const size_t mem_after{real.DynamicMemoryUsage()};
570                 assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
571                 last_compaction_pos = real.PositionRange();
572+                SanityCheck(real);
573                 break;
574             }
575         }
576diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
577--- a/src/cluster_linearize.h	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
578+++ b/src/cluster_linearize.h	(date 1760204167676)
579@@ -165,9 +165,10 @@
580         // Remove the deleted transactions from ancestors/descendants of other transactions. Note
581         // that the deleted positions will retain old feerate and dependency information. This does
582         // not matter as they will be overwritten by AddTransaction if they get used again.
583-        for (auto& entry : entries) {
584-            entry.ancestors &= m_used;
585-            entry.descendants &= m_used;
586+        assert(entries.size() >= m_used.Count()); // TODO delete
587+        for (auto idx : m_used) {
588+            entries[idx].ancestors &= m_used;
589+            entries[idx].descendants &= m_used;
590         }
591     }

code review ACK 7421e58dee402ee8b5b58a18684953a89ad350d7

l0rinc approved

txgraph: Make level of Cluster implicit (optimization)

This reduces per-Cluster memory usage by making Clusters not aware of their
own level. Instead, track it either in calling code, or infer it based on
the transactions in them.

d40302fbaf

txgraph: move some sanity checks from Cluster to TxGraphImpl (refactor) 2b1d302508

txgraph: avoid holes in DepGraph positions (mem optimization) b1637a90de

depgraph: add memory usage control (feature)

Co-Authored-By: Lőrinc <pap.lorinc@gmail.com>

bb5cb222ae

txgraph: keep data structures compact (mem optimization) 4ba562e5f4

txgraph: keep track of Cluster memory usage (preparation) 7680bb8fd4

txgraph: expose memory usage estimate function (feature) 04c808ac4c

txgraph: avoid accessing other Cluster internals (refactor)

This adds 4 functions to Cluster to help implement Merge() and Split() without
needing access to the internals of the other Cluster. This is a preparation for
a follow-up that will make Clusters a virtual class whose internals are abstracted
away.

2602d89edd

txgraph: make Cluster an abstract class (refactor) 726b995739

txgraph: comment fixes (doc fix) 6baf12621f

txgraph: abstract out creation of empty Clusters (refactor) e93b0f09cc

txgraph: give Clusters a range of intended tx counts (preparation) e346250732

txgraph: add SingletonClusterImpl (mem optimization)

This adds a specialized Cluster implementation for singleton clusters, saving
a significant amount of memory by avoiding the need for m_depgraph, m_mapping,
and m_linearization, and their overheads.

023cd5a546

sipa force-pushed on Oct 11, 2025

sipa commented at 10:14 pm on October 11, 2025: member

Not going to address any further nits, unless I need to repush for other reasons.

l0rinc commented at 2:27 am on October 12, 2025: contributor

code review reACK 023cd5a5469ad61205bf7bb1135895f2b4a20ea9

Thanks for the quick responses. Build failures seem systemic and unrelated.

DrahtBot requested review from instagibbs on Oct 12, 2025

instagibbs commented at 12:29 pm on October 13, 2025: member

reACK 023cd5a5469ad61205bf7bb1135895f2b4a20ea9

git range-diff master 7421e58dee402ee8b5b58a18684953a89ad350d7 023cd5a5469ad61205bf7bb1135895f2b4a20ea9

fanquake commented at 12:57 pm on October 13, 2025: member

Kicked all the unrelated failures.

ismaelsadeeq commented at 12:40 pm on October 14, 2025: member

reACK 023cd5a5469ad61205bf7bb1135895f2b4a20ea9 🚢

ad350d7..023cd5a

Several nits from recent comments were addressed, clarifying comments were added for clarity.

in src/test/fuzz/txgraph.cpp:1016 in 023cd5a546

1011@@ -1012,6 +1012,21 @@ FUZZ_TARGET(txgraph)
1012                 }
1013                 assert(!top_sim.IsOversized());
1014                 break;
1015+            } else if (command-- == 0) {
1016+                // GetMainMemoryUsage().

glozow commented at 3:06 pm on October 14, 2025:

Fwiw, I think parts of the original comment could have been kept, it’s helpful to know e.g. that it’s “implementation-specific, and can go up (even when transactions are removed) and down (even when dependencies are added), as clusters can split and merge.”

glozow commented at 3:56 pm on October 14, 2025: member

reACK 023cd5a5469ad61205bf7bb1135895f2b4a20ea9

Thanks for taking the suggestions!

glozow merged this on Oct 14, 2025

glozow closed this on Oct 14, 2025

TheCharlatan referenced this in commit f50d90fcbb on Oct 29, 2025

l0rinc referenced this in commit 2d23820ee1 on Nov 3, 2025

cluster mempool: control/optimize TxGraph memory usage #33157

Code Coverage & Benchmarks

Reviews

Conflicts

LLM Linter (✨ experimental)