Inside Bitcoin

1001            return MergeChunks(chunk_idx, merge_chunk_idx);
1002        } else {
1003            return MergeChunks(merge_chunk_idx, chunk_idx);
1004        }
1005    }
1006
1007    /** Determine which chunk to merge chunk_idx with, or INVALID_SET_IDX if none. */
1008    template<bool DownWard>
1009    SetIdx PickMergeCandidate(SetIdx chunk_idx) noexcept
1010    {
1011        m_cost.PickMergeCandidateBegin();
1012        /** Information about the chunk. */
1013        Assume(m_chunk_idxs[chunk_idx]);
1014        auto& chunk_info = m_set_info[chunk_idx];
1015        // Iterate over all chunks reachable from this one. For those depended-on chunks,
1016        // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one.
1017        // If multiple equal-feerate candidate chunks to merge with exist, pick a random one
1018        // among them.
1019
1020        /** The minimum feerate (if downward) or maximum feerate (if upward) to consider when
1021         *  looking for candidate chunks to merge with. Initially, this is the original chunk's
1022         *  feerate, but is updated to be the current best candidate whenever one is found. */
1023        FeeFrac best_other_chunk_feerate = chunk_info.feerate;
1024        /** The chunk index for the best candidate chunk to merge with. INVALID_SET_IDX if none. */
1025        SetIdx best_other_chunk_idx = INVALID_SET_IDX;
1026        /** We generate random tiebreak values to pick between equal-feerate candidate chunks.
1027         *  This variable stores the tiebreak of the current best candidate. */
1028        uint64_t best_other_chunk_tiebreak{0};
1029
1030        /** Which parent/child transactions we still need to process the chunks for. */
1031        auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first;
1032        unsigned steps = 0;
1033        while (todo.Any()) {
1034            ++steps;
1035            // Find a chunk for a transaction in todo, and remove all its transactions from todo.
1036            auto reached_chunk_idx = m_tx_data[todo.First()].chunk_idx;
1037            auto& reached_chunk_info = m_set_info[reached_chunk_idx];
1038            todo -= reached_chunk_info.transactions;
1039            // See if it has an acceptable feerate.
1040            auto cmp = DownWard ? ByRatio{best_other_chunk_feerate} <=> ByRatio{reached_chunk_info.feerate}
1041                                : ByRatio{reached_chunk_info.feerate} <=> ByRatio{best_other_chunk_feerate};
1042            if (cmp > 0) continue;
1043            uint64_t tiebreak = m_rng.rand64();
1044            if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) {
1045                best_other_chunk_feerate = reached_chunk_info.feerate;
1046                best_other_chunk_idx = reached_chunk_idx;
1047                best_other_chunk_tiebreak = tiebreak;
1048            }
1049        }
1050        Assume(steps <= m_set_info.size());
1051
1052        m_cost.PickMergeCandidateEnd(/*num_steps=*/steps);
1053        return best_other_chunk_idx;
1054    }
1055
1056    /** Perform an upward or downward merge step, on the specified chunk. Returns the merged chunk,
1057     *  or INVALID_SET_IDX if no merge took place. */
1058    template<bool DownWard>
1059    SetIdx MergeStep(SetIdx chunk_idx) noexcept
1060    {
1061        auto merge_chunk_idx = PickMergeCandidate<DownWard>(chunk_idx);
1062        if (merge_chunk_idx == INVALID_SET_IDX) return INVALID_SET_IDX;
1063        chunk_idx = MergeChunksDirected<DownWard>(chunk_idx, merge_chunk_idx);
1064        Assume(chunk_idx != INVALID_SET_IDX);
1065        return chunk_idx;
1066    }
1067
1068    /** Perform an upward or downward merge sequence on the specified chunk. */
1069    template<bool DownWard>
1070    void MergeSequence(SetIdx chunk_idx) noexcept
1071    {
1072        Assume(m_chunk_idxs[chunk_idx]);
1073        while (true) {
1074            auto merged_chunk_idx = MergeStep<DownWard>(chunk_idx);
1075            if (merged_chunk_idx == INVALID_SET_IDX) break;
1076            chunk_idx = merged_chunk_idx;
1077        }
1078        // Add the chunk to the queue of improvable chunks, if it wasn't already there.
1079        if (!m_suboptimal_idxs[chunk_idx]) {
1080            m_suboptimal_idxs.Set(chunk_idx);
1081            m_suboptimal_chunks.push_back(chunk_idx);
1082        }
1083    }
1084
1085    /** Split a chunk, and then merge the resulting two chunks to make the graph topological
1086     *  again. */
1087    void Improve(TxIdx parent_idx, TxIdx child_idx) noexcept
1088    {
1089        // Deactivate the specified dependency, splitting it into two new chunks: a top containing
1090        // the parent, and a bottom containing the child. The top should have a higher feerate.
1091        auto [parent_chunk_idx, child_chunk_idx] = Deactivate(parent_idx, child_idx);
1092
1093        // At this point we have exactly two chunks which may violate topology constraints (the
1094        // parent chunk and child chunk that were produced by deactivation). We can fix
1095        // these using just merge sequences, one upwards and one downwards, avoiding the need for a
1096        // full MakeTopological.
1097        const auto& parent_reachable = m_reachable[parent_chunk_idx].first;
1098        const auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
1099        if (parent_reachable.Overlaps(child_chunk_txn)) {
1100            // The parent chunk has a dependency on a transaction in the child chunk. In this case,
1101            // the parent needs to merge back with the child chunk (a self-merge), and no other
1102            // merges are needed. Special-case this, so the overhead of PickMergeCandidate and
1103            // MergeSequence can be avoided.
1104
1105            // In the self-merge, the roles reverse: the parent chunk (from the split) depends
1106            // on the child chunk, so child_chunk_idx is the "top" and parent_chunk_idx is the
1107            // "bottom" for MergeChunks.
1108            auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
1109            if (!m_suboptimal_idxs[merged_chunk_idx]) {
1110                m_suboptimal_idxs.Set(merged_chunk_idx);
1111                m_suboptimal_chunks.push_back(merged_chunk_idx);
1112            }
1113        } else {
1114            // Merge the top chunk with lower-feerate chunks it depends on.
1115            MergeSequence<false>(parent_chunk_idx);
1116            // Merge the bottom chunk with higher-feerate chunks that depend on it.
1117            MergeSequence<true>(child_chunk_idx);
1118        }
1119    }
1120
1121    /** Determine the next chunk to optimize, or INVALID_SET_IDX if none. */
1122    SetIdx PickChunkToOptimize() noexcept
1123    {
1124        m_cost.PickChunkToOptimizeBegin();
1125        unsigned steps{0};
1126        while (!m_suboptimal_chunks.empty()) {
1127            ++steps;
1128            // Pop an entry from the potentially-suboptimal chunk queue.
1129            SetIdx chunk_idx = m_suboptimal_chunks.front();
1130            Assume(m_suboptimal_idxs[chunk_idx]);
1131            m_suboptimal_idxs.Reset(chunk_idx);
1132            m_suboptimal_chunks.pop_front();
1133            if (m_chunk_idxs[chunk_idx]) {
1134                m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
1135                return chunk_idx;
1136            }
1137            // If what was popped is not currently a chunk, continue. This may
1138            // happen when a split chunk merges in Improve() with one or more existing chunks that
1139            // are themselves on the suboptimal queue already.
1140        }
1141        m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
1142        return INVALID_SET_IDX;
1143    }
1144
1145    /** Find a (parent, child) dependency to deactivate in chunk_idx, or (-1, -1) if none. */
1146    std::pair<TxIdx, TxIdx> PickDependencyToSplit(SetIdx chunk_idx) noexcept
1147    {
1148        m_cost.PickDependencyToSplitBegin();
1149        Assume(m_chunk_idxs[chunk_idx]);
1150        auto& chunk_info = m_set_info[chunk_idx];
1151
1152        // Remember the best dependency {par, chl} seen so far.
1153        std::pair<TxIdx, TxIdx> candidate_dep = {TxIdx(-1), TxIdx(-1)};
1154        uint64_t candidate_tiebreak = 0;
1155        // Iterate over all transactions.
1156        for (auto tx_idx : chunk_info.transactions) {
1157            const auto& tx_data = m_tx_data[tx_idx];
1158            // Iterate over all active child dependencies of the transaction.
1159            for (auto child_idx : tx_data.active_children) {
1160                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
1161                // Skip if this dependency is ineligible (the top chunk that would be created
1162                // does not have higher feerate than the chunk it is currently part of).
1163                auto cmp = ByRatio{dep_top_info.feerate} <=> ByRatio{chunk_info.feerate};
1164                if (cmp <= 0) continue;
1165                // Generate a random tiebreak for this dependency, and reject it if its tiebreak
1166                // is worse than the best so far. This means that among all eligible
1167                // dependencies, a uniformly random one will be chosen.
1168                uint64_t tiebreak = m_rng.rand64();
1169                if (tiebreak < candidate_tiebreak) continue;
1170                // Remember this as our (new) candidate dependency.
1171                candidate_dep = {tx_idx, child_idx};
1172                candidate_tiebreak = tiebreak;
1173            }
1174        }
1175        m_cost.PickDependencyToSplitEnd(/*num_txns=*/chunk_info.transactions.Count());
1176        return candidate_dep;
1177    }
1178
1179public:
1180    /** Construct a spanning forest for the given DepGraph, with every transaction in its own chunk
1181     *  (not topological). */
1182    explicit SpanningForestState(const DepGraph<SetType>& depgraph LIFETIMEBOUND, uint64_t rng_seed, const CostModel& cost = CostModel{}) noexcept :
1183        m_rng(rng_seed), m_depgraph(depgraph), m_cost(cost)
1184    {
1185        m_cost.InitializeBegin();
1186        m_transaction_idxs = depgraph.Positions();
1187        auto num_transactions = m_transaction_idxs.Count();
1188        m_tx_data.resize(depgraph.PositionRange());
1189        m_set_info.resize(num_transactions);
1190        m_reachable.resize(num_transactions);
1191        m_suboptimal_chunks.reserve(num_transactions);
1192        size_t num_chunks = 0;
1193        size_t num_deps = 0;
1194        for (auto tx_idx : m_transaction_idxs) {
1195            // Fill in transaction data.
1196            auto& tx_data = m_tx_data[tx_idx];
1197            tx_data.parents = depgraph.GetReducedParents(tx_idx);
1198            for (auto parent_idx : tx_data.parents) {
1199                m_tx_data[parent_idx].children.Set(tx_idx);
1200            }
1201            num_deps += tx_data.parents.Count();
1202            // Create a singleton chunk for it.
1203            tx_data.chunk_idx = num_chunks;
1204            m_set_info[num_chunks++] = SetInfo(depgraph, tx_idx);
1205        }
1206        // Set the reachable transactions for each chunk to the transactions' parents and children.
1207        for (SetIdx chunk_idx = 0; chunk_idx < num_transactions; ++chunk_idx) {
1208            auto& tx_data = m_tx_data[m_set_info[chunk_idx].transactions.First()];
1209            m_reachable[chunk_idx].first = tx_data.parents;
1210            m_reachable[chunk_idx].second = tx_data.children;
1211        }
1212        Assume(num_chunks == num_transactions);
1213        // Mark all chunk sets as chunks.
1214        m_chunk_idxs = SetType::Fill(num_chunks);
1215        m_cost.InitializeEnd(/*num_txns=*/num_chunks, /*num_deps=*/num_deps);
1216    }
1217
1218    /** Load an existing linearization. Must be called immediately after constructor. The result is
1219     *  topological if the linearization is valid. Otherwise, MakeTopological still needs to be
1220     *  called. */
1221    void LoadLinearization(std::span<const DepGraphIndex> old_linearization) noexcept
1222    {
1223        // Add transactions one by one, in order of existing linearization.
1224        for (DepGraphIndex tx_idx : old_linearization) {
1225            auto chunk_idx = m_tx_data[tx_idx].chunk_idx;
1226            // Merge the chunk upwards, as long as merging succeeds.
1227            while (true) {
1228                chunk_idx = MergeStep<false>(chunk_idx);
1229                if (chunk_idx == INVALID_SET_IDX) break;
1230            }
1231        }
1232    }
1233
1234    /** Make state topological. Can be called after constructing, or after LoadLinearization. */
1235    void MakeTopological() noexcept
1236    {
1237        m_cost.MakeTopologicalBegin();
1238        Assume(m_suboptimal_chunks.empty());
1239        /** What direction to initially merge chunks in; one of the two directions is enough. This
1240         *  is sufficient because if a non-topological inactive dependency exists between two
1241         *  chunks, at least one of the two chunks will eventually be processed in a direction that
1242         *  discovers it - either the lower chunk tries upward, or the upper chunk tries downward.
1243         *  Chunks that are the result of the merging are always tried in both directions. */
1244        unsigned init_dir = m_rng.randbool();
1245        /** Which chunks are the result of merging, and thus need merge attempts in both
1246         *  directions. */
1247        SetType merged_chunks;
1248        // Mark chunks as suboptimal.
1249        m_suboptimal_idxs = m_chunk_idxs;
1250        for (auto chunk_idx : m_chunk_idxs) {