cluster mempool: control/optimize TxGraph memory usage #33157

pull sipa wants to merge 13 commits into bitcoin:master from sipa:202508_txgraph_memusage changing 5 files +838 −254
  1. 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.

  2. 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 instagibbs
    Concept ACK l0rinc
    Stale ACK 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)
    • #33335 (txgraph: randomize order of same-feerate distinct-cluster transactions by sipa)
    • #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.

  3. sipa force-pushed on Aug 8, 2025
  4. DrahtBot added the label CI failed on Aug 8, 2025
  5. 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.

  6. DrahtBot removed the label CI failed on Aug 8, 2025
  7. 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.
  8. 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!
  9. 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.
  10. 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.
  11. 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.
  12. 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”.
  13. 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.
  14. instagibbs commented at 8:20 pm on September 4, 2025: member
    concept ACK, I refuse to do math
  15. sipa force-pushed on Sep 5, 2025
  16. sipa force-pushed on Sep 5, 2025
  17. 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
  18. sipa force-pushed on Sep 5, 2025
  19. 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,
    
  20. sipa force-pushed on Sep 7, 2025
  21. sipa force-pushed on Sep 8, 2025
  22. sipa force-pushed on Sep 9, 2025
  23. DrahtBot added the label Needs rebase on Sep 11, 2025
  24. sipa force-pushed on Sep 11, 2025
  25. sipa commented at 5:07 pm on September 11, 2025: member
    Rebased after #33354 merge.
  26. DrahtBot removed the label Needs rebase on Sep 11, 2025
  27. 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.
  28. 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.
  29. 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?
  30. sipa force-pushed on Sep 17, 2025
  31. 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.
  32. 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%.

  33. DrahtBot requested review from instagibbs on Sep 18, 2025
  34. 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.
  35. in src/txgraph.cpp:3436 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.

  36. in src/txgraph.cpp:887 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.
  37. 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.
  38. instagibbs approved
  39. instagibbs commented at 5:00 pm on September 18, 2025: member

    ACK 66401148ddcba04c27751e39e53fc41e6deb5d14

    Did not validate the numbers, non-blocking comments only

  40. sipa force-pushed on Sep 23, 2025
  41. sipa force-pushed on Sep 23, 2025
  42. instagibbs commented at 1:55 pm on September 23, 2025: member

    reACK 99e144778eeffc1074d5a1c193896bea335db8af

    via git range-diff master 66401148ddcba04c27751e39e53fc41e6deb5d14 99e144778eeffc1074d5a1c193896bea335db8af

  43. DrahtBot requested review from ismaelsadeeq on Sep 23, 2025
  44. sipa force-pushed on Sep 23, 2025
  45. instagibbs commented at 2:58 pm on September 23, 2025: member

    reACK 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354

    just a rebase

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

    reACK 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354

    Changes since last ACK are nits fixes.

  47. 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).

  48. in src/txgraph.cpp:950 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).
  49. 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.
  50. in src/txgraph.cpp:945 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.
  51. in src/txgraph.cpp:1286 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.
  52. 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.
  53. 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.
  54. 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?
  55. 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.
  56. 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.
  57. 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.
  58. 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.
  59. 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.
  60. 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.
  61. in src/txgraph.cpp:1210 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.

  62. 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.
  63. 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.
  64. 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.
  65. 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.
  66. 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.
  67. 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.
  68. 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.
  69. 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.
  70. 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.
  71. 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.
  72. 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.
  73. 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.
  74. 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.
  75. 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.

  76. 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.
  77. 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.
  78. in src/txgraph.cpp:889 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.
  79. 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.
  80. 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.
  81. 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.
  82. in src/txgraph.cpp:2016 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.
  83. 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.
  84. 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).

  85. 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.
  86. 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.
  87. 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.
  88. in src/txgraph.cpp:942 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
  89. 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.
  90. 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.
  91. 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.
  92. 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.
  93. 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.

  94. in src/txgraph.cpp:1258 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.
  95. 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.
  96. 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.
  97. in src/txgraph.cpp:2262 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:

    sipa commented at 4:48 pm on October 9, 2025:
    This matches the code that’s already in GenericClusterImpl.
  98. 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.
  99. in src/txgraph.cpp:912 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.
  100. in src/txgraph.cpp:2292 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.

  101. 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).

  102. 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.
  103. in src/txgraph.cpp:2906 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.

  104. 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.

  105. 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.
  106. in src/txgraph.cpp:1062 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.
  107. 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.
  108. in src/txgraph.cpp:2121 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.
  109. 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.

  110. DrahtBot requested review from l0rinc on Oct 7, 2025
  111. sipa force-pushed on Oct 9, 2025
  112. 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.
  113. 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.
    d9b7be5a83
  114. txgraph: move some sanity checks from Cluster to TxGraphImpl (refactor) 19b990fd44
  115. txgraph: avoid holes in DepGraph positions (mem optimization) e405dfe13d
  116. depgraph: add memory usage control (feature)
    Co-Authored-By: Lőrinc <pap.lorinc@gmail.com>
    c4b381bde0
  117. txgraph: keep data structures compact (mem optimization) de8ebdd795
  118. sipa force-pushed on Oct 9, 2025
  119. txgraph: keep track of Cluster memory usage (preparation) b1eb8675db
  120. txgraph: expose memory usage estimate function (feature) 6ef1e5bb85
  121. 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.
    3475ec6898
  122. txgraph: make Cluster an abstract class (refactor) 14ef53c906
  123. txgraph: comment fixes (doc fix) a90e228684
  124. txgraph: abstract out creation of empty Clusters (refactor) b0befb842c
  125. txgraph: give Clusters a range of intended tx counts (preparation) 4d5ad0eb72
  126. 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.
    7421e58dee
  127. sipa force-pushed on Oct 9, 2025
  128. in src/txgraph.cpp:1063 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.
  129. instagibbs approved
  130. instagibbs commented at 1:43 pm on October 10, 2025: member

    reACK 7421e58dee402ee8b5b58a18684953a89ad350d7

    git range-diff master 5ac32aa441bf3ec1f1fa826f689405bc4a7b7354 7421e58dee402ee8b5b58a18684953a89ad350d7

  131. DrahtBot requested review from glozow on Oct 10, 2025

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2025-10-10 21:13 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me