How does Bitcoin Core sort memory pool transactions by fee?

Question

I'm trying to understand the algorithm Bitcoin Core uses to sort memory pool transactions by fee.

Gavin's fee rework proposal states:

Next, sort all remaining memory pool transactions by fee-paid-per-kilobyte, and include as many as will fit until the block is maximum block size bytes big, not including "free" transactions (transactions with fee-per-kb of less than the default spam threshold of 0.0001 BTC/kilobyte).

This makes sense, because a miner should want to load a block with transactions carrying the most "fee density", or fee per byte.

However, reviewing the CreateNewBlock function in miner.cpp, it's not clear how Bitcoin Core accounts for transaction length when prioritizing memory pool items:

// Prioritise by fee once past the priority size or we run out of high-priority
// transactions:
if (!fSortedByFee &&
    ((nBlockSize + nTxSize >= nBlockPrioritySize) || !AllowFree(dPriority)))
{
    fSortedByFee = true;
    comparer = TxPriorityCompare(fSortedByFee);
    std::make_heap(vecPriority.begin(), vecPriority.end(), comparer);
}

TXPriorityCompare seems to just look at absolute fee:

public:
    TxPriorityCompare(bool _byFee) : byFee(_byFee) { }

    bool operator()(const TxPriority& a, const TxPriority& b)
    {
        if (byFee)
        {
            if (a.get<1>() == b.get<1>())
                return a.get<0>() < b.get<0>();
            return a.get<1>() < b.get<1>();
        }
        else
        {
            if (a.get<0>() == b.get<0>())
                return a.get<1>() < b.get<1>();
            return a.get<0>() < b.get<0>();
        }
    }
};

In other words, this looks like a sort on absolute transaction fee, not fee density. What am I missing?

Answer 1

The excerpt you're showing is for the priority area in blocks. The concept of "priority" in the source code corresponds modified bitcoin-days-destroyed per kilobyte. It is only used for a small portion of the block size (max 50kB by default in Bitcoin Core 0.11.x, and max 0kB by default in 0.12.x, it can be changed with a configuration setting).

Look at the rest of CreateNewBlock, which uses sorting by feerate, by iterating an index on the mempool that is pre-sorted by feerate (=satoshi per kB).