Here is a patch that merges the two processing loops into one (deduplicating some logic between them), and also makes the tail feerate explicit (even though only FeeFrac{0, 1} is used for now).
No need to take this, but in case people find it simpler to review a generic approach, perhaps it’s useful.
0diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp
1index a970adedc30..569f32f4615 100644
2--- a/src/util/feefrac.cpp
3+++ b/src/util/feefrac.cpp
4@@ -22,7 +22,7 @@ void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<Fe
5 }
6 }
7
8-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1)
9+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1, FeeFrac tail_feerate)
10 {
11 /** Array to allow indexed access to input diagrams. */
12 const std::array<Span<const FeeFrac>, 2> dias = {dia0, dia1};
13@@ -40,51 +40,47 @@ std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const
14 Assert(prev_point(0).IsEmpty());
15 Assert(prev_point(1).IsEmpty());
16
17- // Compare the overlapping area of the diagrams.
18- while (next_index[0] < dias[0].size() && next_index[1] < dias[1].size()) {
19- // Determine which diagram has the first unprocessed point.
20- const int unproc_side = next_point(0).size > next_point(1).size;
21+ do {
22+ bool done_0 = next_index[0] == dias[0].size();
23+ bool done_1 = next_index[1] == dias[1].size();
24+ if (done_0 && done_1) break;
25+
26+ // Determine which diagram has the first unprocessed point. If one side is finished, use the
27+ // other one.
28+ const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
29
30 // let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
31 // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
32- // compute the direction coefficients of line AB and of line AP, and compare them. These
33- // direction coefficients are fee per size, and can thus be expressed as FeeFracs.
34+ // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
35+ // and can thus be expressed as FeeFracs.
36 const FeeFrac& point_p = next_point(unproc_side);
37 const FeeFrac& point_a = prev_point(!unproc_side);
38- const FeeFrac& point_b = next_point(!unproc_side);
39- const auto coef_ab = point_b - point_a;
40- const auto coef_ap = point_p - point_a;
41- Assume(coef_ap.size > 0);
42- Assume(coef_ab.size >= coef_ap.size);
43- // Perform the comparison. If P lies above AB, unproc_side is better in P. If P lies below
44- // AB, then !unproc_side is better in P.
45- const auto cmp = FeeRateCompare(coef_ap, coef_ab);
46+ const auto slope_ap = point_p - point_a;
47+ Assume(slope_ap.size > 0);
48+ std::weak_ordering cmp = std::weak_ordering::equivalent;
49+ if (!(done_0 || done_1)) {
50+ // If both sides have points left, compute B, and the slope of AB explicitly.
51+ const FeeFrac& point_b = next_point(!unproc_side);
52+ const auto slope_ab = point_b - point_a;
53+ Assume(slope_ab.size >= slope_ap.size);
54+ cmp = FeeRateCompare(slope_ap, slope_ab);
55+
56+ // If B and P have the same size, B can be marked as processed (in addition to P, see
57+ // below), as we've already performed a comparison at this size.
58+ if (point_b.size == point_p.size) ++next_index[!unproc_side];
59+ } else {
60+ // If one of the sides has no points left, act as if AB has slope tail_feerate.
61+ cmp = FeeRateCompare(slope_ap, tail_feerate);
62+ }
63+
64+ // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is
65+ // better in P.
66 if (std::is_gt(cmp)) better_somewhere[unproc_side] = true;
67 if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true;
68
69- // Mark P as processed. If B and P have the same size, B can also be marked as processed as
70- // we've already performed a comparison at this size.
71- ++next_index[unproc_side];
72- if (point_b.size == point_p.size) ++next_index[!unproc_side];
73- }
74-
75- // Tail check at 0 feerate: Compare the remaining area. Use similar logic as in the loop above,
76- // except we use a horizontal line instead of AB, as no point B exists anymore.
77- const int long_side = next_index[1] != dias[1].size();
78- Assume(next_index[!long_side] == dias[!long_side].size());
79- // The point A now remains fixed: the last point of the shorter diagram.
80- const FeeFrac& point_a = prev_point(!long_side);
81- while (next_index[long_side] < dias[long_side].size()) {
82- // Compare AP (where P is the next unprocessed point on the longer diagram) with a horizontal line
83- // extending infinitely from A. This is equivalent to checking the sign of the fee of P-A.
84- const FeeFrac& point_p = next_point(long_side);
85- const auto coef_ap = point_p - point_a;
86- const auto cmp = coef_ap.fee <=> 0;
87- if (std::is_gt(cmp)) better_somewhere[long_side] = true;
88- if (std::is_lt(cmp)) better_somewhere[!long_side] = true;
89 // Mark P as processed.
90- ++next_index[long_side];
91- }
92+ ++next_index[unproc_side];
93+ } while(true);
94
95 // If both diagrams are better somewhere, they are incomparable.
96 if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
97diff --git a/src/util/feefrac.h b/src/util/feefrac.h
98index 12698a4a653..706facc34b0 100644
99--- a/src/util/feefrac.h
100+++ b/src/util/feefrac.h
101@@ -156,7 +156,7 @@ struct FeeFrac
102 void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram);
103
104 /** Compares two feerate diagrams (which must both start at size=0). The shorter one is implicitly
105- * extended with a horizontal straight line. */
106-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
107+ * extended with an infinite line whose slope equals tail_feefrac (by default: horizontal). */
108+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1, FeeFrac tail_feerate={0, 1});
109
110 #endif // BITCOIN_UTIL_FEEFRAC_H
