Repository: bitcoin/bitcoin
File: src/txgraph.cpp (C++)

Code before:
        todo.Set(locator.index);
        // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
        //   are just never accessed, but set it to -1 here to increase the ability to detect a bug
        //   that causes it to be accessed regardless.
        m_mapping[locator.index] = GraphIndex(-1);
        // - Remove its linearization index from the Entry (if in main).
        if (level == 0) {
            entry.m_main_lin_index = LinearizationIndex(-1);
        }
        // - Mark it as missing/removed in the Entry's locator.
        graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
        to_remove = to_remove.subspan(1);
    } while(!to_remove.empty());

    Assume(todo.Any());
    // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
    // removed, so we benefit from batching all the removals).
    m_depgraph.RemoveTransactions(todo);
    m_mapping.resize(m_depgraph.PositionRange());

    // First remove all removals at the end of the linearization.
    while (!m_linearization.empty() && todo[m_linearization.back()]) {
        todo.Reset(m_linearization.back());
        m_linearization.pop_back();
    }
    if (todo.Any()) {
        // If more removals remain, filter those out of m_linearization.
        m_linearization.erase(std::remove_if(
            m_linearization.begin(),
            m_linearization.end(),
            [&](auto pos) { return todo[pos]; }), m_linearization.end());
    }

    Compact();
    graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
    graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
    Updated(graph, level);
}

void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
{
    // We can only remove the one transaction this Cluster has.
    Assume(!to_remove.empty());
    Assume(GetTxCount());
    Assume(to_remove.front() == m_graph_index);
    // Pop all copies of m_graph_index from the front of to_remove (at least one, but there may be
    // multiple).
    do {
        to_remove = to_remove.subspan(1);
    } while (!to_remove.empty() && to_remove.front() == m_graph_index);
    // Clear this cluster.

Review comment (performance):
1b2c53ae0c9020791d39c85b032f7f907b468c99

Could we go another step further and delete the 

>// First remove all removals at the end of the linearization

Stuff, drop this specific conditional and just filter or is this still a performance win

Code after:
void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
{
    // Iterate over the prefix of to_remove that applies to this cluster.
    Assume(!to_remove.empty());
    SetType todo;
    graph.GetClusterSet(level).m_cluster_usage -= TotalMemoryUsage();
    do {
        GraphIndex idx = to_remove.front();
        Assume(idx < graph.m_entries.size());
        auto& entry = graph.m_entries[idx];
        auto& locator = entry.m_locator[level];
        // Stop once we hit an entry that applies to another Cluster.
        if (locator.cluster != this) break;
        // - Remember it in a set of to-remove DepGraphIndexes.
        todo.Set(locator.index);
        // - Remove from m_mapping. This isn't strictly necessary as unused positions in m_mapping
        //   are just never accessed, but set it to -1 here to increase the ability to detect a bug
        //   that causes it to be accessed regardless.
        m_mapping[locator.index] = GraphIndex(-1);
        // - Remove its linearization index from the Entry (if in main).
        if (level == 0) {
            entry.m_main_lin_index = LinearizationIndex(-1);
        }
        // - Mark it as missing/removed in the Entry's locator.
        graph.ClearLocator(level, idx, m_quality == QualityLevel::OVERSIZED_SINGLETON);
        to_remove = to_remove.subspan(1);
    } while(!to_remove.empty());

    Assume(todo.Any());
    // Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
    // removed, so we benefit from batching all the removals).
    m_depgraph.RemoveTransactions(todo);
    m_mapping.resize(m_depgraph.PositionRange());

    // Filter removed transactions out of m_linearization.
    m_linearization.erase(std::remove_if(m_linearization.begin(), m_linearization.end(),
                                         [&](auto pos) { return todo[pos]; }),
                          m_linearization.end());

    Compact();
    graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
    auto new_quality = IsTopological() ? QualityLevel::NEEDS_SPLIT : QualityLevel::NEEDS_SPLIT_FIX;
    graph.SetClusterQuality(level, m_quality, m_setindex, new_quality);
    Updated(graph, level);
}

void SingletonClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<GraphIndex>& to_remove) noexcept
{
    // We can only remove the one transaction this Cluster has.
    Assume(!to_remove.empty());
    Assume(GetTxCount());