cluster mempool: cluster linearization algorithm #30126

10+#include <cstdint>
11+#include <limits>
12+#include <type_traits>
13+
14+#ifdef _MSC_VER
15+#  include <intrin.h>

510+        auto best = anc_finder.FindCandidateSet();
511+
512+        // Invoke bounded search to update best, with up to half of our remaining iterations as
513+        // limit.
514+        uint64_t iterations = (iteration_limit + 1) / 2;
515+        iteration_limit -= iterations;

43+        S ancestors;
44+        /** All descendants of the transaction (including itself). */
45+        S descendants;
46+
47+        friend bool operator==(const Entry&, const Entry&) noexcept = default;
48+        friend auto operator<=>(const Entry&, const Entry&) noexcept = default;

70+     *
71+     * Complexity: O(N) where N=ntx.
72+     **/
73+    explicit DepGraph(ClusterIndex ntx) noexcept
74+    {
75+        entries.resize(ntx);

118+     *
119+     * Complexity: O(N^2) where N=depgraph.TxCount().
120+     */
121+    DepGraph(const DepGraph<S>& depgraph, Span<const ClusterIndex> mapping) noexcept : entries(depgraph.TxCount())
122+    {
123+        // Fill in fee, size, ancestors.

29+/** Data type to represent transaction indices in clusters. */
30+using ClusterIndex = uint32_t;
31+
32+/** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
33+ *  descendants). */
34+template<typename S>

553+                // split on.
554+                if (und.None()) return;
555+            }
556+
557+            // Actually construct new work item on the queue.
558+            Assume(queue.size() < queue.capacity());

261+    // Construct a cluster of a certain length, with no dependencies.
262+    Cluster<TestBitSet> cluster;
263+    FuzzedDataProvider provider(buffer.data(), buffer.size());
264+    auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(2, 32);
265+    cluster.resize(num_tx);
266+    for (auto& item : cluster) item.first.size = 1;

265+    cluster.resize(num_tx);
266+    for (auto& item : cluster) item.first.size = 1;
267+    // Construct the corresponding DepGraph object (also no dependencies).
268+    DepGraph depgraph(cluster);
269+    SanityCheck(depgraph);
270+    // Read (parent, child) pairs, and add them to the cluster and txgraph.

136+     *
137+     * Complexity: O(N) where N=TxCount().
138+     **/
139+    void AddDependency(ClusterIndex parent, ClusterIndex child) noexcept
140+    {
141+        // To each ancestor of the parent, add as descendants the descendants of the child.

121+    const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
122+
123+    /** Add a new unconnected transaction to this transaction graph (at the end), and return its
124+     *  ClusterIndex.
125+     *
126+     * Complexity: Amortized O(1).

266+    for (auto& item : cluster) item.first.size = 1;
267+    // Construct the corresponding DepGraph object (also no dependencies).
268+    DepGraph depgraph(cluster);
269+    SanityCheck(depgraph);
270+    // Read (parent, child) pairs, and add them to the cluster and txgraph.
271+    LIMITED_WHILE(provider.remaining_bytes() > 0, 1024) {

237+                m_ancestor_set_feerates[j] -= feerate;
238+            }
239+        }
240+    }
241+
242+    /** Find the best remaining ancestor set. Unlinearized transactions must remain.

149+        depgraph = {};
150+        while (true) {
151+            // Read size. Size 0 signifies the end of the DepGraph.
152+            int32_t size;
153+            s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED);
154+            size &= 0x3FFFFF; // Enough for size up to 4M.

154+            size &= 0x3FFFFF; // Enough for size up to 4M.
155+            if (size == 0 || depgraph.TxCount() == SetType::Size()) break;
156+            // Read fee, encoded as a signed varint (odd means negative, even means non-negative).
157+            uint64_t coded_fee;
158+            s >> VARINT(coded_fee);
159+            coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC.

346+        /** Local copy of the iteration limit. */
347+        uint64_t iterations_left = max_iterations;
348+
349+        /** Internal function to add a work item.
350+         *
351+         * - inc: the "inc" value for the new work item

210+            FeeFrac anc_feerate;
211+            // Reuse accumulated feerate from first ancestor, if usable.
212+            Assume(anc_to_add.Any());
213+            ClusterIndex first = anc_to_add.First();
214+            if (first < i) {
215+                anc_feerate = m_ancestor_set_feerates[first];

245+     */
246+    SetInfo<SetType> FindCandidateSet() const noexcept
247+    {
248+        std::optional<ClusterIndex> best;
249+        for (auto i : m_todo) {
250+            if (best.has_value()) {

405+        // Find a topologically valid subset of transactions to remove from the graph.
406+        auto del_set = ReadTopologicalSet(depgraph, todo, reader);
407+        // If we did not find anything, use best_anc itself, because we should remove something.
408+        if (del_set.None()) del_set = best_anc.transactions;
409+        todo -= del_set;
410+        anc_finder.MarkDone(del_set);

232+        }
233+        return best;
234+    }
235+};
236+
237+/** A simple finder class for candidate sets. */

582+            }
583+        }
584+
585+        // Find a topologically valid subset of transactions to remove from the graph.
586+        auto del_set = ReadTopologicalSet(depgraph, todo, reader);
587+        // If we did not find anything, use found_set itself, because we should remove something.

242+    const DepGraph<SetType>& m_depgraph;
243+    /** Which transaction are left to include. */
244+    SetType m_todo;
245+
246+public:
247+    /** Construct an SimpleOptimalCandidateFinder for a given graph. */

201+    const DepGraph<SetType>& m_depgraph;
202+    /** Which transaction are left to include. */
203+    SetType m_todo;
204+
205+public:
206+    /** Construct an SimpleOptimalCandidateFinder for a given graph. */

561+        assert(iterations_done <= ((uint64_t{1} << todo.Count()) - 1));
562+
563+        // Perform quality checks only if SearchCandidateFinder claims an optimal result.
564+        if (iterations_done < max_iterations) {
565+            // Compare with SimpleCandidateFinder.
566+            auto [simple, simple_iters] = smp_finder.FindCandidateSet(0x3ffff);

69+bool CanAddDependency(const DepGraph<SetType>& depgraph, ClusterIndex parent, ClusterIndex child) noexcept
70+{
71+    // If child is already a descendant of parent, the dependency would be redundant.
72+    if (depgraph.Descendants(parent)[child]) return false;
73+    // If child is already an ancestor of parent, the dependency would cause a cycle.
74+    if (depgraph.Ancestors(parent)[child]) return false;

70+{
71+    // If child is already a descendant of parent, the dependency would be redundant.
72+    if (depgraph.Descendants(parent)[child]) return false;
73+    // If child is already an ancestor of parent, the dependency would cause a cycle.
74+    if (depgraph.Ancestors(parent)[child]) return false;
75+    // If there is an ancestor of parent which is a direct parent of a descendant of child,

611+
612+            // Compare with AncestorCandidateFinder;
613+            auto anc = anc_finder.FindCandidateSet();
614+            assert(found.feerate >= anc.feerate);
615+
616+            // If todo isn't too big, compare with ExhaustiveCandidateFinder.

329+                    if (new_inc.feerate > best.feerate) best = new_inc;
330+                    break;
331+                }
332+            }
333+        }
334+        return {std::move(best), max_iterations - iterations_left};

314+     * Complexity: O(N * min(max_iterations, 2^N)) where N=depgraph.TxCount().
315+     */
316+    std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations, SetInfo<SetType> best) noexcept
317+    {
318+        // Bail out quickly if we're given a (remaining) cluster that is empty.
319+        if (m_todo.None()) return {};

314+            auto [inc, und] = queue.back();
315+            queue.pop_back();
316+            // Look for a transaction to consider adding/removing.
317+            bool inc_none = inc.None();
318+            for (auto pivot : und) {
319+                // If inc is empty, consider any pivot. Otherwise only consider transactions

355+            if (!inc.feerate.IsEmpty()) {
356+                // If inc's feerate is better than best's, remember it as our new best.
357+                if (inc.feerate > best.feerate) {
358+                    best = inc;
359+                }
360+            }

716+    }
717+
718+    // If Linearize claims optimal result, run quality tests.
719+    if (optimal) {
720+        // It must be as good as SimpleLinearize.
721+        auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, 0x3ffff);

89+void BenchLinearizeNoItersWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
90+{
91+    const auto depgraph = MakeLinearGraph<SetType>(ntx);
92+    bench.run([&] {
93+        // Do 10 iterations just to make sure some of that logic is executed, but this is
94+        // effectively negligible.

 97+    });
 98+}
 99+
100+} // namespace
101+
102+static void LinearizePerIter16TxWorstCase(benchmark::Bench& bench) { BenchLinearizePerIterWorstCase<BitSet<16>>(16, bench); }

84+    });
85+}
86+
87+/** Benchmark for linearization of a trivial linear graph using just ancestor sort. */
88+template<typename SetType>
89+void BenchLinearizeNoItersWorstCase(ClusterIndex ntx, benchmark::Bench& bench)

22+        if (i > 0) depgraph.AddDependency(i - 1, i);
23+    }
24+    return depgraph;
25+}
26+
27+// Construct a difficult graph. These need at least sqrt(2^(n-1)) iterations in the best

351@@ -351,7 +352,8 @@ class SearchCandidateFinder
352         };
353 
354         /** The queue of work items. */
355-        std::vector<WorkItem> queue;
356+        VecDeque<WorkItem> queue;
357+        queue.reserve(std::max<size_t>(256, 2 * m_todo.Count()));

428+        // The approach here combines the two: use BFS until the queue grows too large, at which
429+        // point we temporarily switch to DFS until the size shrinks again.
430         while (!queue.empty()) {
431+            // See if processing the first queue item (BFS) is possible without exceeding the queue
432+            // capacity(), assuming we process the last queue items (DFS) after that.
433+            const auto queuesize_for_front = queue.capacity() - queue.front().und.Count();

76@@ -77,8 +77,9 @@ void BenchLinearizePerIterWorstCase(ClusterIndex ntx, benchmark::Bench& bench)
77 {

494@@ -467,6 +495,7 @@ class SearchCandidateFinder
495  *
496  * @param[in] depgraph        Dependency graph of the the cluster to be linearized.
497  * @param[in] max_iterations  Upper bound on the number of optimization steps that will be done.
498+ * @param[in] rng_seed        A random number seed to control search order.

522+std::pair<std::vector<ClusterIndex>, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, Span<const ClusterIndex> old_linearization = {}) noexcept
523 {
524     uint64_t iterations_left = max_iterations;
525     auto todo = SetType::Fill(depgraph.TxCount());
526     std::vector<ClusterIndex> linearization;
527 

560+                }
561+            }
562+        }
563+
564+        // Then initialize best to be either the best remaining ancestor set, or the first chunk.
565+        auto best_anc = anc_finder.FindCandidateSet();

562@@ -527,6 +563,24 @@ std::pair<std::vector<ClusterIndex>, uint64_t> Linearize(const DepGraph<SetType>
563 
564         if (iterations_done_now == max_iterations_now) {
565             optimal = false;
566+            // If the search result is not (guaranteed to be) optimal, run intersections to make
567+            // sure we don't pick something that makes us unable to reach further diagram points
568+            // of the old linearization.
569+            if (best.transactions != best_prefix.transactions) {

468+template<typename BS>
469+std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader)
470+{
471+    std::vector<ClusterIndex> linearization;
472+    TestBitSet todo = TestBitSet::Fill(depgraph.TxCount());
473+    for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {

165@@ -166,6 +166,45 @@ class DepGraph
166         return ret;
167     }
168 
169+    /** Find some connected component within the subset "left" of this graph.

433+{
434+    auto todo = BS::Fill(depgraph.TxCount());
435+    auto comp = depgraph.FindConnectedComponent(todo);
436+    todo -= comp;
437+    while (todo.Any()) {
438+        auto nextcomp = depgraph.FindConnectedComponent(todo);

348+
349+    // Construct dependency graph. The sanity check here includes a round-trip check.
350+    DepGraph depgraph(cluster);
351+    SanityCheck(depgraph);
352+
353+    // Verify that ancestry is computed correctly.

131@@ -132,6 +132,7 @@ BITCOIN_CORE_H = \
132   chainparamsseeds.h \

38+        SetType ancestors;
39+        /** All descendants of the transaction (including itself). */
40+        SetType descendants;
41+
42+        /** Equality operator. */
43+        friend bool operator==(const Entry&, const Entry&) noexcept = default;

125+     *
126+     * Complexity: O(1) (amortized, due to resizing of backing vector).
127+     */
128+    ClusterIndex AddTransaction(const FeeFrac& feefrac) noexcept
129+    {
130+        ClusterIndex new_idx = TxCount();

74+ *   - The fee: VARINT(SignedToUnsigned(tx[t].fee)), see below for SignedToUnsigned.
75+ *   - The dependencies: for each minimized parent and minimized child of t among tx[0..t-1]:
76+ *     - VARINT(delta), which cannot be 0.
77+ *       To determine these values, consider the list of all potential parents and children tx t
78+ *       has among tx[0..t-1]. First the parents, in order from t-1 back to 0, and then the
79+ *       children in the same order. For these, we only consider ones that satisyfy

171+                // In loop 0 store parents among tx 0..idx-1; in loop 1 store children among those.
172+                SetType towrite = loop ? GetReducedChildren(depgraph, idx) : GetReducedParents(depgraph, idx);
173+                for (ClusterIndex i = 0; i < idx; ++i) {
174+                    ClusterIndex parent = loop ? idx : idx - 1 - i;
175+                    ClusterIndex child = loop ? idx - 1 - i : idx;
176+                    if (CanAddDependency(rebuild, parent, child)) {

155+    }
156+
157+    template <typename Stream, typename SetType>
158+    static void Ser(Stream& s, const DepGraph<SetType>& depgraph)
159+    {
160+        /** The graph corresponding to what the deserializer already knows. */

 97+ *   absolute value. This way we can encode negative fees in graphs, but still let small negative
 98+ *   numbers have small encodings.
 99+ * - Why are the parents/children emitted in order from t-1 back to 0? This means that if E is the
100+ *   encoding of a subgraph with no outside dependencies, copies of E in the serialization (in the
101+ *   right places) will result in copies of that subgraph.
102+ * - Why use CanAddDependency in the serialization definition? This makes sure that every variation

59+    TestDepGraphSerialization<TestBitSet>({{{0, 1}, {}}}, "010000");
60+
61+    // Transactions: A(fee=42,size=11), B(fee=-13,size=7), B depends on A.
62+    TestDepGraphSerialization<TestBitSet>(
63+        {{{42, 11}, {}}, {{-13, 7}, {0}}},
64+        "0b5407190100");

66+    // Transactions: A(64,128), B(128,256), C(1,1), C depends on A and B.
67+    TestDepGraphSerialization<TestBitSet>(
68+        {{{64, 128}, {}}, {{128, 256}, {}}, {{1, 1}, {0, 1}}},
69+        "8000800081008100000102010100");
70+
71+    // Transactions: A(-58,113), B(36,114), C(-59,115), D(37,116). Deps: B->A, C->A, D->C, in order

4@@ -5,6 +5,7 @@
5 #ifndef BITCOIN_CLUSTER_LINEARIZE_H

46+        Entry() noexcept = default;
47+        /** Construct an entry with a given feerate, ancestor set, descendant set. */
48+        Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
49+    };
50+
51+    /** Data for each transaction, in order. */

43+    assert(DepGraph(cluster) == depgraph);
44+}
45+
46+FUZZ_TARGET(clusterlin_cluster_serialization)
47+{
48+    // Verify that any graph of transaction has its ancestry correctly computed by DepGraph, and if

237+     *
238+     * Complexity: O(N*M) where N=depgraph.TxCount(), M=select.Count().
239+     */
240+    void MarkDone(SetType select) noexcept
241+    {
242+        Assume(select.IsSubsetOf(m_todo));

197+class AncestorCandidateFinder
198+{
199+    /** Internal dependency graph. */
200+    const DepGraph<SetType>& m_depgraph;
201+    /** Which transaction are left to include. */
202+    SetType m_todo;

331+     *                              be <= max_iterations. If strictly < max_iterations, the
332+     *                              returned subset is optimal.
333+     *
334+     * Complexity: O(N * min(max_iterations, 2^N)) where N=depgraph.TxCount().
335+     */
336+    std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations, SetInfo<SetType> best) noexcept

467@@ -452,6 +468,54 @@ class SearchCandidateFinder
468     }
469 };
470 
471+/** Find a linearization for a cluster.
472+ *
473+ * @param[in] depgraph        Dependency graph of the the cluster to be linearized.

555  *
556  * Complexity: O(N * min(max_iterations + N, 2^N)) where N=depgraph.TxCount().
557  */
558 template<typename SetType>
559-std::pair<std::vector<ClusterIndex>, bool> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed) noexcept
560+std::pair<std::vector<ClusterIndex>, bool> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, Span<const ClusterIndex> old_linearization = {}) noexcept