_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2Ev:
   68|  8.69k|    DepGraph() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7TxCountEv:
  118|  73.2k|    auto TxCount() const noexcept { return m_used.Count(); }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2Ev:
  324|  31.4k|    SetInfo() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9PositionsEv:
  114|   102k|    const SetType& Positions() const noexcept { return m_used; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj:
  122|   495k|    FeeFrac& FeeRate(ClusterIndex i) noexcept { return entries[i].feerate; }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9AncestorsEj:
  124|  4.82M|    const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE14AddTransactionERK7FeeFrac:
  134|  38.5k|    {
  135|  38.5k|        static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
  136|  38.5k|        auto available = ALL_POSITIONS - m_used;
  137|  38.5k|        Assume(available.Any());
  ------------------
  |  |   97|  38.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  138|  38.5k|        ClusterIndex new_idx = available.First();
  139|  38.5k|        if (new_idx == entries.size()) {
  ------------------
  |  Branch (139:13): [True: 38.5k, False: 0]
  ------------------
  140|  38.5k|            entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  141|  38.5k|        } else {
  142|      0|            entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
  143|      0|        }
  144|  38.5k|        m_used.Set(new_idx);
  145|  38.5k|        return new_idx;
  146|  38.5k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2ERK7FeeFracRKS3_SA_:
   46|  38.5k|        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE15AddDependenciesERKS3_j:
  178|   139k|    {
  179|   139k|        Assume(m_used[child]);
  ------------------
  |  |   97|   139k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  180|   139k|        Assume(parents.IsSubsetOf(m_used));
  ------------------
  |  |   97|   139k|#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|   139k|        SetType par_anc;
  183|   139k|        for (auto par : parents - Ancestors(child)) {
  ------------------
  |  Branch (183:23): [True: 83.8k, False: 139k]
  ------------------
  184|  83.8k|            par_anc |= Ancestors(par);
  185|  83.8k|        }
  186|   139k|        par_anc -= Ancestors(child);
  187|       |        // Bail out if there are no such ancestors.
  188|   139k|        if (par_anc.None()) return;
  ------------------
  |  Branch (188:13): [True: 76.6k, False: 63.3k]
  ------------------
  189|       |        // To each such ancestor, add as descendants the descendants of the child.
  190|  63.3k|        const auto& chl_des = entries[child].descendants;
  191|   578k|        for (auto anc_of_par : par_anc) {
  ------------------
  |  Branch (191:30): [True: 578k, False: 63.3k]
  ------------------
  192|   578k|            entries[anc_of_par].descendants |= chl_des;
  193|   578k|        }
  194|       |        // To each descendant of the child, add those ancestors.
  195|  68.2k|        for (auto dec_of_chl : Descendants(child)) {
  ------------------
  |  Branch (195:30): [True: 68.2k, False: 63.3k]
  ------------------
  196|  68.2k|            entries[dec_of_chl].ancestors |= par_anc;
  197|  68.2k|        }
  198|  63.3k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj:
  120|  2.72M|    const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEaSEOS4_:
   72|  5.60k|    DepGraph& operator=(DepGraph&&) noexcept = default;
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2ERKS4_4SpanIKjEj:
   89|  5.60k|    DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping, ClusterIndex pos_range) noexcept : entries(pos_range)
   90|  5.60k|    {
   91|  5.60k|        Assume(mapping.size() == depgraph.PositionRange());
  ------------------
  |  |   97|  5.60k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   92|  5.60k|        Assume((pos_range == 0) == (depgraph.TxCount() == 0));
  ------------------
  |  |   97|  5.60k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   93|  74.3k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (93:29): [True: 74.3k, False: 5.60k]
  ------------------
   94|  74.3k|            auto new_idx = mapping[i];
   95|  74.3k|            Assume(new_idx < pos_range);
  ------------------
  |  |   97|  74.3k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   96|       |            // Add transaction.
   97|  74.3k|            entries[new_idx].ancestors = SetType::Singleton(new_idx);
   98|  74.3k|            entries[new_idx].descendants = SetType::Singleton(new_idx);
   99|  74.3k|            m_used.Set(new_idx);
  100|       |            // Fill in fee and size.
  101|  74.3k|            entries[new_idx].feerate = depgraph.entries[i].feerate;
  102|  74.3k|        }
  103|  74.3k|        for (ClusterIndex i : depgraph.Positions()) {
  ------------------
  |  Branch (103:29): [True: 74.3k, False: 5.60k]
  ------------------
  104|       |            // Fill in dependencies by mapping direct parents.
  105|  74.3k|            SetType parents;
  106|  74.3k|            for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
  ------------------
  |  Branch (106:25): [True: 40.5k, False: 74.3k]
  ------------------
  107|  74.3k|            AddDependencies(parents, mapping[i]);
  108|  74.3k|        }
  109|       |        // Verify that the provided pos_range was correct (no unused positions at the end).
  110|  5.60k|        Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
  ------------------
  |  |   97|  11.2k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 107, False: 5.50k]
  |  |  ------------------
  ------------------
  111|  5.60k|    }
_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2Ev:
   44|   116k|        Entry() noexcept = default;
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE22FindConnectedComponentERKS3_:
  266|  77.6k|    {
  267|  77.6k|        if (todo.None()) return todo;
  ------------------
  |  Branch (267:13): [True: 464, False: 77.1k]
  ------------------
  268|  77.1k|        auto to_add = SetType::Singleton(todo.First());
  269|  77.1k|        SetType ret;
  270|   160k|        do {
  271|   160k|            SetType old = ret;
  272|   262k|            for (auto add : to_add) {
  ------------------
  |  Branch (272:27): [True: 262k, False: 160k]
  ------------------
  273|   262k|                ret |= Descendants(add);
  274|   262k|                ret |= Ancestors(add);
  275|   262k|            }
  276|   160k|            ret &= todo;
  277|   160k|            to_add = ret - old;
  278|   160k|        } while (to_add.Any());
  ------------------
  |  Branch (278:18): [True: 83.5k, False: 77.1k]
  ------------------
  279|  77.1k|        return ret;
  280|  77.6k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11IsConnectedERKS3_:
  287|  30.0k|    {
  288|  30.0k|        return FindConnectedComponent(subset) == subset;
  289|  30.0k|    }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11DescendantsEj:
  126|  1.54M|    const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
_ZN17cluster_linearize18ChunkLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorI7FeeFracNS4_9allocatorIS6_EEEERKNS_8DepGraphIT_EE4SpanIKjE:
  375|  34.7k|{
  376|  34.7k|    std::vector<FeeFrac> ret;
  377|   262k|    for (ClusterIndex i : linearization) {
  ------------------
  |  Branch (377:25): [True: 262k, False: 34.7k]
  ------------------
  378|       |        /** The new chunk to be added, initially a singleton. */
  379|   262k|        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|   404k|        while (!ret.empty() && new_chunk >> ret.back()) {
  ------------------
  |  Branch (381:16): [True: 323k, False: 81.2k]
  |  Branch (381:32): [True: 142k, False: 180k]
  ------------------
  382|   142k|            new_chunk += ret.back();
  383|   142k|            ret.pop_back();
  384|   142k|        }
  385|       |        // Actually move that new chunk into the chunking.
  386|   262k|        ret.push_back(std::move(new_chunk));
  387|   262k|    }
  388|  34.7k|    return ret;
  389|  34.7k|}
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEE3SetERKNS_8DepGraphIS3_EEj:
  339|   365k|    {
  340|   365k|        Assume(!transactions[pos]);
  ------------------
  |  |   97|   365k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  341|   365k|        transactions.Set(pos);
  342|   365k|        feerate += depgraph.FeeRate(pos);
  343|   365k|    }
_ZN17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EE:
  544|  2.84k|        m_depgraph(depgraph),
  545|  2.84k|        m_todo{depgraph.Positions()},
  546|  2.84k|        m_ancestor_set_feerates(depgraph.PositionRange())
  547|  2.84k|    {
  548|       |        // Precompute ancestor-set feerates.
  549|  38.5k|        for (ClusterIndex i : m_depgraph.Positions()) {
  ------------------
  |  Branch (549:29): [True: 38.5k, False: 2.84k]
  ------------------
  550|       |            /** The remaining ancestors for transaction i. */
  551|  38.5k|            SetType anc_to_add = m_depgraph.Ancestors(i);
  552|  38.5k|            FeeFrac anc_feerate;
  553|       |            // Reuse accumulated feerate from first ancestor, if usable.
  554|  38.5k|            Assume(anc_to_add.Any());
  ------------------
  |  |   97|  38.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  555|  38.5k|            ClusterIndex first = anc_to_add.First();
  556|  38.5k|            if (first < i) {
  ------------------
  |  Branch (556:17): [True: 28.4k, False: 10.0k]
  ------------------
  557|  28.4k|                anc_feerate = m_ancestor_set_feerates[first];
  558|  28.4k|                Assume(!anc_feerate.IsEmpty());
  ------------------
  |  |   97|  28.4k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  559|  28.4k|                anc_to_add -= m_depgraph.Ancestors(first);
  560|  28.4k|            }
  561|       |            // Add in other ancestors (which necessarily include i itself).
  562|  38.5k|            Assume(anc_to_add[i]);
  ------------------
  |  |   97|  38.5k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  563|  38.5k|            anc_feerate += m_depgraph.FeeRate(anc_to_add);
  564|       |            // Store the result.
  565|  38.5k|            m_ancestor_set_feerates[i] = anc_feerate;
  566|  38.5k|        }
  567|  2.84k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE7AllDoneEv:
  590|  25.6k|    {
  591|  25.6k|        return m_todo.None();
  592|  25.6k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE12NumRemainingEv:
  596|  12.1k|    {
  597|  12.1k|        return m_todo.Count();
  598|  12.1k|    }
_ZNK17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEv:
  606|  12.8k|    {
  607|  12.8k|        Assume(!AllDone());
  ------------------
  |  |   97|  12.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  608|  12.8k|        std::optional<ClusterIndex> best;
  609|   140k|        for (auto i : m_todo) {
  ------------------
  |  Branch (609:21): [True: 140k, False: 12.8k]
  ------------------
  610|   140k|            if (best.has_value()) {
  ------------------
  |  Branch (610:17): [True: 127k, False: 12.8k]
  ------------------
  611|   127k|                Assume(!m_ancestor_set_feerates[i].IsEmpty());
  ------------------
  |  |   97|   127k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  612|   127k|                if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue;
  ------------------
  |  Branch (612:21): [True: 106k, False: 20.9k]
  ------------------
  613|   127k|            }
  614|  33.7k|            best = i;
  615|  33.7k|        }
  616|  12.8k|        Assume(best.has_value());
  ------------------
  |  |   97|  12.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  617|  12.8k|        return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]};
  618|  12.8k|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKS3_RK7FeeFrac:
  327|   122k|    SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateERKS3_:
  247|  1.14M|    {
  248|  1.14M|        FeeFrac ret;
  249|  12.6M|        for (auto pos : elems) ret += entries[pos].feerate;
  ------------------
  |  Branch (249:23): [True: 12.6M, False: 1.14M]
  ------------------
  250|  1.14M|        return ret;
  251|  1.14M|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EERKS3_:
  335|   784k|        transactions(txn), feerate(depgraph.FeeRate(txn)) {}
_ZN17cluster_linearize23AncestorCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
  576|  12.8k|    {
  577|  12.8k|        Assume(select.Any());
  ------------------
  |  |   97|  12.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  578|  12.8k|        Assume(select.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  12.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  579|  12.8k|        m_todo -= select;
  580|  38.5k|        for (auto i : select) {
  ------------------
  |  Branch (580:21): [True: 38.5k, False: 12.8k]
  ------------------
  581|  38.5k|            auto feerate = m_depgraph.FeeRate(i);
  582|   112k|            for (auto j : m_depgraph.Descendants(i) & m_todo) {
  ------------------
  |  Branch (582:25): [True: 112k, False: 38.5k]
  ------------------
  583|   112k|                m_ancestor_set_feerates[j] -= feerate;
  584|   112k|            }
  585|  38.5k|        }
  586|  12.8k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEm:
  670|  2.65k|        m_rng(rng_seed),
  671|  2.65k|        m_sorted_to_original(depgraph.TxCount()),
  672|  2.65k|        m_original_to_sorted(depgraph.PositionRange())
  673|  2.65k|    {
  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.65k|        ClusterIndex sorted_pos{0};
  677|  35.8k|        for (auto i : depgraph.Positions()) {
  ------------------
  |  Branch (677:21): [True: 35.8k, False: 2.65k]
  ------------------
  678|  35.8k|            m_sorted_to_original[sorted_pos++] = i;
  679|  35.8k|        }
  680|  2.65k|        std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) {
  681|  2.65k|            auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b);
  682|  2.65k|            if (feerate_cmp == 0) return a < b;
  683|  2.65k|            return feerate_cmp > 0;
  684|  2.65k|        });
  685|       |        // Compute reverse mapping.
  686|  38.4k|        for (ClusterIndex i = 0; i < m_sorted_to_original.size(); ++i) {
  ------------------
  |  Branch (686:34): [True: 35.8k, False: 2.65k]
  ------------------
  687|  35.8k|            m_original_to_sorted[m_sorted_to_original[i]] = i;
  688|  35.8k|        }
  689|       |        // Compute reordered dependency graph.
  690|  2.65k|        m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted, m_sorted_to_original.size());
  691|  2.65k|        m_todo = m_sorted_depgraph.Positions();
  692|  2.65k|    }
_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: 413k, False: 606k]
  ------------------
  683|   606k|            return feerate_cmp > 0;
  684|  1.01M|        });
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE7AllDoneEv:
  696|  9.95k|    {
  697|  9.95k|        return m_todo.None();
  698|  9.95k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EE:
  718|  9.95k|    {
  719|  9.95k|        Assume(!AllDone());
  ------------------
  |  |   97|  9.95k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  720|       |
  721|       |        // Convert the provided best to internal sorted indices.
  722|  9.95k|        best.transactions = OriginalToSorted(best.transactions);
  723|       |
  724|       |        /** Type for work queue items. */
  725|  9.95k|        struct WorkItem
  726|  9.95k|        {
  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|  9.95k|            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|  9.95k|            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|  9.95k|            FeeFrac pot_feerate;
  741|       |
  742|       |            /** Construct a new work item. */
  743|  9.95k|            WorkItem(SetInfo<SetType>&& i, SetType&& u, FeeFrac&& p_f) noexcept :
  744|  9.95k|                inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
  745|  9.95k|            {
  746|  9.95k|                Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
  747|  9.95k|            }
  748|       |
  749|       |            /** Swap two WorkItems. */
  750|  9.95k|            void Swap(WorkItem& other) noexcept
  751|  9.95k|            {
  752|  9.95k|                swap(inc, other.inc);
  753|  9.95k|                swap(und, other.und);
  754|  9.95k|                swap(pot_feerate, other.pot_feerate);
  755|  9.95k|            }
  756|  9.95k|        };
  757|       |
  758|       |        /** The queue of work items. */
  759|  9.95k|        VecDeque<WorkItem> queue;
  760|  9.95k|        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|  9.95k|        auto to_cover = m_todo;
  767|  17.4k|        do {
  768|  17.4k|            auto component = m_sorted_depgraph.FindConnectedComponent(to_cover);
  769|  17.4k|            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|  17.4k|            if (best.feerate.IsEmpty()) best = SetInfo(m_sorted_depgraph, component);
  ------------------
  |  Branch (773:17): [True: 0, False: 17.4k]
  ------------------
  774|  17.4k|            queue.emplace_back(/*inc=*/SetInfo<SetType>{},
  775|  17.4k|                               /*und=*/std::move(component),
  776|  17.4k|                               /*pot_feerate=*/FeeFrac{});
  777|  17.4k|        } while (to_cover.Any());
  ------------------
  |  Branch (777:18): [True: 7.53k, False: 9.95k]
  ------------------
  778|       |
  779|       |        /** Local copy of the iteration limit. */
  780|  9.95k|        uint64_t iterations_left = max_iterations;
  781|       |
  782|       |        /** The set of transactions in m_todo which have feerate > best's. */
  783|  9.95k|        SetType imp = m_todo;
  784|  99.0k|        while (imp.Any()) {
  ------------------
  |  Branch (784:16): [True: 94.3k, False: 4.64k]
  ------------------
  785|  94.3k|            ClusterIndex check = imp.Last();
  786|  94.3k|            if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  ------------------
  |  Branch (786:17): [True: 5.30k, False: 89.0k]
  ------------------
  787|  89.0k|            imp.Reset(check);
  788|  89.0k|        }
  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|  9.95k|        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|  9.95k|            auto pot = inc;
  801|  9.95k|            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|  9.95k|                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|  9.95k|                    if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
  812|  9.95k|                    pot.Set(m_sorted_depgraph, pos);
  813|  9.95k|                }
  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|  9.95k|                const auto init_inc = inc.transactions;
  826|  9.95k|                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|  9.95k|                    auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
  831|  9.95k|                    if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
  832|  9.95k|                }
  833|       |                // Finally update und and inc's feerate to account for the added transactions.
  834|  9.95k|                und -= inc.transactions;
  835|  9.95k|                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|  9.95k|                if (inc.feerate > best.feerate) {
  839|  9.95k|                    best = inc;
  840|       |                    // See if we can remove any entries from imp now.
  841|  9.95k|                    while (imp.Any()) {
  842|  9.95k|                        ClusterIndex check = imp.Last();
  843|  9.95k|                        if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  844|  9.95k|                        imp.Reset(check);
  845|  9.95k|                    }
  846|  9.95k|                }
  847|       |
  848|       |                // If no potential transactions exist beyond the already included ones, no
  849|       |                // improvement is possible anymore.
  850|  9.95k|                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|  9.95k|                Assume(und.Any());
  853|  9.95k|            } else {
  854|  9.95k|                Assume(inc.transactions.None());
  855|       |                // If inc is empty, we just make sure there are undecided transactions left to
  856|       |                // split on.
  857|  9.95k|                if (und.None()) return;
  858|  9.95k|            }
  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|  9.95k|            Assume(queue.size() < queue.capacity());
  864|  9.95k|            queue.emplace_back(/*inc=*/std::move(inc),
  865|  9.95k|                               /*und=*/std::move(und),
  866|  9.95k|                               /*pot_feerate=*/std::move(pot.feerate));
  867|  9.95k|        };
  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|  9.95k|        auto split_fn = [&](WorkItem&& elem) noexcept {
  873|       |            // Any queue element must have undecided transactions left, otherwise there is nothing
  874|       |            // to explore anymore.
  875|  9.95k|            Assume(elem.und.Any());
  876|       |            // The included and undecided set are all subsets of m_todo.
  877|  9.95k|            Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
  878|       |            // Included transactions cannot be undecided.
  879|  9.95k|            Assume(!elem.inc.transactions.Overlaps(elem.und));
  880|       |            // If pot is empty, then so is inc.
  881|  9.95k|            Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
  882|       |
  883|  9.95k|            const ClusterIndex first = elem.und.First();
  884|  9.95k|            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|  9.95k|                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|  9.95k|                if (elem.pot_feerate <= best.feerate) return;
  891|  9.95k|            } else {
  892|       |                // In case inc is empty use a simpler alternative check.
  893|  9.95k|                if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
  894|  9.95k|            }
  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|  9.95k|            ClusterIndex split = 0;
  910|  9.95k|            const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
  911|  9.95k|            Assume(select.Any());
  912|  9.95k|            std::optional<std::pair<ClusterIndex, ClusterIndex>> split_counts;
  913|  9.95k|            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|  9.95k|                std::pair<ClusterIndex, ClusterIndex> counts{
  920|  9.95k|                    (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
  921|  9.95k|                    (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
  922|  9.95k|                if (counts.first < counts.second) std::swap(counts.first, counts.second);
  923|       |                // Remember the t with the lowest counts.
  924|  9.95k|                if (!split_counts.has_value() || counts < *split_counts) {
  925|  9.95k|                    split = t;
  926|  9.95k|                    split_counts = counts;
  927|  9.95k|                }
  928|  9.95k|            }
  929|       |            // Since there was at least one transaction in select, we must always find one.
  930|  9.95k|            Assume(split_counts.has_value());
  931|       |
  932|       |            // Add a work item corresponding to exclusion of the split transaction.
  933|  9.95k|            const auto& desc = m_sorted_depgraph.Descendants(split);
  934|  9.95k|            add_fn(/*inc=*/elem.inc,
  935|  9.95k|                   /*und=*/elem.und - desc);
  936|       |
  937|       |            // Add a work item corresponding to inclusion of the split transaction.
  938|  9.95k|            const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
  939|  9.95k|            add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
  940|  9.95k|                   /*und=*/elem.und - anc);
  941|       |
  942|       |            // Account for the performed split.
  943|  9.95k|            --iterations_left;
  944|  9.95k|        };
  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|   135k|        while (!queue.empty()) {
  ------------------
  |  Branch (958:16): [True: 125k, False: 9.61k]
  ------------------
  959|       |            // Randomly swap the first two items to randomize the search order.
  960|   125k|            if (queue.size() > 1 && m_rng.randbool()) {
  ------------------
  |  Branch (960:17): [True: 109k, False: 16.8k]
  |  Branch (960:37): [True: 56.0k, False: 52.9k]
  ------------------
  961|  56.0k|                queue[0].Swap(queue[1]);
  962|  56.0k|            }
  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|   173k|            while (queue.size() - 1 + queue.front().und.Count() > queue.capacity()) {
  ------------------
  |  Branch (968:20): [True: 48.0k, False: 125k]
  ------------------
  969|  48.0k|                if (!iterations_left) break;
  ------------------
  |  Branch (969:21): [True: 10, False: 48.0k]
  ------------------
  970|  48.0k|                auto elem = queue.back();
  971|  48.0k|                queue.pop_back();
  972|  48.0k|                split_fn(std::move(elem));
  973|  48.0k|            }
  974|       |
  975|       |            // Process one entry from the front of the queue (BFS exploration)
  976|   125k|            if (!iterations_left) break;
  ------------------
  |  Branch (976:17): [True: 344, False: 125k]
  ------------------
  977|   125k|            auto elem = queue.front();
  978|   125k|            queue.pop_front();
  979|   125k|            split_fn(std::move(elem));
  980|   125k|        }
  981|       |
  982|       |        // Return the found best set (converted to the original transaction indices), and the
  983|       |        // number of iterations performed.
  984|  9.95k|        best.transactions = SortedToOriginal(best.transactions);
  985|  9.95k|        return {std::move(best), max_iterations - iterations_left};
  986|  9.95k|    }
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16OriginalToSortedERKS3_:
  655|  19.4k|    {
  656|  19.4k|        SetType ret;
  657|  52.7k|        for (auto pos : arg) ret.Set(m_original_to_sorted[pos]);
  ------------------
  |  Branch (657:23): [True: 52.7k, False: 19.4k]
  ------------------
  658|  19.4k|        return ret;
  659|  19.4k|    }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEEN8WorkItemC2EOS6_OS3_O7FeeFrac:
  744|   178k|                inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
  745|   178k|            {
  746|   178k|                Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
  ------------------
  |  |   97|   178k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  747|   178k|            }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEEN8WorkItem4SwapERS7_:
  751|  56.0k|            {
  752|  56.0k|                swap(inc, other.inc);
  753|  56.0k|                swap(und, other.und);
  754|  56.0k|                swap(pot_feerate, other.pot_feerate);
  755|  56.0k|            }
_ZN17cluster_linearize4swapERNS_7SetInfoIN13bitset_detail9IntBitSetIjEEEES5_:
  363|  56.0k|    {
  364|  56.0k|        swap(a.transactions, b.transactions);
  365|  56.0k|        swap(a.feerate, b.feerate);
  366|  56.0k|    }
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEENKUlOZNS4_16FindCandidateSetEmS6_E8WorkItemE_clES8_:
  872|   173k|        auto split_fn = [&](WorkItem&& elem) noexcept {
  873|       |            // Any queue element must have undecided transactions left, otherwise there is nothing
  874|       |            // to explore anymore.
  875|   173k|            Assume(elem.und.Any());
  ------------------
  |  |   97|   173k|#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|   173k|            Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
  ------------------
  |  |   97|   347k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 173k, False: 0]
  |  |  |  Branch (97:51): [True: 173k, False: 0]
  |  |  ------------------
  ------------------
  878|       |            // Included transactions cannot be undecided.
  879|   173k|            Assume(!elem.inc.transactions.Overlaps(elem.und));
  ------------------
  |  |   97|   173k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  880|       |            // If pot is empty, then so is inc.
  881|   173k|            Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
  ------------------
  |  |   97|   173k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  882|       |
  883|   173k|            const ClusterIndex first = elem.und.First();
  884|   173k|            if (!elem.inc.feerate.IsEmpty()) {
  ------------------
  |  Branch (884:17): [True: 145k, False: 27.5k]
  ------------------
  885|       |                // If no undecided transactions remain with feerate higher than best, this entry
  886|       |                // cannot be improved beyond best.
  887|   145k|                if (!elem.und.Overlaps(imp)) return;
  ------------------
  |  Branch (887:21): [True: 364, False: 145k]
  ------------------
  888|       |                // We can ignore any queue item whose potential feerate isn't better than the best
  889|       |                // seen so far.
  890|   145k|                if (elem.pot_feerate <= best.feerate) return;
  ------------------
  |  Branch (890:21): [True: 46.3k, False: 99.2k]
  ------------------
  891|   145k|            } else {
  892|       |                // In case inc is empty use a simpler alternative check.
  893|  27.5k|                if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
  ------------------
  |  Branch (893:21): [True: 16.8k, False: 10.7k]
  ------------------
  894|  27.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|   109k|            ClusterIndex split = 0;
  910|   109k|            const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
  911|   109k|            Assume(select.Any());
  ------------------
  |  |   97|   109k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  912|   109k|            std::optional<std::pair<ClusterIndex, ClusterIndex>> split_counts;
  913|   291k|            for (auto t : select) {
  ------------------
  |  Branch (913:25): [True: 291k, False: 109k]
  ------------------
  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|   291k|                std::pair<ClusterIndex, ClusterIndex> counts{
  920|   291k|                    (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
  921|   291k|                    (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
  922|   291k|                if (counts.first < counts.second) std::swap(counts.first, counts.second);
  ------------------
  |  Branch (922:21): [True: 113k, False: 177k]
  ------------------
  923|       |                // Remember the t with the lowest counts.
  924|   291k|                if (!split_counts.has_value() || counts < *split_counts) {
  ------------------
  |  Branch (924:21): [True: 109k, False: 181k]
  |  Branch (924:50): [True: 31.0k, False: 150k]
  ------------------
  925|   140k|                    split = t;
  926|   140k|                    split_counts = counts;
  927|   140k|                }
  928|   291k|            }
  929|       |            // Since there was at least one transaction in select, we must always find one.
  930|   109k|            Assume(split_counts.has_value());
  ------------------
  |  |   97|   109k|#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|   109k|            const auto& desc = m_sorted_depgraph.Descendants(split);
  934|   109k|            add_fn(/*inc=*/elem.inc,
  935|   109k|                   /*und=*/elem.und - desc);
  936|       |
  937|       |            // Add a work item corresponding to inclusion of the split transaction.
  938|   109k|            const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
  939|   109k|            add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
  940|   109k|                   /*und=*/elem.und - anc);
  941|       |
  942|       |            // Account for the performed split.
  943|   109k|            --iterations_left;
  944|   109k|        };
_ZZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS_7SetInfoIS3_EEENKUlS6_S3_E_clES6_S3_:
  797|   219k|        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|   219k|            auto pot = inc;
  801|   219k|            if (!inc.feerate.IsEmpty()) {
  ------------------
  |  Branch (801:17): [True: 209k, False: 10.7k]
  ------------------
  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|   372k|                for (auto pos : imp & und) {
  ------------------
  |  Branch (806:31): [True: 372k, False: 202k]
  ------------------
  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|   372k|                    if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
  ------------------
  |  Branch (811:25): [True: 6.82k, False: 365k]
  ------------------
  812|   365k|                    pot.Set(m_sorted_depgraph, pos);
  813|   365k|                }
  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|   209k|                const auto init_inc = inc.transactions;
  826|   365k|                for (auto pos : pot.transactions - inc.transactions) {
  ------------------
  |  Branch (826:31): [True: 365k, False: 209k]
  ------------------
  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|   365k|                    auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
  831|   365k|                    if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
  ------------------
  |  Branch (831:25): [True: 31.0k, False: 334k]
  ------------------
  832|   365k|                }
  833|       |                // Finally update und and inc's feerate to account for the added transactions.
  834|   209k|                und -= inc.transactions;
  835|   209k|                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|   209k|                if (inc.feerate > best.feerate) {
  ------------------
  |  Branch (838:21): [True: 546, False: 208k]
  ------------------
  839|    546|                    best = inc;
  840|       |                    // See if we can remove any entries from imp now.
  841|    867|                    while (imp.Any()) {
  ------------------
  |  Branch (841:28): [True: 867, False: 0]
  ------------------
  842|    867|                        ClusterIndex check = imp.Last();
  843|    867|                        if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
  ------------------
  |  Branch (843:29): [True: 546, False: 321]
  ------------------
  844|    321|                        imp.Reset(check);
  845|    321|                    }
  846|    546|                }
  847|       |
  848|       |                // If no potential transactions exist beyond the already included ones, no
  849|       |                // improvement is possible anymore.
  850|   209k|                if (pot.feerate.size == inc.feerate.size) return;
  ------------------
  |  Branch (850:21): [True: 59.0k, False: 150k]
  ------------------
  851|       |                // At this point und must be non-empty. If it were empty then pot would equal inc.
  852|   150k|                Assume(und.Any());
  ------------------
  |  |   97|   150k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  853|   150k|            } else {
  854|  10.7k|                Assume(inc.transactions.None());
  ------------------
  |  |   97|  10.7k|#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|  10.7k|                if (und.None()) return;
  ------------------
  |  Branch (857:21): [True: 281, False: 10.4k]
  ------------------
  858|  10.7k|            }
  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|   160k|            Assume(queue.size() < queue.capacity());
  ------------------
  |  |   97|   160k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  864|   160k|            queue.emplace_back(/*inc=*/std::move(inc),
  865|   160k|                               /*und=*/std::move(und),
  866|   160k|                               /*pot_feerate=*/std::move(pot.feerate));
  867|   160k|        };
_ZNK17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEE3AddERKNS_8DepGraphIS3_EERKS3_:
  357|   109k|    {
  358|   109k|        return {transactions | txn, feerate + depgraph.FeeRate(txn - transactions)};
  359|   109k|    }
_ZNK17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16SortedToOriginalERKS3_:
  647|  9.95k|    {
  648|  9.95k|        SetType ret;
  649|  30.7k|        for (auto pos : arg) ret.Set(m_sorted_to_original[pos]);
  ------------------
  |  Branch (649:23): [True: 30.7k, False: 9.95k]
  ------------------
  650|  9.95k|        return ret;
  651|  9.95k|    }
_ZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneERKS3_:
  993|  9.45k|    {
  994|  9.45k|        const auto done_sorted = OriginalToSorted(done);
  995|  9.45k|        Assume(done_sorted.Any());
  ------------------
  |  |   97|  9.45k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  996|  9.45k|        Assume(done_sorted.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  9.45k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  997|  9.45k|        m_todo -= done_sorted;
  998|  9.45k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EE4SpanIKjE:
  441|  2.84k|        m_depgraph(depgraph), m_linearization(lin)
  442|  2.84k|    {
  443|       |        // Mark everything in lin as todo still.
  444|  5.76k|        for (auto i : m_linearization) m_todo.Set(i);
  ------------------
  |  Branch (444:21): [True: 5.76k, False: 2.84k]
  ------------------
  445|       |        // Compute the initial chunking.
  446|  2.84k|        m_chunks.reserve(depgraph.TxCount());
  447|  2.84k|        BuildChunks();
  448|  2.84k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE11BuildChunksEv:
  412|  3.97k|    {
  413|       |        // Caller must clear m_chunks.
  414|  3.97k|        Assume(m_chunks.empty());
  ------------------
  |  |   97|  3.97k|#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|  4.62k|        while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
  ------------------
  |  Branch (417:16): [True: 2.22k, False: 2.39k]
  |  Branch (417:44): [True: 644, False: 1.58k]
  ------------------
  418|    644|            m_linearization = m_linearization.subspan(1);
  419|    644|        }
  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|  26.5k|        for (auto idx : m_linearization) {
  ------------------
  |  Branch (424:23): [True: 26.5k, False: 3.97k]
  ------------------
  425|  26.5k|            if (!m_todo[idx]) continue;
  ------------------
  |  Branch (425:17): [True: 9.24k, False: 17.3k]
  ------------------
  426|       |            // Start with an initial chunk containing just element idx.
  427|  17.3k|            SetInfo add(m_depgraph, idx);
  428|       |            // Absorb existing final chunks into add while they have lower feerate.
  429|  30.7k|            while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
  ------------------
  |  Branch (429:20): [True: 23.6k, False: 7.07k]
  |  Branch (429:41): [True: 13.4k, False: 10.2k]
  ------------------
  430|  13.4k|                add |= m_chunks.back();
  431|  13.4k|                m_chunks.pop_back();
  432|  13.4k|            }
  433|       |            // Remember new chunk.
  434|  17.3k|            m_chunks.push_back(std::move(add));
  435|  17.3k|        }
  436|  3.97k|    }
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEj:
  331|  17.3k|        transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
_ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEoRERKS4_:
  347|  13.4k|    {
  348|  13.4k|        Assume(!transactions.Overlaps(other.transactions));
  ------------------
  |  |   97|  13.4k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  349|  13.4k|        transactions |= other.transactions;
  350|  13.4k|        feerate += other.feerate;
  351|  13.4k|        return *this;
  352|  13.4k|    }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE13NumChunksLeftEv:
  451|  27.8k|    ClusterIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8GetChunkEj:
  455|  5.66k|    {
  456|  5.66k|        Assume(n + m_chunks_skip < m_chunks.size());
  ------------------
  |  |   97|  5.66k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  457|  5.66k|        return m_chunks[n + m_chunks_skip];
  458|  5.66k|    }
_ZNK17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE17IntersectPrefixesERKNS_7SetInfoIS3_EE:
  493|  1.17k|    {
  494|  1.17k|        Assume(subset.transactions.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  1.17k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  495|  1.17k|        SetInfo<SetType> accumulator;
  496|       |        // Iterate over all chunks of the remaining linearization.
  497|  1.80k|        for (ClusterIndex i = 0; i < NumChunksLeft(); ++i) {
  ------------------
  |  Branch (497:34): [True: 1.80k, False: 0]
  ------------------
  498|       |            // Find what (if any) intersection the chunk has with subset.
  499|  1.80k|            const SetType to_add = GetChunk(i).transactions & subset.transactions;
  500|  1.80k|            if (to_add.Any()) {
  ------------------
  |  Branch (500:17): [True: 1.29k, False: 512]
  ------------------
  501|       |                // If adding that to accumulator makes us hit all of subset, we are done as no
  502|       |                // shorter intersection with higher/equal feerate exists.
  503|  1.29k|                accumulator.transactions |= to_add;
  504|  1.29k|                if (accumulator.transactions == subset.transactions) break;
  ------------------
  |  Branch (504:21): [True: 1.16k, False: 130]
  ------------------
  505|       |                // Otherwise update the accumulator feerate.
  506|    130|                accumulator.feerate += m_depgraph.FeeRate(to_add);
  507|       |                // If that does result in something better, or something with the same feerate but
  508|       |                // smaller, return that. Even if a longer, higher-feerate intersection exists, it
  509|       |                // does not hurt to return the shorter one (the remainder of the longer intersection
  510|       |                // will generally be found in the next call to Intersect, but even if not, it is not
  511|       |                // required for the improvement guarantee this function makes).
  512|    130|                if (!(accumulator.feerate << subset.feerate)) return accumulator;
  ------------------
  |  Branch (512:21): [True: 12, False: 118]
  ------------------
  513|    130|            }
  514|  1.80k|        }
  515|  1.16k|        return subset;
  516|  1.17k|    }
_ZN17cluster_linearize21LinearizationChunkingIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
  462|  1.69k|    {
  463|  1.69k|        Assume(subset.Any());
  ------------------
  |  |   97|  1.69k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  464|  1.69k|        Assume(subset.IsSubsetOf(m_todo));
  ------------------
  |  |   97|  1.69k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  465|  1.69k|        m_todo -= subset;
  466|  1.69k|        if (GetChunk(0).transactions == subset) {
  ------------------
  |  Branch (466:13): [True: 571, False: 1.12k]
  ------------------
  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|    571|            ++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|    571|            m_linearization = m_linearization.subspan(subset.Count());
  475|  1.12k|        } else {
  476|       |            // Otherwise rechunk what remains of m_linearization.
  477|  1.12k|            m_chunks.clear();
  478|  1.12k|            m_chunks_skip = 0;
  479|  1.12k|            BuildChunks();
  480|  1.12k|        }
  481|  1.69k|    }
_ZN17cluster_linearize9LinearizeIN13bitset_detail9IntBitSetIjEEEENSt3__14pairINS4_6vectorIjNS4_9allocatorIjEEEEbEERKNS_8DepGraphIT_EEmm4SpanIKjE:
 1020|  3.08k|{
 1021|  3.08k|    Assume(old_linearization.empty() || old_linearization.size() == depgraph.TxCount());
  ------------------
  |  |   97|  3.53k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 2.62k, False: 455]
  |  |  |  Branch (97:51): [True: 455, False: 0]
  |  |  ------------------
  ------------------
 1022|  3.08k|    if (depgraph.TxCount() == 0) return {{}, true};
  ------------------
  |  Branch (1022:9): [True: 232, False: 2.84k]
  ------------------
 1023|       |
 1024|  2.84k|    uint64_t iterations_left = max_iterations;
 1025|  2.84k|    std::vector<ClusterIndex> linearization;
 1026|       |
 1027|  2.84k|    AncestorCandidateFinder anc_finder(depgraph);
 1028|  2.84k|    std::optional<SearchCandidateFinder<SetType>> src_finder;
 1029|  2.84k|    linearization.reserve(depgraph.TxCount());
 1030|  2.84k|    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.84k|    uint64_t start_iterations = (uint64_t{depgraph.TxCount()} * depgraph.TxCount() + 63) / 64;
 1037|  2.84k|    if (iterations_left > start_iterations) {
  ------------------
  |  Branch (1037:9): [True: 2.65k, False: 196]
  ------------------
 1038|  2.65k|        iterations_left -= start_iterations;
 1039|  2.65k|        src_finder.emplace(depgraph, rng_seed);
 1040|  2.65k|    }
 1041|       |
 1042|       |    /** Chunking of what remains of the old linearization. */
 1043|  2.84k|    LinearizationChunking old_chunking(depgraph, old_linearization);
 1044|       |
 1045|  12.8k|    while (true) {
  ------------------
  |  Branch (1045:12): [Folded - Ignored]
  ------------------
 1046|       |        // Find the highest-feerate prefix of the remainder of old_linearization.
 1047|  12.8k|        SetInfo<SetType> best_prefix;
 1048|  12.8k|        if (old_chunking.NumChunksLeft()) best_prefix = old_chunking.GetChunk(0);
  ------------------
  |  Branch (1048:13): [True: 2.15k, False: 10.6k]
  ------------------
 1049|       |
 1050|       |        // Then initialize best to be either the best remaining ancestor set, or the first chunk.
 1051|  12.8k|        auto best = anc_finder.FindCandidateSet();
 1052|  12.8k|        if (!best_prefix.feerate.IsEmpty() && best_prefix.feerate >= best.feerate) best = best_prefix;
  ------------------
  |  Branch (1052:13): [True: 2.15k, False: 10.6k]
  |  Branch (1052:47): [True: 1.03k, False: 1.12k]
  ------------------
 1053|       |
 1054|  12.8k|        uint64_t iterations_done_now = 0;
 1055|  12.8k|        uint64_t max_iterations_now = 0;
 1056|  12.8k|        if (src_finder) {
  ------------------
  |  Branch (1056:13): [True: 12.1k, False: 714]
  ------------------
 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|  12.1k|            uint64_t base_iterations = (anc_finder.NumRemaining() + 3) / 4;
 1061|  12.1k|            if (iterations_left > base_iterations) {
  ------------------
  |  Branch (1061:17): [True: 9.95k, False: 2.15k]
  ------------------
 1062|       |                // Invoke bounded search to update best, with up to half of our remaining
 1063|       |                // iterations as limit.
 1064|  9.95k|                iterations_left -= base_iterations;
 1065|  9.95k|                max_iterations_now = (iterations_left + 1) / 2;
 1066|  9.95k|                std::tie(best, iterations_done_now) = src_finder->FindCandidateSet(max_iterations_now, best);
 1067|  9.95k|                iterations_left -= iterations_done_now;
 1068|  9.95k|            }
 1069|  12.1k|        }
 1070|       |
 1071|  12.8k|        if (iterations_done_now == max_iterations_now) {
  ------------------
  |  Branch (1071:13): [True: 3.22k, False: 9.59k]
  ------------------
 1072|  3.22k|            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|  3.22k|            if (old_chunking.NumChunksLeft() > 0) {
  ------------------
  |  Branch (1076:17): [True: 1.17k, False: 2.04k]
  ------------------
 1077|  1.17k|                best = old_chunking.IntersectPrefixes(best);
 1078|  1.17k|            }
 1079|  3.22k|        }
 1080|       |
 1081|       |        // Add to output in topological order.
 1082|  12.8k|        depgraph.AppendTopo(linearization, best.transactions);
 1083|       |
 1084|       |        // Update state to reflect best is no longer to be linearized.
 1085|  12.8k|        anc_finder.MarkDone(best.transactions);
 1086|  12.8k|        if (anc_finder.AllDone()) break;
  ------------------
  |  Branch (1086:13): [True: 2.84k, False: 9.97k]
  ------------------
 1087|  9.97k|        if (src_finder) src_finder->MarkDone(best.transactions);
  ------------------
  |  Branch (1087:13): [True: 9.45k, False: 518]
  ------------------
 1088|  9.97k|        if (old_chunking.NumChunksLeft() > 0) {
  ------------------
  |  Branch (1088:13): [True: 1.69k, False: 8.27k]
  ------------------
 1089|  1.69k|            old_chunking.MarkDone(best.transactions);
 1090|  1.69k|        }
 1091|  9.97k|    }
 1092|       |
 1093|  2.84k|    return {std::move(linearization), optimal};
 1094|  3.08k|}
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_:
  302|  21.0k|    {
  303|  21.0k|        ClusterIndex old_len = list.size();
  304|  64.5k|        for (auto i : select) list.push_back(i);
  ------------------
  |  Branch (304:21): [True: 64.5k, False: 21.0k]
  ------------------
  305|  21.0k|        std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
  306|  21.0k|            const auto a_anc_count = entries[a].ancestors.Count();
  307|  21.0k|            const auto b_anc_count = entries[b].ancestors.Count();
  308|  21.0k|            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
  309|  21.0k|            return a < b;
  310|  21.0k|        });
  311|  21.0k|    }
_ZZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_ENKUljjE_clEjj:
  305|   988k|        std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
  306|   988k|            const auto a_anc_count = entries[a].ancestors.Count();
  307|   988k|            const auto b_anc_count = entries[b].ancestors.Count();
  308|   988k|            if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
  ------------------
  |  Branch (308:17): [True: 807k, False: 180k]
  ------------------
  309|   180k|            return a < b;
  310|   988k|        });
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE13PositionRangeEv:
  116|  11.1k|    ClusterIndex PositionRange() const noexcept { return entries.size(); }
_ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE17GetReducedParentsEj:
  209|  74.3k|    {
  210|  74.3k|        SetType parents = Ancestors(i);
  211|  74.3k|        parents.Reset(i);
  212|   295k|        for (auto parent : parents) {
  ------------------
  |  Branch (212:26): [True: 295k, False: 74.3k]
  ------------------
  213|   295k|            if (parents[parent]) {
  ------------------
  |  Branch (213:17): [True: 281k, False: 13.5k]
  ------------------
  214|   281k|                parents -= Ancestors(parent);
  215|   281k|                parents.Set(parent);
  216|   281k|            }
  217|   295k|        }
  218|  74.3k|        return parents;
  219|  74.3k|    }

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

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

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

_ZNK4SpanIKhE4sizeEv:
  187|   147k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIhE4dataEv:
  174|   144k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE4dataEv:
  174|   134k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanISt4byteE4sizeEv:
  187|   564k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanISt4byteE4dataEv:
  174|   134k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanIKhE7subspanEm:
  196|   134k|    {
  197|   134k|        ASSERT_IF_DEBUG(size() >= offset);
  198|   134k|        return Span<C>(m_data + offset, m_size - offset);
  199|   134k|    }
_ZNK4SpanIhE10size_bytesEv:
  188|   144k|    constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
_ZNK4SpanImE4dataEv:
  174|  2.95k|    constexpr C* data() const noexcept { return m_data; }
_ZNK4SpanImE10size_bytesEv:
  188|  2.95k|    constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
_ZN4SpanIKhEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|   134k|    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|   147k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_Z15AsWritableBytesIhE4SpanISt4byteES0_IT_E:
  264|   144k|{
  265|   144k|    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  266|   144k|}
_ZN4SpanIhEC2IhTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_hEE5valueEiE4typeELi0EEEPS4_m:
  119|   144k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_Z15AsWritableBytesImE4SpanISt4byteES0_IT_E:
  264|  2.95k|{
  265|  2.95k|    return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
  266|  2.95k|}
_ZN4SpanImEC2ImTnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_mEE5valueEiE4typeELi0EEEPS4_m:
  119|  2.95k|    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|  3.08k|        : 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|  49.3k|        : 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|  63.3k|        : m_data(other.data()), m_size(other.size()){}
_ZNK4SpanIKjE4sizeEv:
  187|  19.7k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIKjEixEm:
  191|   189k|    {
  192|   189k|        ASSERT_IF_DEBUG(size() > pos);
  193|   189k|        return m_data[pos];
  194|   189k|    }
_ZNK4SpanIKjE5beginEv:
  175|  47.5k|    constexpr C* begin() const noexcept { return m_data; }
_ZNK4SpanIKjE3endEv:
  176|  47.5k|    constexpr C* end() const noexcept { return m_data + m_size; }
_ZNK4SpanIKjE5emptyEv:
  189|  7.70k|    constexpr bool empty() const noexcept { return size() == 0; }
_ZNK4SpanIKjE5frontEv:
  178|  2.22k|    {
  179|  2.22k|        ASSERT_IF_DEBUG(size() > 0);
  180|  2.22k|        return m_data[0];
  181|  2.22k|    }
_ZNK4SpanIKjE7subspanEm:
  196|  1.21k|    {
  197|  1.21k|        ASSERT_IF_DEBUG(size() >= offset);
  198|  1.21k|        return Span<C>(m_data + offset, m_size - offset);
  199|  1.21k|    }
_ZN4SpanIKjEC2IS0_TnNSt3__19enable_ifIXsr3std14is_convertibleIPA_T_PA_S0_EE5valueEiE4typeELi0EEEPS5_m:
  119|  1.21k|    constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
_ZNK4SpanIK7FeeFracE4sizeEv:
  187|   472k|    constexpr std::size_t size() const noexcept { return m_size; }
_ZNK4SpanIK7FeeFracEixEm:
  191|  1.11M|    {
  192|  1.11M|        ASSERT_IF_DEBUG(size() > pos);
  193|  1.11M|        return m_data[pos];
  194|  1.11M|    }

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

_Z32clusterlin_linearize_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEE:
  831|  3.08k|{
  832|       |    // Verify the behavior of Linearize().
  833|       |
  834|       |    // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from
  835|       |    // the fuzz input.
  836|  3.08k|    SpanReader reader(buffer);
  837|  3.08k|    DepGraph<TestBitSet> depgraph;
  838|  3.08k|    uint64_t rng_seed{0};
  839|  3.08k|    uint64_t iter_count{0};
  840|  3.08k|    uint8_t make_connected{1};
  841|  3.08k|    try {
  842|  3.08k|        reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
  ------------------
  |  |  500|  3.08k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  843|  3.08k|    } catch (const std::ios_base::failure&) {}
  844|       |    // The most complicated graphs are connected ones (other ones just split up). Optionally force
  845|       |    // the graph to be connected.
  846|  3.08k|    if (make_connected) MakeConnected(depgraph);
  ------------------
  |  Branch (846:9): [True: 3.00k, False: 77]
  ------------------
  847|       |
  848|       |    // Optionally construct an old linearization for it.
  849|  3.08k|    std::vector<ClusterIndex> old_linearization;
  850|  3.08k|    {
  851|  3.08k|        uint8_t have_old_linearization{0};
  852|  3.08k|        try {
  853|  3.08k|            reader >> have_old_linearization;
  854|  3.08k|        } catch(const std::ios_base::failure&) {}
  855|  3.08k|        if (have_old_linearization & 1) {
  ------------------
  |  Branch (855:13): [True: 456, False: 2.62k]
  ------------------
  856|    456|            old_linearization = ReadLinearization(depgraph, reader);
  857|    456|            SanityCheck(depgraph, old_linearization);
  858|    456|        }
  859|  3.08k|    }
  860|       |
  861|       |    // Invoke Linearize().
  862|  3.08k|    iter_count &= 0x7ffff;
  863|  3.08k|    auto [linearization, optimal] = Linearize(depgraph, iter_count, rng_seed, old_linearization);
  864|  3.08k|    SanityCheck(depgraph, linearization);
  865|  3.08k|    auto chunking = ChunkLinearization(depgraph, linearization);
  866|       |
  867|       |    // Linearization must always be as good as the old one, if provided.
  868|  3.08k|    if (!old_linearization.empty()) {
  ------------------
  |  Branch (868:9): [True: 455, False: 2.62k]
  ------------------
  869|    455|        auto old_chunking = ChunkLinearization(depgraph, old_linearization);
  870|    455|        auto cmp = CompareChunks(chunking, old_chunking);
  871|    455|        assert(cmp >= 0);
  872|    455|    }
  873|       |
  874|       |    // If the iteration count is sufficiently high, an optimal linearization must be found.
  875|       |    // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is
  876|       |    // 2^n - 1.
  877|  3.08k|    const uint64_t n = depgraph.TxCount();
  878|  3.08k|    if (n <= 19 && iter_count > (uint64_t{1} << n)) {
  ------------------
  |  Branch (878:9): [True: 2.05k, False: 1.02k]
  |  Branch (878:20): [True: 1.06k, False: 998]
  ------------------
  879|  1.06k|        assert(optimal);
  880|  1.06k|    }
  881|       |    // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4)
  882|       |    // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper
  883|       |    // bound for a whole linearization (summing for k=1..n) using the Python expression
  884|       |    // [sum((k+3)//4 + int(math.sqrt(2**k)) + 1 for k in range(1, n + 1)) + (n**2 + 63) // 64 for n in range(0, 35)]:
  885|  3.08k|    static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
  886|  3.08k|        0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
  887|  3.08k|        3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
  888|  3.08k|        316629, 447712
  889|  3.08k|    };
  890|  3.08k|    if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
  ------------------
  |  Branch (890:9): [True: 3.08k, False: 0]
  |  Branch (890:45): [True: 1.35k, False: 1.72k]
  ------------------
  891|  1.35k|        Assume(optimal);
  ------------------
  |  |   97|  1.35k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  892|  1.35k|    }
  893|       |
  894|       |    // If Linearize claims optimal result, run quality tests.
  895|  3.08k|    if (optimal) {
  ------------------
  |  Branch (895:9): [True: 2.40k, False: 673]
  ------------------
  896|       |        // It must be as good as SimpleLinearize.
  897|  2.40k|        auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS);
  898|  2.40k|        SanityCheck(depgraph, simple_linearization);
  899|  2.40k|        auto simple_chunking = ChunkLinearization(depgraph, simple_linearization);
  900|  2.40k|        auto cmp = CompareChunks(chunking, simple_chunking);
  901|  2.40k|        assert(cmp >= 0);
  902|       |        // If SimpleLinearize finds the optimal result too, they must be equal (if not,
  903|       |        // SimpleLinearize is broken).
  904|  2.40k|        if (simple_optimal) assert(cmp == 0);
  ------------------
  |  Branch (904:13): [True: 2.40k, False: 4]
  ------------------
  905|       |
  906|       |        // Only for very small clusters, test every topologically-valid permutation.
  907|  2.40k|        if (depgraph.TxCount() <= 7) {
  ------------------
  |  Branch (907:13): [True: 1.36k, False: 1.04k]
  ------------------
  908|  1.36k|            std::vector<ClusterIndex> perm_linearization;
  909|  4.11k|            for (ClusterIndex i : depgraph.Positions()) perm_linearization.push_back(i);
  ------------------
  |  Branch (909:33): [True: 4.11k, False: 1.36k]
  ------------------
  910|       |            // Iterate over all valid permutations.
  911|   359k|            do {
  912|       |                // Determine whether perm_linearization is topological.
  913|   359k|                TestBitSet perm_done;
  914|   359k|                bool perm_is_topo{true};
  915|   675k|                for (auto i : perm_linearization) {
  ------------------
  |  Branch (915:29): [True: 675k, False: 28.7k]
  ------------------
  916|   675k|                    perm_done.Set(i);
  917|   675k|                    if (!depgraph.Ancestors(i).IsSubsetOf(perm_done)) {
  ------------------
  |  Branch (917:25): [True: 330k, False: 345k]
  ------------------
  918|   330k|                        perm_is_topo = false;
  919|   330k|                        break;
  920|   330k|                    }
  921|   675k|                }
  922|       |                // If so, verify that the obtained linearization is as good as the permutation.
  923|   359k|                if (perm_is_topo) {
  ------------------
  |  Branch (923:21): [True: 28.7k, False: 330k]
  ------------------
  924|  28.7k|                    auto perm_chunking = ChunkLinearization(depgraph, perm_linearization);
  925|  28.7k|                    auto cmp = CompareChunks(chunking, perm_chunking);
  926|  28.7k|                    assert(cmp >= 0);
  927|  28.7k|                }
  928|   359k|            } while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
  ------------------
  |  Branch (928:21): [True: 357k, False: 1.36k]
  ------------------
  929|  1.36k|        }
  930|  2.40k|    }
  931|  3.08k|}
cluster_linearize.cpp:_ZN12_GLOBAL__N_113MakeConnectedIN13bitset_detail9IntBitSetIjEEEEvRN17cluster_linearize8DepGraphIT_EE:
  172|  3.00k|{
  173|  3.00k|    auto todo = depgraph.Positions();
  174|  3.00k|    auto comp = depgraph.FindConnectedComponent(todo);
  175|  3.00k|    Assume(depgraph.IsConnected(comp));
  ------------------
  |  |   97|  3.00k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  176|  3.00k|    todo -= comp;
  177|  30.0k|    while (todo.Any()) {
  ------------------
  |  Branch (177:12): [True: 27.0k, False: 3.00k]
  ------------------
  178|  27.0k|        auto nextcomp = depgraph.FindConnectedComponent(todo);
  179|  27.0k|        Assume(depgraph.IsConnected(nextcomp));
  ------------------
  |  |   97|  27.0k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  180|  27.0k|        depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
  181|  27.0k|        todo -= nextcomp;
  182|  27.0k|        comp = nextcomp;
  183|  27.0k|    }
  184|  3.00k|}
cluster_linearize.cpp:_ZN12_GLOBAL__N_117ReadLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorIjNS4_9allocatorIjEEEERKN17cluster_linearize8DepGraphIT_EER10SpanReader:
  207|    456|{
  208|    456|    std::vector<ClusterIndex> linearization;
  209|    456|    TestBitSet todo = depgraph.Positions();
  210|       |    // In every iteration one topologically-valid transaction is appended to linearization.
  211|  6.22k|    while (todo.Any()) {
  ------------------
  |  Branch (211:12): [True: 5.76k, False: 456]
  ------------------
  212|       |        // Compute the set of transactions with no not-yet-included ancestors.
  213|  5.76k|        TestBitSet potential_next;
  214|  62.3k|        for (auto j : todo) {
  ------------------
  |  Branch (214:21): [True: 62.3k, False: 5.76k]
  ------------------
  215|  62.3k|            if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
  ------------------
  |  Branch (215:17): [True: 17.3k, False: 45.0k]
  ------------------
  216|  17.3k|                potential_next.Set(j);
  217|  17.3k|            }
  218|  62.3k|        }
  219|       |        // There must always be one (otherwise there is a cycle in the graph).
  220|  5.76k|        assert(potential_next.Any());
  221|       |        // Read a number from reader, and interpret it as index into potential_next.
  222|  5.76k|        uint64_t idx{0};
  223|  5.76k|        try {
  224|  5.76k|            reader >> VARINT(idx);
  ------------------
  |  |  500|  5.76k|#define VARINT(obj) Using<VarIntFormatter<VarIntMode::DEFAULT>>(obj)
  ------------------
  225|  5.76k|        } catch (const std::ios_base::failure&) {}
  226|  5.76k|        idx %= potential_next.Count();
  227|       |        // Find out which transaction that corresponds to.
  228|  6.26k|        for (auto j : potential_next) {
  ------------------
  |  Branch (228:21): [True: 6.26k, False: 0]
  ------------------
  229|  6.26k|            if (idx == 0) {
  ------------------
  |  Branch (229:17): [True: 5.76k, False: 500]
  ------------------
  230|       |                // When found, add it to linearization and remove it from todo.
  231|  5.76k|                linearization.push_back(j);
  232|  5.76k|                assert(todo[j]);
  233|  5.76k|                todo.Reset(j);
  234|  5.76k|                break;
  235|  5.76k|            }
  236|    500|            --idx;
  237|    500|        }
  238|  5.76k|    }
  239|    456|    return linearization;
  240|    456|}
cluster_linearize.cpp:_ZN12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKN17cluster_linearize8DepGraphIS3_EE:
   40|  2.40k|        m_depgraph(depgraph), m_todo{depgraph.Positions()} {}
cluster_linearize.cpp:_ZNK12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEm:
   55|  8.18k|    {
   56|  8.18k|        uint64_t iterations_left = max_iterations;
   57|       |        // Queue of work units. Each consists of:
   58|       |        // - inc: set of transactions definitely included
   59|       |        // - und: set of transactions that can be added to inc still
   60|  8.18k|        std::vector<std::pair<SetType, SetType>> queue;
   61|       |        // Initially we have just one queue element, with the entire graph in und.
   62|  8.18k|        queue.emplace_back(SetType{}, m_todo);
   63|       |        // Best solution so far.
   64|  8.18k|        SetInfo best(m_depgraph, m_todo);
   65|       |        // Process the queue.
   66|  1.56M|        while (!queue.empty() && iterations_left) {
  ------------------
  |  Branch (66:16): [True: 1.56M, False: 8.17k]
  |  Branch (66:34): [True: 1.56M, False: 7]
  ------------------
   67|  1.56M|            --iterations_left;
   68|       |            // Pop top element of the queue.
   69|  1.56M|            auto [inc, und] = queue.back();
   70|  1.56M|            queue.pop_back();
   71|       |            // Look for a transaction to consider adding/removing.
   72|  1.56M|            bool inc_none = inc.None();
   73|  1.56M|            for (auto split : und) {
  ------------------
  |  Branch (73:29): [True: 1.32M, False: 784k]
  ------------------
   74|       |                // If inc is empty, consider any split transaction. Otherwise only consider
   75|       |                // transactions that share ancestry with inc so far (which means only connected
   76|       |                // sets will be considered).
   77|  1.32M|                if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) {
  ------------------
  |  Branch (77:21): [True: 29.3k, False: 1.29M]
  |  Branch (77:33): [True: 747k, False: 546k]
  ------------------
   78|       |                    // Add a queue entry with split included.
   79|   776k|                    SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split)));
   80|   776k|                    queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
   81|       |                    // Add a queue entry with split excluded.
   82|   776k|                    queue.emplace_back(inc, und - m_depgraph.Descendants(split));
   83|       |                    // Update statistics to account for the candidate new_inc.
   84|   776k|                    if (new_inc.feerate > best.feerate) best = new_inc;
  ------------------
  |  Branch (84:25): [True: 9.58k, False: 767k]
  ------------------
   85|   776k|                    break;
   86|   776k|                }
   87|  1.32M|            }
   88|  1.56M|        }
   89|  8.18k|        return {std::move(best), max_iterations - iterations_left};
   90|  8.18k|    }
cluster_linearize.cpp:_ZN12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_:
   43|  8.18k|    void MarkDone(SetType select) noexcept { m_todo -= select; }
cluster_linearize.cpp:_ZN12_GLOBAL__N_115SimpleLinearizeIN13bitset_detail9IntBitSetIjEEEENSt3__14pairINS4_6vectorIjNS4_9allocatorIjEEEEbEERKN17cluster_linearize8DepGraphIT_EEm:
  153|  2.40k|{
  154|  2.40k|    std::vector<ClusterIndex> linearization;
  155|  2.40k|    SimpleCandidateFinder finder(depgraph);
  156|  2.40k|    SetType todo = depgraph.Positions();
  157|  2.40k|    bool optimal = true;
  158|  10.5k|    while (todo.Any()) {
  ------------------
  |  Branch (158:12): [True: 8.18k, False: 2.40k]
  ------------------
  159|  8.18k|        auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
  160|  8.18k|        if (iterations_done == max_iterations) optimal = false;
  ------------------
  |  Branch (160:13): [True: 7, False: 8.17k]
  ------------------
  161|  8.18k|        depgraph.AppendTopo(linearization, candidate.transactions);
  162|  8.18k|        todo -= candidate.transactions;
  163|  8.18k|        finder.MarkDone(candidate.transactions);
  164|  8.18k|        max_iterations -= iterations_done;
  165|  8.18k|    }
  166|  2.40k|    return {std::move(linearization), optimal};
  167|  2.40k|}

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

_ZN12CheckGlobalsC2Ev:
   56|  3.08k|CheckGlobals::CheckGlobals() : m_impl(std::make_unique<CheckGlobalsImpl>()) {}
_ZN12CheckGlobalsD2Ev:
   57|  3.08k|CheckGlobals::~CheckGlobals() = default;
_ZN16CheckGlobalsImplC2Ev:
   17|  3.08k|    {
   18|  3.08k|        g_used_g_prng = false;
   19|  3.08k|        g_seeded_g_prng_zero = false;
   20|  3.08k|        g_used_system_time = false;
   21|  3.08k|        SetMockTime(0s);
   22|  3.08k|    }
_ZN16CheckGlobalsImplD2Ev:
   24|  3.08k|    {
   25|  3.08k|        if (g_used_g_prng && !g_seeded_g_prng_zero) {
  ------------------
  |  Branch (25:13): [True: 0, False: 3.08k]
  |  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|  3.08k|        if (g_used_system_time) {
  ------------------
  |  Branch (41:13): [True: 0, False: 3.08k]
  ------------------
   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|  3.08k|    }

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

_ZN13bitset_detail9IntBitSetIjE4SizeEv:
  177|   179k|    static constexpr unsigned Size() noexcept { return MAX_SIZE; }
_ZNK13bitset_detail9IntBitSetIjEixEj:
  170|  1.31M|    {
  171|  1.31M|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  1.31M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  172|  1.31M|        return (m_val >> pos) & 1U;
  173|  1.31M|    }
_ZN13bitset_detail9IntBitSetIjE3SetEj:
  152|  1.65M|    {
  153|  1.65M|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|  1.65M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  154|  1.65M|        m_val |= I{1U} << pos;
  155|  1.65M|    }
_ZN13bitset_detail9IntBitSetIjE5ResetEj:
  164|   511k|    {
  165|   511k|        Assume(pos < MAX_SIZE);
  ------------------
  |  |   97|   511k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  166|   511k|        m_val &= ~I(I{1U} << pos);
  167|   511k|    }
_ZN13bitset_detail9IntBitSetIjE9SingletonEj:
  138|   480k|    {
  139|   480k|        Assume(i < MAX_SIZE);
  ------------------
  |  |   97|   480k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  140|   480k|        return IntBitSet(I(1U) << i);
  141|   480k|    }
_ZN13bitset_detail9IntBitSetIjEC2Ej:
   71|  6.34M|    IntBitSet(I val) noexcept : m_val{val} {}
_ZNK13bitset_detail9IntBitSetIjE3AnyEv:
  181|   867k|    constexpr bool Any() const noexcept { return !None(); }
_ZNK13bitset_detail9IntBitSetIjE4NoneEv:
  179|  2.70M|    constexpr bool None() const noexcept { return m_val == 0; }
_ZNK13bitset_detail9IntBitSetIjE5FirstEv:
  188|   354k|    {
  189|   354k|        Assume(m_val != 0);
  ------------------
  |  |   97|   354k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  190|   354k|        return std::countr_zero(m_val);
  191|   354k|    }
_ZNK13bitset_detail9IntBitSetIjE4LastEv:
  194|   127k|    {
  195|   127k|        Assume(m_val != 0);
  ------------------
  |  |   97|   127k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  196|   127k|        return std::bit_width(m_val) - 1;
  197|   127k|    }
_ZNK13bitset_detail9IntBitSetIjE5CountEv:
  175|  2.83M|    constexpr unsigned Count() const noexcept { return PopCount(m_val); }
_ZN13bitset_detail8PopCountIjEEjT_:
   39|  2.83M|{
   40|  2.83M|    static_assert(std::is_integral_v<I> && std::is_unsigned_v<I> && std::numeric_limits<I>::radix == 2);
   41|  2.83M|    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|  2.83M|    if constexpr (BITS <= 32) {
   45|  2.83M|        v -= (v >> 1) & 0x55555555;
   46|  2.83M|        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
   47|  2.83M|        v = (v + (v >> 4)) & 0x0f0f0f0f;
   48|  2.83M|        if constexpr (BITS > 8) v += v >> 8;
   49|  2.83M|        if constexpr (BITS > 16) v += v >> 16;
   50|  2.83M|        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|  2.83M|}
_ZN13bitset_detail9IntBitSetIjEC2Ev:
  119|  1.04M|    constexpr IntBitSet() noexcept : m_val{0} {}
_ZN13bitset_detail4swapERNS_9IntBitSetIjEES2_:
  223|   112k|    friend constexpr void swap(IntBitSet& a, IntBitSet& b) noexcept { std::swap(a.m_val, b.m_val); }
_ZN13bitset_detail9IntBitSetIjE4FillEj:
  144|  24.8k|    {
  145|  24.8k|        IntBitSet ret;
  146|  24.8k|        Assume(count <= MAX_SIZE);
  ------------------
  |  |   97|  24.8k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  147|  24.8k|        if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count);
  ------------------
  |  Branch (147:13): [True: 24.8k, False: 0]
  ------------------
  148|  24.8k|        return ret;
  149|  24.8k|    }
_ZNK13bitset_detail9IntBitSetIjE5beginEv:
  183|  3.97M|    constexpr Iterator begin() const noexcept { return Iterator(m_val); }
_ZN13bitset_detail9IntBitSetIjE8IteratorC2Ej:
   86|  3.97M|        constexpr Iterator(I val) noexcept : m_val(val), m_pos(0)
   87|  3.97M|        {
   88|  3.97M|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (88:17): [True: 2.82M, False: 1.15M]
  ------------------
   89|  3.97M|        }
_ZN13bitset_detaileqERKNS_9IntBitSetIjE8IteratorERKNS1_11IteratorEndE:
   98|  20.4M|        {
   99|  20.4M|            return a.m_val == 0;
  100|  20.4M|        }
_ZNK13bitset_detail9IntBitSetIjE3endEv:
  185|  3.97M|    constexpr IteratorEnd end() const noexcept { return IteratorEnd(); }
_ZNK13bitset_detail9IntBitSetIjE8IteratordeEv:
  111|  17.3M|        {
  112|  17.3M|            Assume(m_val != 0);
  ------------------
  |  |   97|  17.3M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  113|  17.3M|            return m_pos;
  114|  17.3M|        }
_ZN13bitset_detail9IntBitSetIjE8IteratorppEv:
  103|  16.4M|        {
  104|  16.4M|            Assume(m_val != 0);
  ------------------
  |  |   97|  16.4M|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  105|  16.4M|            m_val &= m_val - I{1U};
  106|  16.4M|            if (m_val != 0) m_pos = std::countr_zero(m_val);
  ------------------
  |  Branch (106:17): [True: 14.4M, False: 2.00M]
  ------------------
  107|  16.4M|            return *this;
  108|  16.4M|        }
_ZN13bitset_detail9IntBitSetIjEoRERKS1_:
  199|  1.30M|    constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEaNERKS1_:
  201|   160k|    constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; }
_ZN13bitset_detail9IntBitSetIjEmIERKS1_:
  203|   747k|    constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; }
_ZN13bitset_detailorERKNS_9IntBitSetIjEES3_:
  211|   886k|    friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); }
_ZN13bitset_detailanERKNS_9IntBitSetIjEES3_:
  209|  1.68M|    friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); }
_ZN13bitset_detailmiERKNS_9IntBitSetIjEES3_:
  213|  3.29M|    friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); }
_ZNK13bitset_detail9IntBitSetIjE10IsSubsetOfERKS1_:
  221|  1.55M|    constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; }
_ZN13bitset_detaileqERKNS_9IntBitSetIjEES3_:
  217|   165k|    friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default;
_ZNK13bitset_detail9IntBitSetIjE8OverlapsERKS1_:
  207|  1.62M|    constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; }

_Z22inline_assertion_checkILb0EbEOT0_S1_PKciS3_S3_:
   52|  41.8M|{
   53|  41.8M|    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|  41.8M|    ) {
   58|  41.8M|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 41.8M]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  41.8M|    }
   62|  41.8M|    return std::forward<T>(val);
   63|  41.8M|}
_Z22inline_assertion_checkILb0ERbEOT0_S2_PKciS4_S4_:
   52|  1.35k|{
   53|  1.35k|    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.35k|    ) {
   58|  1.35k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 1.35k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  1.35k|    }
   62|  1.35k|    return std::forward<T>(val);
   63|  1.35k|}
_Z22inline_assertion_checkILb0ERmEOT0_S2_PKciS4_S4_:
   52|   520k|{
   53|   520k|    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|   520k|    ) {
   58|   520k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 520k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|   520k|    }
   62|   520k|    return std::forward<T>(val);
   63|   520k|}
_Z22inline_assertion_checkILb1EbEOT0_S1_PKciS3_S3_:
   52|  3.08k|{
   53|  3.08k|    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|  3.08k|    ) {
   58|  3.08k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 3.08k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  3.08k|    }
   62|  3.08k|    return std::forward<T>(val);
   63|  3.08k|}
_Z22inline_assertion_checkILb1ERPKNSt3__18functionIFvNS0_4spanIKhLm18446744073709551615EEEEEEEOT0_SB_PKciSD_SD_:
   52|  3.08k|{
   53|  3.08k|    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|  3.08k|    ) {
   58|  3.08k|        if (!val) {
  ------------------
  |  Branch (58:13): [True: 0, False: 3.08k]
  ------------------
   59|      0|            assertion_fail(file, line, func, assertion);
   60|      0|        }
   61|  3.08k|    }
   62|  3.08k|    return std::forward<T>(val);
   63|  3.08k|}

_Z13CompareChunks4SpanIK7FeeFracES2_:
   11|  31.6k|{
   12|       |    /** Array to allow indexed access to input diagrams. */
   13|  31.6k|    const std::array<Span<const FeeFrac>, 2> chunk = {chunks0, chunks1};
   14|       |    /** How many elements we have processed in each input. */
   15|  31.6k|    size_t next_index[2] = {0, 0};
   16|       |    /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */
   17|  31.6k|    FeeFrac accum[2];
   18|       |    /** Whether the corresponding input is strictly better than the other at least in one place. */
   19|  31.6k|    bool better_somewhere[2] = {false, false};
   20|       |    /** Get the first unprocessed point in diagram number dia. */
   21|  31.6k|    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|  31.6k|    const auto prev_point = [&](int dia) { return accum[dia]; };
   24|       |    /** Move to the next point in diagram number dia. */
   25|  31.6k|    const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };
   26|       |
   27|   236k|    do {
   28|   236k|        bool done_0 = next_index[0] == chunk[0].size();
   29|   236k|        bool done_1 = next_index[1] == chunk[1].size();
   30|   236k|        if (done_0 && done_1) break;
  ------------------
  |  Branch (30:13): [True: 31.6k, False: 204k]
  |  Branch (30:23): [True: 31.6k, 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|   204k|        const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
  ------------------
  |  Branch (34:34): [True: 0, False: 204k]
  |  Branch (34:44): [True: 0, False: 204k]
  ------------------
   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|   204k|        const FeeFrac& point_p = next_point(unproc_side);
   41|   204k|        const FeeFrac& point_a = prev_point(!unproc_side);
   42|       |
   43|   204k|        const auto slope_ap = point_p - point_a;
   44|   204k|        Assume(slope_ap.size > 0);
  ------------------
  |  |   97|   204k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   45|   204k|        std::weak_ordering cmp = std::weak_ordering::equivalent;
   46|   204k|        if (done_0 || done_1) {
  ------------------
  |  Branch (46:13): [True: 0, False: 204k]
  |  Branch (46:23): [True: 0, False: 204k]
  ------------------
   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|   204k|        } else {
   51|       |            // If both sides have points left, compute B, and the slope of AB explicitly.
   52|   204k|            const FeeFrac& point_b = next_point(!unproc_side);
   53|   204k|            const auto slope_ab = point_b - point_a;
   54|   204k|            Assume(slope_ab.size >= slope_ap.size);
  ------------------
  |  |   97|   204k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   55|   204k|            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|   204k|            if (point_b.size == point_p.size) advance(!unproc_side);
  ------------------
  |  Branch (59:17): [True: 87.5k, False: 117k]
  ------------------
   60|   204k|        }
   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|   204k|        if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
  ------------------
  |  Branch (63:13): [True: 98.0k, False: 106k]
  ------------------
   64|   204k|        if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
  ------------------
  |  Branch (64:13): [True: 18.0k, False: 186k]
  ------------------
   65|   204k|        advance(unproc_side);
   66|       |
   67|       |        // If both diagrams are better somewhere, they are incomparable.
   68|   204k|        if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
  ------------------
  |  Branch (68:13): [True: 145k, False: 59.3k]
  |  Branch (68:36): [True: 0, False: 145k]
  ------------------
   69|   204k|    } while(true);
  ------------------
  |  Branch (69:13): [Folded - Ignored]
  ------------------
   70|       |
   71|       |    // Otherwise compare the better_somewhere values.
   72|  31.6k|    return better_somewhere[0] <=> better_somewhere[1];
   73|  31.6k|}
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_0clEi:
   21|   818k|    const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; };
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_1clEi:
   23|   204k|    const auto prev_point = [&](int dia) { return accum[dia]; };
feefrac.cpp:_ZZ13CompareChunks4SpanIK7FeeFracES2_ENK3$_2clEi:
   25|   292k|    const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };

_ZN7FeeFrac3MulEli:
   55|  6.65M|    {
   56|       |        // If __int128 is available, use 128-bit wide multiply.
   57|  6.65M|        return __int128{a} * b;
   58|  6.65M|    }
_ZN7FeeFracC2Ev:
   67|  1.52M|    constexpr inline FeeFrac() noexcept : fee{0}, size{0} {}
_ZN7FeeFracC2Eli:
   70|  1.37M|    constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {}
_ZNK7FeeFrac7IsEmptyEv:
   76|  1.32M|    bool inline IsEmpty() const noexcept {
   77|  1.32M|        return size == 0;
   78|  1.32M|    }
_ZN7FeeFracpLERKS_:
   82|  13.6M|    {
   83|  13.6M|        fee += other.fee;
   84|  13.6M|        size += other.size;
   85|  13.6M|    }
_ZN7FeeFracmIERKS_:
   89|   112k|    {
   90|   112k|        fee -= other.fee;
   91|   112k|        size -= other.size;
   92|   112k|    }
_ZplRK7FeeFracS1_:
   96|   928k|    {
   97|   928k|        return {a.fee + b.fee, a.size + b.size};
   98|   928k|    }
_ZmiRK7FeeFracS1_:
  102|   409k|    {
  103|   409k|        return {a.fee - b.fee, a.size - b.size};
  104|   409k|    }
_Z14FeeRateCompareRK7FeeFracS1_:
  114|   204k|    {
  115|   204k|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  116|   204k|        return cross_a <=> cross_b;
  117|   204k|    }
_ZlsRK7FeeFracS1_:
  121|    130|    {
  122|    130|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  123|    130|        return cross_a < cross_b;
  124|    130|    }
_ZrsRK7FeeFracS1_:
  128|   815k|    {
  129|   815k|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  130|   815k|        return cross_a > cross_b;
  131|   815k|    }
_ZssRK7FeeFracS1_:
  135|  2.30M|    {
  136|  2.30M|        auto cross_a = Mul(a.fee, b.size), cross_b = Mul(b.fee, a.size);
  137|  2.30M|        if (cross_a == cross_b) return b.size <=> a.size;
  ------------------
  |  Branch (137:13): [True: 579k, False: 1.72M]
  ------------------
  138|  1.72M|        return cross_a <=> cross_b;
  139|  2.30M|    }
_Z4swapR7FeeFracS0_:
  143|   112k|    {
  144|   112k|        std::swap(a.fee, b.fee);
  145|   112k|        std::swap(a.size, b.size);
  146|   112k|    }

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

_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemEC2Ev:
  107|  9.95k|    VecDeque() noexcept = default;
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE7reserveEm:
  207|  9.95k|    {
  208|  9.95k|        if (capacity > m_capacity) Reallocate(capacity);
  ------------------
  |  Branch (208:13): [True: 9.95k, False: 0]
  ------------------
  209|  9.95k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE10ReallocateEm:
   40|  19.9k|    {
   41|  19.9k|        Assume(capacity >= m_size);
  ------------------
  |  |   97|  19.9k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   42|  19.9k|        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
  ------------------
  |  |   97|  59.7k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 9.97k, False: 9.92k]
  |  |  |  Branch (97:51): [True: 9.95k, False: 25]
  |  |  |  Branch (97:51): [True: 9.95k, False: 0]
  |  |  ------------------
  ------------------
   43|       |        // Allocate new buffer.
   44|  19.9k|        T* new_buffer = capacity ? std::allocator<T>().allocate(capacity) : nullptr;
  ------------------
  |  Branch (44:25): [True: 9.95k, False: 9.95k]
  ------------------
   45|  19.9k|        if (capacity) {
  ------------------
  |  Branch (45:13): [True: 9.95k, False: 9.95k]
  ------------------
   46|  9.95k|            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|  9.95k|                size_t first_part = FirstPart();
   49|  9.95k|                if (first_part != 0) {
  ------------------
  |  Branch (49:21): [True: 0, False: 9.95k]
  ------------------
   50|      0|                    std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T));
   51|      0|                }
   52|  9.95k|                if (first_part != m_size) {
  ------------------
  |  Branch (52:21): [True: 0, False: 9.95k]
  ------------------
   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|  9.95k|        }
   66|       |        // Deallocate old buffer and update housekeeping.
   67|  19.9k|        std::allocator<T>().deallocate(m_buffer, m_capacity);
   68|  19.9k|        m_buffer = new_buffer;
   69|  19.9k|        m_offset = 0;
   70|  19.9k|        m_capacity = capacity;
   71|  19.9k|        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
  ------------------
  |  |   97|  69.6k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  |  |  ------------------
  |  |  |  Branch (97:51): [True: 19.9k, False: 0]
  |  |  |  Branch (97:51): [True: 9.95k, False: 9.95k]
  |  |  |  Branch (97:51): [True: 9.95k, False: 0]
  |  |  ------------------
  ------------------
   72|  19.9k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE9FirstPartEv:
   37|  9.95k|    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE12emplace_backIJS7_S4_7FeeFracEEEvDpOT_:
  220|   178k|    {
  221|   178k|        if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
  ------------------
  |  Branch (221:13): [True: 0, False: 178k]
  ------------------
  222|   178k|        std::construct_at(m_buffer + BufferIndex(m_size), std::forward<Args>(args)...);
  223|   178k|        ++m_size;
  224|   178k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE11BufferIndexEm:
   76|   386k|    {
   77|   386k|        Assume(pos < m_capacity);
  ------------------
  |  |   97|   386k|#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|   386k|        if (pos >= m_capacity - m_offset) {
  ------------------
  |  Branch (80:13): [True: 176k, False: 210k]
  ------------------
   81|   176k|            return (m_offset + pos) - m_capacity;
   82|   210k|        } else {
   83|   210k|            return m_offset + pos;
   84|   210k|        }
   85|   386k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5emptyEv:
  310|   135k|    bool empty() const noexcept { return m_size == 0; }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE4sizeEv:
  312|   460k|    size_t size() const noexcept { return m_size; }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemEixEm:
  297|   112k|    {
  298|   112k|        Assume(idx < m_size);
  ------------------
  |  |   97|   112k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  299|   112k|        return m_buffer[BufferIndex(idx)];
  300|   112k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5frontEv:
  269|   299k|    {
  270|   299k|        Assume(m_size);
  ------------------
  |  |   97|   299k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  271|   299k|        return m_buffer[m_offset];
  272|   299k|    }
_ZNK8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE8capacityEv:
  314|   334k|    size_t capacity() const noexcept { return m_capacity; }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE4backEv:
  283|  48.0k|    {
  284|  48.0k|        Assume(m_size);
  ------------------
  |  |   97|  48.0k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  285|  48.0k|        return m_buffer[BufferIndex(m_size - 1)];
  286|  48.0k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE8pop_backEv:
  261|  48.0k|    {
  262|  48.0k|        Assume(m_size);
  ------------------
  |  |   97|  48.0k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  263|  48.0k|        std::destroy_at(m_buffer + BufferIndex(m_size - 1));
  264|  48.0k|        --m_size;
  265|  48.0k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE9pop_frontEv:
  251|   125k|    {
  252|   125k|        Assume(m_size);
  ------------------
  |  |   97|   125k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
  253|   125k|        std::destroy_at(m_buffer + m_offset);
  254|   125k|        --m_size;
  255|   125k|        ++m_offset;
  256|   125k|        if (m_offset == m_capacity) m_offset = 0;
  ------------------
  |  Branch (256:13): [True: 256, False: 125k]
  ------------------
  257|   125k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemED2Ev:
  130|  9.95k|    {
  131|  9.95k|        clear();
  132|  9.95k|        Reallocate(0);
  133|  9.95k|    }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE5clearEv:
  126|  9.95k|    void clear() noexcept { ResizeDown(0); }
_ZN8VecDequeIZN17cluster_linearize21SearchCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEmNS0_7SetInfoIS4_EEE8WorkItemE10ResizeDownEm:
   90|  9.95k|    {
   91|  9.95k|        Assume(size <= m_size);
  ------------------
  |  |   97|  9.95k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
  ------------------
   92|  9.95k|        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|  9.95k|            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|  9.95k|    }