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

Code before:
        m_cur_cluster = nullptr;
        if (m_cur_iter == m_graph->m_main_chunkindex.end()) break;
        // Find the cluster pointed to by m_cur_iter.
        const auto& chunk_data = *m_cur_iter;
        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
        m_cur_cluster = chunk_end_entry.m_locator[0].cluster;
        m_known_end_of_cluster = false;
        // If we previously skipped a chunk from this cluster we cannot include more from it.
        if (!m_excluded_clusters.contains(m_cur_cluster)) break;
    }
}

std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> BlockBuilderImpl::GetCurrentChunk() noexcept
{
    std::optional<std::pair<std::vector<TxGraph::Ref*>, FeePerWeight>> ret;
    // Populate the return value if we are not done.
    if (m_cur_iter != m_graph->m_main_chunkindex.end()) {
        ret.emplace();
        const auto& chunk_data = *m_cur_iter;
        const auto& chunk_end_entry = m_graph->m_entries[chunk_data.m_graph_index];
        if (chunk_data.m_chunk_count == LinearizationIndex(-1)) {
            // Special case in case just a single transaction remains, avoiding the need to
            // dispatch to and dereference Cluster.
            ret->first.resize(1);
            Assume(chunk_end_entry.m_ref != nullptr);
            ret->first[0] = chunk_end_entry.m_ref;
            m_known_end_of_cluster = true;
        } else {
            Assume(m_cur_cluster);
            ret->first.resize(chunk_data.m_chunk_count);
            auto start_pos = chunk_end_entry.m_main_lin_index + 1 - chunk_data.m_chunk_count;
            m_known_end_of_cluster = m_cur_cluster->GetClusterRefs(*m_graph, ret->first, start_pos);
            // If the chunk size was 1 and at end of cluster, then the special case above should
            // have been used.
            Assume(!m_known_end_of_cluster || chunk_data.m_chunk_count > 1);
        }
        ret->second = chunk_end_entry.m_main_chunk_feerate;
    }
    return ret;
}

BlockBuilderImpl::BlockBuilderImpl(TxGraphImpl& graph) noexcept : m_graph(&graph)
{
    // Make sure all clusters in main are up to date, and acceptable.
    m_graph->MakeAllAcceptable(0);
    // There cannot remain any inapplicable dependencies (only possible if main is oversized).
    Assume(m_graph->m_main_clusterset.m_deps_to_add.empty());
    // Remember that this object is observing the graph's index, so that we can detect concurrent
    // modifications.
    ++m_graph->m_main_chunkindex_observers;
    // Find the first chunk.

Review comment (suggestion):
```Suggestion
            Assume(iters >= iters_done);
            auto [cost, optimal] = queue[pos].get()->Relinearize(*this, iters - iters_done);
```

Code after:
}

bool TxGraphImpl::DoWork(uint64_t iters) noexcept
{
    uint64_t iters_done{0};
    // First linearize everything in NEEDS_RELINEARIZE to an acceptable level. If more budget
    // remains after that, try to make everything optimal.
    for (QualityLevel quality : {QualityLevel::NEEDS_RELINEARIZE, QualityLevel::ACCEPTABLE}) {
        // First linearize staging, if it exists, then main.
        for (int level = GetTopLevel(); level >= 0; --level) {
            // Do not modify main if it has any observers.
            if (level == 0 && m_main_chunkindex_observers != 0) continue;
            ApplyDependencies(level);
            auto& clusterset = GetClusterSet(level);
            // Do not modify oversized levels.
            if (clusterset.m_oversized == true) continue;
            auto& queue = clusterset.m_clusters[int(quality)];
            while (!queue.empty()) {
                if (iters_done >= iters) return false;
                // Randomize the order in which we process, so that if the first cluster somehow
                // needs more work than what iters allows, we don't keep spending it on the same
                // one.
                auto pos = m_rng.randrange<size_t>(queue.size());
                auto iters_now = iters - iters_done;
                if (quality == QualityLevel::NEEDS_RELINEARIZE) {
                    // If we're working with clusters that need relinearization still, only perform
                    // up to m_acceptable_iters iterations. If they become ACCEPTABLE, and we still
                    // have budget after all other clusters are ACCEPTABLE too, we'll spend the
                    // remaining budget on trying to make them OPTIMAL.
                    iters_now = std::min(iters_now, m_acceptable_iters);
                }
                auto [cost, improved] = queue[pos].get()->Relinearize(*this, iters_now);
                iters_done += cost;
                // If no improvement was made to the Cluster, it means we've essentially run out of
                // budget. Even though it may be the case that iters_done < iters still, the
                // linearizer decided there wasn't enough budget left to attempt anything with.
                // To avoid an infinite loop that keeps trying clusters with minuscule budgets,
                // stop here too.
                if (!improved) return false;
            }
        }
    }
    // All possible work has been performed, so we can return true. Note that this does *not* mean
    // that all clusters are optimally linearized now. It may be that there is nothing to do left
    // because all non-optimal clusters are in oversized and/or observer-bearing levels.
    return true;
}

void BlockBuilderImpl::Next() noexcept
{
    // Don't do anything if we're already done.