From b22901dfa9cc3af94bf13163a28300eb1ab25b22 Mon Sep 17 00:00:00 2001
From: Pieter Wuille <pieter@wuille.net>
Date: Sun, 17 Mar 2024 09:42:12 -0400
Subject: Avoid explicitly computing diagram; compare based on chunks

---
 src/util/feefrac.cpp | 40 +++++++++++++---------------------------
 src/util/feefrac.h   | 15 +++++++--------
 2 files changed, 20 insertions(+), 35 deletions(-)

(limited to 'src/util')

diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp
index 68fb836936..5b6173835c 100644
--- a/src/util/feefrac.cpp
+++ b/src/util/feefrac.cpp
@@ -7,39 +7,26 @@
 #include <array>
 #include <vector>
 
-std::vector<FeeFrac> BuildDiagramFromChunks(const Span<const FeeFrac> chunks)
-{
-    std::vector<FeeFrac> diagram;
-    diagram.reserve(chunks.size() + 1);
-
-    diagram.emplace_back(0, 0);
-    for (auto& chunk : chunks) {
-        diagram.emplace_back(diagram.back() + chunk);
-    }
-    return diagram;
-}
-
-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1)
+std::partial_ordering CompareChunks(Span<const FeeFrac> chunks0, Span<const FeeFrac> chunks1)
 {
     /** Array to allow indexed access to input diagrams. */
-    const std::array<Span<const FeeFrac>, 2> dias = {dia0, dia1};
+    const std::array<Span<const FeeFrac>, 2> chunk = {chunks0, chunks1};
     /** How many elements we have processed in each input. */
-    size_t next_index[2] = {1, 1};
+    size_t next_index[2] = {0, 0};
+    /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */
+    FeeFrac accum[2];
     /** Whether the corresponding input is strictly better than the other at least in one place. */
     bool better_somewhere[2] = {false, false};
     /** Get the first unprocessed point in diagram number dia. */
-    const auto next_point = [&](int dia) { return dias[dia][next_index[dia]]; };
+    const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; };
     /** Get the last processed point in diagram number dia. */
-    const auto prev_point = [&](int dia) { return dias[dia][next_index[dia] - 1]; };
-
-    // Diagrams should be non-empty, and first elements zero in size and fee
-    Assert(!dia0.empty() && !dia1.empty());
-    Assert(prev_point(0).IsEmpty());
-    Assert(prev_point(1).IsEmpty());
+    const auto prev_point = [&](int dia) { return accum[dia]; };
+    /** Move to the next point in diagram number dia. */
+    const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; };
 
     do {
-        bool done_0 = next_index[0] == dias[0].size();
-        bool done_1 = next_index[1] == dias[1].size();
+        bool done_0 = next_index[0] == chunk[0].size();
+        bool done_1 = next_index[1] == chunk[1].size();
         if (done_0 && done_1) break;
 
         // Determine which diagram has the first unprocessed point. If a single side is finished, use the
@@ -69,17 +56,16 @@ std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const
 
             // If B and P have the same size, B can be marked as processed (in addition to P, see
             // below), as we've already performed a comparison at this size.
-            if (point_b.size == point_p.size) ++next_index[!unproc_side];
+            if (point_b.size == point_p.size) advance(!unproc_side);
         }
         // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
         // better in P.
         if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
         if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
-        ++next_index[unproc_side];
+        advance(unproc_side);
 
         // If both diagrams are better somewhere, they are incomparable.
         if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
-
     } while(true);
 
     // Otherwise compare the better_somewhere values.
diff --git a/src/util/feefrac.h b/src/util/feefrac.h
index 7102f85f88..9772162010 100644
--- a/src/util/feefrac.h
+++ b/src/util/feefrac.h
@@ -146,15 +146,14 @@ struct FeeFrac
     }
 };
 
-/** Takes the pre-computed and topologically-valid chunks and generates a fee diagram which starts at FeeFrac of (0, 0) */
-std::vector<FeeFrac> BuildDiagramFromChunks(Span<const FeeFrac> chunks);
-
-/** Compares two feerate diagrams. The shorter one is implicitly
- * extended with a horizontal straight line.
+/** Compare the feerate diagrams implied by the provided sorted chunks data.
+ *
+ * The implied diagram for each starts at (0, 0), then contains for each chunk the cumulative fee
+ * and size up to that chunk, and then extends infinitely to the right with a horizontal line.
  *
- * A feerate diagram consists of a list of (fee, size) points with the property that size
- * is strictly increasing and that the first entry is (0, 0).
+ * The caller must guarantee that the sum of the FeeFracs in either of the chunks' data set do not
+ * overflow (so sum fees < 2^63, and sum sizes < 2^31).
  */
-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
+std::partial_ordering CompareChunks(Span<const FeeFrac> chunks0, Span<const FeeFrac> chunks1);
 
 #endif // BITCOIN_UTIL_FEEFRAC_H
-- 
cgit v1.2.3