Inside Bitcoin

251        FeeFrac ret;
252        for (auto pos : elems) ret += entries[pos].feerate;
253        return ret;
254    }
255
256    /** Get the connected component within the subset "todo" that contains tx (which must be in
257     *  todo).
258     *
259     * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
260     * of the other in the entire graph (so not just within `todo`), or transitively there is a
261     * path of transactions connecting them. This does mean that if `todo` contains a transaction
262     * and a grandparent, but misses the parent, they will still be part of the same component.
263     *
264     * Complexity: O(ret.Count()).
265     */
266    SetType GetConnectedComponent(const SetType& todo, DepGraphIndex tx) const noexcept
267    {
268        Assume(todo[tx]);
269        Assume(todo.IsSubsetOf(m_used));
270        auto to_add = SetType::Singleton(tx);
271        SetType ret;
272        do {
273            SetType old = ret;
274            for (auto add : to_add) {
275                ret |= Descendants(add);
276                ret |= Ancestors(add);
277            }
278            ret &= todo;
279            to_add = ret - old;
280        } while (to_add.Any());
281        return ret;
282    }
283
284    /** Find some connected component within the subset "todo" of this graph.
285     *
286     * Specifically, this finds the connected component which contains the first transaction of
287     * todo (if any).
288     *
289     * Complexity: O(ret.Count()).
290     */
291    SetType FindConnectedComponent(const SetType& todo) const noexcept
292    {
293        if (todo.None()) return todo;
294        return GetConnectedComponent(todo, todo.First());
295    }
296
297    /** Determine if a subset is connected.
298     *
299     * Complexity: O(subset.Count()).
300     */
301    bool IsConnected(const SetType& subset) const noexcept
302    {
303        return FindConnectedComponent(subset) == subset;
304    }
305
306    /** Determine if this entire graph is connected.
307     *
308     * Complexity: O(TxCount()).
309     */
310    bool IsConnected() const noexcept { return IsConnected(m_used); }
311
312    /** Append the entries of select to list in a topologically valid order.
313     *
314     * Complexity: O(select.Count() * log(select.Count())).
315     */
316    void AppendTopo(std::vector<DepGraphIndex>& list, const SetType& select) const noexcept
317    {
318        DepGraphIndex old_len = list.size();
319        for (auto i : select) list.push_back(i);
320        std::ranges::sort(std::span{list}.subspan(old_len), [&](DepGraphIndex a, DepGraphIndex b) noexcept {
321            const auto a_anc_count = entries[a].ancestors.Count();
322            const auto b_anc_count = entries[b].ancestors.Count();
323            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
324            return a < b;
325        });
326    }
327
328    /** Check if this graph is acyclic. */
329    bool IsAcyclic() const noexcept
330    {
331        for (auto i : Positions()) {
332            if ((Ancestors(i) & Descendants(i)) != SetType::Singleton(i)) {
333                return false;
334            }
335        }
336        return true;
337    }
338
339    unsigned CountDependencies() const noexcept
340    {
341        unsigned ret = 0;
342        for (auto i : Positions()) {
343            ret += GetReducedParents(i).Count();
344        }
345        return ret;
346    }
347
348    /** Reduce memory usage if possible. No observable effect. */
349    void Compact() noexcept
350    {
351        entries.shrink_to_fit();
352    }
353
354    size_t DynamicMemoryUsage() const noexcept
355    {
356        return memusage::DynamicUsage(entries);
357    }
358};
359
360/** A set of transactions together with their aggregate feerate. */
361template<typename SetType>
362struct SetInfo
363{
364    /** The transactions in the set. */
365    SetType transactions;
366    /** Their combined fee and size. */
367    FeeFrac feerate;
368
369    /** Construct a SetInfo for the empty set. */
370    SetInfo() noexcept = default;
371
372    /** Construct a SetInfo for a specified set and feerate. */
373    SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
374
375    /** Construct a SetInfo for a given transaction in a depgraph. */
376    explicit SetInfo(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept :
377        transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
378
379    /** Construct a SetInfo for a set of transactions in a depgraph. */
380    explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
381        transactions(txn), feerate(depgraph.FeeRate(txn)) {}
382
383    /** Add a transaction to this SetInfo (which must not yet be in it). */
384    void Set(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept
385    {
386        Assume(!transactions[pos]);
387        transactions.Set(pos);
388        feerate += depgraph.FeeRate(pos);
389    }
390
391    /** Add the transactions of other to this SetInfo (no overlap allowed). */
392    SetInfo& operator|=(const SetInfo& other) noexcept
393    {
394        Assume(!transactions.Overlaps(other.transactions));
395        transactions |= other.transactions;
396        feerate += other.feerate;
397        return *this;
398    }
399
400    /** Remove the transactions of other from this SetInfo (which must be a subset). */
401    SetInfo& operator-=(const SetInfo& other) noexcept
402    {
403        Assume(other.transactions.IsSubsetOf(transactions));
404        transactions -= other.transactions;
405        feerate -= other.feerate;
406        return *this;
407    }
408
409    /** Compute the difference between this and other SetInfo (which must be a subset). */
410    SetInfo operator-(const SetInfo& other) const noexcept
411    {
412        Assume(other.transactions.IsSubsetOf(transactions));
413        return {transactions - other.transactions, feerate - other.feerate};
414    }
415
416    /** Swap two SetInfo objects. */
417    friend void swap(SetInfo& a, SetInfo& b) noexcept
418    {
419        swap(a.transactions, b.transactions);
420        swap(a.feerate, b.feerate);
421    }
422
423    /** Permit equality testing. */
424    friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
425};
426
427/** Compute the chunks of linearization as SetInfos. */
428template<typename SetType>
429std::vector<SetInfo<SetType>> ChunkLinearizationInfo(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
430{
431    std::vector<SetInfo<SetType>> ret;
432    for (DepGraphIndex i : linearization) {
433        /** The new chunk to be added, initially a singleton. */
434        SetInfo<SetType> new_chunk(depgraph, i);
435        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
436        while (!ret.empty() && ByRatio{new_chunk.feerate} > ByRatio{ret.back().feerate}) {
437            new_chunk |= ret.back();
438            ret.pop_back();
439        }
440        // Actually move that new chunk into the chunking.
441        ret.emplace_back(std::move(new_chunk));
442    }
443    return ret;
444}
445
446/** Compute the feerates of the chunks of linearization. Identical to ChunkLinearizationInfo, but
447 *  only returns the chunk feerates, not the corresponding transaction sets. */
448template<typename SetType>
449std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
450{
451    std::vector<FeeFrac> ret;
452    for (DepGraphIndex i : linearization) {
453        /** The new chunk to be added, initially a singleton. */
454        auto new_chunk = depgraph.FeeRate(i);
455        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
456        while (!ret.empty() && ByRatio{new_chunk} > ByRatio{ret.back()}) {
457            new_chunk += ret.back();
458            ret.pop_back();
459        }
460        // Actually move that new chunk into the chunking.
461        ret.push_back(std::move(new_chunk));
462    }
463    return ret;
464}
465
466/** Concept for function objects that return std::strong_ordering when invoked with two Args. */
467template<typename F, typename Arg>
468concept StrongComparator =
469    std::regular_invocable<F, Arg, Arg> &&
470    std::is_same_v<std::invoke_result_t<F, Arg, Arg>, std::strong_ordering>;
471
472/** Simple default transaction ordering function for SpanningForestState::GetLinearization() and
473 *  Linearize(), which just sorts by DepGraphIndex. */
474using IndexTxOrder = std::compare_three_way;
475
476/** A default cost model for SFL for SetType=BitSet<64>, based on benchmarks.
477 *
478 * The numbers here were obtained in February 2026 by:
479 * - For a variety of machines:
480 *   - Running a fixed collection of ~385000 clusters found through random generation and fuzzing,
481 *     optimizing for difficulty of linearization.
482 *     - Linearize each ~3000 times, with different random seeds. Sometimes without input
483 *       linearization, sometimes with a bad one.
484 *       - Gather cycle counts for each of the operations included in this cost model,
485 *         broken down by their parameters.
486 *   - Correct the data by subtracting the runtime of obtaining the cycle count.
487 *   - Drop the 5% top and bottom samples from each cycle count dataset, and compute the average
488 *     of the remaining samples.
489 *   - For each operation, fit a least-squares linear function approximation through the samples.
490 * - Rescale all machine expressions to make their total time match, as we only care about
491 *   relative cost of each operation.
492 * - Take the per-operation average of operation expressions across all machines, to construct
493 *   expressions for an average machine.
494 * - Approximate the result with integer coefficients. Each cost unit corresponds to somewhere
495 *   between 0.5 ns and 2.5 ns, depending on the hardware.
496 */
497class SFLDefaultCostModel
498{
499    uint64_t m_cost{0};
500