clusterlin: precompute reachable sets (optimization)

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index de5c6b20..58a7b8b1 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -681,6 +681,9 @@ private:
     std::vector<TxData> m_tx_data;
     /** Information about each set (chunk, or active dependency top set). Indexed by SetIdx. */
     std::vector<SetInfo<SetType>> m_set_info;
+    /** For each chunk, indexed by SetIdx, the set of out-of-chunk reachable transactions, in the
+     *  upwards (.first) and downwards (.second) direction. */
+    std::vector<std::pair<SetType, SetType>> m_reachable;
     /** A FIFO of chunk SetIdxs for chunks that may be improved still. */
     VecDeque<SetIdx> m_suboptimal_chunks;
     /** A FIFO of chunk indexes with a pivot transaction in them, and a flag to indicate their
@@ -742,20 +745,17 @@ private:
         }
     }
 
-    /** Find the set of out-of-chunk transactions reachable from tx_idxs. */
-    template<bool DownWard>
-    SetType GetReachable(const SetType& tx_idxs) const noexcept
+    /** Find the set of out-of-chunk transactions reachable from tx_idxs, both in upwards and
+     *  downwards direction. */
+    std::pair<SetType, SetType> GetReachable(const SetType& tx_idxs) const noexcept
     {
-        SetType ret;
+        SetType parents, children;
         for (auto tx_idx : tx_idxs) {
             const auto& tx_data = m_tx_data[tx_idx];
-            if constexpr (DownWard) {
-                ret |= tx_data.children;
-            } else {
-                ret |= tx_data.parents;
-            }
+            parents |= tx_data.parents;
+            children |= tx_data.children;
         }
-        return ret - tx_idxs;
+        return {parents - tx_idxs, children - tx_idxs};
     }
 
     /** Make the inactive dependency from child to parent, which must not be in the same chunk
@@ -807,6 +807,13 @@ private:
         // Merge top_info into bottom_info, which becomes the merged chunk.
         bottom_info |= top_info;
         m_cost += bottom_info.transactions.Count();
+        // Compute merged sets of reachable transactions from the new chunk. There is no need to
+        // call GetReachable here, because they can be computed directly from the input chunks'
+        // reachable sets.
+        m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first;
+        m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second;
+        m_reachable[child_chunk_idx].first -= bottom_info.transactions;
+        m_reachable[child_chunk_idx].second -= bottom_info.transactions;
         // Make parent chunk the set for the new active dependency.
         parent_data.dep_top_idx[child_idx] = parent_chunk_idx;
         m_chunk_idxs.Reset(parent_chunk_idx);
@@ -843,6 +850,9 @@ private:
                           /*chunk_idx=*/parent_chunk_idx, /*dep_change=*/bottom_info);
         UpdateChunk<true>(/*tx_idxs=*/bottom_info.transactions, /*query=*/child_idx,
                           /*chunk_idx=*/child_chunk_idx, /*dep_change=*/top_info);
+        // Compute the new sets of reachable transactions for each new chunk.
+        m_reachable[child_chunk_idx] = GetReachable(bottom_info.transactions);
+        m_reachable[parent_chunk_idx] = GetReachable(top_info.transactions);
     }
 
     /** Activate a dependency from the bottom set to the top set. Return the index of the merged
@@ -915,7 +925,7 @@ private:
         uint64_t best_other_chunk_tiebreak{0};
 
         /** Which parent/child transactions we still need to process the chunks for. */
-        auto todo = GetReachable<DownWard>(chunk_info.transactions);
+        auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first;
         unsigned steps = 0;
         while (todo.Any()) {
             ++steps;
@@ -1043,6 +1053,7 @@ public:
         auto num_transactions = m_transaction_idxs.Count();
         m_tx_data.resize(depgraph.PositionRange());
         m_set_info.resize(num_transactions);
+        m_reachable.resize(num_transactions);
         size_t num_chunks = 0;
         for (auto tx_idx : m_transaction_idxs) {
             // Fill in transaction data.
@@ -1057,6 +1068,12 @@ public:
             // Mark all its dependencies inactive.
             tx_data.dep_top_idx.fill(INVALID_SET_IDX);
         }
+        // Set the reachable transactions for each chunk to the transactions' parents and children.
+        for (SetIdx chunk_idx = 0; chunk_idx < num_transactions; ++chunk_idx) {
+            auto& tx_data = m_tx_data[m_set_info[chunk_idx].transactions.First()];
+            m_reachable[chunk_idx].first = tx_data.parents;
+            m_reachable[chunk_idx].second = tx_data.children;
+        }
         Assume(num_chunks == num_transactions);
         // Mark all chunk sets as chunks.
         m_chunk_idxs = SetType::Fill(num_chunks);
@@ -1503,6 +1520,11 @@ public:
             assert(chunk_info.transactions == expected_chunk);
             // Verify the chunk's feerate.
             assert(chunk_info.feerate == m_depgraph.FeeRate(chunk_info.transactions));
+            // Verify the chunk's reachable transactions.
+            assert(m_reachable[chunk_idx] == GetReachable(expected_chunk));
+            // Verify that the chunk's reachable transactions don't include its own transactions.
+            assert(!m_reachable[chunk_idx].first.Overlaps(chunk_info.transactions));
+            assert(!m_reachable[chunk_idx].second.Overlaps(chunk_info.transactions));
         }
         // Verify that together, the chunks cover all transactions.
         assert(chunk_cover == m_depgraph.Positions());