cluster mempool: control/optimize TxGraph memory usage #33157

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.

Indeed!

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

Done.

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

Added a comment to explain that.

this in unconditionally called I think

I've rewritten this using the "loop of comand-- approach".

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

I have rewritten this.

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

Should also add coverage for GetLevel

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

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 "txgraph: keep track of Cluster memory usage (preparation)" 7974ed311c1843d548d98e9eae8fed71a42a1026

Should also count the sequence number of the cluster?

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

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

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

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.

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

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?

fdcb5f17bd100eb2c1765c13bbb8367d03fc7ea5

micro-nit for readability

        MakeAcceptable(*cluster, level);

Done.

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

Done something like this.

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)

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

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

89b7997e7414074da3b0a35a17d86a2dfe24f378

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

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

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

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

66401148ddcba04c27751e39e53fc41e6deb5d14

micro-nit: couldn't figure out what tot meant for a second... "to t.... size?"

    DepGraphIndex total_size = max_size;

Done.

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)

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.

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.

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

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?

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

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

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

Fixed.

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:

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

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.

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

Right.

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

I'm not going to change that now.

Thanks for doing it anyway :)

nit: we could minimize the diff slightly with:

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

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

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

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

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

        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)

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

The question was referring to the documentation of NEEDS_SPLIT

/** 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)

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.

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:

auto last_compaction_pos{real.PositionRange()};

...

const size_t mem_before{real.DynamicMemoryUsage()};
real.Compact();
const size_t mem_after{real.DynamicMemoryUsage()};

assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
last_compaction_pos = real.PositionRange();
break;

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

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

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.

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.

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

And extensibility, yes.

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

We always treat allocation errors as fatal.

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?

We could experiment with that in a follow-up.

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:

auto mem_before{TotalMemoryUsage()};
Updated(graph, level);
Compact();
assert(mem_before == TotalMemoryUsage());

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

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.

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

Seems overkill.

nit: maybe we could reduce duplication here:

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

fwiw, I think the existing code is clearer.

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

I will leave as-is.

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:

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

or

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

I have reordered the statements.

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 👍

I have reordered these statements and added comments.

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

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.

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

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

    return /* From clusters */
           m_main_clusterset.m_cluster_usage +
           /* From Entry objects. */
           sizeof(Entry) * m_main_clusterset.m_txcount +
           /* From the chunk index. */
           memusage::DynamicUsage(m_main_chunkindex);

Done.

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

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

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

Done.

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

Done.

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

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

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:

    size_t TotalMemoryUsage() const noexcept override

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

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

diff --git a/src/txgraph.cpp b/src/txgraph.cpp
--- a/src/txgraph.cpp	(revision 2ab1b802ad070853777a3c207a4fe49ef32bc978)
+++ b/src/txgraph.cpp	(date 1759773463470)
@@ -104,6 +104,7 @@
     using GraphIndex = TxGraph::GraphIndex;
 
 protected:
+    using SetType = BitSet<MAX_CLUSTER_COUNT_LIMIT>;
     /** The quality level of m_linearization. */
     QualityLevel m_quality{QualityLevel::NONE};
     /** Which position this Cluster has in Graph::ClusterSet::m_clusters[m_quality]. */
@@ -157,6 +158,8 @@
     virtual uint64_t GetTotalTxSize() const noexcept = 0;
     /** Given a DepGraphIndex into this Cluster, find the corresponding GraphIndex. */
     virtual GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept = 0;
+    /** Add dependencies to a given child in this cluster. */
+    virtual void AddDependencies(SetType parents, DepGraphIndex child) noexcept = 0;
     /** Figure out what level this Cluster exists at in Graph::m_clustersets. In most cases this
      *  is known by the caller already (see all "int level" arguments below), but not always. */
     virtual int GetLevel(const TxGraphImpl& graph) const noexcept = 0;
@@ -262,6 +265,10 @@
     LinearizationIndex GetTxCount() const noexcept final { return m_linearization.size(); }
     uint64_t GetTotalTxSize() const noexcept final;
     GraphIndex GetClusterEntry(DepGraphIndex index) const noexcept final { return m_mapping[index]; }
+    void AddDependencies(SetType parent, DepGraphIndex child) noexcept
+    {
+        m_depgraph.AddDependencies(parent, child);
+    }
     int GetLevel(const TxGraphImpl& graph) const noexcept final;
     void UpdateMapping(DepGraphIndex cluster_idx, GraphIndex graph_idx) noexcept final { m_mapping[cluster_idx] = graph_idx; }
     void Updated(TxGraphImpl& graph, int level) noexcept final;
@@ -1128,12 +1135,11 @@
     // Redistribute the dependencies.
     for (auto i : m_linearization) {
         /** The cluster transaction in position i is moved to. */
-        Cluster* new_abstract_cluster = remap[i].first;
-        GenericClusterImpl* new_cluster = static_cast<GenericClusterImpl*>(new_abstract_cluster);
+        Cluster* new_cluster = remap[i].first;
         // Copy its parents, translating positions.
         SetType new_parents;
         for (auto par : m_depgraph.GetReducedParents(i)) new_parents.Set(remap[par].second);
-        new_cluster->m_depgraph.AddDependencies(new_parents, remap[i].second);
+        new_cluster->AddDependencies(new_parents, remap[i].second);
     }
     // Update all the Locators of moved transactions, and memory usage.
     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.

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

Thanks, it's a lot cleaner this way

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

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

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

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.

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

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.

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.

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

you're right, my mistake

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.

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:

• https://storage.googleapis.com/oss-fuzz-coverage/bitcoin-core/reports/20251011/linux/src/bitcoin-core/src/cluster_linearize.h.html#L867
• https://storage.googleapis.com/oss-fuzz-coverage/bitcoin-core/reports/20251011/linux/src/bitcoin-core/src/cluster_linearize.h.html#L1096
• https://storage.googleapis.com/oss-fuzz-coverage/bitcoin-core/reports/20251011/linux/src/bitcoin-core/src/txgraph.cpp.html#L2923

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.

I have tested with them added and the fuzzers are passing

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

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.

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.

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

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

Done.

This seems unused

m_depgraph is a DepGraph<SetType>

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

Indeed, fixed.

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

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

and

    Assume(graph_idx != Cluster::INVALID);

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

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

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:

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

Done.

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

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

and

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

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

etc

Done.

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

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

Did rephrase a bit more elaborately.

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.

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

nit: when is it index and when idx?

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

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

assert(real->GetMainMemoryUsage() == real->GetMainMemoryUsage());

if (real->GetTransactionCount(TxGraph::Level::MAIN) == 0) {
    assert(real->GetMainMemoryUsage() == 0);
} else {
    assert(real->GetMainMemoryUsage() > 0);
}

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

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

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

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

Except this one

Is this necessary here? Seems like a noop

Nice catch. Removed.

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

Moved it.

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;?

Done.

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

A proper risk analysis would have vetted this

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

Seems unrelated to this PR.

I can't find Graph::m_clustersets

Added a commit that fixes some outdated comments.

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

Fixed in a commit that fixes some outdated comments.

Hmm, but SingletonClusterImpl can also be in the duplicates:

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

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

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

Indeed, fixed.

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:

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

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.

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.

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

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

This was a leftover, gone.

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

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

or

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

or even:

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

Addressed by introducing a separate FindCluster and FindClusterAndLevel function.

similarly to:

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

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

This matches the code that's already in GenericClusterImpl.

Could we document here that its quality is also changed?

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

Done, in a new comment-fixing commit.

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

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.

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

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.

Thank you

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.

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

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

Ok, resolving.

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.

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

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

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

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.

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

Fixed.

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

Good idea, done.

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

Fair point, done.

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

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

de8ebdd795e35644435c7b68b2c2bc5f54ea9d7c

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

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

yep, just noting

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

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:

diff --git a/src/txgraph.cpp b/src/txgraph.cpp
--- a/src/txgraph.cpp	(revision 262762bbb6f7157ba8c54972909c9214448c304b)
+++ b/src/txgraph.cpp	(date 1760144001634)
@@ -722,7 +722,7 @@
     /** If cluster is not in staging, copy it there, and return a pointer to it.
     *   Staging must exist, and this modifies the locators of its
     *   transactions from inherited (P,M) to explicit (P,P). */
-    Cluster* PullIn(Cluster* cluster) noexcept;
+    Cluster* PullIn(Cluster* cluster, int level) noexcept;
     /** Apply all removals queued up in m_to_remove to the relevant Clusters (which get a
      *  NEEDS_SPLIT* QualityLevel) up to the specified level. */
     void ApplyRemovals(int up_to_level) noexcept;
@@ -1634,11 +1634,12 @@
     return {nullptr, -1};
 }
 
-Cluster* TxGraphImpl::PullIn(Cluster* cluster) noexcept
+Cluster* TxGraphImpl::PullIn(Cluster* cluster, int cluster_level) noexcept
 {
     int to_level = GetTopLevel();
     Assume(to_level == 1);
     int level = cluster->GetLevel(*this);
+    Assert(level == cluster_level); // TODO use parent call calculations instead
     Assume(level <= to_level);
     // Copy the Cluster from main to staging, if it's not already there.
     if (level == 0) {
@@ -1661,8 +1662,8 @@
         // Pull in all Clusters that are not in staging.
         if (level == 1) {
             for (GraphIndex index : to_remove) {
-                auto cluster = FindCluster(index, level);
-                if (cluster != nullptr) PullIn(cluster);
+                auto [cluster, cluster_level] = FindClusterAndLevel(index, level);
+                if (cluster != nullptr) PullIn(cluster, cluster_level);
             }
         }
         // Group the set of to-be-removed entries by Cluster::m_sequence.
@@ -2067,7 +2068,7 @@
         // Pull in all the Clusters that contain dependencies.
         if (level == 1) {
             for (Cluster*& cluster : cluster_span) {
-                cluster = PullIn(cluster);
+                cluster = PullIn(cluster, cluster->GetLevel(*this));
             }
         }
         // 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.

Done.

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

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

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.

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

nit: for consistency:

    Assume(!GetTxCount());

Done.

nit: likely missed because of the extra space

    if (!GetTxCount()) return 0;

Done.

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

Done.

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

Done.

nit:

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

Done.

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

Indeed unrelated.

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

Done.

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

nit: it seems to me this can now be private

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

Is the explicit reset meant for clarity here instead of

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

Yes.

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

Done.

I find this a lot more intuitive, thanks

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

assert(entries.size() > m_used.Count()); // TODO fails fuzzing, indicating that entries can have holes
for (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.

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

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.

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

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

or maybe even

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

so that here we're not leaking internals:

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

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

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.

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