clusterlin: randomize various decisions in SFL (feature)

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 4d0d7c55..6639244f 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -682,25 +682,28 @@ public:
  * - How to decide which chunks to merge:
  *   - The merge upwards and downward rules specify that the lowest-feerate respectively
  *     highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate
- *     candidates, the chunk with the highest-index transaction involving a relevant dependency is
- *     picked (this will be changed in a later commit).
+ *     candidates, a uniformly random one among them is picked.
  *
  * - How to decide what dependency to activate (when merging chunks):
- *   - After picking two chunks to be merged (see above), the dependency with the lowest-index
- *     transaction in the other chunk is activated (this will be changed in a later commit).
+ *   - After picking two chunks to be merged (see above), a uniformly random dependency between the
+ *     two chunks is activated.
  *
  * - How to decide which chunk to find a dependency to split in:
- *   - A round-robin queue of chunks to improve is maintained.
+ *   - A round-robin queue of chunks to improve is maintained. The initial ordering of this queue
+ *     is uniformly randomly permuted.
  *
  * - How to decide what dependency to deactivate (when splitting chunks):
  *   - Inside the selected chunk (see above), among the dependencies whose top feerate is strictly
- *     higher than its bottom feerate in the selected chunk, if any, the one with the lowest-index
- *     child is deactivated (this will be changed in a later commit).
+ *     higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency
+ *     is deactivated.
  */
 template<typename SetType>
 class SpanningForestState
 {
 private:
+    /** Internal RNG. */
+    InsecureRandomContext m_rng;
+
     /** Data type to represent indexing into m_tx_data. */
     using TxIdx = uint32_t;
     /** Data type to represent indexing into m_dep_data. */
@@ -876,20 +879,30 @@ private:
         Assume(top_chunk.chunk_rep == top_rep);
         auto& bottom_chunk = m_tx_data[bottom_rep];
         Assume(bottom_chunk.chunk_rep == bottom_rep);
-        // Activate the first dependency between bottom_chunk and top_chunk.
+        // Count the number of dependencies between bottom_chunk and top_chunk.
+        TxIdx num_deps{0};
+        for (auto tx : top_chunk.chunk_setinfo.transactions) {
+            auto& tx_data = m_tx_data[tx];
+            num_deps += (tx_data.children & bottom_chunk.chunk_setinfo.transactions).Count();
+        }
+        Assume(num_deps > 0);
+        // Uniformly randomly pick one of them and activate it.
+        TxIdx pick = m_rng.randrange(num_deps);
         for (auto tx : top_chunk.chunk_setinfo.transactions) {
             auto& tx_data = m_tx_data[tx];
-            // As an optimization, only iterate over transactions which have dependencies in the
-            // bottom chunk.
-            if (tx_data.children.Overlaps(bottom_chunk.chunk_setinfo.transactions)) {
+            auto intersect = tx_data.children & bottom_chunk.chunk_setinfo.transactions;
+            auto count = intersect.Count();
+            if (pick < count) {
                 for (auto dep : tx_data.child_deps) {
                     auto& dep_data = m_dep_data[dep];
                     if (bottom_chunk.chunk_setinfo.transactions[dep_data.child]) {
-                        return Activate(dep);
+                        if (pick == 0) return Activate(dep);
+                        --pick;
                     }
                 }
                 break;
             }
+            pick -= count;
         }
         Assume(false);
         return TxIdx(-1);
@@ -906,7 +919,7 @@ private:
         // Iterate over all transactions in the chunk, figuring out which other chunk each
         // depends on, but only testing each other chunk once. For those depended-on chunks,
         // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one.
-        // If multiple equal-feerate candidate chunks to merge with exist, pick the last one
+        // If multiple equal-feerate candidate chunks to merge with exist, pick a random one
         // among them.
 
         /** Which transactions have been reached from this chunk already. Initialize with the
@@ -918,6 +931,9 @@ private:
         FeeFrac best_other_chunk_feerate = chunk_data.chunk_setinfo.feerate;
         /** The representative for the best candidate chunk to merge with. -1 if none. */
         TxIdx best_other_chunk_rep = TxIdx(-1);
+        /** We generate random tiebreak values to pick between equal-feerate candidate chunks.
+         *  This variable stores the tiebreak of the current best candidate. */
+        uint64_t best_other_chunk_tiebreak{0};
         for (auto tx : chunk_txn) {
             auto& tx_data = m_tx_data[tx];
             /** The transactions reached by following dependencies from tx that have not been
@@ -932,9 +948,12 @@ private:
                 // See if it has an acceptable feerate.
                 auto cmp = DownWard ? FeeRateCompare(best_other_chunk_feerate, reached_chunk.feerate)
                                     : FeeRateCompare(reached_chunk.feerate, best_other_chunk_feerate);
-                if (cmp <= 0) {
+                if (cmp > 0) continue;
+                uint64_t tiebreak = m_rng.rand64();
+                if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) {
                     best_other_chunk_feerate = reached_chunk.feerate;
                     best_other_chunk_rep = reached_chunk_rep;
+                    best_other_chunk_tiebreak = tiebreak;
                 }
             }
         }
@@ -989,7 +1008,7 @@ private:
 public:
     /** Construct a spanning forest for the given DepGraph, with every transaction in its own chunk
      *  (not topological). */
-    explicit SpanningForestState(const DepGraph<SetType>& depgraph) noexcept
+    explicit SpanningForestState(const DepGraph<SetType>& depgraph, uint64_t rng_seed) noexcept : m_rng(rng_seed)
     {
         m_transaction_idxs = depgraph.Positions();
         auto num_transactions = m_transaction_idxs.Count();
@@ -1050,6 +1069,11 @@ public:
             auto& tx_data = m_tx_data[tx];
             if (tx_data.chunk_rep == tx) {
                 m_suboptimal_chunks.emplace_back(tx);
+                // Randomize the initial order of suboptimal chunks in the queue.
+                TxIdx j = m_rng.randrange<TxIdx>(m_suboptimal_chunks.size());
+                if (j != m_suboptimal_chunks.size() - 1) {
+                    std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
+                }
             }
         }
         while (!m_suboptimal_chunks.empty()) {
@@ -1060,17 +1084,23 @@ public:
             // If what was popped is not currently a chunk representative, continue. This may
             // happen when it was merged with something else since being added.
             if (chunk_data.chunk_rep != chunk) continue;
-            // Attempt to merge the chunk upwards.
-            auto result_up = MergeStep<false>(chunk);
-            if (result_up != TxIdx(-1)) {
-                m_suboptimal_chunks.push_back(result_up);
-                continue;
-            }
-            // Attempt to merge the chunk downwards.
-            auto result_down = MergeStep<true>(chunk);
-            if (result_down != TxIdx(-1)) {
-                m_suboptimal_chunks.push_back(result_down);
-                continue;
+            int flip = m_rng.randbool();
+            for (int i = 0; i < 2; ++i) {
+                if (i ^ flip) {
+                    // Attempt to merge the chunk upwards.
+                    auto result_up = MergeStep<false>(chunk);
+                    if (result_up != TxIdx(-1)) {
+                        m_suboptimal_chunks.push_back(result_up);
+                        break;
+                    }
+                } else {
+                    // Attempt to merge the chunk downwards.
+                    auto result_down = MergeStep<true>(chunk);
+                    if (result_down != TxIdx(-1)) {
+                        m_suboptimal_chunks.push_back(result_down);
+                        break;
+                    }
+                }
             }
         }
     }
@@ -1083,6 +1113,11 @@ public:
             auto& tx_data = m_tx_data[tx];
             if (tx_data.chunk_rep == tx) {
                 m_suboptimal_chunks.push_back(tx);
+                // Randomize the initial order of suboptimal chunks in the queue.
+                TxIdx j = m_rng.randrange<TxIdx>(m_suboptimal_chunks.size());
+                if (j != m_suboptimal_chunks.size() - 1) {
+                    std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
+                }
             }
         }
     }
@@ -1099,7 +1134,10 @@ public:
             // happen when a split chunk merges in Improve() with one or more existing chunks that
             // are themselves on the suboptimal queue already.
             if (chunk_data.chunk_rep != chunk) continue;
-            // Iterate over all transactions of the chunk.
+            // Remember the best dependency seen so far.
+            DepIdx candidate_dep = DepIdx(-1);
+            uint64_t candidate_tiebreak = 0;
+            // Iterate over all transactions.
             for (auto tx : chunk_data.chunk_setinfo.transactions) {
                 const auto& tx_data = m_tx_data[tx];
                 // Iterate over all active child dependencies of the transaction.
@@ -1109,13 +1147,24 @@ public:
                     if (!dep_data.active) continue;
                     // Skip if this dependency is ineligible (the top chunk that would be created
                     // does not have higher feerate than the chunk it is currently part of).
-                    if (!(dep_data.top_setinfo.feerate >> chunk_data.chunk_setinfo.feerate)) continue;
-                    // Otherwise, deactivate it and then make the state topological again with a
-                    // sequence of merges.
-                    Improve(dep_idx);
-                    return true;
+                    auto cmp = FeeRateCompare(dep_data.top_setinfo.feerate, chunk_data.chunk_setinfo.feerate);
+                    if (cmp <= 0) continue;
+                    // Generate a random tiebreak for this dependency, and reject it if its tiebreak
+                    // is worse than the best so far. This means that among all eligible
+                    // dependencies, a uniformly random one will be chosen.
+                    uint64_t tiebreak = m_rng.rand64();
+                    if (tiebreak < candidate_tiebreak) continue;
+                    // Remember this as our (new) candidate dependency.
+                    candidate_dep = dep_idx;
+                    candidate_tiebreak = tiebreak;
                 }
             }
+            // If a candidate with positive gain was found, deactivate it and then make the state
+            // topological again with a sequence of merges.
+            if (candidate_dep != DepIdx(-1)) Improve(candidate_dep);
+            // Stop processing for now, even if nothing was activated, as the loop above may have
+            // had a nontrivial cost.
+            return !m_suboptimal_chunks.empty();
         }
         // No improvable chunk was found, we are done.
         return false;
@@ -1397,9 +1446,8 @@ public:
 template<typename SetType>
 std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}) noexcept
 {
-    (void)rng_seed; // Unused for now.
     /** Initialize a spanning forest data structure for this cluster. */
-    SpanningForestState forest(depgraph);
+    SpanningForestState forest(depgraph, rng_seed);
     if (!old_linearization.empty()) {
         forest.LoadLinearization(old_linearization);
     } else {
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index fe18407d..a32fc169 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -1021,7 +1021,7 @@ FUZZ_TARGET(clusterlin_sfl)
 
     // Initialize SFL state.
     if (make_connected) MakeConnected(depgraph);
-    SpanningForestState sfl(depgraph);
+    SpanningForestState sfl(depgraph, rng.rand64());
 
     // Function to test the state.
     std::vector<FeeFrac> last_diagram;
diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h
index 2e73032e..f57c486b 100644
--- a/src/test/util/cluster_linearize.h
+++ b/src/test/util/cluster_linearize.h
@@ -402,14 +402,14 @@ inline uint64_t MaxOptimalLinearizationIters(DepGraphIndex cluster_count)
     // *some* reasonable cost bound, optimal linearizations are always found.
     static constexpr uint64_t ITERS[65] = {
         0,
-        0, 2, 8, 21, 51, 99, 162, 208,
-        300, 349, 489, 627, 776, 867, 982, 1204,
-        1414, 1473, 1770, 2045, 2285, 2417, 3669, 3953,
-        3816, 5720, 4103, 5934, 5443, 5323, 6338, 6407,
-        7671, 11625, 11799, 10104, 9631, 11203, 12487, 15262,
-        17800, 14132, 21915, 16495, 23350, 21304, 22221, 22230,
-        26119, 22182, 31118, 30848, 32166, 37174, 39708, 36189,
-        42747, 43689, 46555, 39818, 51077, 58489, 72633, 59756
+        0, 2, 8, 21, 51, 96, 162, 200,
+        273, 323, 413, 506, 602, 788, 883, 948,
+        1153, 1187, 1367, 1619, 1854, 2271, 2257, 2707,
+        2904, 3275, 3342, 4209, 4648, 4146, 4273, 4905,
+        5358, 5767, 5977, 6777, 7812, 7689, 8478, 8425,
+        9561, 11765, 10743, 11806, 12812, 12838, 15421, 16778,
+        16661, 19393, 17995, 23947, 23314, 24564, 26209, 29267,
+        24719, 31065, 31794, 29185, 32465, 35432, 39986, 36865
     };
     assert(cluster_count < std::size(ITERS));
     // Multiply the table number by two, to account for the fact that they are not absolutes.