Decrement can still go below m_max_debt before checking is complete.

decrement() can always go below m_max_debt, it only reports when it has done so -- it leaves it up to the caller to not go further into debt.

It looks like both eventual production call sites of this function (BumpInvVecForProcessing and PeerManagerImpl::SendMessages) do a deduplication pass on the results.

Would it make sense to do this on the fly inside this function? It can't use std::partial_sort anymore, but it can use std::make_heap and friends to implement partial sorting, with a dynamic end point until n distinct elements have been found? Something like

std::vector<CTxMemPool::txiter> CTxMemPool::SortMiningScoreWithTopology(std::span<const Wtxid> wtxids, size_t n) const
{
    auto cmp = [&](const auto& a, const auto& b) EXCLUSIVE_LOCKS_REQUIRED(cs) noexcept { return m_txgraph->CompareMainOrder(*a, *b) > 0; };

    std::vector<txiter> res;

    n = std::min(wtxids.size(), n);
    if (n > 0) {
        // Construct a heap with txiters for all wtxids that exist in the mempool.
        std::vector<txiter> heap;
        heap.reserve(wtxids.size());
        for (auto& wtxid : wtxids) {
            if (auto i{GetIter(wtxid)}; i.has_value()) {
                heap.push_back(i.value());
            }
        }
        std::ranges::make_heap(heap, cmp);

        // Pop transactions until n distinct ones in res have been found.
        res.reserve(heap.size());
        while (res.size() < n && !heap.empty()) {
            std::ranges::pop_heap(heap, cmp);
            if (res.empty() || heap.back() != res.back()) {
                res.push_back(heap.back());
            }
            heap.pop_back();
        }

        // Copy the remainder over, without sorting or deduplication.
        res.insert(res.end(), heap.begin(), heap.end());
    }

    return res;
}

With even more low-level code the duplicate vector can be avoided, I think. Tests don't pass with this, I haven't investigated why.

Without having looked, is the comparison backwards?

My understanding is partial_sort has two benefits:

• it only makes a heap out of the target size, so iterates through the source array once and then does log(k) work for each element, with better locality
• when updating the k elements in the heap with a new element from the source, it does the sift-down algorithm which is more efficient than heap_push()/heap_pop(), but isn't exposed via the STL so would mean writing your own heap implementation

Deduping the fairly small output list as you pass through it, when duplicates are rare anyway, seemed fine to me?

Without having looked, is the comparison backwards?

I don't think so. It's a max heap, but I want to pop the "lowest" elements off first, so I needed to swap the comparator I think.

My understanding is partial_sort has two benefits:

Interesting. So it has complexity O(n log m) (with n = number of elements, m = sorted prefix size), while the approach I have in mind is O(n + (m log n)) (O(n) to construct the heap of all elements, and then m operations of each O(log n) to extract the best m elements. Complexity-wise, my approach seems better, since n > m, except it has worse memory locality. This makes me wonder if I'm missing something, since the cppreference.cpp documentation seems to imply std::partial_sort is intended for low m values.

Deduping the fairly small output list as you pass through it, when duplicates are rare anyway, seemed fine to me?

Yeah, it probably doesn't matter that much. It just looked like the deduplication is something that CTxMemPool::SortMiningScoreWithTopology could do internally since both call sites need it anyway. And then it seemed possible to have the count be dynamic, but only when using a different approach than what std::partial_sort seems to enable.

In commit "util/tokenbucket.h: Provide a generic TokenBucket class"

Is it useful to support debt? I believe it can be avoided by a transformation that raises both m_value and m_cap by -m_max_debt.

The distinction is in InvToSendBucket::avail() which says "you can start doing stuff as long as the size_bucket's value is >=0", which would have to get incremented as well to be equivalent.

The main effect is that when the size bucket is under pressure, you get a chance to relay at least 50kB each iteration, rather than the avail test passing as soon as you can relay 1B, then the loop ending immediately after you relay the first tx.

I think it can be simplified a bit by moving the max_debt value to just being a parameter of decrement() though. Will update.