_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2Ev:
   68|  10.4k|    DepGraph() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7TxCountEv:
  118|   101k|    auto TxCount() const noexcept { return m_used.Count(); }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2Ev:
  324|   238k|    SetInfo() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9PositionsEv:
  114|   186k|    const SetType& Positions() const noexcept { return m_used; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj:
  122|   943k|    FeeFrac& FeeRate(ClusterIndex i) noexcept { return entries[i].feerate; }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9AncestorsEj:
  124|  2.83M|    const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE14AddTransactionERK7FeeFrac:
  134|  92.8k|    {
  135|  92.8k|        static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
  136|  92.8k|        auto available = ALL_POSITIONS - m_used;
  137|  92.8k|        Assume(available.Any());
  ------------------
  |  |   97|  92.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  138|  92.8k|        ClusterIndex new_idx = available.First();
  139|  92.8k|        if (new_idx == entries.size()) {
  ------------------
  |  Branch (139:13): [True: 92.8k, False: 0]
  ------------------
  140|  92.8k|            entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  141|  92.8k|        } else {
  142|      0|            entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  143|      0|        }
  144|  92.8k|        m_used.Set(new_idx);
  145|  92.8k|        return new_idx;
  146|  92.8k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2ERK7FeeFracRKS3_SA_:
   46|  92.8k|        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE15AddDependenciesERKS3_j:
  178|   115k|    {
  179|   115k|        Assume(m_used[child]);
  ------------------
  |  |   97|   115k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  180|   115k|        Assume(parents.IsSubsetOf(m_used));
  ------------------
  |  |   97|   115k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  181|       |        // Compute the ancestors of parents that are not already ancestors of child.
  182|   115k|        SetType par_anc;
  183|   135k|        for (auto par : parents - Ancestors(child)) {
  ------------------
  |  Branch (183:23): [True: 135k, False: 115k]
  ------------------
  184|   135k|            par_anc |= Ancestors(par);
  185|   135k|        }
  186|   115k|        par_anc -= Ancestors(child);
  187|       |        // Bail out if there are no such ancestors.
  188|   115k|        if (par_anc.None()) return;
  ------------------
  |  Branch (188:13): [True: 70.9k, False: 44.9k]
  ------------------
  189|       |        // To each such ancestor, add as descendants the descendants of the child.
  190|  44.9k|        const auto& chl_des = entries[child].descendants;
  191|   315k|        for (auto anc_of_par : par_anc) {
  ------------------
  |  Branch (191:30): [True: 315k, False: 44.9k]
  ------------------
  192|   315k|            entries[anc_of_par].descendants |= chl_des;
  193|   315k|        }
  194|       |        // To each descendant of the child, add those ancestors.
  195|  53.1k|        for (auto dec_of_chl : Descendants(child)) {
  ------------------
  |  Branch (195:30): [True: 53.1k, False: 44.9k]
  ------------------
  196|  53.1k|            entries[dec_of_chl].ancestors |= par_anc;
  197|  53.1k|        }
  198|  44.9k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE18RemoveTransactionsERKS3_:
  158|  2.67k|    {
  159|  2.67k|        m_used -= del;
  160|       |        // Remove now-unused trailing entries.
  161|  2.67k|        while (!entries.empty() && !m_used[entries.size() - 1]) {
  ------------------
  |  Branch (161:16): [True: 2.44k, False: 232]
  |  Branch (161:36): [True: 0, False: 2.44k]
  ------------------
  162|      0|            entries.pop_back();
  163|      0|        }
  164|       |        // Remove the deleted transactions from ancestors/descendants of other transactions. Note
  165|       |        // that the deleted positions will retain old feerate and dependency information. This does
  166|       |        // not matter as they will be overwritten by AddTransaction if they get used again.
  167|  58.6k|        for (auto& entry : entries) {
  ------------------
  |  Branch (167:26): [True: 58.6k, False: 2.67k]
  ------------------
  168|  58.6k|            entry.ancestors &= m_used;
  169|  58.6k|            entry.descendants &= m_used;
  170|  58.6k|        }
  171|  2.67k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj:
  120|  2.81M|    const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEaSEOS4_:
   72|  5.11k|    DepGraph& operator=(DepGraph&&) noexcept = default;
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2ERKS4_4SpanIKjEj:
   89|  5.11k|    DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping, ClusterIndex pos_range) noexcept : entries(pos_range)
   90|  5.11k|    {
   91|  5.11k|        Assume(mapping.size() == depgraph.PositionRange());
  ------------------
  |  |   97|  5.11k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   92|  5.11k|        Assume((pos_range == 0) == (depgraph.TxCount() == 0));
  ------------------
  |  |   97|  5.11k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   93|  68.3k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (93:29): [True: 68.3k, False: 5.11k]
  ------------------
   94|  68.3k|            auto new_idx = mapping[i];
   95|  68.3k|            Assume(new_idx < pos_range);
  ------------------
  |  |   97|  68.3k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   96|       |            // Add transaction.
   97|  68.3k|            entries[new_idx].ancestors = SetType::Singleton(new_idx);
   98|  68.3k|            entries[new_idx].descendants = SetType::Singleton(new_idx);
   99|  68.3k|            m_used.Set(new_idx);
  100|       |            // Fill in fee and size.
  101|  68.3k|            entries[new_idx].feerate = depgraph.entries[i].feerate;
  102|  68.3k|        }
  103|  68.3k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (103:29): [True: 68.3k, False: 5.11k]
  ------------------
  104|       |            // Fill in dependencies by mapping direct parents.
  105|  68.3k|            SetType parents;
  106|  68.3k|            for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
  ------------------
  |  Branch (106:25): [True: 28.9k, False: 68.3k]
  ------------------
  107|  68.3k|            AddDependencies(parents, mapping[i]);
  108|  68.3k|        }
  109|       |        // Verify that the provided pos_range was correct (no unused positions at the end).
  110|  5.11k|        Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
  ------------------
  |  |   97|  10.2k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 225, False: 4.89k]
  |  |  ------------------
  ------------------
  111|  5.11k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2Ev:
   44|  92.8k|        Entry() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE22FindConnectedComponentERKS3_:
  266|   214k|    {
  267|   214k|        if (todo.None()) return todo;
  ------------------
  |  Branch (267:13): [True: 0, False: 214k]
  ------------------
  268|   214k|        auto to_add = SetType::Singleton(todo.First());
  269|   214k|        SetType ret;
  270|   431k|        do {
  271|   431k|            SetType old = ret;
  272|   496k|            for (auto add : to_add) {
  ------------------
  |  Branch (272:27): [True: 496k, False: 431k]
  ------------------
  273|   496k|                ret |= Descendants(add);
  274|   496k|                ret |= Ancestors(add);
  275|   496k|            }
  276|   431k|            ret &= todo;
  277|   431k|            to_add = ret - old;
  278|   431k|        } while (to_add.Any());
  ------------------
  |  Branch (278:18): [True: 216k, False: 214k]
  ------------------
  279|   214k|        return ret;
  280|   214k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11DescendantsEj:
  126|  1.18M|    const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
_ZN17cluster_linearize18ChunkLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorI7FeeFracNS4_9allocatorIS6_EEEERKNS_8DepGraphIT_EE4SpanIKjE:
  375|  10.7k|{
  376|  10.7k|    std::vector<FeeFrac> ret;
  377|   136k|    for (ClusterIndex i : linearization) {
  ------------------
  |  Branch (377:25): [True: 136k, False: 10.7k]
  ------------------
  378|       |        /** The new chunk to be added, initially a singleton. */
  379|   136k|        auto new_chunk = depgraph.FeeRate(i);
  380|       |        // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
  381|   194k|        while (!ret.empty() && new_chunk >> ret.back()) {
  ------------------
  |  Branch (381:16): [True: 166k, False: 28.8k]
  |  Branch (381:32): [True: 58.1k, False: 107k]
  ------------------
  382|  58.1k|            new_chunk += ret.back();
  383|  58.1k|            ret.pop_back();
  384|  58.1k|        }
  385|       |        // Actually move that new chunk into the chunking.
  386|   136k|        ret.push_back(std::move(new_chunk));
  387|   136k|    }
  388|  10.7k|    return ret;
  389|  10.7k|}
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEE3SetERKNS_8DepGraphIS3_EEj:
  339|   405k|    {
  340|   405k|        Assume(!transactions[pos]);
  ------------------
  |  |   97|   405k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  341|   405k|        transactions.Set(pos);
  342|   405k|        feerate += depgraph.FeeRate(pos);
  343|   405k|    }
_ZN17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EE:
  544|  2.44k|        m_depgraph(depgraph),
  545|  2.44k|        m_todo{depgraph.Positions()},
  546|  2.44k|        m_ancestor_set_feerates(depgraph.PositionRange())
  547|  2.44k|    {
  548|       |        // Precompute ancestor-set feerates.
  549|  34.1k|        for (ClusterIndex i : m_depgraph.Positions()) {
  ------------------
  |  Branch (549:29): [True: 34.1k, False: 2.44k]
  ------------------
  550|       |            /** The remaining ancestors for transaction i. */
  551|  34.1k|            SetType anc_to_add = m_depgraph.Ancestors(i);
  552|  34.1k|            FeeFrac anc_feerate;
  553|       |            // Reuse accumulated feerate from first ancestor, if usable.
  554|  34.1k|            Assume(anc_to_add.Any());
  ------------------
  |  |   97|  34.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  555|  34.1k|            ClusterIndex first = anc_to_add.First();
  556|  34.1k|            if (first < i) {
  ------------------
  |  Branch (556:17): [True: 8.64k, False: 25.5k]
  ------------------
  557|  8.64k|                anc_feerate = m_ancestor_set_feerates[first];
  558|  8.64k|                Assume(!anc_feerate.IsEmpty());
  ------------------
  |  |   97|  8.64k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  559|  8.64k|                anc_to_add -= m_depgraph.Ancestors(first);
  560|  8.64k|            }
  561|       |            // Add in other ancestors (which necessarily include i itself).
  562|  34.1k|            Assume(anc_to_add[i]);
  ------------------
  |  |   97|  34.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  563|  34.1k|            anc_feerate += m_depgraph.FeeRate(anc_to_add);
  564|       |            // Store the result.
  565|  34.1k|            m_ancestor_set_feerates[i] = anc_feerate;
  566|  34.1k|        }
  567|  2.44k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE7AllDoneEv:
  590|  47.1k|    {
  591|  47.1k|        return m_todo.None();
  592|  47.1k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE12NumRemainingEv:
  596|  23.5k|    {
  597|  23.5k|        return m_todo.Count();
  598|  23.5k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEv:
  606|  23.5k|    {
  607|  23.5k|        Assume(!AllDone());
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  608|  23.5k|        std::optional<ClusterIndex> best;
  609|   281k|        for (auto i : m_todo) {
  ------------------
  |  Branch (609:21): [True: 281k, False: 23.5k]
  ------------------
  610|   281k|            if (best.has_value()) {
  ------------------
  |  Branch (610:17): [True: 258k, False: 23.5k]
  ------------------
  611|   258k|                Assume(!m_ancestor_set_feerates[i].IsEmpty());
  ------------------
  |  |   97|   258k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  612|   258k|                if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue;
  ------------------
  |  Branch (612:21): [True: 225k, False: 32.7k]
  ------------------
  613|   258k|            }
  614|  56.3k|            best = i;
  615|  56.3k|        }
  616|  23.5k|        Assume(best.has_value());
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  617|  23.5k|        return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]};
  618|  23.5k|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKS3_RK7FeeFrac:
  327|   179k|    SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateERKS3_:
  247|   492k|    {
  248|   492k|        FeeFrac ret;
  249|   492k|        for (auto pos : elems) ret += entries[pos].feerate;
  ------------------
  |  Branch (249:23): [True: 437k, False: 492k]
  ------------------
  250|   492k|        return ret;
  251|   492k|    }
_ZN17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
  576|  23.5k|    {
  577|  23.5k|        Assume(select.Any());
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  578|  23.5k|        Assume(select.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  579|  23.5k|        m_todo -= select;
  580|  34.1k|        for (auto i : select) {
  ------------------
  |  Branch (580:21): [True: 34.1k, False: 23.5k]
  ------------------
  581|  34.1k|            auto feerate = m_depgraph.FeeRate(i);
  582|  34.1k|            for (auto j : m_depgraph.Descendants(i) & m_todo) {
  ------------------
  |  Branch (582:25): [True: 15.6k, False: 34.1k]
  ------------------
  583|  15.6k|                m_ancestor_set_feerates[j] -= feerate;
  584|  15.6k|            }
  585|  34.1k|        }
  586|  23.5k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEm:
  670|  2.44k|        m_rng(rng_seed),
  671|  2.44k|        m_sorted_to_original(depgraph.TxCount()),
  672|  2.44k|        m_original_to_sorted(depgraph.PositionRange())
  673|  2.44k|    {
  674|       |        // Determine reordering mapping, by sorting by decreasing feerate. Unused positions are
  675|       |        // not included, as they will never be looked up anyway.
  676|  2.44k|        ClusterIndex sorted_pos{0};
  677|  34.1k|        for (auto i : depgraph.Positions()) {
  ------------------
  |  Branch (677:21): [True: 34.1k, False: 2.44k]
  ------------------
  678|  34.1k|            m_sorted_to_original[sorted_pos++] = i;
  679|  34.1k|        }
  680|  2.44k|        std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) {
  681|  2.44k|            auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b);
  682|  2.44k|            if (feerate_cmp == 0) return a < b;
  683|  2.44k|            return feerate_cmp > 0;
  684|  2.44k|        });
  685|       |        // Compute reverse mapping.
  686|  36.6k|        for (ClusterIndex i = 0; i < m_sorted_to_original.size(); ++i) {
  ------------------
  |  Branch (686:34): [True: 34.1k, False: 2.44k]
  ------------------
  687|  34.1k|            m_original_to_sorted[m_sorted_to_original[i]] = i;
  688|  34.1k|        }
  689|       |        // Compute reordered dependency graph.
  690|  2.44k|        m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted, m_sorted_to_original.size());
  691|  2.44k|        m_todo = m_sorted_depgraph.Positions();
  692|  2.44k|    }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEEC1ERKNS_8DepGraphIS3_EEmENKUlT_T0_E_clIjjEEDaS9_SA_:
  680|  1.01M|        std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) {
  681|  1.01M|            auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b);
  682|  1.01M|            if (feerate_cmp == 0) return a < b;
  ------------------
  |  Branch (682:17): [True: 424k, False: 593k]
  ------------------
  683|   593k|            return feerate_cmp > 0;
  684|  1.01M|        });
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE7AllDoneEv:
  696|  23.5k|    {
  697|  23.5k|        return m_todo.None();
  698|  23.5k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EE:
  718|  23.5k|    {
  719|  23.5k|        Assume(!AllDone());
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  720|       |
  721|       |        // Convert the provided best to internal sorted indices.
  722|  23.5k|        best.transactions = OriginalToSorted(best.transactions);
  723|       |
  724|       |        /** Type for work queue items. */
  725|  23.5k|        struct WorkItem
  726|  23.5k|        {
  727|       |            /** Set of transactions definitely included (and its feerate). This must be a subset
  728|       |             *  of m_todo, and be topologically valid (includes all in-m_todo ancestors of
  729|       |             *  itself). */
  730|  23.5k|            SetInfo<SetType> inc;
  731|       |            /** Set of undecided transactions. This must be a subset of m_todo, and have no overlap
  732|       |             *  with inc. The set (inc | und) must be topologically valid. */
  733|  23.5k|            SetType und;
  734|       |            /** (Only when inc is not empty) The best feerate of any superset of inc that is also a
  735|       |             *  subset of (inc | und), without requiring it to be topologically valid. It forms a
  736|       |             *  conservative upper bound on how good a set this work item can give rise to.
  737|       |             *  Transactions whose feerate is below best's are ignored when determining this value,
  738|       |             *  which means it may technically be an underestimate, but if so, this work item
  739|       |             *  cannot result in something that beats best anyway. */
  740|  23.5k|            FeeFrac pot_feerate;
  741|       |
  742|       |            /** Construct a new work item. */
  743|  23.5k|            WorkItem(SetInfo<SetType>&& i, SetType&& u, FeeFrac&& p_f) noexcept :
  744|  23.5k|                inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
  745|  23.5k|            {
  746|  23.5k|                Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
  747|  23.5k|            }
  748|       |
  749|       |            /** Swap two WorkItems. */
  750|  23.5k|            void Swap(WorkItem& other) noexcept
  751|  23.5k|            {
  752|  23.5k|                swap(inc, other.inc);
  753|  23.5k|                swap(und, other.und);
  754|  23.5k|                swap(pot_feerate, other.pot_feerate);
  755|  23.5k|            }
  756|  23.5k|        };
  757|       |
  758|       |        /** The queue of work items. */
  759|  23.5k|        VecDeque<WorkItem> queue;
  760|  23.5k|        queue.reserve(std::max<size_t>(256, 2 * m_todo.Count()));
  761|       |
  762|       |        // Create initial entries per connected component of m_todo. While clusters themselves are
  763|       |        // generally connected, this is not necessarily true after some parts have already been
  764|       |        // removed from m_todo. Without this, effort can be wasted on searching "inc" sets that
  765|       |        // span multiple components.
  766|  23.5k|        auto to_cover = m_todo;
  767|   214k|        do {
  768|   214k|            auto component = m_sorted_depgraph.FindConnectedComponent(to_cover);
  769|   214k|            to_cover -= component;
  770|       |            // If best is not provided, set it to the first component, so that during the work
  771|       |            // processing loop below, and during the add_fn/split_fn calls, we do not need to deal
  772|       |            // with the best=empty case.
  773|   214k|            if (best.feerate.IsEmpty()) best = SetInfo(m_sorted_depgraph, component);
  ------------------
  |  Branch (773:17): [True: 0, False: 214k]
  ------------------
  774|   214k|            queue.emplace_back(/*inc=*/SetInfo<SetType>{},
  775|   214k|                               /*und=*/std::move(component),
  776|   214k|                               /*pot_feerate=*/FeeFrac{});
  777|   214k|        } while (to_cover.Any());
  ------------------
  |  Branch (777:18): [True: 191k, False: 23.5k]
  ------------------
  778|       |
  779|       |        /** Local copy of the iteration limit. */
  780|  23.5k|        uint64_t iterations_left = max_iterations;
  781|       |
  782|       |        /** The set of transactions in m_todo which have feerate > best's. */
  783|  23.5k|        SetType imp = m_todo;
  784|   289k|        while (imp.Any()) {
  ------------------
  |  Branch (784:16): [True: 270k, False: 19.4k]
  ------------------
  785|   270k|            ClusterIndex check = imp.Last();
  786|   270k|            if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  ------------------
  |  Branch (786:17): [True: 4.15k, False: 266k]
  ------------------
  787|   266k|            imp.Reset(check);
  788|   266k|        }
  789|       |
  790|       |        /** Internal function to add an item to the queue of elements to explore if there are any
  791|       |         *  transactions left to split on, possibly improving it before doing so, and to update
  792|       |         *  best/imp.
  793|       |         *
  794|       |         * - inc: the "inc" value for the new work item (must be topological).
  795|       |         * - und: the "und" value for the new work item ((inc | und) must be topological).
  796|       |         */
  797|  23.5k|        auto add_fn = [&](SetInfo<SetType> inc, SetType und) noexcept {
  798|       |            /** SetInfo object with the set whose feerate will become the new work item's
  799|       |             *  pot_feerate. It starts off equal to inc. */
  800|  23.5k|            auto pot = inc;
  801|  23.5k|            if (!inc.feerate.IsEmpty()) {
  802|       |                // Add entries to pot. We iterate over all undecided transactions whose feerate is
  803|       |                // higher than best. While undecided transactions of lower feerate may improve pot,
  804|       |                // the resulting pot feerate cannot possibly exceed best's (and this item will be
  805|       |                // skipped in split_fn anyway).
  806|  23.5k|                for (auto pos : imp & und) {
  807|       |                    // Determine if adding transaction pos to pot (ignoring topology) would improve
  808|       |                    // it. If not, we're done updating pot. This relies on the fact that
  809|       |                    // m_sorted_depgraph, and thus the transactions iterated over, are in decreasing
  810|       |                    // individual feerate order.
  811|  23.5k|                    if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
  812|  23.5k|                    pot.Set(m_sorted_depgraph, pos);
  813|  23.5k|                }
  814|       |
  815|       |                // The "jump ahead" optimization: whenever pot has a topologically-valid subset,
  816|       |                // that subset can be added to inc. Any subset of (pot - inc) has the property that
  817|       |                // its feerate exceeds that of any set compatible with this work item (superset of
  818|       |                // inc, subset of (inc | und)). Thus, if T is a topological subset of pot, and B is
  819|       |                // the best topologically-valid set compatible with this work item, and (T - B) is
  820|       |                // non-empty, then (T | B) is better than B and also topological. This is in
  821|       |                // contradiction with the assumption that B is best. Thus, (T - B) must be empty,
  822|       |                // or T must be a subset of B.
  823|       |                //
  824|       |                // See https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303 section 2.4.
  825|  23.5k|                const auto init_inc = inc.transactions;
  826|  23.5k|                for (auto pos : pot.transactions - inc.transactions) {
  827|       |                    // If the transaction's ancestors are a subset of pot, we can add it together
  828|       |                    // with its ancestors to inc. Just update the transactions here; the feerate
  829|       |                    // update happens below.
  830|  23.5k|                    auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
  831|  23.5k|                    if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
  832|  23.5k|                }
  833|       |                // Finally update und and inc's feerate to account for the added transactions.
  834|  23.5k|                und -= inc.transactions;
  835|  23.5k|                inc.feerate += m_sorted_depgraph.FeeRate(inc.transactions - init_inc);
  836|       |
  837|       |                // If inc's feerate is better than best's, remember it as our new best.
  838|  23.5k|                if (inc.feerate > best.feerate) {
  839|  23.5k|                    best = inc;
  840|       |                    // See if we can remove any entries from imp now.
  841|  23.5k|                    while (imp.Any()) {
  842|  23.5k|                        ClusterIndex check = imp.Last();
  843|  23.5k|                        if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  844|  23.5k|                        imp.Reset(check);
  845|  23.5k|                    }
  846|  23.5k|                }
  847|       |
  848|       |                // If no potential transactions exist beyond the already included ones, no
  849|       |                // improvement is possible anymore.
  850|  23.5k|                if (pot.feerate.size == inc.feerate.size) return;
  851|       |                // At this point und must be non-empty. If it were empty then pot would equal inc.
  852|  23.5k|                Assume(und.Any());
  853|  23.5k|            } else {
  854|  23.5k|                Assume(inc.transactions.None());
  855|       |                // If inc is empty, we just make sure there are undecided transactions left to
  856|       |                // split on.
  857|  23.5k|                if (und.None()) return;
  858|  23.5k|            }
  859|       |
  860|       |            // Actually construct a new work item on the queue. Due to the switch to DFS when queue
  861|       |            // space runs out (see below), we know that no reallocation of the queue should ever
  862|       |            // occur.
  863|  23.5k|            Assume(queue.size() < queue.capacity());
  864|  23.5k|            queue.emplace_back(/*inc=*/std::move(inc),
  865|  23.5k|                               /*und=*/std::move(und),
  866|  23.5k|                               /*pot_feerate=*/std::move(pot.feerate));
  867|  23.5k|        };
  868|       |
  869|       |        /** Internal process function. It takes an existing work item, and splits it in two: one
  870|       |         *  with a particular transaction (and its ancestors) included, and one with that
  871|       |         *  transaction (and its descendants) excluded. */
  872|  23.5k|        auto split_fn = [&](WorkItem&& elem) noexcept {
  873|       |            // Any queue element must have undecided transactions left, otherwise there is nothing
  874|       |            // to explore anymore.
  875|  23.5k|            Assume(elem.und.Any());
  876|       |            // The included and undecided set are all subsets of m_todo.
  877|  23.5k|            Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
  878|       |            // Included transactions cannot be undecided.
  879|  23.5k|            Assume(!elem.inc.transactions.Overlaps(elem.und));
  880|       |            // If pot is empty, then so is inc.
  881|  23.5k|            Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
  882|       |
  883|  23.5k|            const ClusterIndex first = elem.und.First();
  884|  23.5k|            if (!elem.inc.feerate.IsEmpty()) {
  885|       |                // If no undecided transactions remain with feerate higher than best, this entry
  886|       |                // cannot be improved beyond best.
  887|  23.5k|                if (!elem.und.Overlaps(imp)) return;
  888|       |                // We can ignore any queue item whose potential feerate isn't better than the best
  889|       |                // seen so far.
  890|  23.5k|                if (elem.pot_feerate <= best.feerate) return;
  891|  23.5k|            } else {
  892|       |                // In case inc is empty use a simpler alternative check.
  893|  23.5k|                if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
  894|  23.5k|            }
  895|       |
  896|       |            // Decide which transaction to split on. Splitting is how new work items are added, and
  897|       |            // how progress is made. One split transaction is chosen among the queue item's
  898|       |            // undecided ones, and:
  899|       |            // - A work item is (potentially) added with that transaction plus its remaining
  900|       |            //   descendants excluded (removed from the und set).
  901|       |            // - A work item is (potentially) added with that transaction plus its remaining
  902|       |            //   ancestors included (added to the inc set).
  903|       |            //
  904|       |            // To decide what to split on, consider the undecided ancestors of the highest
  905|       |            // individual feerate undecided transaction. Pick the one which reduces the search space
  906|       |            // most. Let I(t) be the size of the undecided set after including t, and E(t) the size
  907|       |            // of the undecided set after excluding t. Then choose the split transaction t such
  908|       |            // that 2^I(t) + 2^E(t) is minimal, tie-breaking by highest individual feerate for t.
  909|  23.5k|            ClusterIndex split = 0;
  910|  23.5k|            const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
  911|  23.5k|            Assume(select.Any());
  912|  23.5k|            std::optional<std::pair<ClusterIndex, ClusterIndex>> split_counts;
  913|  23.5k|            for (auto t : select) {
  914|       |                // Call max = max(I(t), E(t)) and min = min(I(t), E(t)). Let counts = {max,min}.
  915|       |                // Sorting by the tuple counts is equivalent to sorting by 2^I(t) + 2^E(t). This
  916|       |                // expression is equal to 2^max + 2^min = 2^max * (1 + 1/2^(max - min)). The second
  917|       |                // factor (1 + 1/2^(max - min)) there is in (1,2]. Thus increasing max will always
  918|       |                // increase it, even when min decreases. Because of this, we can first sort by max.
  919|  23.5k|                std::pair<ClusterIndex, ClusterIndex> counts{
  920|  23.5k|                    (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
  921|  23.5k|                    (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
  922|  23.5k|                if (counts.first < counts.second) std::swap(counts.first, counts.second);
  923|       |                // Remember the t with the lowest counts.
  924|  23.5k|                if (!split_counts.has_value() || counts < *split_counts) {
  925|  23.5k|                    split = t;
  926|  23.5k|                    split_counts = counts;
  927|  23.5k|                }
  928|  23.5k|            }
  929|       |            // Since there was at least one transaction in select, we must always find one.
  930|  23.5k|            Assume(split_counts.has_value());
  931|       |
  932|       |            // Add a work item corresponding to exclusion of the split transaction.
  933|  23.5k|            const auto& desc = m_sorted_depgraph.Descendants(split);
  934|  23.5k|            add_fn(/*inc=*/elem.inc,
  935|  23.5k|                   /*und=*/elem.und - desc);
  936|       |
  937|       |            // Add a work item corresponding to inclusion of the split transaction.
  938|  23.5k|            const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
  939|  23.5k|            add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
  940|  23.5k|                   /*und=*/elem.und - anc);
  941|       |
  942|       |            // Account for the performed split.
  943|  23.5k|            --iterations_left;
  944|  23.5k|        };
  945|       |
  946|       |        // Work processing loop.
  947|       |        //
  948|       |        // New work items are always added at the back of the queue, but items to process use a
  949|       |        // hybrid approach where they can be taken from the front or the back.
  950|       |        //
  951|       |        // Depth-first search (DFS) corresponds to always taking from the back of the queue. This
  952|       |        // is very memory-efficient (linear in the number of transactions). Breadth-first search
  953|       |        // (BFS) corresponds to always taking from the front, which potentially uses more memory
  954|       |        // (up to exponential in the transaction count), but seems to work better in practice.
  955|       |        //
  956|       |        // The approach here combines the two: use BFS (plus random swapping) until the queue grows
  957|       |        // too large, at which point we temporarily switch to DFS until the size shrinks again.
  958|   358k|        while (!queue.empty()) {
  ------------------
  |  Branch (958:16): [True: 334k, False: 23.5k]
  ------------------
  959|       |            // Randomly swap the first two items to randomize the search order.
  960|   334k|            if (queue.size() > 1 && m_rng.randbool()) {
  ------------------
  |  Branch (960:17): [True: 307k, False: 26.7k]
  |  Branch (960:37): [True: 154k, False: 153k]
  ------------------
  961|   154k|                queue[0].Swap(queue[1]);
  962|   154k|            }
  963|       |
  964|       |            // Processing the first queue item, and then using DFS for everything it gives rise to,
  965|       |            // may increase the queue size by the number of undecided elements in there, minus 1
  966|       |            // for the first queue item being removed. Thus, only when that pushes the queue over
  967|       |            // its capacity can we not process from the front (BFS), and should we use DFS.
  968|   405k|            while (queue.size() - 1 + queue.front().und.Count() > queue.capacity()) {
  ------------------
  |  Branch (968:20): [True: 70.6k, False: 334k]
  ------------------
  969|  70.6k|                if (!iterations_left) break;
  ------------------
  |  Branch (969:21): [True: 0, False: 70.6k]
  ------------------
  970|  70.6k|                auto elem = queue.back();
  971|  70.6k|                queue.pop_back();
  972|  70.6k|                split_fn(std::move(elem));
  973|  70.6k|            }
  974|       |
  975|       |            // Process one entry from the front of the queue (BFS exploration)
  976|   334k|            if (!iterations_left) break;
  ------------------
  |  Branch (976:17): [True: 0, False: 334k]
  ------------------
  977|   334k|            auto elem = queue.front();
  978|   334k|            queue.pop_front();
  979|   334k|            split_fn(std::move(elem));
  980|   334k|        }
  981|       |
  982|       |        // Return the found best set (converted to the original transaction indices), and the
  983|       |        // number of iterations performed.
  984|  23.5k|        best.transactions = SortedToOriginal(best.transactions);
  985|  23.5k|        return {std::move(best), max_iterations - iterations_left};
  986|  23.5k|    }
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16OriginalToSortedERKS3_:
  655|  44.7k|    {
  656|  44.7k|        SetType ret;
  657|  60.5k|        for (auto pos : arg) ret.Set(m_original_to_sorted[pos]);
  ------------------
  |  Branch (657:23): [True: 60.5k, False: 44.7k]
  ------------------
  658|  44.7k|        return ret;
  659|  44.7k|    }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEEN8WorkItemC2EOS6_OS3_O7FeeFrac:
  744|   405k|                inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
  745|   405k|            {
  746|   405k|                Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
  ------------------
  |  |   97|   405k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  747|   405k|            }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEEN8WorkItem4SwapERS7_:
  751|   154k|            {
  752|   154k|                swap(inc, other.inc);
  753|   154k|                swap(und, other.und);
  754|   154k|                swap(pot_feerate, other.pot_feerate);
  755|   154k|            }
_ZN17cluster_linearize4swapERNS_7SetInfoIN13bitset_detail9IntBitSetIjEEEES5_:
  363|   154k|    {
  364|   154k|        swap(a.transactions, b.transactions);
  365|   154k|        swap(a.feerate, b.feerate);
  366|   154k|    }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEENKUlOZNS4_16FindCandidateSetEmS6_E8WorkItemE_clES8_:
  872|   405k|        auto split_fn = [&](WorkItem&& elem) noexcept {
  873|       |            // Any queue element must have undecided transactions left, otherwise there is nothing
  874|       |            // to explore anymore.
  875|   405k|            Assume(elem.und.Any());
  ------------------
  |  |   97|   405k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  876|       |            // The included and undecided set are all subsets of m_todo.
  877|   405k|            Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
  ------------------
  |  |   97|   810k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 405k, False: 0]
  |  |  |  Branch (97:51): [True: 405k, False: 0]
  |  |  ------------------
  ------------------
  878|       |            // Included transactions cannot be undecided.
  879|   405k|            Assume(!elem.inc.transactions.Overlaps(elem.und));
  ------------------
  |  |   97|   405k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  880|       |            // If pot is empty, then so is inc.
  881|   405k|            Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
  ------------------
  |  |   97|   405k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  882|       |
  883|   405k|            const ClusterIndex first = elem.und.First();
  884|   405k|            if (!elem.inc.feerate.IsEmpty()) {
  ------------------
  |  Branch (884:17): [True: 181k, False: 223k]
  ------------------
  885|       |                // If no undecided transactions remain with feerate higher than best, this entry
  886|       |                // cannot be improved beyond best.
  887|   181k|                if (!elem.und.Overlaps(imp)) return;
  ------------------
  |  Branch (887:21): [True: 0, False: 181k]
  ------------------
  888|       |                // We can ignore any queue item whose potential feerate isn't better than the best
  889|       |                // seen so far.
  890|   181k|                if (elem.pot_feerate <= best.feerate) return;
  ------------------
  |  Branch (890:21): [True: 35.2k, False: 146k]
  ------------------
  891|   223k|            } else {
  892|       |                // In case inc is empty use a simpler alternative check.
  893|   223k|                if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
  ------------------
  |  Branch (893:21): [True: 214k, False: 9.52k]
  ------------------
  894|   223k|            }
  895|       |
  896|       |            // Decide which transaction to split on. Splitting is how new work items are added, and
  897|       |            // how progress is made. One split transaction is chosen among the queue item's
  898|       |            // undecided ones, and:
  899|       |            // - A work item is (potentially) added with that transaction plus its remaining
  900|       |            //   descendants excluded (removed from the und set).
  901|       |            // - A work item is (potentially) added with that transaction plus its remaining
  902|       |            //   ancestors included (added to the inc set).
  903|       |            //
  904|       |            // To decide what to split on, consider the undecided ancestors of the highest
  905|       |            // individual feerate undecided transaction. Pick the one which reduces the search space
  906|       |            // most. Let I(t) be the size of the undecided set after including t, and E(t) the size
  907|       |            // of the undecided set after excluding t. Then choose the split transaction t such
  908|       |            // that 2^I(t) + 2^E(t) is minimal, tie-breaking by highest individual feerate for t.
  909|   155k|            ClusterIndex split = 0;
  910|   155k|            const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
  911|   155k|            Assume(select.Any());
  ------------------
  |  |   97|   155k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  912|   155k|            std::optional<std::pair<ClusterIndex, ClusterIndex>> split_counts;
  913|   342k|            for (auto t : select) {
  ------------------
  |  Branch (913:25): [True: 342k, False: 155k]
  ------------------
  914|       |                // Call max = max(I(t), E(t)) and min = min(I(t), E(t)). Let counts = {max,min}.
  915|       |                // Sorting by the tuple counts is equivalent to sorting by 2^I(t) + 2^E(t). This
  916|       |                // expression is equal to 2^max + 2^min = 2^max * (1 + 1/2^(max - min)). The second
  917|       |                // factor (1 + 1/2^(max - min)) there is in (1,2]. Thus increasing max will always
  918|       |                // increase it, even when min decreases. Because of this, we can first sort by max.
  919|   342k|                std::pair<ClusterIndex, ClusterIndex> counts{
  920|   342k|                    (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
  921|   342k|                    (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
  922|   342k|                if (counts.first < counts.second) std::swap(counts.first, counts.second);
  ------------------
  |  Branch (922:21): [True: 152k, False: 189k]
  ------------------
  923|       |                // Remember the t with the lowest counts.
  924|   342k|                if (!split_counts.has_value() || counts < *split_counts) {
  ------------------
  |  Branch (924:21): [True: 155k, False: 186k]
  |  Branch (924:50): [True: 4.97k, False: 181k]
  ------------------
  925|   160k|                    split = t;
  926|   160k|                    split_counts = counts;
  927|   160k|                }
  928|   342k|            }
  929|       |            // Since there was at least one transaction in select, we must always find one.
  930|   155k|            Assume(split_counts.has_value());
  ------------------
  |  |   97|   155k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  931|       |
  932|       |            // Add a work item corresponding to exclusion of the split transaction.
  933|   155k|            const auto& desc = m_sorted_depgraph.Descendants(split);
  934|   155k|            add_fn(/*inc=*/elem.inc,
  935|   155k|                   /*und=*/elem.und - desc);
  936|       |
  937|       |            // Add a work item corresponding to inclusion of the split transaction.
  938|   155k|            const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
  939|   155k|            add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
  940|   155k|                   /*und=*/elem.und - anc);
  941|       |
  942|       |            // Account for the performed split.
  943|   155k|            --iterations_left;
  944|   155k|        };
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEENKUlS6_S3_E_clES6_S3_:
  797|   311k|        auto add_fn = [&](SetInfo<SetType> inc, SetType und) noexcept {
  798|       |            /** SetInfo object with the set whose feerate will become the new work item's
  799|       |             *  pot_feerate. It starts off equal to inc. */
  800|   311k|            auto pot = inc;
  801|   311k|            if (!inc.feerate.IsEmpty()) {
  ------------------
  |  Branch (801:17): [True: 302k, False: 9.52k]
  ------------------
  802|       |                // Add entries to pot. We iterate over all undecided transactions whose feerate is
  803|       |                // higher than best. While undecided transactions of lower feerate may improve pot,
  804|       |                // the resulting pot feerate cannot possibly exceed best's (and this item will be
  805|       |                // skipped in split_fn anyway).
  806|   415k|                for (auto pos : imp & und) {
  ------------------
  |  Branch (806:31): [True: 415k, False: 292k]
  ------------------
  807|       |                    // Determine if adding transaction pos to pot (ignoring topology) would improve
  808|       |                    // it. If not, we're done updating pot. This relies on the fact that
  809|       |                    // m_sorted_depgraph, and thus the transactions iterated over, are in decreasing
  810|       |                    // individual feerate order.
  811|   415k|                    if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
  ------------------
  |  Branch (811:25): [True: 9.37k, False: 405k]
  ------------------
  812|   405k|                    pot.Set(m_sorted_depgraph, pos);
  813|   405k|                }
  814|       |
  815|       |                // The "jump ahead" optimization: whenever pot has a topologically-valid subset,
  816|       |                // that subset can be added to inc. Any subset of (pot - inc) has the property that
  817|       |                // its feerate exceeds that of any set compatible with this work item (superset of
  818|       |                // inc, subset of (inc | und)). Thus, if T is a topological subset of pot, and B is
  819|       |                // the best topologically-valid set compatible with this work item, and (T - B) is
  820|       |                // non-empty, then (T | B) is better than B and also topological. This is in
  821|       |                // contradiction with the assumption that B is best. Thus, (T - B) must be empty,
  822|       |                // or T must be a subset of B.
  823|       |                //
  824|       |                // See https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303 section 2.4.
  825|   302k|                const auto init_inc = inc.transactions;
  826|   405k|                for (auto pos : pot.transactions - inc.transactions) {
  ------------------
  |  Branch (826:31): [True: 405k, False: 302k]
  ------------------
  827|       |                    // If the transaction's ancestors are a subset of pot, we can add it together
  828|       |                    // with its ancestors to inc. Just update the transactions here; the feerate
  829|       |                    // update happens below.
  830|   405k|                    auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
  831|   405k|                    if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
  ------------------
  |  Branch (831:25): [True: 7.29k, False: 398k]
  ------------------
  832|   405k|                }
  833|       |                // Finally update und and inc's feerate to account for the added transactions.
  834|   302k|                und -= inc.transactions;
  835|   302k|                inc.feerate += m_sorted_depgraph.FeeRate(inc.transactions - init_inc);
  836|       |
  837|       |                // If inc's feerate is better than best's, remember it as our new best.
  838|   302k|                if (inc.feerate > best.feerate) {
  ------------------
  |  Branch (838:21): [True: 89, False: 302k]
  ------------------
  839|     89|                    best = inc;
  840|       |                    // See if we can remove any entries from imp now.
  841|     89|                    while (imp.Any()) {
  ------------------
  |  Branch (841:28): [True: 89, False: 0]
  ------------------
  842|     89|                        ClusterIndex check = imp.Last();
  843|     89|                        if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  ------------------
  |  Branch (843:29): [True: 89, False: 0]
  ------------------
  844|      0|                        imp.Reset(check);
  845|      0|                    }
  846|     89|                }
  847|       |
  848|       |                // If no potential transactions exist beyond the already included ones, no
  849|       |                // improvement is possible anymore.
  850|   302k|                if (pot.feerate.size == inc.feerate.size) return;
  ------------------
  |  Branch (850:21): [True: 120k, False: 181k]
  ------------------
  851|       |                // At this point und must be non-empty. If it were empty then pot would equal inc.
  852|   181k|                Assume(und.Any());
  ------------------
  |  |   97|   181k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  853|   181k|            } else {
  854|  9.52k|                Assume(inc.transactions.None());
  ------------------
  |  |   97|  9.52k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  855|       |                // If inc is empty, we just make sure there are undecided transactions left to
  856|       |                // split on.
  857|  9.52k|                if (und.None()) return;
  ------------------
  |  Branch (857:21): [True: 460, False: 9.06k]
  ------------------
  858|  9.52k|            }
  859|       |
  860|       |            // Actually construct a new work item on the queue. Due to the switch to DFS when queue
  861|       |            // space runs out (see below), we know that no reallocation of the queue should ever
  862|       |            // occur.
  863|   190k|            Assume(queue.size() < queue.capacity());
  ------------------
  |  |   97|   190k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  864|   190k|            queue.emplace_back(/*inc=*/std::move(inc),
  865|   190k|                               /*und=*/std::move(und),
  866|   190k|                               /*pot_feerate=*/std::move(pot.feerate));
  867|   190k|        };
_ZNK17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEE3AddERKNS_8DepGraphIS3_EERKS3_:
  357|   155k|    {
  358|   155k|        return {transactions | txn, feerate + depgraph.FeeRate(txn - transactions)};
  359|   155k|    }
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16SortedToOriginalERKS3_:
  647|  23.5k|    {
  648|  23.5k|        SetType ret;
  649|  34.1k|        for (auto pos : arg) ret.Set(m_sorted_to_original[pos]);
  ------------------
  |  Branch (649:23): [True: 34.1k, False: 23.5k]
  ------------------
  650|  23.5k|        return ret;
  651|  23.5k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneERKS3_:
  993|  21.1k|    {
  994|  21.1k|        const auto done_sorted = OriginalToSorted(done);
  995|  21.1k|        Assume(done_sorted.Any());
  ------------------
  |  |   97|  21.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  996|  21.1k|        Assume(done_sorted.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  21.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  997|  21.1k|        m_todo -= done_sorted;
  998|  21.1k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EE4SpanIKjE:
  441|  2.44k|        m_depgraph(depgraph), m_linearization(lin)
  442|  2.44k|    {
  443|       |        // Mark everything in lin as todo still.
  444|  34.1k|        for (auto i : m_linearization) m_todo.Set(i);
  ------------------
  |  Branch (444:21): [True: 34.1k, False: 2.44k]
  ------------------
  445|       |        // Compute the initial chunking.
  446|  2.44k|        m_chunks.reserve(depgraph.TxCount());
  447|  2.44k|        BuildChunks();
  448|  2.44k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE11BuildChunksEv:
  412|  5.35k|    {
  413|       |        // Caller must clear m_chunks.
  414|  5.35k|        Assume(m_chunks.empty());
  ------------------
  |  |   97|  5.35k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  415|       |
  416|       |        // Chop off the initial part of m_linearization that is already done.
  417|  5.91k|        while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
  ------------------
  |  Branch (417:16): [True: 5.91k, False: 0]
  |  Branch (417:44): [True: 559, False: 5.35k]
  ------------------
  418|    559|            m_linearization = m_linearization.subspan(1);
  419|    559|        }
  420|       |
  421|       |        // Iterate over the remaining entries in m_linearization. This is effectively the same
  422|       |        // algorithm as ChunkLinearization, but supports skipping parts of the linearization and
  423|       |        // keeps track of the sets themselves instead of just their feerates.
  424|  80.6k|        for (auto idx : m_linearization) {
  ------------------
  |  Branch (424:23): [True: 80.6k, False: 5.35k]
  ------------------
  425|  80.6k|            if (!m_todo[idx]) continue;
  ------------------
  |  Branch (425:17): [True: 12.4k, False: 68.2k]
  ------------------
  426|       |            // Start with an initial chunk containing just element idx.
  427|  68.2k|            SetInfo add(m_depgraph, idx);
  428|       |            // Absorb existing final chunks into add while they have lower feerate.
  429|  81.5k|            while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
  ------------------
  |  Branch (429:20): [True: 71.6k, False: 9.88k]
  |  Branch (429:41): [True: 13.3k, False: 58.3k]
  ------------------
  430|  13.3k|                add |= m_chunks.back();
  431|  13.3k|                m_chunks.pop_back();
  432|  13.3k|            }
  433|       |            // Remember new chunk.
  434|  68.2k|            m_chunks.push_back(std::move(add));
  435|  68.2k|        }
  436|  5.35k|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEj:
  331|  68.2k|        transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEoRERKS4_:
  347|  13.3k|    {
  348|  13.3k|        Assume(!transactions.Overlaps(other.transactions));
  ------------------
  |  |   97|  13.3k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  349|  13.3k|        transactions |= other.transactions;
  350|  13.3k|        feerate += other.feerate;
  351|  13.3k|        return *this;
  352|  13.3k|    }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE13NumChunksLeftEv:
  451|  44.7k|    ClusterIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8GetChunkEj:
  455|  44.7k|    {
  456|  44.7k|        Assume(n + m_chunks_skip < m_chunks.size());
  ------------------
  |  |   97|  44.7k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  457|  44.7k|        return m_chunks[n + m_chunks_skip];
  458|  44.7k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
  462|  21.1k|    {
  463|  21.1k|        Assume(subset.Any());
  ------------------
  |  |   97|  21.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  464|  21.1k|        Assume(subset.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  21.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  465|  21.1k|        m_todo -= subset;
  466|  21.1k|        if (GetChunk(0).transactions == subset) {
  ------------------
  |  Branch (466:13): [True: 18.2k, False: 2.90k]
  ------------------
  467|       |            // If the newly done transactions exactly match the first chunk of the remainder of
  468|       |            // the linearization, we do not need to rechunk; just remember to skip one
  469|       |            // additional chunk.
  470|  18.2k|            ++m_chunks_skip;
  471|       |            // With subset marked done, some prefix of m_linearization will be done now. How long
  472|       |            // that prefix is depends on how many done elements were interspersed with subset,
  473|       |            // but at least as many transactions as there are in subset.
  474|  18.2k|            m_linearization = m_linearization.subspan(subset.Count());
  475|  18.2k|        } else {
  476|       |            // Otherwise rechunk what remains of m_linearization.
  477|  2.90k|            m_chunks.clear();
  478|  2.90k|            m_chunks_skip = 0;
  479|  2.90k|            BuildChunks();
  480|  2.90k|        }
  481|  21.1k|    }
_ZN17cluster_linearize9LinearizeIN13bitset_detail9IntBitSetIjEEEENSt3__14pairINS4_6vectorIjNS4_9allocatorIjEEEEbEERKNS_8DepGraphIT_EEmm4SpanIKjE:
 1020|  2.67k|{
 1021|  2.67k|    Assume(old_linearization.empty() || old_linearization.size() == depgraph.TxCount());
  ------------------
  |  |   97|  5.12k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 232, False: 2.44k]
  |  |  |  Branch (97:51): [True: 2.44k, False: 0]
  |  |  ------------------
  ------------------
 1022|  2.67k|    if (depgraph.TxCount() == 0) return {{}, true};
  ------------------
  |  Branch (1022:9): [True: 232, False: 2.44k]
  ------------------
 1023|       |
 1024|  2.44k|    uint64_t iterations_left = max_iterations;
 1025|  2.44k|    std::vector<ClusterIndex> linearization;
 1026|       |
 1027|  2.44k|    AncestorCandidateFinder anc_finder(depgraph);
 1028|  2.44k|    std::optional<SearchCandidateFinder<SetType>> src_finder;
 1029|  2.44k|    linearization.reserve(depgraph.TxCount());
 1030|  2.44k|    bool optimal = true;
 1031|       |
 1032|       |    // Treat the initialization of SearchCandidateFinder as taking N^2/64 (rounded up) iterations
 1033|       |    // (largely due to the cost of constructing the internal sorted-by-feerate DepGraph inside
 1034|       |    // SearchCandidateFinder), a rough approximation based on benchmark. If we don't have that
 1035|       |    // many, don't start it.
 1036|  2.44k|    uint64_t start_iterations = (uint64_t{depgraph.TxCount()} * depgraph.TxCount() + 63) / 64;
 1037|  2.44k|    if (iterations_left > start_iterations) {
  ------------------
  |  Branch (1037:9): [True: 2.44k, False: 0]
  ------------------
 1038|  2.44k|        iterations_left -= start_iterations;
 1039|  2.44k|        src_finder.emplace(depgraph, rng_seed);
 1040|  2.44k|    }
 1041|       |
 1042|       |    /** Chunking of what remains of the old linearization. */
 1043|  2.44k|    LinearizationChunking old_chunking(depgraph, old_linearization);
 1044|       |
 1045|  23.5k|    while (true) {
  ------------------
  |  Branch (1045:12): [Folded - Ignored]
  ------------------
 1046|       |        // Find the highest-feerate prefix of the remainder of old_linearization.
 1047|  23.5k|        SetInfo<SetType> best_prefix;
 1048|  23.5k|        if (old_chunking.NumChunksLeft()) best_prefix = old_chunking.GetChunk(0);
  ------------------
  |  Branch (1048:13): [True: 23.5k, False: 0]
  ------------------
 1049|       |
 1050|       |        // Then initialize best to be either the best remaining ancestor set, or the first chunk.
 1051|  23.5k|        auto best = anc_finder.FindCandidateSet();
 1052|  23.5k|        if (!best_prefix.feerate.IsEmpty() && best_prefix.feerate >= best.feerate) best = best_prefix;
  ------------------
  |  Branch (1052:13): [True: 23.5k, False: 0]
  |  Branch (1052:47): [True: 20.7k, False: 2.83k]
  ------------------
 1053|       |
 1054|  23.5k|        uint64_t iterations_done_now = 0;
 1055|  23.5k|        uint64_t max_iterations_now = 0;
 1056|  23.5k|        if (src_finder) {
  ------------------
  |  Branch (1056:13): [True: 23.5k, False: 0]
  ------------------
 1057|       |            // Treat the invocation of SearchCandidateFinder::FindCandidateSet() as costing N/4
 1058|       |            // up-front (rounded up) iterations (largely due to the cost of connected-component
 1059|       |            // splitting), a rough approximation based on benchmarks.
 1060|  23.5k|            uint64_t base_iterations = (anc_finder.NumRemaining() + 3) / 4;
 1061|  23.5k|            if (iterations_left > base_iterations) {
  ------------------
  |  Branch (1061:17): [True: 23.5k, False: 0]
  ------------------
 1062|       |                // Invoke bounded search to update best, with up to half of our remaining
 1063|       |                // iterations as limit.
 1064|  23.5k|                iterations_left -= base_iterations;
 1065|  23.5k|                max_iterations_now = (iterations_left + 1) / 2;
 1066|  23.5k|                std::tie(best, iterations_done_now) = src_finder->FindCandidateSet(max_iterations_now, best);
 1067|  23.5k|                iterations_left -= iterations_done_now;
 1068|  23.5k|            }
 1069|  23.5k|        }
 1070|       |
 1071|  23.5k|        if (iterations_done_now == max_iterations_now) {
  ------------------
  |  Branch (1071:13): [True: 0, False: 23.5k]
  ------------------
 1072|      0|            optimal = false;
 1073|       |            // If the search result is not (guaranteed to be) optimal, run intersections to make
 1074|       |            // sure we don't pick something that makes us unable to reach further diagram points
 1075|       |            // of the old linearization.
 1076|      0|            if (old_chunking.NumChunksLeft() > 0) {
  ------------------
  |  Branch (1076:17): [True: 0, False: 0]
  ------------------
 1077|      0|                best = old_chunking.IntersectPrefixes(best);
 1078|      0|            }
 1079|      0|        }
 1080|       |
 1081|       |        // Add to output in topological order.
 1082|  23.5k|        depgraph.AppendTopo(linearization, best.transactions);
 1083|       |
 1084|       |        // Update state to reflect best is no longer to be linearized.
 1085|  23.5k|        anc_finder.MarkDone(best.transactions);
 1086|  23.5k|        if (anc_finder.AllDone()) break;
  ------------------
  |  Branch (1086:13): [True: 2.44k, False: 21.1k]
  ------------------
 1087|  21.1k|        if (src_finder) src_finder->MarkDone(best.transactions);
  ------------------
  |  Branch (1087:13): [True: 21.1k, False: 0]
  ------------------
 1088|  21.1k|        if (old_chunking.NumChunksLeft() > 0) {
  ------------------
  |  Branch (1088:13): [True: 21.1k, False: 0]
  ------------------
 1089|  21.1k|            old_chunking.MarkDone(best.transactions);
 1090|  21.1k|        }
 1091|  21.1k|    }
 1092|       |
 1093|  2.44k|    return {std::move(linearization), optimal};
 1094|  2.67k|}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_:
  302|  23.5k|    {
  303|  23.5k|        ClusterIndex old_len = list.size();
  304|  34.1k|        for (auto i : select) list.push_back(i);
  ------------------
  |  Branch (304:21): [True: 34.1k, False: 23.5k]
  ------------------
  305|  23.5k|        std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
  306|  23.5k|            const auto a_anc_count = entries[a].ancestors.Count();
  307|  23.5k|            const auto b_anc_count = entries[b].ancestors.Count();
  308|  23.5k|            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
  309|  23.5k|            return a < b;
  310|  23.5k|        });
  311|  23.5k|    }
_ZZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_ENKUljjE_clEjj:
  305|   292k|        std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
  306|   292k|            const auto a_anc_count = entries[a].ancestors.Count();
  307|   292k|            const auto b_anc_count = entries[b].ancestors.Count();
  308|   292k|            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
  ------------------
  |  Branch (308:17): [True: 187k, False: 105k]
  ------------------
  309|   105k|            return a < b;
  310|   292k|        });
_ZN17cluster_linearize13PostLinearizeIN13bitset_detail9IntBitSetIjEEEEvRKNS_8DepGraphIT_EE4SpanIjE:
 1114|  5.35k|{
 1115|       |    // This algorithm performs a number of passes (currently 2); the even ones operate from back to
 1116|       |    // front, the odd ones from front to back. Each results in an equal-or-better linearization
 1117|       |    // than the one started from.
 1118|       |    // - One pass in either direction guarantees that the resulting chunks are connected.
 1119|       |    // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
 1120|       |    //   guarantee this for graphs where each transaction has at most one child; backward passes
 1121|       |    //   guarantee this for graphs where each transaction has at most one parent).
 1122|       |    // - Starting with a backward pass guarantees the moved-tree property.
 1123|       |    //
 1124|       |    // During an odd (forward) pass, the high-level operation is:
 1125|       |    // - Start with an empty list of groups L=[].
 1126|       |    // - For every transaction i in the old linearization, from front to back:
 1127|       |    //   - Append a new group C=[i], containing just i, to the back of L.
 1128|       |    //   - While L has at least one group before C, and the group immediately before C has feerate
 1129|       |    //     lower than C:
 1130|       |    //     - If C depends on P:
 1131|       |    //       - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
 1132|       |    //     - Otherwise:
 1133|       |    //       - Swap P with C, continuing with the now-moved C.
 1134|       |    // - The output linearization is the concatenation of the groups in L.
 1135|       |    //
 1136|       |    // During even (backward) passes, i iterates from the back to the front of the existing
 1137|       |    // linearization, and new groups are prepended instead of appended to the list L. To enable
 1138|       |    // more code reuse, both passes append groups, but during even passes the meanings of
 1139|       |    // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
 1140|       |    // on output.
 1141|       |    //
 1142|       |    // In the implementation below, the groups are represented by singly-linked lists (pointing
 1143|       |    // from the back to the front), which are themselves organized in a singly-linked circular
 1144|       |    // list (each group pointing to its predecessor, with a special sentinel group at the front
 1145|       |    // that points back to the last group).
 1146|       |    //
 1147|       |    // Information about transaction t is stored in entries[t + 1], while the sentinel is in
 1148|       |    // entries[0].
 1149|       |
 1150|       |    /** Index of the sentinel in the entries array below. */
 1151|  5.35k|    static constexpr ClusterIndex SENTINEL{0};
 1152|       |    /** Indicator that a group has no previous transaction. */
 1153|  5.35k|    static constexpr ClusterIndex NO_PREV_TX{0};
 1154|       |
 1155|       |
 1156|       |    /** Data structure per transaction entry. */
 1157|  5.35k|    struct TxEntry
 1158|  5.35k|    {
 1159|       |        /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
 1160|       |         *  entry of a group. */
 1161|  5.35k|        ClusterIndex prev_tx;
 1162|       |
 1163|       |        // The fields below are only used for transactions that are the last one in a group
 1164|       |        // (referred to as tail transactions below).
 1165|       |
 1166|       |        /** Index of the first transaction in this group, possibly itself. */
 1167|  5.35k|        ClusterIndex first_tx;
 1168|       |        /** Index of the last transaction in the previous group. The first group (the sentinel)
 1169|       |         *  points back to the last group here, making it a singly-linked circular list. */
 1170|  5.35k|        ClusterIndex prev_group;
 1171|       |        /** All transactions in the group. Empty for the sentinel. */
 1172|  5.35k|        SetType group;
 1173|       |        /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
 1174|  5.35k|        SetType deps;
 1175|       |        /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
 1176|  5.35k|        FeeFrac feerate;
 1177|  5.35k|    };
 1178|       |
 1179|       |    // As an example, consider the state corresponding to the linearization [1,0,3,2], with
 1180|       |    // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
 1181|       |    //
 1182|       |    //                                        +-----+
 1183|       |    //                                 0<-P-- | 0 S | ---\     Legend:
 1184|       |    //                                        +-----+    |
 1185|       |    //                                           ^       |     - digit in box: entries index
 1186|       |    //             /--------------F---------+    G       |       (note: one more than tx value)
 1187|       |    //             v                         \   |       |     - S: sentinel group
 1188|       |    //          +-----+        +-----+        +-----+    |          (empty feerate)
 1189|       |    //   0<-P-- | 2   | <--P-- | 1   | <--P-- | 4 T |    |     - T: tail transaction, contains
 1190|       |    //          +-----+        +-----+        +-----+    |          fields beyond prev_tv.
 1191|       |    //                                           ^       |     - P: prev_tx reference
 1192|       |    //                                           G       G     - F: first_tx reference
 1193|       |    //                                           |       |     - G: prev_group reference
 1194|       |    //                                        +-----+    |
 1195|       |    //                                 0<-P-- | 3 T | <--/
 1196|       |    //                                        +-----+
 1197|       |    //                                         ^   |
 1198|       |    //                                         \-F-/
 1199|       |    //
 1200|       |    // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
 1201|       |    // groups [2] and [3,0,1].
 1202|       |
 1203|  5.35k|    std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
 1204|       |
 1205|       |    // Perform two passes over the linearization.
 1206|  16.0k|    for (int pass = 0; pass < 2; ++pass) {
  ------------------
  |  Branch (1206:24): [True: 10.7k, False: 5.35k]
  ------------------
 1207|  10.7k|        int rev = !(pass & 1);
 1208|       |        // Construct a sentinel group, identifying the start of the list.
 1209|  10.7k|        entries[SENTINEL].prev_group = SENTINEL;
 1210|  10.7k|        Assume(entries[SENTINEL].feerate.IsEmpty());
  ------------------
  |  |   97|  10.7k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1211|       |
 1212|       |        // Iterate over all elements in the existing linearization.
 1213|   147k|        for (ClusterIndex i = 0; i < linearization.size(); ++i) {
  ------------------
  |  Branch (1213:34): [True: 136k, False: 10.7k]
  ------------------
 1214|       |            // Even passes are from back to front; odd passes from front to back.
 1215|   136k|            ClusterIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
  ------------------
  |  Branch (1215:46): [True: 68.3k, False: 68.3k]
  ------------------
 1216|       |            // Construct a new group containing just idx. In even passes, the meaning of
 1217|       |            // parent/child and high/low feerate are swapped.
 1218|   136k|            ClusterIndex cur_group = idx + 1;
 1219|   136k|            entries[cur_group].group = SetType::Singleton(idx);
 1220|   136k|            entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
  ------------------
  |  Branch (1220:39): [True: 68.3k, False: 68.3k]
  ------------------
 1221|   136k|            entries[cur_group].feerate = depgraph.FeeRate(idx);
 1222|   136k|            if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
  ------------------
  |  Branch (1222:17): [True: 68.3k, False: 68.3k]
  ------------------
 1223|   136k|            entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
 1224|   136k|            entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
 1225|       |            // Insert the new group at the back of the groups linked list.
 1226|   136k|            entries[cur_group].prev_group = entries[SENTINEL].prev_group;
 1227|   136k|            entries[SENTINEL].prev_group = cur_group;
 1228|       |
 1229|       |            // Start merge/swap cycle.
 1230|   136k|            ClusterIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
 1231|   136k|            ClusterIndex prev_group = entries[cur_group].prev_group;
 1232|       |            // Continue as long as the current group has higher feerate than the previous one.
 1233|   249k|            while (entries[cur_group].feerate >> entries[prev_group].feerate) {
  ------------------
  |  Branch (1233:20): [True: 113k, False: 136k]
  ------------------
 1234|       |                // prev_group/cur_group/next_group refer to (the last transactions of) 3
 1235|       |                // consecutive entries in groups list.
 1236|   113k|                Assume(cur_group == entries[next_group].prev_group);
  ------------------
  |  |   97|   113k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1237|   113k|                Assume(prev_group == entries[cur_group].prev_group);
  ------------------
  |  |   97|   113k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1238|       |                // The sentinel has empty feerate, which is neither higher or lower than other
 1239|       |                // feerates. Thus, the while loop we are in here guarantees that cur_group and
 1240|       |                // prev_group are not the sentinel.
 1241|   113k|                Assume(cur_group != SENTINEL);
  ------------------
  |  |   97|   113k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1242|   113k|                Assume(prev_group != SENTINEL);
  ------------------
  |  |   97|   113k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1243|   113k|                if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
  ------------------
  |  Branch (1243:21): [True: 42.9k, False: 70.0k]
  ------------------
 1244|       |                    // There is a dependency between cur_group and prev_group; merge prev_group
 1245|       |                    // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
 1246|       |                    // but become unused.
 1247|  42.9k|                    entries[cur_group].group |= entries[prev_group].group;
 1248|  42.9k|                    entries[cur_group].deps |= entries[prev_group].deps;
 1249|  42.9k|                    entries[cur_group].feerate += entries[prev_group].feerate;
 1250|       |                    // Make the first of the current group point to the tail of the previous group.
 1251|  42.9k|                    entries[entries[cur_group].first_tx].prev_tx = prev_group;
 1252|       |                    // The first of the previous group becomes the first of the newly-merged group.
 1253|  42.9k|                    entries[cur_group].first_tx = entries[prev_group].first_tx;
 1254|       |                    // The previous group becomes whatever group was before the former one.
 1255|  42.9k|                    prev_group = entries[prev_group].prev_group;
 1256|  42.9k|                    entries[cur_group].prev_group = prev_group;
 1257|  70.0k|                } else {
 1258|       |                    // There is no dependency between cur_group and prev_group; swap them.
 1259|  70.0k|                    ClusterIndex preprev_group = entries[prev_group].prev_group;
 1260|       |                    // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
 1261|       |                    // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
 1262|  70.0k|                    entries[next_group].prev_group = prev_group;
 1263|  70.0k|                    entries[prev_group].prev_group = cur_group;
 1264|  70.0k|                    entries[cur_group].prev_group = preprev_group;
 1265|       |                    // The current group remains the same, but the groups before/after it have
 1266|       |                    // changed.
 1267|  70.0k|                    next_group = prev_group;
 1268|  70.0k|                    prev_group = preprev_group;
 1269|  70.0k|                }
 1270|   113k|            }
 1271|   136k|        }
 1272|       |
 1273|       |        // Convert the entries back to linearization (overwriting the existing one).
 1274|  10.7k|        ClusterIndex cur_group = entries[0].prev_group;
 1275|  10.7k|        ClusterIndex done = 0;
 1276|   104k|        while (cur_group != SENTINEL) {
  ------------------
  |  Branch (1276:16): [True: 93.8k, False: 10.7k]
  ------------------
 1277|  93.8k|            ClusterIndex cur_tx = cur_group;
 1278|       |            // Traverse the transactions of cur_group (from back to front), and write them in the
 1279|       |            // same order during odd passes, and reversed (front to back) in even passes.
 1280|  93.8k|            if (rev) {
  ------------------
  |  Branch (1280:17): [True: 46.6k, False: 47.1k]
  ------------------
 1281|  68.3k|                do {
 1282|  68.3k|                    *(linearization.begin() + (done++)) = cur_tx - 1;
 1283|  68.3k|                    cur_tx = entries[cur_tx].prev_tx;
 1284|  68.3k|                } while (cur_tx != NO_PREV_TX);
  ------------------
  |  Branch (1284:26): [True: 21.7k, False: 46.6k]
  ------------------
 1285|  47.1k|            } else {
 1286|  68.3k|                do {
 1287|  68.3k|                    *(linearization.end() - (++done)) = cur_tx - 1;
 1288|  68.3k|                    cur_tx = entries[cur_tx].prev_tx;
 1289|  68.3k|                } while (cur_tx != NO_PREV_TX);
  ------------------
  |  Branch (1289:26): [True: 21.2k, False: 47.1k]
  ------------------
 1290|  47.1k|            }
 1291|  93.8k|            cur_group = entries[cur_group].prev_group;
 1292|  93.8k|        }
 1293|  10.7k|        Assume(done == linearization.size());
  ------------------
  |  |   97|  10.7k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
 1294|  10.7k|    }
 1295|  5.35k|}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE13PositionRangeEv:
  116|  79.4k|    ClusterIndex PositionRange() const noexcept { return entries.size(); }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE18GetReducedChildrenEj:
  230|  24.7k|    {
  231|  24.7k|        SetType children = Descendants(i);
  232|  24.7k|        children.Reset(i);
  233|  70.5k|        for (auto child : children) {
  ------------------
  |  Branch (233:25): [True: 70.5k, False: 24.7k]
  ------------------
  234|  70.5k|            if (children[child]) {
  ------------------
  |  Branch (234:17): [True: 15.3k, False: 55.1k]
  ------------------
  235|  15.3k|                children -= Descendants(child);
  236|  15.3k|                children.Set(child);
  237|  15.3k|            }
  238|  70.5k|        }
  239|  24.7k|        return children;
  240|  24.7k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE17GetReducedParentsEj:
  209|  77.8k|    {
  210|  77.8k|        SetType parents = Ancestors(i);
  211|  77.8k|        parents.Reset(i);
  212|   198k|        for (auto parent : parents) {
  ------------------
  |  Branch (212:26): [True: 198k, False: 77.8k]
  ------------------
  213|   198k|            if (parents[parent]) {
  ------------------
  |  Branch (213:17): [True: 169k, False: 29.6k]
  ------------------
  214|   169k|                parents -= Ancestors(parent);
  215|   169k|                parents.Set(parent);
  216|   169k|            }
  217|   198k|        }
  218|  77.8k|        return parents;
  219|  77.8k|    }

_Z16le64toh_internalm:
   69|  2.67k|{
   70|       |    if constexpr (std::endian::native == std::endian::big) return internal_bswap_64(little_endian_64bits);
   71|  2.67k|        else return little_endian_64bits;
   72|  2.67k|}

_ZN21InsecureRandomContext10SplitMix64ERm:
  421|  4.89k|    {
  422|  4.89k|        uint64_t z = (seedval += 0x9e3779b97f4a7c15);
  423|  4.89k|        z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
  424|  4.89k|        z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
  425|  4.89k|        return z ^ (z >> 31);
  426|  4.89k|    }
_ZN21InsecureRandomContextC2Em:
  430|  2.44k|        : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {}
_ZN21InsecureRandomContext6rand64Ev:
  440|  6.46k|    {
  441|  6.46k|        uint64_t s0 = m_s0, s1 = m_s1;
  442|  6.46k|        const uint64_t result = std::rotl(s0 + s1, 17) + s0;
  443|  6.46k|        s1 ^= s0;
  444|  6.46k|        m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21);
  445|  6.46k|        m_s1 = std::rotl(s1, 28);
  446|  6.46k|        return result;
  447|  6.46k|    }
_ZN11RandomMixinI21InsecureRandomContextEC2Ev:
  195|  2.44k|    constexpr RandomMixin() noexcept = default;
_ZN11RandomMixinI21InsecureRandomContextE4ImplEv:
  185|   314k|    RandomNumberGenerator auto& Impl() noexcept { return static_cast<T&>(*this); }
_ZN11RandomMixinI21InsecureRandomContextE8randboolEv:
  316|   307k|    bool randbool() noexcept { return Impl().template randbits<1>(); }
_ZN11RandomMixinI21InsecureRandomContextE8randbitsILi1EEEmv:
  231|   307k|    {
  232|   307k|        static_assert(Bits >= 0 && Bits <= 64);
  233|       |        if constexpr (Bits == 64) {
  234|       |            return Impl().rand64();
  235|   307k|        } else {
  236|   307k|            uint64_t ret;
  237|   307k|            if (Bits <= bitbuf_size) {
  ------------------
  |  Branch (237:17): [True: 301k, False: 6.46k]
  ------------------
  238|   301k|                ret = bitbuf;
  239|   301k|                bitbuf >>= Bits;
  240|   301k|                bitbuf_size -= Bits;
  241|   301k|            } else {
  242|  6.46k|                uint64_t gen = Impl().rand64();
  243|  6.46k|                ret = (gen << bitbuf_size) | bitbuf;
  244|  6.46k|                bitbuf = gen >> (Bits - bitbuf_size);
  245|  6.46k|                bitbuf_size = 64 + bitbuf_size - Bits;
  246|  6.46k|            }
  247|   307k|            constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1;
  248|   307k|            return ret & MASK;
  249|   307k|        }
  250|   307k|    }

_ZN15CheckVarIntModeIL10VarIntMode0EmEC2Ev:
  410|   118k|    {
  411|   118k|        static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned<I>::value, "Unsigned type required with mode DEFAULT.");
  412|   118k|        static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed<I>::value, "Signed type required with mode NONNEGATIVE_SIGNED.");
  413|   118k|    }
_ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmEC2ES3_:
  481|   118k|    explicit Wrapper(T obj) : m_object(obj) {}
_ZN15CheckVarIntModeIL10VarIntMode1EiEC2Ev:
  410|  34.8k|    {
  411|  34.8k|        static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned<I>::value, "Unsigned type required with mode DEFAULT.");
  412|  34.8k|        static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed<I>::value, "Signed type required with mode NONNEGATIVE_SIGNED.");
  413|  34.8k|    }
_ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiEC2ES3_:
  481|  34.8k|    explicit Wrapper(T obj) : m_object(obj) {}
cluster_linearize.cpp:_ZL5UsingIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE7WrapperIT_RT0_EOSB_:
  497|  2.67k|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEC2ES8_:
  481|  2.67k|    explicit Wrapper(T obj) : m_object(obj) {}
cluster_linearize.cpp:_Z11UnserializeI10SpanReaderR7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEQ14UnserializableIT0_T_EEvRSE_OSD_:
  762|  2.67k|{
  763|  2.67k|    a.Unserialize(is);
  764|  2.67k|}
cluster_linearize.cpp:_ZN7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEE11UnserializeI10SpanReaderEEvRT_:
  483|  2.67k|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode1EERiEQ14UnserializableIT0_T_EEvRS9_OS8_:
  762|  34.8k|{
  763|  34.8k|    a.Unserialize(is);
  764|  34.8k|}
_ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiE11UnserializeI10SpanReaderEEvRT_:
  483|  34.8k|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_ZN15VarIntFormatterIL10VarIntMode1EE5UnserI10SpanReaderiEEvRT_RT0_:
  514|  34.8k|    {
  515|  34.8k|        v = ReadVarInt<Stream,Mode,typename std::remove_cv<I>::type>(s);
  516|  34.8k|    }
_Z10ReadVarIntI10SpanReaderL10VarIntMode1EiET1_RT_:
  453|  34.8k|{
  454|  34.8k|    CheckVarIntMode<Mode, I>();
  455|  34.8k|    I n = 0;
  456|  38.0k|    while(true) {
  ------------------
  |  Branch (456:11): [Folded - Ignored]
  ------------------
  457|  38.0k|        unsigned char chData = ser_readdata8(is);
  458|  38.0k|        if (n > (std::numeric_limits<I>::max() >> 7)) {
  ------------------
  |  Branch (458:13): [True: 11, False: 38.0k]
  ------------------
  459|     11|           throw std::ios_base::failure("ReadVarInt(): size too large");
  460|     11|        }
  461|  38.0k|        n = (n << 7) | (chData & 0x7F);
  462|  38.0k|        if (chData & 0x80) {
  ------------------
  |  Branch (462:13): [True: 3.19k, False: 34.8k]
  ------------------
  463|  3.19k|            if (n == std::numeric_limits<I>::max()) {
  ------------------
  |  Branch (463:17): [True: 1, False: 3.19k]
  ------------------
  464|      1|                throw std::ios_base::failure("ReadVarInt(): size too large");
  465|      1|            }
  466|  3.19k|            n++;
  467|  34.8k|        } else {
  468|  34.8k|            return n;
  469|  34.8k|        }
  470|  38.0k|    }
  471|  34.8k|}
_Z13ser_readdata8I10SpanReaderEhRT_:
   84|   163k|{
   85|   163k|    uint8_t obj;
   86|   163k|    s.read(AsWritableBytes(Span{&obj, 1}));
   87|   163k|    return obj;
   88|   163k|}
cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode1EERiE7WrapperIT_RT0_EOS6_:
  497|  34.8k|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode0EERmE7WrapperIT_RT0_EOS6_:
  497|   118k|static inline Wrapper<Formatter, T&> Using(T&& t) { return Wrapper<Formatter, T&>(t); }
_Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode0EERmEQ14UnserializableIT0_T_EEvRS9_OS8_:
  762|   118k|{
  763|   118k|    a.Unserialize(is);
  764|   118k|}
_ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmE11UnserializeI10SpanReaderEEvRT_:
  483|   118k|    template<typename Stream> void Unserialize(Stream &s) { Formatter().Unser(s, m_object); }
_ZN15VarIntFormatterIL10VarIntMode0EE5UnserI10SpanReadermEEvRT_RT0_:
  514|   118k|    {
  515|   118k|        v = ReadVarInt<Stream,Mode,typename std::remove_cv<I>::type>(s);
  516|   118k|    }
_Z10ReadVarIntI10SpanReaderL10VarIntMode0EmET1_RT_:
  453|   118k|{
  454|   118k|    CheckVarIntMode<Mode, I>();
  455|   118k|    I n = 0;
  456|   122k|    while(true) {
  ------------------
  |  Branch (456:11): [Folded - Ignored]
  ------------------
  457|   122k|        unsigned char chData = ser_readdata8(is);
  458|   122k|        if (n > (std::numeric_limits<I>::max() >> 7)) {
  ------------------
  |  Branch (458:13): [True: 90, False: 122k]
  ------------------
  459|     90|           throw std::ios_base::failure("ReadVarInt(): size too large");
  460|     90|        }
  461|   122k|        n = (n << 7) | (chData & 0x7F);
  462|   122k|        if (chData & 0x80) {
  ------------------
  |  Branch (462:13): [True: 4.42k, False: 118k]
  ------------------
  463|  4.42k|            if (n == std::numeric_limits<I>::max()) {
  ------------------
  |  Branch (463:17): [True: 34, False: 4.39k]
  ------------------
  464|     34|                throw std::ios_base::failure("ReadVarInt(): size too large");
  465|     34|            }
  466|  4.39k|            n++;
  467|   118k|        } else {
  468|   118k|            return n;
  469|   118k|        }
  470|   122k|    }
  471|   118k|}
_Z11UnserializeI10SpanReaderEvRT_Rm:
  279|  2.67k|template<typename Stream> inline void Unserialize(Stream& s, uint64_t& a) { a = ser_readdata64(s); }
_Z14ser_readdata64I10SpanReaderEmRT_:
  114|  2.67k|{
  115|  2.67k|    uint64_t obj;
  116|  2.67k|    s.read(AsWritableBytes(Span{&obj, 1}));
  117|  2.67k|    return le64toh_internal(obj);
  118|  2.67k|}
_Z11UnserializeI10SpanReaderEvRT_Rh:
  273|  2.67k|template<typename Stream> inline void Unserialize(Stream& s, uint8_t& a ) { a = ser_readdata8(s); }

_ZNK4SpanIKhE4sizeEv:
  187|   166k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIhE4dataEv:
  174|   163k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE4dataEv:
  174|   129k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanISt4byteE4sizeEv:
  187|   591k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanISt4byteE4dataEv:
  174|   129k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE7subspanEm:
  196|   129k|    {
  197|   129k|        ASSERT_IF_DEBUG(size() >= offset);
  198|   129k|        return Span<C>(m_data + offset, m_size - offset);
  199|   129k|    }
_ZNK4SpanIhE10size_bytesEv:
  188|   163k|    constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
_ZNK4SpanImE4dataEv:
  174|  2.67k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanImE10size_bytesEv:
  188|  2.67k|    constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
_ZN4SpanIKhEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|   129k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZN4SpanISt4byteEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|   166k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_Z15AsWritableBytesIhE4SpanISt4byteES0_IT_E:
  264|   163k|{
  265|   163k|    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  266|   163k|}
_ZN4SpanIhEC2IhTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_hEE5valueEiE4typeELi0EEEPS4_m:
  119|   163k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_Z15AsWritableBytesImE4SpanISt4byteES0_IT_E:
  264|  2.67k|{
  265|  2.67k|    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  266|  2.67k|}
_ZN4SpanImEC2ImTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_mEE5valueEiE4typeELi0EEEPS4_m:
  119|  2.67k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZN4SpanIKhEC2INSt3__14spanIS0_Lm18446744073709551615EEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS6_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS7_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS7_EE4sizeEEmEE5valueEDnE4typeE:
  165|  2.67k|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIKjEC2INSt3__16vectorIjNS3_9allocatorIjEEEEEERT_NS3_9enable_ifIXaaaantsr7is_SpanIS8_EE5valuesr3std14is_convertibleIPA_NS3_14remove_pointerIDTcldtclsr3stdE7declvalIS9_EE4dataEEE4typeEPA_S0_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS9_EE4sizeEEmEE5valueEDnE4typeE:
  165|  26.5k|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIK7FeeFracEC2INSt3__16vectorIS0_NS4_9allocatorIS0_EEEEEERT_NS4_9enable_ifIXaaaantsr7is_SpanIS9_EE5valuesr3std14is_convertibleIPA_NS4_14remove_pointerIDTcldtclsr3stdE7declvalISA_EE4dataEEE4typeEPA_S1_EE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalISA_EE4sizeEEmEE5valueEDnE4typeE:
  165|  16.0k|        : m_data(other.data()), m_size(other.size()){}
_ZN4SpanIjEC2INSt3__16vectorIjNS2_9allocatorIjEEEEEERT_NS2_9enable_ifIXaaaantsr7is_SpanIS7_EE5valuesr3std14is_convertibleIPA_NS2_14remove_pointerIDTcldtclsr3stdE7declvalIS8_EE4dataEEE4typeEPA_jEE5valuesr3std14is_convertibleIDTcldtclsr3stdE7declvalIS8_EE4sizeEEmEE5valueEDnE4typeE:
  165|  5.35k|        : m_data(other.data()), m_size(other.size()){}
_ZNK4SpanIKjE4sizeEv:
  187|  24.1k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIKjEixEm:
  191|   165k|    {
  192|   165k|        ASSERT_IF_DEBUG(size() > pos);
  193|   165k|        return m_data[pos];
  194|   165k|    }
_ZNK4SpanIKjE5beginEv:
  175|  26.5k|    constexpr C* begin() const noexcept { return m_data; }
_ZNK4SpanIKjE3endEv:
  176|  26.5k|    constexpr C* end() const noexcept { return m_data + m_size; }
_ZNK4SpanIKjE5emptyEv:
  189|  8.58k|    constexpr bool empty() const noexcept { return size() == 0; }
_ZNK4SpanIKjE5frontEv:
  178|  5.91k|    {
  179|  5.91k|        ASSERT_IF_DEBUG(size() > 0);
  180|  5.91k|        return m_data[0];
  181|  5.91k|    }
_ZNK4SpanIKjE7subspanEm:
  196|  18.7k|    {
  197|  18.7k|        ASSERT_IF_DEBUG(size() >= offset);
  198|  18.7k|        return Span<C>(m_data + offset, m_size - offset);
  199|  18.7k|    }
_ZN4SpanIKjEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|  18.7k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZNK4SpanIjE4sizeEv:
  187|   226k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIjEixEm:
  191|   136k|    {
  192|   136k|        ASSERT_IF_DEBUG(size() > pos);
  193|   136k|        return m_data[pos];
  194|   136k|    }
_ZNK4SpanIjE5beginEv:
  175|  68.3k|    constexpr C* begin() const noexcept { return m_data; }
_ZNK4SpanIjE3endEv:
  176|  68.3k|    constexpr C* end() const noexcept { return m_data + m_size; }
_ZNK4SpanIK7FeeFracE4sizeEv:
  187|   169k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIK7FeeFracEixEm:
  191|   432k|    {
  192|   432k|        ASSERT_IF_DEBUG(size() > pos);
  193|   432k|        return m_data[pos];
  194|   432k|    }

_ZN10SpanReaderC2E4SpanIKhE:
  109|  2.67k|    explicit SpanReader(Span<const unsigned char> data) : m_data{data} {}
_ZN10SpanReader4readE4SpanISt4byteE:
  122|   166k|    {
  123|   166k|        if (dst.size() == 0) {
  ------------------
  |  Branch (123:13): [True: 0, False: 166k]
  ------------------
  124|      0|            return;
  125|      0|        }
  126|       |
  127|       |        // Read from the beginning of the buffer
  128|   166k|        if (dst.size() > m_data.size()) {
  ------------------
  |  Branch (128:13): [True: 36.4k, False: 129k]
  ------------------
  129|  36.4k|            throw std::ios_base::failure("SpanReader::read(): end of data");
  130|  36.4k|        }
  131|   129k|        memcpy(dst.data(), m_data.data(), dst.size());
  132|   129k|        m_data = m_data.subspan(dst.size());
  133|   129k|    }
cluster_linearize.cpp:_ZN10SpanReaderrsI7WrapperIN12_GLOBAL__N_117DepGraphFormatterERN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEEEEERS_OT_:
  113|  2.67k|    {
  114|  2.67k|        ::Unserialize(*this, obj);
  115|  2.67k|        return (*this);
  116|  2.67k|    }
_ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode1EERiEEERS_OT_:
  113|  34.8k|    {
  114|  34.8k|        ::Unserialize(*this, obj);
  115|  34.8k|        return (*this);
  116|  34.8k|    }
_ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode0EERmEEERS_OT_:
  113|   118k|    {
  114|   118k|        ::Unserialize(*this, obj);
  115|   118k|        return (*this);
  116|   118k|    }
_ZN10SpanReaderrsIRmEERS_OT_:
  113|  2.67k|    {
  114|  2.67k|        ::Unserialize(*this, obj);
  115|  2.67k|        return (*this);
  116|  2.67k|    }
_ZN10SpanReaderrsIRhEERS_OT_:
  113|  2.67k|    {
  114|  2.67k|        ::Unserialize(*this, obj);
  115|  2.67k|        return (*this);
  116|  2.67k|    }

_Z41clusterlin_postlinearize_tree_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEE:
  977|  2.67k|{
  978|       |    // Verify expected properties of PostLinearize() on linearizations of graphs that form either
  979|       |    // an upright or reverse tree structure.
  980|       |
  981|       |    // Construct a direction, RNG seed, and an arbitrary graph from the fuzz input.
  982|  2.67k|    SpanReader reader(buffer);
  983|  2.67k|    uint64_t rng_seed{0};
  984|  2.67k|    DepGraph<TestBitSet> depgraph_gen;
  985|  2.67k|    uint8_t direction{0};
  986|  2.67k|    try {
  987|  2.67k|        reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
  988|  2.67k|    } catch (const std::ios_base::failure&) {}
  989|       |
  990|       |    // Now construct a new graph, copying the nodes, but leaving only the first parent (even
  991|       |    // direction) or the first child (odd direction).
  992|  2.67k|    DepGraph<TestBitSet> depgraph_tree;
  993|  61.3k|    for (ClusterIndex i = 0; i < depgraph_gen.PositionRange(); ++i) {
  ------------------
  |  Branch (993:30): [True: 58.6k, False: 2.67k]
  ------------------
  994|  58.6k|        if (depgraph_gen.Positions()[i]) {
  ------------------
  |  Branch (994:13): [True: 34.1k, False: 24.4k]
  ------------------
  995|  34.1k|            depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i));
  996|  34.1k|        } else {
  997|       |            // For holes, add a dummy transaction which is deleted below, so that non-hole
  998|       |            // transactions retain their position.
  999|  24.4k|            depgraph_tree.AddTransaction(FeeFrac{});
 1000|  24.4k|        }
 1001|  58.6k|    }
 1002|  2.67k|    depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions());
 1003|       |
 1004|  2.67k|    if (direction & 1) {
  ------------------
  |  Branch (1004:9): [True: 1.72k, False: 956]
  ------------------
 1005|  26.4k|        for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
  ------------------
  |  Branch (1005:34): [True: 24.7k, False: 1.72k]
  ------------------
 1006|  24.7k|            auto children = depgraph_gen.GetReducedChildren(i);
 1007|  24.7k|            if (children.Any()) {
  ------------------
  |  Branch (1007:17): [True: 10.7k, False: 13.9k]
  ------------------
 1008|  10.7k|                depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First());
 1009|  10.7k|            }
 1010|  24.7k|         }
 1011|  1.72k|    } else {
 1012|  10.4k|        for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) {
  ------------------
  |  Branch (1012:34): [True: 9.48k, False: 956]
  ------------------
 1013|  9.48k|            auto parents = depgraph_gen.GetReducedParents(i);
 1014|  9.48k|            if (parents.Any()) {
  ------------------
  |  Branch (1014:17): [True: 2.63k, False: 6.84k]
  ------------------
 1015|  2.63k|                depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i);
 1016|  2.63k|            }
 1017|  9.48k|        }
 1018|    956|    }
 1019|       |
 1020|       |    // Retrieve a linearization from the fuzz input.
 1021|  2.67k|    std::vector<ClusterIndex> linearization;
 1022|  2.67k|    linearization = ReadLinearization(depgraph_tree, reader);
 1023|  2.67k|    SanityCheck(depgraph_tree, linearization);
 1024|       |
 1025|       |    // Produce a postlinearized version.
 1026|  2.67k|    auto post_linearization = linearization;
 1027|  2.67k|    PostLinearize(depgraph_tree, post_linearization);
 1028|  2.67k|    SanityCheck(depgraph_tree, post_linearization);
 1029|       |
 1030|       |    // Compare diagrams.
 1031|  2.67k|    auto chunking = ChunkLinearization(depgraph_tree, linearization);
 1032|  2.67k|    auto post_chunking = ChunkLinearization(depgraph_tree, post_linearization);
 1033|  2.67k|    auto cmp = CompareChunks(post_chunking, chunking);
 1034|  2.67k|    assert(cmp >= 0);
 1035|       |
 1036|       |    // Verify that post-linearizing again does not change the diagram. The result must be identical
 1037|       |    // as post_linearization ought to be optimal already with a tree-structured graph.
 1038|  2.67k|    auto post_post_linearization = post_linearization;
 1039|  2.67k|    PostLinearize(depgraph_tree, post_linearization);
 1040|  2.67k|    SanityCheck(depgraph_tree, post_linearization);
 1041|  2.67k|    auto post_post_chunking = ChunkLinearization(depgraph_tree, post_post_linearization);
 1042|  2.67k|    auto cmp_post = CompareChunks(post_post_chunking, post_chunking);
 1043|  2.67k|    assert(cmp_post == 0);
 1044|       |
 1045|       |    // Try to find an even better linearization directly. This must not change the diagram for the
 1046|       |    // same reason.
 1047|  2.67k|    auto [opt_linearization, _optimal] = Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
 1048|  2.67k|    auto opt_chunking = ChunkLinearization(depgraph_tree, opt_linearization);
 1049|  2.67k|    auto cmp_opt = CompareChunks(opt_chunking, post_chunking);
 1050|  2.67k|    assert(cmp_opt == 0);
 1051|  2.67k|}
cluster_linearize.cpp:_ZN12_GLOBAL__N_117ReadLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorIjNS4_9allocatorIjEEEERKN17cluster_linearize8DepGraphIT_EER10SpanReader:
  207|  2.67k|{
  208|  2.67k|    std::vector<ClusterIndex> linearization;
  209|  2.67k|    TestBitSet todo = depgraph.Positions();
  210|       |    // In every iteration one topologically-valid transaction is appended to linearization.
  211|  36.8k|    while (todo.Any()) {
  ------------------
  |  Branch (211:12): [True: 34.1k, False: 2.67k]
  ------------------
  212|       |        // Compute the set of transactions with no not-yet-included ancestors.
  213|  34.1k|        TestBitSet potential_next;
  214|   405k|        for (auto j : todo) {
  ------------------
  |  Branch (214:21): [True: 405k, False: 34.1k]
  ------------------
  215|   405k|            if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
  ------------------
  |  Branch (215:17): [True: 290k, False: 114k]
  ------------------
  216|   290k|                potential_next.Set(j);
  217|   290k|            }
  218|   405k|        }
  219|       |        // There must always be one (otherwise there is a cycle in the graph).
  220|  34.1k|        assert(potential_next.Any());
  221|       |        // Read a number from reader, and interpret it as index into potential_next.
  222|  34.1k|        uint64_t idx{0};
  223|  34.1k|        try {
  224|  34.1k|            reader >> VARINT(idx);
  ------------------
  |  |  500|  34.1k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  225|  34.1k|        } catch (const std::ios_base::failure&) {}
  226|  34.1k|        idx %= potential_next.Count();
  227|       |        // Find out which transaction that corresponds to.
  228|  35.0k|        for (auto j : potential_next) {
  ------------------
  |  Branch (228:21): [True: 35.0k, False: 0]
  ------------------
  229|  35.0k|            if (idx == 0) {
  ------------------
  |  Branch (229:17): [True: 34.1k, False: 859]
  ------------------
  230|       |                // When found, add it to linearization and remove it from todo.
  231|  34.1k|                linearization.push_back(j);
  232|  34.1k|                assert(todo[j]);
  233|  34.1k|                todo.Reset(j);
  234|  34.1k|                break;
  235|  34.1k|            }
  236|    859|            --idx;
  237|    859|        }
  238|  34.1k|    }
  239|  2.67k|    return linearization;
  240|  2.67k|}

LLVMFuzzerTestOneInput:
  222|  2.67k|{
  223|  2.67k|    test_one_input({data, size});
  224|  2.67k|    return 0;
  225|  2.67k|}
fuzz.cpp:_ZL14test_one_inputNSt3__14spanIKhLm18446744073709551615EEE:
   83|  2.67k|{
   84|  2.67k|    CheckGlobals check{};
   85|  2.67k|    (*Assert(g_test_one_input))(buffer);
  ------------------
  |  |   85|  2.67k|#define Assert(val) inline_assertion_check<true>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   86|  2.67k|}

_ZN12CheckGlobalsC2Ev:
   56|  2.67k|CheckGlobals::CheckGlobals() : m_impl(std::make_unique<CheckGlobalsImpl>()) {}
_ZN12CheckGlobalsD2Ev:
   57|  2.67k|CheckGlobals::~CheckGlobals() = default;
_ZN16CheckGlobalsImplC2Ev:
   17|  2.67k|    {
   18|  2.67k|        g_used_g_prng = false;
   19|  2.67k|        g_seeded_g_prng_zero = false;
   20|  2.67k|        g_used_system_time = false;
   21|  2.67k|        SetMockTime(0s);
   22|  2.67k|    }
_ZN16CheckGlobalsImplD2Ev:
   24|  2.67k|    {
   25|  2.67k|        if (g_used_g_prng && !g_seeded_g_prng_zero) {
  ------------------
  |  Branch (25:13): [True: 0, False: 2.67k]
  |  Branch (25:30): [True: 0, False: 0]
  ------------------
   26|      0|            std::cerr << "\n\n"
   27|      0|                         "The current fuzz target used the global random state.\n\n"
   28|       |
   29|      0|                         "This is acceptable, but requires the fuzz target to call \n"
   30|      0|                         "SeedRandomStateForTest(SeedRand::ZEROS) in the first line \n"
   31|      0|                         "of the FUZZ_TARGET function.\n\n"
   32|       |
   33|      0|                         "An alternative solution would be to avoid any use of globals.\n\n"
   34|       |
   35|      0|                         "Without a solution, fuzz instability and non-determinism can lead \n"
   36|      0|                         "to non-reproducible bugs or inefficient fuzzing.\n\n"
   37|      0|                      << std::endl;
   38|      0|            std::abort(); // Abort, because AFL may try to recover from a std::exit
   39|      0|        }
   40|       |
   41|  2.67k|        if (g_used_system_time) {
  ------------------
  |  Branch (41:13): [True: 0, False: 2.67k]
  ------------------
   42|      0|            std::cerr << "\n\n"
   43|      0|                         "The current fuzz target accessed system time.\n\n"
   44|       |
   45|      0|                         "This is acceptable, but requires the fuzz target to call \n"
   46|      0|                         "SetMockTime() at the beginning of processing the fuzz input.\n\n"
   47|       |
   48|      0|                         "Without setting mock time, time-dependent behavior can lead \n"
   49|      0|                         "to non-reproducible bugs or inefficient fuzzing.\n\n"
   50|      0|                      << std::endl;
   51|      0|            std::abort();
   52|      0|        }
   53|  2.67k|    }

cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter5UnserI10SpanReaderN13bitset_detail9IntBitSetIjEEEEvRT_RN17cluster_linearize8DepGraphIT0_EE:
  200|  2.67k|    {
  201|       |        /** The dependency graph which we deserialize into first, with transactions in
  202|       |         *  topological serialization order, not original cluster order. */
  203|  2.67k|        DepGraph<SetType> topo_depgraph;
  204|       |        /** Mapping from serialization order to cluster order, used later to reconstruct the
  205|       |         *  cluster order. */
  206|  2.67k|        std::vector<ClusterIndex> reordering;
  207|       |        /** How big the entries vector in the reconstructed depgraph will be (including holes). */
  208|  2.67k|        ClusterIndex total_size{0};
  209|       |
  210|       |        // Read transactions in topological order.
  211|  34.8k|        while (true) {
  ------------------
  |  Branch (211:16): [Folded - Ignored]
  ------------------
  212|  34.8k|            FeeFrac new_feerate; //!< The new transaction's fee and size.
  213|  34.8k|            SetType new_ancestors; //!< The new transaction's ancestors (excluding itself).
  214|  34.8k|            uint64_t diff{0}; //!< How many potential parents/insertions we have to skip.
  215|  34.8k|            bool read_error{false};
  216|  34.8k|            try {
  217|       |                // Read size. Size 0 signifies the end of the DepGraph.
  218|  34.8k|                int32_t size;
  219|  34.8k|                s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED);
  ------------------
  |  |  499|  34.8k|#define VARINT_MODE(obj, mode) Using<VarIntFormatter<mode>>(obj)
  ------------------
  220|  34.8k|                size &= 0x3FFFFF; // Enough for size up to 4M.
  221|  34.8k|                static_assert(0x3FFFFF >= 4000000);
  222|  34.8k|                if (size == 0 || topo_depgraph.TxCount() == SetType::Size()) break;
  ------------------
  |  Branch (222:21): [True: 513, False: 34.3k]
  |  Branch (222:34): [True: 5, False: 34.3k]
  ------------------
  223|       |                // Read fee, encoded as an unsigned varint (odd=negative, even=non-negative).
  224|  34.8k|                uint64_t coded_fee;
  225|  34.8k|                s >> VARINT(coded_fee);
  ------------------
  |  |  500|  34.8k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  226|  34.8k|                coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC.
  227|  34.8k|                static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000);
  228|  34.8k|                new_feerate = {UnsignedToSigned(coded_fee), size};
  229|       |                // Read dependency information.
  230|  34.8k|                auto topo_idx = reordering.size();
  231|  34.8k|                s >> VARINT(diff);
  ------------------
  |  |  500|  34.8k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  232|   382k|                for (ClusterIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) {
  ------------------
  |  Branch (232:49): [True: 347k, False: 34.8k]
  ------------------
  233|       |                    /** Which topo_depgraph index we are currently considering as parent of topo_idx. */
  234|   347k|                    ClusterIndex dep_topo_idx = topo_idx - 1 - dep_dist;
  235|       |                    // Ignore transactions which are already known ancestors of topo_idx.
  236|   347k|                    if (new_ancestors[dep_topo_idx]) continue;
  ------------------
  |  Branch (236:25): [True: 73.0k, False: 274k]
  ------------------
  237|   274k|                    if (diff == 0) {
  ------------------
  |  Branch (237:25): [True: 15.5k, False: 259k]
  ------------------
  238|       |                        // When the skip counter has reached 0, add an actual dependency.
  239|  15.5k|                        new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx);
  240|       |                        // And read the number of skips after it.
  241|  15.5k|                        s >> VARINT(diff);
  ------------------
  |  |  500|  15.5k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  242|   259k|                    } else {
  243|       |                        // Otherwise, dep_topo_idx is not a parent. Decrement and continue.
  244|   259k|                        --diff;
  245|   259k|                    }
  246|   274k|                }
  247|  34.8k|            } catch (const std::ios_base::failure&) {
  248|       |                // Continue even if a read error was encountered.
  249|  2.59k|                read_error = true;
  250|  2.59k|            }
  251|       |            // Construct a new transaction whenever we made it past the new_feerate construction.
  252|  34.8k|            if (new_feerate.IsEmpty()) break;
  ------------------
  |  Branch (252:17): [True: 616, False: 34.1k]
  ------------------
  253|  34.1k|            assert(reordering.size() < SetType::Size());
  254|  34.1k|            auto topo_idx = topo_depgraph.AddTransaction(new_feerate);
  255|  34.1k|            topo_depgraph.AddDependencies(new_ancestors, topo_idx);
  256|  34.1k|            if (total_size < SetType::Size()) {
  ------------------
  |  Branch (256:17): [True: 18.3k, False: 15.8k]
  ------------------
  257|       |                // Normal case.
  258|  18.3k|                diff %= SetType::Size();
  259|  18.3k|                if (diff <= total_size) {
  ------------------
  |  Branch (259:21): [True: 15.1k, False: 3.22k]
  ------------------
  260|       |                    // Insert the new transaction at distance diff back from the end.
  261|   117k|                    for (auto& pos : reordering) {
  ------------------
  |  Branch (261:36): [True: 117k, False: 15.1k]
  ------------------
  262|   117k|                        pos += (pos >= total_size - diff);
  263|   117k|                    }
  264|  15.1k|                    reordering.push_back(total_size++ - diff);
  265|  15.1k|                } else {
  266|       |                    // Append diff - total_size holes at the end, plus the new transaction.
  267|  3.22k|                    total_size = diff;
  268|  3.22k|                    reordering.push_back(total_size++);
  269|  3.22k|                }
  270|  18.3k|            } else {
  271|       |                // In case total_size == SetType::Size, it is not possible to insert the new
  272|       |                // transaction without exceeding SetType's size. Instead, interpret diff as an
  273|       |                // index into the holes, and overwrite a position there. This branch is never used
  274|       |                // when deserializing the output of the serializer, but gives meaning to otherwise
  275|       |                // invalid input.
  276|  15.8k|                diff %= (SetType::Size() - reordering.size());
  277|  15.8k|                SetType holes = SetType::Fill(SetType::Size());
  278|   249k|                for (auto pos : reordering) holes.Reset(pos);
  ------------------
  |  Branch (278:31): [True: 249k, False: 15.8k]
  ------------------
  279|   131k|                for (auto pos : holes) {
  ------------------
  |  Branch (279:31): [True: 131k, False: 0]
  ------------------
  280|   131k|                    if (diff == 0) {
  ------------------
  |  Branch (280:25): [True: 15.8k, False: 115k]
  ------------------
  281|  15.8k|                        reordering.push_back(pos);
  282|  15.8k|                        break;
  283|  15.8k|                    }
  284|   115k|                    --diff;
  285|   115k|                }
  286|  15.8k|            }
  287|       |            // Stop if a read error was encountered during deserialization.
  288|  34.1k|            if (read_error) break;
  ------------------
  |  Branch (288:17): [True: 1.97k, False: 32.2k]
  ------------------
  289|  34.1k|        }
  290|       |
  291|       |        // Construct the original cluster order depgraph.
  292|  2.67k|        depgraph = DepGraph(topo_depgraph, reordering, total_size);
  293|  2.67k|    }
cluster_linearize.cpp:_ZN12_GLOBAL__N_117DepGraphFormatter16UnsignedToSignedEm:
  125|  34.1k|    {
  126|  34.1k|        if (x & 1) {
  ------------------
  |  Branch (126:13): [True: 13.3k, False: 20.8k]
  ------------------
  127|  13.3k|            return -int64_t(x / 2) - 1;
  128|  20.8k|        } else {
  129|  20.8k|            return int64_t(x / 2);
  130|  20.8k|        }
  131|  34.1k|    }
cluster_linearize.cpp:_ZN12_GLOBAL__N_111SanityCheckIN13bitset_detail9IntBitSetIjEEEEvRKN17cluster_linearize8DepGraphIT_EE4SpanIKjE:
  396|  8.03k|{
  397|       |    // Check completeness.
  398|  8.03k|    assert(linearization.size() == depgraph.TxCount());
  399|  8.03k|    TestBitSet done;
  400|   102k|    for (auto i : linearization) {
  ------------------
  |  Branch (400:17): [True: 102k, False: 8.03k]
  ------------------
  401|       |        // Check transaction position is in range.
  402|   102k|        assert(depgraph.Positions()[i]);
  403|       |        // Check topology and lack of duplicates.
  404|   102k|        assert((depgraph.Ancestors(i) - done) == TestBitSet::Singleton(i));
  405|   102k|        done.Set(i);
  406|   102k|    }
  407|  8.03k|}

_ZN13bitset_detail9IntBitSetIjE4SizeEv:
  177|   152k|    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
_ZNK13bitset_detail9IntBitSetIjEixEj:
  170|  1.45M|    {
  171|  1.45M|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  1.45M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  172|  1.45M|        return (m_val >> pos) & 1U;
  173|  1.45M|    }
_ZN13bitset_detail9IntBitSetIjE3SetEj:
  152|  1.30M|    {
  153|  1.30M|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  1.30M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  154|  1.30M|        m_val |= I{1U} << pos;
  155|  1.30M|    }
_ZN13bitset_detail9IntBitSetIjE5ResetEj:
  164|   652k|    {
  165|   652k|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|   652k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  166|   652k|        m_val &= ~I(I{1U} << pos);
  167|   652k|    }
_ZN13bitset_detail9IntBitSetIjE9SingletonEj:
  138|  1.26M|    {
  139|  1.26M|        Assume(i < MAX_SIZE);
  ------------------
  |  |   97|  1.26M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  140|  1.26M|        return IntBitSet(I(1U) << i);
  141|  1.26M|    }
_ZN13bitset_detail9IntBitSetIjEC2Ej:
   71|  5.40M|    IntBitSet(I val) noexcept : m_val{val} {}
_ZNK13bitset_detail9IntBitSetIjE3AnyEv:
  181|  1.97M|    constexpr bool Any() const noexcept { return !None(); }
_ZNK13bitset_detail9IntBitSetIjE4NoneEv:
  179|  2.40M|    constexpr bool None() const noexcept { return m_val == 0; }
_ZNK13bitset_detail9IntBitSetIjE5FirstEv:
  188|   760k|    {
  189|   760k|        Assume(m_val != 0);
  ------------------
  |  |   97|   760k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  190|   760k|        return std::countr_zero(m_val);
  191|   760k|    }
_ZNK13bitset_detail9IntBitSetIjE4LastEv:
  194|   275k|    {
  195|   275k|        Assume(m_val != 0);
  ------------------
  |  |   97|   275k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  196|   275k|        return std::bit_width(m_val) - 1;
  197|   275k|    }
_ZNK13bitset_detail9IntBitSetIjE5CountEv:
  175|  1.87M|    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
_ZN13bitset_detail8PopCountIjEEjT_:
   39|  1.87M|{
   40|  1.87M|    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
   41|  1.87M|    constexpr auto BITS = std::numeric_limits<I>::digits;
   42|       |    // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation.
   43|       |    // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64.
   44|  1.87M|    if constexpr (BITS <= 32) {
   45|  1.87M|        v -= (v >> 1) & 0x55555555;
   46|  1.87M|        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
   47|  1.87M|        v = (v + (v >> 4)) & 0x0f0f0f0f;
   48|  1.87M|        if constexpr (BITS > 8) v += v >> 8;
   49|  1.87M|        if constexpr (BITS > 16) v += v >> 16;
   50|  1.87M|        return v & 0x3f;
   51|       |    } else {
   52|       |        static_assert(BITS <= 64);
   53|       |        v -= (v >> 1) & 0x5555555555555555;
   54|       |        v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
   55|       |        v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f;
   56|       |        return (v * uint64_t{0x0101010101010101}) >> 56;
   57|       |    }
   58|  1.87M|}
_ZN13bitset_detail9IntBitSetIjEC2Ev:
  119|  1.25M|    constexpr IntBitSet() noexcept : m_val{0} {}
_ZN13bitset_detail4swapERNS_9IntBitSetIjEES2_:
  223|   309k|    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
_ZN13bitset_detail9IntBitSetIjE4FillEj:
  144|  18.4k|    {
  145|  18.4k|        IntBitSet ret;
  146|  18.4k|        Assume(count <= MAX_SIZE);
  ------------------
  |  |   97|  18.4k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  147|  18.4k|        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
  ------------------
  |  Branch (147:13): [True: 18.2k, False: 232]
  ------------------
  148|  18.4k|        return ret;
  149|  18.4k|    }
_ZNK13bitset_detail9IntBitSetIjE5beginEv:
  183|  2.33M|    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
_ZN13bitset_detail9IntBitSetIjE8IteratorC2Ej:
   86|  2.33M|        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
   87|  2.33M|        {
   88|  2.33M|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (88:17): [True: 1.58M, False: 752k]
  ------------------
   89|  2.33M|        }
_ZN13bitset_detaileqERKNS_9IntBitSetIjE8IteratorERKNS1_11IteratorEndE:
   98|  6.41M|        {
   99|  6.41M|            return a.m_val == 0;
  100|  6.41M|        }
_ZNK13bitset_detail9IntBitSetIjE3endEv:
  185|  2.33M|    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
_ZNK13bitset_detail9IntBitSetIjE8IteratordeEv:
  111|  4.13M|        {
  112|  4.13M|            Assume(m_val != 0);
  ------------------
  |  |   97|  4.13M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  113|  4.13M|            return m_pos;
  114|  4.13M|        }
_ZN13bitset_detail9IntBitSetIjE8IteratorppEv:
  103|  4.07M|        {
  104|  4.07M|            Assume(m_val != 0);
  ------------------
  |  |   97|  4.07M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  105|  4.07M|            m_val &= m_val - I{1U};
  106|  4.07M|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (106:17): [True: 2.55M, False: 1.52M]
  ------------------
  107|  4.07M|            return *this;
  108|  4.07M|        }
_ZN13bitset_detail9IntBitSetIjEoRERKS1_:
  199|  1.62M|    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEaNERKS1_:
  201|   548k|    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEmIERKS1_:
  203|   894k|    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
_ZN13bitset_detailorERKNS_9IntBitSetIjEES3_:
  211|   155k|    friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
_ZN13bitset_detailanERKNS_9IntBitSetIjEES3_:
  209|  1.48M|    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
_ZN13bitset_detailmiERKNS_9IntBitSetIjEES3_:
  213|  2.50M|    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
_ZNK13bitset_detail9IntBitSetIjE10IsSubsetOfERKS1_:
  221|  1.39M|    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
_ZN13bitset_detaileqERKNS_9IntBitSetIjEES3_:
  217|   529k|    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
_ZNK13bitset_detail9IntBitSetIjE8OverlapsERKS1_:
  207|   713k|    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }

_Z22inline_assertion_checkILb0EbEOT0_S1_PKciS3_S3_:
   52|  20.0M|{
   53|  20.0M|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|  20.0M|    ) {
   58|  20.0M|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 20.0M]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  20.0M|    }
   62|  20.0M|    return std::forward<T>(val);
   63|  20.0M|}
_Z22inline_assertion_checkILb0ERmEOT0_S2_PKciS4_S4_:
   52|  1.21M|{
   53|  1.21M|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|  1.21M|    ) {
   58|  1.21M|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 1.21M]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  1.21M|    }
   62|  1.21M|    return std::forward<T>(val);
   63|  1.21M|}
_Z22inline_assertion_checkILb1EbEOT0_S1_PKciS3_S3_:
   52|  2.67k|{
   53|  2.67k|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|  2.67k|    ) {
   58|  2.67k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 2.67k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  2.67k|    }
   62|  2.67k|    return std::forward<T>(val);
   63|  2.67k|}
_Z22inline_assertion_checkILb1ERPKNSt3__18functionIFvNS0_4spanIKhLm18446744073709551615EEEEEEEOT0_SB_PKciSD_SD_:
   52|  2.67k|{
   53|  2.67k|    if (IS_ASSERT || std::is_constant_evaluated() || G_FUZZING
  ------------------
  |  Branch (53:9): [Folded - Ignored]
  |  Branch (53:22): [Folded - Ignored]
  |  Branch (53:54): [Folded - Ignored]
  ------------------
   54|       |#ifdef ABORT_ON_FAILED_ASSUME
   55|       |        || true
   56|       |#endif
   57|  2.67k|    ) {
   58|  2.67k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 2.67k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  2.67k|    }
   62|  2.67k|    return std::forward<T>(val);
   63|  2.67k|}

_Z13CompareChunks4SpanIK7FeeFracES2_:
   11|  8.03k|{
   12|       |    /** Array to allow indexed access to input diagrams. */
   13|  8.03k|    const std::array<Span<const FeeFrac>, 2> chunk = {chunks0, chunks1};
   14|       |    /** How many elements we have processed in each input. */
   15|  8.03k|    size_t next_index[2] = {0, 0};
   16|       |    /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */
   17|  8.03k|    FeeFrac accum[2];
   18|       |    /** Whether the corresponding input is strictly better than the other at least in one place. */
   19|  8.03k|    bool better_somewhere[2] = {false, false};
   20|       |    /** Get the first unprocessed point in diagram number dia. */
   21|  8.03k|    const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; };
   22|       |    /** Get the last processed point in diagram number dia. */
   23|  8.03k|    const auto prev_point = [&](int dia) { return accum[dia]; };
   24|       |    /** Move to the next point in diagram number dia. */
   25|  8.03k|    const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };
   26|       |
   27|  84.6k|    do {
   28|  84.6k|        bool done_0 = next_index[0] == chunk[0].size();
   29|  84.6k|        bool done_1 = next_index[1] == chunk[1].size();
   30|  84.6k|        if (done_0 && done_1) break;
  ------------------
  |  Branch (30:13): [True: 8.03k, False: 76.6k]
  |  Branch (30:23): [True: 8.03k, False: 0]
  ------------------
   31|       |
   32|       |        // Determine which diagram has the first unprocessed point. If a single side is finished, use the
   33|       |        // other one. Only up to one can be done due to check above.
   34|  76.6k|        const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
  ------------------
  |  Branch (34:34): [True: 0, False: 76.6k]
  |  Branch (34:44): [True: 0, False: 76.6k]
  ------------------
   35|       |
   36|       |        // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
   37|       |        // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
   38|       |        // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
   39|       |        // and can thus be expressed as FeeFracs.
   40|  76.6k|        const FeeFrac& point_p = next_point(unproc_side);
   41|  76.6k|        const FeeFrac& point_a = prev_point(!unproc_side);
   42|       |
   43|  76.6k|        const auto slope_ap = point_p - point_a;
   44|  76.6k|        Assume(slope_ap.size > 0);
  ------------------
  |  |   97|  76.6k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   45|  76.6k|        std::weak_ordering cmp = std::weak_ordering::equivalent;
   46|  76.6k|        if (done_0 || done_1) {
  ------------------
  |  Branch (46:13): [True: 0, False: 76.6k]
  |  Branch (46:23): [True: 0, False: 76.6k]
  ------------------
   47|       |            // If a single side has no points left, act as if AB has slope tail_feerate(of 0).
   48|      0|            Assume(!(done_0 && done_1));
  ------------------
  |  |   97|      0|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 0, False: 0]
  |  |  |  Branch (97:51): [True: 0, False: 0]
  |  |  ------------------
  ------------------
   49|      0|            cmp = FeeRateCompare(slope_ap, FeeFrac(0, 1));
   50|  76.6k|        } else {
   51|       |            // If both sides have points left, compute B, and the slope of AB explicitly.
   52|  76.6k|            const FeeFrac& point_b = next_point(!unproc_side);
   53|  76.6k|            const auto slope_ab = point_b - point_a;
   54|  76.6k|            Assume(slope_ab.size >= slope_ap.size);
  ------------------
  |  |   97|  76.6k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   55|  76.6k|            cmp = FeeRateCompare(slope_ap, slope_ab);
   56|       |
   57|       |            // If B and P have the same size, B can be marked as processed (in addition to P, see
   58|       |            // below), as we've already performed a comparison at this size.
   59|  76.6k|            if (point_b.size == point_p.size) advance(!unproc_side);
  ------------------
  |  Branch (59:17): [True: 49.2k, False: 27.4k]
  ------------------
   60|  76.6k|        }
   61|       |        // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
   62|       |        // better in P.
   63|  76.6k|        if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
  ------------------
  |  Branch (63:13): [True: 17.8k, False: 58.7k]
  ------------------
   64|  76.6k|        if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
  ------------------
  |  Branch (64:13): [True: 2.00k, False: 74.6k]
  ------------------
   65|  76.6k|        advance(unproc_side);
   66|       |
   67|       |        // If both diagrams are better somewhere, they are incomparable.
   68|  76.6k|        if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
  ------------------
  |  Branch (68:13): [True: 22.3k, False: 54.3k]
  |  Branch (68:36): [True: 0, False: 22.3k]
  ------------------
   69|  76.6k|    } while(true);
  ------------------
  |  Branch (69:13): [Folded - Ignored]
  ------------------
   70|       |
   71|       |    // Otherwise compare the better_somewhere values.
   72|  8.03k|    return better_somewhere[0] <=> better_somewhere[1];
   73|  8.03k|}
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_0clEi:
   21|   306k|    const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; };
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_1clEi:
   23|  76.6k|    const auto prev_point = [&](int dia) { return accum[dia]; };
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_2clEi:
   25|   125k|    const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };

_ZN7FeeFrac3MulEli:
   55|  6.51M|    {
   56|       |        // If __int128 is available, use 128-bit wide multiply.
   57|  6.51M|        return __int128{a} * b;
   58|  6.51M|    }
_ZN7FeeFracC2Ev:
   67|  1.32M|    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
_ZN7FeeFracC2Eli:
   70|   649k|    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
_ZNK7FeeFrac7IsEmptyEv:
   76|  2.88M|    bool inline IsEmpty() const noexcept {
   77|  2.88M|        return size == 0;
   78|  2.88M|    }
_ZN7FeeFracpLERKS_:
   82|  1.41M|    {
   83|  1.41M|        fee += other.fee;
   84|  1.41M|        size += other.size;
   85|  1.41M|    }
_ZN7FeeFracmIERKS_:
   89|  15.6k|    {
   90|  15.6k|        fee -= other.fee;
   91|  15.6k|        size -= other.size;
   92|  15.6k|    }
_ZplRK7FeeFracS1_:
   96|   462k|    {
   97|   462k|        return {a.fee + b.fee, a.size + b.size};
   98|   462k|    }
_ZmiRK7FeeFracS1_:
  102|   153k|    {
  103|   153k|        return {a.fee - b.fee, a.size - b.size};
  104|   153k|    }
_Z14FeeRateCompareRK7FeeFracS1_:
  114|  76.6k|    {
  115|  76.6k|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  116|  76.6k|        return cross_a <=> cross_b;
  117|  76.6k|    }
_ZrsRK7FeeFracS1_:
  128|  1.17M|    {
  129|  1.17M|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  130|  1.17M|        return cross_a > cross_b;
  131|  1.17M|    }
_ZssRK7FeeFracS1_:
  135|  2.00M|    {
  136|  2.00M|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  137|  2.00M|        if (cross_a == cross_b) return b.size <=> a.size;
  ------------------
  |  Branch (137:13): [True: 781k, False: 1.22M]
  ------------------
  138|  1.22M|        return cross_a <=> cross_b;
  139|  2.00M|    }
_Z4swapR7FeeFracS0_:
  143|   309k|    {
  144|   309k|        std::swap(a.fee, b.fee);
  145|   309k|        std::swap(a.size, b.size);
  146|   309k|    }

_Z11SetMockTimeNSt3__16chrono8durationIxNS_5ratioILl1ELl1EEEEE:
   42|  2.67k|{
   43|  2.67k|    Assert(mock_time_in >= 0s);
  ------------------
  |  |   85|  2.67k|#define Assert(val) inline_assertion_check<true>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   44|  2.67k|    g_mock_time.store(mock_time_in, std::memory_order_relaxed);
   45|  2.67k|}

_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemEC2Ev:
  107|  23.5k|    VecDeque() noexcept = default;
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE7reserveEm:
  207|  23.5k|    {
  208|  23.5k|        if (capacity > m_capacity) Reallocate(capacity);
  ------------------
  |  Branch (208:13): [True: 23.5k, False: 0]
  ------------------
  209|  23.5k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE10ReallocateEm:
   40|  47.1k|    {
   41|  47.1k|        Assume(capacity >= m_size);
  ------------------
  |  |   97|  47.1k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   42|  47.1k|        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
  ------------------
  |  |   97|   141k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 23.6k, False: 23.5k]
  |  |  |  Branch (97:51): [True: 23.5k, False: 31]
  |  |  |  Branch (97:51): [True: 23.5k, False: 0]
  |  |  ------------------
  ------------------
   43|       |        // Allocate new buffer.
   44|  47.1k|        T* new_buffer = capacity ? std::allocator<T>().allocate(capacity) : nullptr;
  ------------------
  |  Branch (44:25): [True: 23.5k, False: 23.5k]
  ------------------
   45|  47.1k|        if (capacity) {
  ------------------
  |  Branch (45:13): [True: 23.5k, False: 23.5k]
  ------------------
   46|  23.5k|            if constexpr (std::is_trivially_copyable_v<T>) {
   47|       |                // When T is trivially copyable, just copy the data over from old to new buffer.
   48|  23.5k|                size_t first_part = FirstPart();
   49|  23.5k|                if (first_part != 0) {
  ------------------
  |  Branch (49:21): [True: 0, False: 23.5k]
  ------------------
   50|      0|                    std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T));
   51|      0|                }
   52|  23.5k|                if (first_part != m_size) {
  ------------------
  |  Branch (52:21): [True: 0, False: 23.5k]
  ------------------
   53|      0|                    std::memcpy(new_buffer + first_part, m_buffer, (m_size - first_part) * sizeof(T));
   54|      0|                }
   55|       |            } else {
   56|       |                // Otherwise move-construct in place in the new buffer, and destroy old buffer objects.
   57|       |                size_t old_pos = m_offset;
   58|       |                for (size_t new_pos = 0; new_pos < m_size; ++new_pos) {
   59|       |                    std::construct_at(new_buffer + new_pos, std::move(*(m_buffer + old_pos)));
   60|       |                    std::destroy_at(m_buffer + old_pos);
   61|       |                    ++old_pos;
   62|       |                    if (old_pos == m_capacity) old_pos = 0;
   63|       |                }
   64|       |            }
   65|  23.5k|        }
   66|       |        // Deallocate old buffer and update housekeeping.
   67|  47.1k|        std::allocator<T>().deallocate(m_buffer, m_capacity);
   68|  47.1k|        m_buffer = new_buffer;
   69|  47.1k|        m_offset = 0;
   70|  47.1k|        m_capacity = capacity;
   71|  47.1k|        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
  ------------------
  |  |   97|   165k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 47.1k, False: 0]
  |  |  |  Branch (97:51): [True: 23.5k, False: 23.5k]
  |  |  |  Branch (97:51): [True: 23.5k, False: 0]
  |  |  ------------------
  ------------------
   72|  47.1k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE9FirstPartEv:
   37|  23.5k|    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE12emplace_backIJS7_S4_7FeeFracEEEvDpOT_:
  220|   405k|    {
  221|   405k|        if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
  ------------------
  |  Branch (221:13): [True: 0, False: 405k]
  ------------------
  222|   405k|        std::construct_at(m_buffer + BufferIndex(m_size), std::forward<Args>(args)...);
  223|   405k|        ++m_size;
  224|   405k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE11BufferIndexEm:
   76|   856k|    {
   77|   856k|        Assume(pos < m_capacity);
  ------------------
  |  |   97|   856k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   78|       |        // The expression below is used instead of the more obvious (pos + m_offset >= m_capacity),
   79|       |        // because the addition there could in theory overflow with very large deques.
   80|   856k|        if (pos >= m_capacity - m_offset) {
  ------------------
  |  Branch (80:13): [True: 241k, False: 614k]
  ------------------
   81|   241k|            return (m_offset + pos) - m_capacity;
   82|   614k|        } else {
   83|   614k|            return m_offset + pos;
   84|   614k|        }
   85|   856k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5emptyEv:
  310|   358k|    bool empty() const noexcept { return m_size == 0; }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE4sizeEv:
  312|   930k|    size_t size() const noexcept { return m_size; }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemEixEm:
  297|   309k|    {
  298|   309k|        Assume(idx < m_size);
  ------------------
  |  |   97|   309k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  299|   309k|        return m_buffer[BufferIndex(idx)];
  300|   309k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5frontEv:
  269|   739k|    {
  270|   739k|        Assume(m_size);
  ------------------
  |  |   97|   739k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  271|   739k|        return m_buffer[m_offset];
  272|   739k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE8capacityEv:
  314|   595k|    size_t capacity() const noexcept { return m_capacity; }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE4backEv:
  283|  70.6k|    {
  284|  70.6k|        Assume(m_size);
  ------------------
  |  |   97|  70.6k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  285|  70.6k|        return m_buffer[BufferIndex(m_size - 1)];
  286|  70.6k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE8pop_backEv:
  261|  70.6k|    {
  262|  70.6k|        Assume(m_size);
  ------------------
  |  |   97|  70.6k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  263|  70.6k|        std::destroy_at(m_buffer + BufferIndex(m_size - 1));
  264|  70.6k|        --m_size;
  265|  70.6k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE9pop_frontEv:
  251|   334k|    {
  252|   334k|        Assume(m_size);
  ------------------
  |  |   97|   334k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  253|   334k|        std::destroy_at(m_buffer + m_offset);
  254|   334k|        --m_size;
  255|   334k|        ++m_offset;
  256|   334k|        if (m_offset == m_capacity) m_offset = 0;
  ------------------
  |  Branch (256:13): [True: 336, False: 334k]
  ------------------
  257|   334k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemED2Ev:
  130|  23.5k|    {
  131|  23.5k|        clear();
  132|  23.5k|        Reallocate(0);
  133|  23.5k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5clearEv:
  126|  23.5k|    void clear() noexcept { ResizeDown(0); }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE10ResizeDownEm:
   90|  23.5k|    {
   91|  23.5k|        Assume(size <= m_size);
  ------------------
  |  |   97|  23.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   92|  23.5k|        if constexpr (std::is_trivially_destructible_v<T>) {
   93|       |            // If T is trivially destructible, we do not need to do anything but update the
   94|       |            // housekeeping record. Default constructor or zero-filling will be used when
   95|       |            // the space is reused.
   96|  23.5k|            m_size = size;
   97|       |        } else {
   98|       |            // If not, we need to invoke the destructor for every element separately.
   99|       |            while (m_size > size) {
  100|       |                std::destroy_at(m_buffer + BufferIndex(m_size - 1));
  101|       |                --m_size;
  102|       |            }
  103|       |        }
  104|  23.5k|    }