Inside Bitcoin

1251            m_suboptimal_chunks.emplace_back(chunk_idx);
1252            // Randomize the initial order of suboptimal chunks in the queue.
1253            SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
1254            if (j != m_suboptimal_chunks.size() - 1) {
1255                std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1256            }
1257        }
1258        unsigned chunks = m_chunk_idxs.Count();
1259        unsigned steps = 0;
1260        while (!m_suboptimal_chunks.empty()) {
1261            ++steps;
1262            // Pop an entry from the potentially-suboptimal chunk queue.
1263            SetIdx chunk_idx = m_suboptimal_chunks.front();
1264            m_suboptimal_chunks.pop_front();
1265            Assume(m_suboptimal_idxs[chunk_idx]);
1266            m_suboptimal_idxs.Reset(chunk_idx);
1267            // If what was popped is not currently a chunk, continue. This may
1268            // happen when it was merged with something else since being added.
1269            if (!m_chunk_idxs[chunk_idx]) continue;
1270            /** What direction(s) to attempt merging in. 1=up, 2=down, 3=both. */
1271            unsigned direction = merged_chunks[chunk_idx] ? 3 : init_dir + 1;
1272            int flip = m_rng.randbool();
1273            for (int i = 0; i < 2; ++i) {
1274                if (i ^ flip) {
1275                    if (!(direction & 1)) continue;
1276                    // Attempt to merge the chunk upwards.
1277                    auto result_up = MergeStep<false>(chunk_idx);
1278                    if (result_up != INVALID_SET_IDX) {
1279                        if (!m_suboptimal_idxs[result_up]) {
1280                            m_suboptimal_idxs.Set(result_up);
1281                            m_suboptimal_chunks.push_back(result_up);
1282                        }
1283                        merged_chunks.Set(result_up);
1284                        break;
1285                    }
1286                } else {
1287                    if (!(direction & 2)) continue;
1288                    // Attempt to merge the chunk downwards.
1289                    auto result_down = MergeStep<true>(chunk_idx);
1290                    if (result_down != INVALID_SET_IDX) {
1291                        if (!m_suboptimal_idxs[result_down]) {
1292                            m_suboptimal_idxs.Set(result_down);
1293                            m_suboptimal_chunks.push_back(result_down);
1294                        }
1295                        merged_chunks.Set(result_down);
1296                        break;
1297                    }
1298                }
1299            }
1300        }
1301        m_cost.MakeTopologicalEnd(/*num_chunks=*/chunks, /*num_steps=*/steps);
1302    }
1303
1304    /** Initialize the data structure for optimization. It must be topological already. */
1305    void StartOptimizing() noexcept
1306    {
1307        m_cost.StartOptimizingBegin();
1308        Assume(m_suboptimal_chunks.empty());
1309        // Mark chunks suboptimal.
1310        m_suboptimal_idxs = m_chunk_idxs;
1311        for (auto chunk_idx : m_chunk_idxs) {
1312            m_suboptimal_chunks.push_back(chunk_idx);
1313            // Randomize the initial order of suboptimal chunks in the queue.
1314            SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
1315            if (j != m_suboptimal_chunks.size() - 1) {
1316                std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1317            }
1318        }
1319        m_cost.StartOptimizingEnd(/*num_chunks=*/m_suboptimal_chunks.size());
1320    }
1321
1322    /** Try to improve the forest. Returns false if it is optimal, true otherwise. */
1323    bool OptimizeStep() noexcept
1324    {
1325        auto chunk_idx = PickChunkToOptimize();
1326        if (chunk_idx == INVALID_SET_IDX) {
1327            // No improvable chunk was found, we are done.
1328            return false;
1329        }
1330        auto [parent_idx, child_idx] = PickDependencyToSplit(chunk_idx);
1331        if (parent_idx == TxIdx(-1)) {
1332            // Nothing to improve in chunk_idx. Need to continue with other chunks, if any.
1333            return !m_suboptimal_chunks.empty();
1334        }
1335        // Deactivate the found dependency and then make the state topological again with a
1336        // sequence of merges.
1337        Improve(parent_idx, child_idx);
1338        return true;
1339    }
1340
1341    /** Initialize data structure for minimizing the chunks. Can only be called if state is known
1342     *  to be optimal. OptimizeStep() cannot be called anymore afterwards. */
1343    void StartMinimizing() noexcept
1344    {
1345        m_cost.StartMinimizingBegin();
1346        m_nonminimal_chunks.clear();
1347        m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
1348        // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
1349        // direction, to m_nonminimal_chunks.
1350        for (auto chunk_idx : m_chunk_idxs) {
1351            TxIdx pivot_idx = PickRandomTx(m_set_info[chunk_idx].transactions);
1352            m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, m_rng.randbits<1>());
1353            // Randomize the initial order of nonminimal chunks in the queue.
1354            SetIdx j = m_rng.randrange<SetIdx>(m_nonminimal_chunks.size());
1355            if (j != m_nonminimal_chunks.size() - 1) {
1356                std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
1357            }
1358        }
1359        m_cost.StartMinimizingEnd(/*num_chunks=*/m_nonminimal_chunks.size());
1360    }
1361
1362    /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
1363    bool MinimizeStep() noexcept
1364    {
1365        // If the queue of potentially-non-minimal chunks is empty, we are done.
1366        if (m_nonminimal_chunks.empty()) return false;
1367        m_cost.MinimizeStepBegin();
1368        // Pop an entry from the potentially-non-minimal chunk queue.
1369        auto [chunk_idx, pivot_idx, flags] = m_nonminimal_chunks.front();
1370        m_nonminimal_chunks.pop_front();
1371        auto& chunk_info = m_set_info[chunk_idx];
1372        /** Whether to move the pivot down rather than up. */
1373        bool move_pivot_down = flags & 1;
1374        /** Whether this is already the second stage. */
1375        bool second_stage = flags & 2;
1376
1377        // Find a random dependency whose top and bottom set feerates are equal, and which has
1378        // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down).
1379        std::pair<TxIdx, TxIdx> candidate_dep;
1380        uint64_t candidate_tiebreak{0};
1381        bool have_any = false;
1382        // Iterate over all transactions.
1383        for (auto tx_idx : chunk_info.transactions) {
1384            const auto& tx_data = m_tx_data[tx_idx];
1385            // Iterate over all active child dependencies of the transaction.
1386            for (auto child_idx : tx_data.active_children) {
1387                const auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
1388                // Skip if this dependency does not have equal top and bottom set feerates. Note
1389                // that the top cannot have higher feerate than the bottom, or OptimizeSteps would
1390                // have dealt with it.
1391                if (ByRatio{dep_top_info.feerate} < ByRatio{chunk_info.feerate}) continue;
1392                have_any = true;
1393                // Skip if this dependency does not have pivot in the right place.
1394                if (move_pivot_down == dep_top_info.transactions[pivot_idx]) continue;
1395                // Remember this as our chosen dependency if it has a better tiebreak.
1396                uint64_t tiebreak = m_rng.rand64() | 1;
1397                if (tiebreak > candidate_tiebreak) {
1398                    candidate_tiebreak = tiebreak;
1399                    candidate_dep = {tx_idx, child_idx};
1400                }
1401            }
1402        }
1403        m_cost.MinimizeStepMid(/*num_txns=*/chunk_info.transactions.Count());
1404        // If no dependencies have equal top and bottom set feerate, this chunk is minimal.
1405        if (!have_any) return true;
1406        // If all found dependencies have the pivot in the wrong place, try moving it in the other
1407        // direction. If this was the second stage already, we are done.
1408        if (candidate_tiebreak == 0) {
1409            // Switch to other direction, and to second phase.
1410            flags ^= 3;
1411            if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, flags);
1412            return true;
1413        }
1414
1415        // Otherwise, deactivate the dependency that was found.
1416        auto [parent_chunk_idx, child_chunk_idx] = Deactivate(candidate_dep.first, candidate_dep.second);
1417        // Determine if there is a dependency from the new bottom to the new top (opposite from the
1418        // dependency that was just deactivated).
1419        auto& parent_reachable = m_reachable[parent_chunk_idx].first;
1420        auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
1421        if (parent_reachable.Overlaps(child_chunk_txn)) {
1422            // A self-merge is needed. Note that the child_chunk_idx is the top, and
1423            // parent_chunk_idx is the bottom, because we activate a dependency in the reverse
1424            // direction compared to the deactivation above.
1425            auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
1426            // Re-insert the chunk into the queue, in the same direction. Note that the chunk_idx
1427            // will have changed.
1428            m_nonminimal_chunks.emplace_back(merged_chunk_idx, pivot_idx, flags);
1429            m_cost.MinimizeStepEnd(/*split=*/false);
1430        } else {
1431            // No self-merge happens, and thus we have found a way to split the chunk. Create two
1432            // smaller chunks, and add them to the queue. The one that contains the current pivot
1433            // gets to continue with it in the same direction, to minimize the number of times we
1434            // alternate direction. If we were in the second phase already, the newly created chunk
1435            // inherits that too, because we know no split with the pivot on the other side is
1436            // possible already. The new chunk without the current pivot gets a new randomly-chosen
1437            // one.
1438            if (move_pivot_down) {
1439                auto parent_pivot_idx = PickRandomTx(m_set_info[parent_chunk_idx].transactions);
1440                m_nonminimal_chunks.emplace_back(parent_chunk_idx, parent_pivot_idx, m_rng.randbits<1>());
1441                m_nonminimal_chunks.emplace_back(child_chunk_idx, pivot_idx, flags);
1442            } else {
1443                auto child_pivot_idx = PickRandomTx(m_set_info[child_chunk_idx].transactions);
1444                m_nonminimal_chunks.emplace_back(parent_chunk_idx, pivot_idx, flags);
1445                m_nonminimal_chunks.emplace_back(child_chunk_idx, child_pivot_idx, m_rng.randbits<1>());
1446            }
1447            if (m_rng.randbool()) {
1448                std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[m_nonminimal_chunks.size() - 2]);
1449            }
1450            m_cost.MinimizeStepEnd(/*split=*/true);
1451        }
1452        return true;
1453    }
1454
1455    /** Construct a topologically-valid linearization from the current forest state. Must be
1456     *  topological. fallback_order is a comparator that defines a strong order for DepGraphIndexes
1457     *  in this cluster, used to order equal-feerate transactions and chunks.
1458     *
1459     * Specifically, the resulting order consists of:
1460     * - The chunks of the current SFL state, sorted by (in decreasing order of priority):
1461     *   - topology (parents before children)
1462     *   - highest chunk feerate first
1463     *   - smallest chunk size first
1464     *   - the chunk with the lowest maximum transaction, by fallback_order, first
1465     * - The transactions within a chunk, sorted by (in decreasing order of priority):
1466     *   - topology (parents before children)
1467     *   - highest tx feerate first
1468     *   - smallest tx size first
1469     *   - the lowest transaction, by fallback_order, first
1470     */
1471    std::vector<DepGraphIndex> GetLinearization(const StrongComparator<DepGraphIndex> auto& fallback_order) noexcept
1472    {
1473        m_cost.GetLinearizationBegin();
1474        /** The output linearization. */
1475        std::vector<DepGraphIndex> ret;
1476        ret.reserve(m_set_info.size());
1477        /** A heap with all chunks (by set index) that can currently be included, sorted by
1478         *  chunk feerate (high to low), chunk size (small to large), and by least maximum element
1479         *  according to the fallback order (which is the second pair element). */
1480        std::array<std::pair<SetIdx, TxIdx>, SetType::Size()> ready_chunks;
1481        /** The number of entries of ready_chunks in use. */
1482        unsigned num_ready_chunks{0};
1483        /** For every chunk, indexed by SetIdx, the number of unmet dependencies the chunk has on
1484         *  other chunks (not including dependencies within the chunk itself). */
1485        std::array<TxIdx, SetType::Size()> chunk_deps;
1486        std::fill_n(chunk_deps.begin(), m_set_info.size(), TxIdx{0});
1487        /** For every transaction, indexed by TxIdx, the number of unmet dependencies the
1488         *  transaction has. */
1489        std::array<TxIdx, SetType::Size()> tx_deps;
1490        std::fill_n(tx_deps.begin(), m_tx_data.size(), TxIdx{0});
1491        /** A heap with all transactions within the current chunk that can be included, sorted by
1492         *  tx feerate (high to low), tx size (small to large), and fallback order. */
1493        std::array<TxIdx, SetType::Size()> ready_tx;
1494        /** The number of entries of ready_tx in use. */
1495        unsigned num_ready_tx{0};
1496        // Populate chunk_deps and tx_deps.
1497        unsigned num_deps{0};
1498        for (TxIdx chl_idx : m_transaction_idxs) {
1499            const auto& chl_data = m_tx_data[chl_idx];
1500            tx_deps[chl_idx] = chl_data.parents.Count();