Repository: bitcoin/bitcoin
File: src/cluster_linearize.h (C/C++)

Code before:
                    // Skip if this dependency is ineligible (the top chunk that would be created
                    // does not have higher feerate than the chunk it is currently part of).
                    auto cmp = FeeRateCompare(dep_data.top_setinfo.feerate, chunk_data.chunk_setinfo.feerate);
                    if (cmp <= 0) continue;
                    // Generate a random tiebreak for this dependency, and reject it if its tiebreak
                    // is worse than the best so far. This means that among all eligible
                    // dependencies, a uniformly random one will be chosen.
                    uint64_t tiebreak = m_rng.rand64();
                    if (tiebreak < candidate_tiebreak) continue;
                    // Remember this as our (new) candidate dependency.
                    candidate_dep = dep_idx;
                    candidate_tiebreak = tiebreak;
                }
            }
            // If a candidate with positive gain was found, deactivate it and then make the state
            // topological again with a sequence of merges.
            if (candidate_dep != DepIdx(-1)) Improve(candidate_dep);
            // Stop processing for now, even if nothing was activated, as the loop above may have
            // had a nontrivial cost.
            return !m_suboptimal_chunks.empty();
        }
        // No improvable chunk was found, we are done.
        return false;
    }

    /** Initialize data structure for minimizing the chunks. Step() cannot be called anymore
     *  afterwards. */
    void StartMinimizing() noexcept
    {
        m_nonminimal_chunks.clear();
        m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
        // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
        // direction, to m_nonminimal_chunks.
        for (auto tx : m_transaction_idxs) {
            auto& tx_data = m_tx_data[tx];
            if (tx_data.chunk_rep == tx) {
                TxIdx pivot_idx = PickRandomTx(tx_data.chunk_setinfo.transactions);
                m_nonminimal_chunks.emplace_back(tx, pivot_idx, m_rng.randbits<1>());
                // Randomize the initial order of nonminimal chunks in the queue.
                TxIdx j = m_rng.randrange<TxIdx>(m_nonminimal_chunks.size());
                if (j != m_nonminimal_chunks.size() - 1) {
                    std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
                }
            }
        }
    }

    /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
    bool MinimizeStep() noexcept
    {
        // If the queue of potentially-non-minimal chunks is empty, we are done.

Review comment (performance):
```suggestion
    /** Initialize data structure for minimizing the chunks. OptimizeStep() cannot be called anymore
```

Code after:
                    // Skip if this dependency is ineligible (the top chunk that would be created
                    // does not have higher feerate than the chunk it is currently part of).
                    auto cmp = FeeRateCompare(dep_data.top_setinfo.feerate, chunk_data.chunk_setinfo.feerate);
                    if (cmp <= 0) continue;
                    // Generate a random tiebreak for this dependency, and reject it if its tiebreak
                    // is worse than the best so far. This means that among all eligible
                    // dependencies, a uniformly random one will be chosen.
                    uint64_t tiebreak = m_rng.rand64();
                    if (tiebreak < candidate_tiebreak) continue;
                    // Remember this as our (new) candidate dependency.
                    candidate_dep = dep_idx;
                    candidate_tiebreak = tiebreak;
                }
            }
            // If a candidate with positive gain was found, deactivate it and then make the state
            // topological again with a sequence of merges.
            if (candidate_dep != DepIdx(-1)) Improve(candidate_dep);
            // Stop processing for now, even if nothing was activated, as the loop above may have
            // had a nontrivial cost.
            return !m_suboptimal_chunks.empty();
        }
        // No improvable chunk was found, we are done.
        return false;
    }

    /** Initialize data structure for minimizing the chunks. Can only be called if state is known
     *  to be optimal. OptimizeStep() cannot be called anymore afterwards. */
    void StartMinimizing() noexcept
    {
        m_nonminimal_chunks.clear();
        m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
        // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
        // direction, to m_nonminimal_chunks.
        for (auto tx : m_transaction_idxs) {
            auto& tx_data = m_tx_data[tx];
            if (tx_data.chunk_rep == tx) {
                TxIdx pivot_idx = PickRandomTx(tx_data.chunk_setinfo.transactions);
                m_nonminimal_chunks.emplace_back(tx, pivot_idx, m_rng.randbits<1>());
                // Randomize the initial order of nonminimal chunks in the queue.
                TxIdx j = m_rng.randrange<TxIdx>(m_nonminimal_chunks.size());
                if (j != m_nonminimal_chunks.size() - 1) {
                    std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
                }
            }
        }
    }

    /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
    bool MinimizeStep() noexcept
    {
        // If the queue of potentially-non-minimal chunks is empty, we are done.