Mempool util: Add RBF diagram checks for single chunks against clusters of size 2 #29242

    /** Add fee and size of another FeeFrac to this one. */
    void inline operator+=(const FeeFrac& other) noexcept
    {
        fee += other.fee;
        size += other.size;
    }

    /** Subtrack fee and size of another FeeFrac from this one. */

also, Subtrack isn't a word...

done

Reserve here?

    diagram.clear();
    diagram.reserve(chunks.size() + 1);

done

No need for this return here

}

done

Maybe add a docstring on what BuildDiagramFromUnsortedChunks does in and out params description that are doxygen compatible?

added comment

The correctness of the result of BuildDiagramFromUnsortedChunks very much depends on the assumption that the chunks can be reordered w.r.t. one another, which seems to be the case in the current PR, but will very much not be the case going forward in a general cluster mempool world.

I would suggest either:

• Removing the sorting step in this function (moving it to the caller). The function can then take Span<const FeeFrac> as input too, and perhaps in a further iteration (in a later PR) this function could then be turned into one that actually performs chunking too.
• Adding a big comment on the function definition that it needs independent chunks.

The correctness of the result of BuildDiagramFromUnsortedChunks very much depends on the assumption that the chunks can be reordered w.r.t. one another, which seems to be the case in the current PR, but will very much not be the case going forward in a general cluster mempool world.

No objection to your suggested change here, but I don't follow this comment -- in a general cluster mempool world, unless we were to bound chunk sizes to something smaller than a cluster size (resulting in the possibility of chunk feerates not being monotonically decreasing), I think for the purposes of a feerate diagram it is fine to sort by chunk feerate and permit equal-feerate-chunks to be reordered? From the perspective of a feerate diagram, two such diagrams are equivalent.

If you're suggesting that we want to preserve the ability in the future to impose a chunk size limit, then yes I agree that we should rewrite this... Is there another case that I'm overlooking?

@sdaftuar that matches my understanding.

Removing the sorting step in this function (moving it to the caller). The function can then take Span<const FeeFrac> as input too, and perhaps in a further iteration (in a later PR) this function could then be turned into one that actually performs chunking too.

Took this suggestion

nit: we can just use the empty constructor

    FeeFrac empty{};

Even better, I'll add a test that they're the same

done

why can we have negative size ?

this is testing that subtraction works correctly, not that an individual chunk can have negative size

Yes, My question was... whats the rationale for FeeFrac to generally have negative size ?

We use subtraction, and should try to handle that?

I can think of one use case where negative sizes are actually useful, though it's pretty far fetched.

Currently the code hardcodes a "tail feerate" (the feerate of which we assume there is an infinite supply) of 0 sat/vB for mempool improvement checks, but in theory this can be configurable. In that case, in addition to the diagram check between old and new package, we want the property that fee_new >= fee_old + (size_new - size_old) * feerate_tail. If old, new, and tail are CFeeFrac objects, this condition is exactly !((new - old) << tail). If new is smaller than old, the new - old object has negative size.

A more pragmatic answer is that there is no real reason to restrict it to just positive sizes, and not enforcing it is simpler.

If old, new, and tail are CFeeFrac objects, this condition is exactly !((new - old) << tail). If new is smaller than old, the new - old object has negative size. @sipa With the various Assume() calls that check that if the size is 0, the fee must also be zero, doesn't that mean that we can't really write code like this example you gave? Unless we checked that new != old first -- otherwise you might create a FeeFrac with 0 size and non-zero fee.

@sdaftuar Indeed. It wouldn't require anything more than dropping those Assume() calls, but right now FeeFrac objects represent (the aggregate fee and size of) sets of transactions, rather differences between such aggregates (as would be needed for this use case).

I think we should drop the Assume() calls, as otherwise I think we ought to do more to ensure that using operator- on FeeFrac's is safe everywhere that it might be invoked.

I think you mean all_conflicts here

    // old diagram will consist of each element of all_conflicts either at

done

use static cast?

            FeeFrac package{txiter->GetModFeesWithAncestors(), static_cast<int32_t>(txiter->GetSizeWithAncestors())};

done

I understand what happens here but its a bit confusing to me the short forms CON, CNK DIAGRAM Will prefer something like the compute in computing the OLD chunk

    // Step 2: build the new diagram

    // Add any parents of direct conflicts that are not conflicted themselves into the NEW chunk
    for (auto direct_conflict : direct_conflicts) {
        // If a direct conflict has an ancestor that is not in all_conflicts,
        // it can be affected by the replacement of the child.
        if (direct_conflict->GetMemPoolParentsConst().size() > 0) {
            // Grab the parent.
            const CTxMemPoolEntry& parent = direct_conflict->GetMemPoolParentsConst().begin()->get();
            if (!all_conflicts.count(mapTx.iterator_to(parent))) {
                // This transaction would be left over, so add to the NEW
                // chunk.
                new_chunks.emplace_back(parent.GetModifiedFee(), parent.GetTxSize());
            }
        }
    }
    // Add the replacement package to NEW
    new_chunks.emplace_back(replacement_fees, int32_t(replacement_vsize));

These are shorthand labels from https://delvingbitcoin.org/t/post-clustermempool-package-rbf-per-chunk-processing/190 which helped me think through preciesely how it maps onto the concepts laid out.

I'd like to keep track of these ideas somehow, maybe by defining the labels?

Yeah, maybe to be consistent define the labels and do the same in the OLD chunk computation loop above. Though the explicit comments in the OLD chunk computation loop is more easier to parse for me :).

took some of hte language, and explicitly defined each term

Should forward the detailed error message also?

can you be more explicit in suggestion? The errors are being returned?

I meant what is being returned by err_string and CompareFeerateDiagram was not used. why were you unable to compute mining score, same for CompareFeerateDiagram why is the fee rate insufficient.

CompareFeerateDiagram won't return much very interesting, but you're right for the err_string, will return it

done

Nit: perhaps this function belongs more in util/feefrac (as the building of the diagram also lives there)

makes sense, moved

Nit: std::array.

done

Nit: EMBRACE THE SPACESHIP

if (a[i] != b[i]) return a[i] <=> b[i];

done

Self-nit: 2^64 -> 2^32

done

Suggested change that (I believe) avoids the need for suppressions (and may be more readable?):

    auto add_fn = [&](uint64_t v, int pos) {
        uint64_t accum{0};
        for (int i = 0; i + pos < 4; ++i) {
            // Add current value at limb pos in ret.
            accum += ret[3 - pos - i];
            // Add low or high half of v.
            if (i == 0) accum += v & 0xffffffff;
            if (i == 1) accum += v >> 32;
            // Store lower half of result in limb pos in ret.
            ret[3 - pos - i] = accum & 0xffffffff;
            // Leave carry in accum.
            accum >>= 32;
        }
        // Make sure no overflow.
        assert(accum == 0);
    };

looks good, done

Avoid the need for a suppression:

// Compute absolute values.
uint64_t abs_a1 = static_cast<uint64_t>(a1), abs_a2 = static_cast<uint64_t>(a2);
uint64_t abs_b1 = static_cast<uint64_t>(b1), abs_b2 = static_cast<uint64_t>(b2);
// Use (~x + 1) instead of the equivalent (-x) to silence the linter; mod 2^64 behavior is
// intentional here.
if (a1 < 0) abs_a1 = ~abs_a1 + 1;
if (a2 < 0) abs_a2 = ~abs_a2 + 1;
if (b1 < 0) abs_b1 = ~abs_b1 + 1;
if (b2 < 0) abs_b2 = ~abs_b2 + 1;

(The same trick is used in CScriptNum::serialize, it could be abstracted out)

done

Self-nit: no need for this namespace anymore.

done

Self-nit: this operator can be dropped (C++20 will automatically generate it as negation of operator==).

done

Self-nit: operator<, operator>, operator<= and operator>= can be dropped (C++20 will autogenerate them using operator<=> (inspecting the compiled code, it's marginally less efficient, but all the actually performance-critical uses use operator<<, operator>>, or FeeRateCompare anyway).

done

In the commit message of "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f):

This new function takes the populated sets of direct and all conflicts computed in the current mempool, assuming the replacements are a single chunk, and computes a diagram check.

The first sentence is confusing to me. Could you perhaps clarify "the populated sets of direct and all conflicts" and split the sentence up?

direct_conflicts and all_conflicts. Does that help?

Yeah, that would improve it

In "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f): Nit: The documentation is in opposite order as the checks. Perhaps switch these two lines.

done

In "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f):

            return strprintf("%s has both ancestor and descendant, exceeding cluster limit of 2", txid_string);

taken

In "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f): Maybe that’s my unfamiliarity with the mempool code, but it is not obvious to me what "direct_conflicts" and "all_conflicts" are, and the description here is self-referential. Do these transactions belong to original, replacement, or both, etc.?

direct_conflicts -> the set of transactions that have at least one input conflicting with a proposed transaction. all_conflicts -> Everything that would be evicted by the proposed transaction

I'll touch this up a bit but this is the nomenclature elsewhere

In "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f): Nit: Spaces around that minus? It took me a moment to realize that dashes aren’t a thing in variables.

fixed

In "Implement ImprovesFeerateDiagram" (9257f33d259bf68f1df1cc41b7b3caaea341782f):

     * [@param](/bitcoin-bitcoin/contributor/param/)[in] direct_conflicts    All transactions that would be removed directly (not by being descendants of conflicting transactions)

tried my own explanation

In "test: Add tests for CompareFeerateDiagram and CheckConflictTopology" (b3d415fe84be7edfbed567a79a25d406b438622b): Nit: I found the comment here confusing. How about: "new_diagram is strictly better due to the first chunk, while the second chunk is worse."

tried my own re-explanation. I agree as-is is confusing

In "test: Add tests for CompareFeerateDiagram and CheckConflictTopology" (b3d415fe84be7edfbed567a79a25d406b438622b):

Nit: in the new diagram, the last two chunks should be one chunk because the last chunk is better (151 sats, 150 vB) than the prior (249 sats, 250 vB).

ah hmm, I'm not sure that matters for correctness of test, but jacked up the last chunk's size just to make it clearer what we're testing

In "test: Add tests for CompareFeerateDiagram and CheckConflictTopology" (b3d415fe84be7edfbed567a79a25d406b438622b):

This is the same old_diagram. Did you mean to repeat the same transactions,

    old_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 399}};
    new_diagram = {FeeFrac{0, 0}, FeeFrac{950, 300}, FeeFrac{1050, 400}};

or just test in both directions?

I can't recall honestly, removed that line

     *                                having a conflicting input with a proposed transaction

fixed

If all diagrams always start with FeeFrac{0, 0}, why do we need to mention that as a first element?

I'll leave this as an ergonomics issue for later debate

    int64_t fee;
    int32_t size;

Should their be more information that will describe the transaction size and fee, base / modified fee, vsize in bytes or something of that sort. If not I think its okay like this.

Unrelated just asking to learn. Why are'nt we using CAmount here for the fee?

In some places I see transaction size as uint32_t while some places its int32_t.

Should we have a type for size just like CAmount?

If not I think its okay like this.

removed comments, how it's precisely used is an implementation detail outside of this code

In implementation they are sorted in increasing fee rate and the chunks in the comments should be ordered as is? and also the 0 fee and size chucks sorts first.

 * by decreasing size. The empty FeeFrac (fee and size both 0) sorts first. So for example, the
 * following FeeFracs are in sorted order:
 *
 * - fee=0 size=0 (undefined feerate)
 * - fee=2 size=1 (feerate 2)
 * - fee=3 size=2 (feerate 1.5)
 * - fee=1 size=1 (feerate 1)
 * - fee=2 size=2 (feerate 1)
 * - fee=2 size=3 (feerate 0.667...)
 * - fee=1 size=2 (feerate 0.5)
 * - fee=0 size=1 (feerate 0)

I don't understand your comment, sorry. They're listed in increasing feerate, with decreasing size as a tie breaker.

Yes but in reverse I think. Suppose to be the other way around no?

A sorted FeeFracs should have undefined chunks first, the highest fee rate chunk second continuously... If their is a tie, the chunk with lower size comes first. Hence the are sorted in increasing fee rates, and then by decreasing size.

I've added test to verify this here https://github.com/ismaelsadeeq/bitcoin/commit/8ce89b132f4304a7feda067a88fd0a72330044a6, this test passed on this branch.

@ismaelsadeeq The comparator you provide to std::sort is supposed to return whether the first argument should sort before the second one (if no comparator is provided, operator< is used). With that, you should see lowest feerate first, highest feerate last, and the undefined feefrac at the very end. Within equal-feerate groups, larger size comes first.

Yes thanks for clarification 👍🏾

I looked at it the other way around, using the result from BuildDiagramFromUnsortedChunks sort which uses custom > operator @instagibbs.

I added some additional feefrac fuzzing for the +/- operations, marking as resolved

Maybe add unit test for CalculateFeerateDiagramsForRBF also?

good point; added

Why not delete the commented version of f1 and f2.

    int32_t s1 = provider.ConsumeIntegral<int32_t>();
    if (s1 == 0) f1 = 0;
    FeeFrac fr1(f1, s1);
    assert(fr1.IsEmpty() == (s1 == 0));

    int64_t f2 = provider.ConsumeIntegral<int64_t>();
      

mistakenly left at some point; removed

this is odd, should we just Assume() replacement_vsize>0 in CalculateFeerateDiagramsForRBF?

Yes, I can't think of a scenario where that will happen!

Added Assume for this and remove test

nit:

    const auto low_tx = make_tx(/*inputs=*/ {m_coinbase_txns[0]}, /*output_values=*/ {10 * COIN});

here an another place below!

fixed

Maybe weshould also check that we can have more than two directly conflicting transactions as long as they are all in a cluster size <=2.

<details> <summary>diff </summary>

diff --git a/src/test/rbf_tests.cpp b/src/test/rbf_tests.cpp
index e15fd29da3..561ebd3881 100644
--- a/src/test/rbf_tests.cpp
+++ b/src/test/rbf_tests.cpp
@@ -431,6 +431,53 @@ BOOST_FIXTURE_TEST_CASE(calc_feerate_diagram_rbf, TestChain100Setup)
     BOOST_CHECK(new_diagram[1] == FeeFrac(high_fee, low_size_2));
     old_diagram.clear();
     new_diagram.clear();
+
+    // You can more than two direct conflicts,  if all the directly conflicting transactions are in a cluster size < 2
+    const auto conflict_1 = make_tx(/*inputs=*/ {m_coinbase_txns[2]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1));
+    const auto conflict_1_entry = pool.GetIter(conflict_1->GetHash()).value();
+
+    const auto conflict_2 = make_tx(/*inputs=*/ {m_coinbase_txns[3]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_2));
+    const auto conflict_2_entry = pool.GetIter(conflict_2->GetHash()).value();
+
+    const auto conflict_3 = make_tx(/*inputs=*/ {m_coinbase_txns[4]}, /*output_values=*/ {10 * COIN});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_3));
+    const auto conflict_3_entry = pool.GetIter(conflict_3->GetHash()).value();
+
+    const auto err_string8{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_ent
ry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry}, old_diagram, new_diagram)};
+
+    BOOST_CHECK(!err_string8.has_value());
+    BOOST_CHECK(old_diagram.size() == 4);
+    BOOST_CHECK(new_diagram.size() == 2);
+    old_diagram.clear();
+    new_diagram.clear();
+
+    // Add a child transaction to conflict_1 and make it cluster size 2
+    const auto conflict_1_child = make_tx(/*inputs=*/{conflict_1}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(low_fee).FromTx(conflict_1_child));
+    const auto conflict_1_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
+
+    const auto err_string9{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_ent
ry}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry}, old_diagram, new_diagram)};
+
+    BOOST_CHECK(!err_string8.has_value());
+    BOOST_CHECK(old_diagram.size() == 4);
+    BOOST_CHECK(new_diagram.size() == 2);
+    old_diagram.clear();
+    new_diagram.clear();
+
+
+    // Add another descendant to conflict_1, making the cluster size > 2 should fail at this point.
+    const auto conflict_1_grand_child = make_tx(/*inputs=*/{conflict_1_child}, /*output_values=*/ {995 * CENT});
+    pool.addUnchecked(entry.Fee(high_fee).FromTx(conflict_1_grand_child));
+    const auto conflict_1_grand_child_entry = pool.GetIter(conflict_1_child->GetHash()).value();
+
+    const auto err_string10{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/high_fee, /*replacement_vsize=*/low_size, {conflict_1_entry, conflict_2_entry, conflict_3_en
try}, {conflict_1_entry, conflict_2_entry, conflict_3_entry, conflict_1_child_entry, conflict_1_grand_child_entry}, old_diagram, new_diagram)};
+
+    BOOST_CHECK(err_string10.has_value());
+    BOOST_CHECK(err_string10.value() == strprintf("%s has 2 descendants, max 1 allowed", conflict_1->GetHash().GetHex()));
+    old_diagram.clear();
+    new_diagram.clear();
 }
 
 BOOST_AUTO_TEST_CASE(feerate_diagram_utilities)

</details>

taken with only light modifications, thanks!

nit: As the functions here don't relate to the FeeFrac implementation, perhaps this should be in a different file? feerate_diagram.cpp maybe?

Curious to know the full meaning of FeeFrac is it Fee Fraction? Maybe Chunk will be a better name?

Yeah, it means "fee fraction", though the name isn't perfect - it really represents any ratio where the numerator is an int64_t and the denominator is an int32_t, with a sort order that tie-breaks by putting larger denominators last.

I don't think Chunk is a good name, as we're using that term for a subset of transactions. A FeeFrac is related, but represents the aggregate feerate of a chunk (or really of any set of transactions, or even the difference between the fees/sizes of two sets of transactions).

@sdaftuar going to hold off on this for now if that's ok

nit: "direction coefficient" is not a term I'm familiar with (and from googling it doesn't seem like a super common term); perhaps it would be clearer to just use the word "slope" here?

Oh, I seem to have translated literally from Dutch. "Slope" is indeed the proper English translation.

replaced, even though I thought it sounded pretty smart

nit: Could add a comment here more precisely defining the preconditions for this function and what definition we are using for feerate diagram: specifically that 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). (If these conditions are violated then the function can fail with an Assume() failure.)

taken with some liberties

nit: "fee vs. size diagram" -- maybe we should standardize the terminology to "feerate diagram"? I was also thinking about adding some documentation to doc/policy/mempool-replacements.md explaining what we're doing now.

changed to standard lingo

nit: Maybe update the comment to be more explicit that this function only works for the situation where (replacement_fees, replacement_size) corresponds to a transaction package that has no in-mempool dependences.

updated to be more explicit on what those values represent

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.

diff --git a/src/util/feefrac.cpp b/src/util/feefrac.cpp
index a970adedc30..569f32f4615 100644
--- a/src/util/feefrac.cpp
+++ b/src/util/feefrac.cpp
@@ -22,7 +22,7 @@ void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<Fe
     }
 }
 
-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1)
+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1, FeeFrac tail_feerate)
 {
     /** Array to allow indexed access to input diagrams. */
     const std::array<Span<const FeeFrac>, 2> dias = {dia0, dia1};
@@ -40,51 +40,47 @@ std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const
     Assert(prev_point(0).IsEmpty());
     Assert(prev_point(1).IsEmpty());
 
-    // Compare the overlapping area of the diagrams.
-    while (next_index[0] < dias[0].size() && next_index[1] < dias[1].size()) {
-        // Determine which diagram has the first unprocessed point.
-        const int unproc_side = next_point(0).size > next_point(1).size;
+    do {
+        bool done_0 = next_index[0] == dias[0].size();
+        bool done_1 = next_index[1] == dias[1].size();
+        if (done_0 && done_1) break;
+
+        // Determine which diagram has the first unprocessed point. If one side is finished, use the
+        // other one.
+        const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size;
 
         // let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points
         // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we
-        // compute the direction coefficients of line AB and of line AP, and compare them. These
-        // direction coefficients are fee per size, and can thus be expressed as FeeFracs.
+        // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size,
+        // and can thus be expressed as FeeFracs.
         const FeeFrac& point_p = next_point(unproc_side);
         const FeeFrac& point_a = prev_point(!unproc_side);
-        const FeeFrac& point_b = next_point(!unproc_side);
-        const auto coef_ab = point_b - point_a;
-        const auto coef_ap = point_p - point_a;
-        Assume(coef_ap.size > 0);
-        Assume(coef_ab.size >= coef_ap.size);
-        // Perform the comparison. If P lies above AB, unproc_side is better in P. If P lies below
-        // AB, then !unproc_side is better in P.
-        const auto cmp = FeeRateCompare(coef_ap, coef_ab);
+        const auto slope_ap = point_p - point_a;
+        Assume(slope_ap.size > 0);
+        std::weak_ordering cmp = std::weak_ordering::equivalent;
+        if (!(done_0 || done_1)) {
+            // If both sides have points left, compute B, and the slope of AB explicitly.
+            const FeeFrac& point_b = next_point(!unproc_side);
+            const auto slope_ab = point_b - point_a;
+            Assume(slope_ab.size >= slope_ap.size);
+            cmp = FeeRateCompare(slope_ap, slope_ab);
+
+            // 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];
+        } else {
+            // If one of the sides has no points left, act as if AB has slope tail_feerate.
+            cmp = FeeRateCompare(slope_ap, tail_feerate);
+        }
+
+        // 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;
 
-        // Mark P as processed. If B and P have the same size, B can also be marked as processed as
-        // we've already performed a comparison at this size.
-        ++next_index[unproc_side];
-        if (point_b.size == point_p.size) ++next_index[!unproc_side];
-    }
-
-    // Tail check at 0 feerate: Compare the remaining area. Use similar logic as in the loop above,
-    // except we use a horizontal line instead of AB, as no point B exists anymore.
-    const int long_side = next_index[1] != dias[1].size();
-    Assume(next_index[!long_side] == dias[!long_side].size());
-    // The point A now remains fixed: the last point of the shorter diagram.
-    const FeeFrac& point_a = prev_point(!long_side);
-    while (next_index[long_side] < dias[long_side].size()) {
-        // Compare AP (where P is the next unprocessed point on the longer diagram) with a horizontal line
-        // extending infinitely from A. This is equivalent to checking the sign of the fee of P-A.
-        const FeeFrac& point_p = next_point(long_side);
-        const auto coef_ap = point_p - point_a;
-        const auto cmp = coef_ap.fee <=> 0;
-        if (std::is_gt(cmp)) better_somewhere[long_side] = true;
-        if (std::is_lt(cmp)) better_somewhere[!long_side] = true;
         // Mark P as processed.
-        ++next_index[long_side];
-    }
+        ++next_index[unproc_side];
+    } while(true);
 
     // If both diagrams are better somewhere, they are incomparable.
     if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered;
diff --git a/src/util/feefrac.h b/src/util/feefrac.h
index 12698a4a653..706facc34b0 100644
--- a/src/util/feefrac.h
+++ b/src/util/feefrac.h
@@ -156,7 +156,7 @@ struct FeeFrac
 void BuildDiagramFromUnsortedChunks(std::vector<FeeFrac>& chunks, std::vector<FeeFrac>& diagram);
 
 /** Compares two feerate diagrams (which must both start at size=0). The shorter one is implicitly
- * extended with a horizontal straight line. */
-std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1);
+ *  extended with an infinite line whose slope equals tail_feefrac (by default: horizontal). */
+std::partial_ordering CompareFeerateDiagram(Span<const FeeFrac> dia0, Span<const FeeFrac> dia1, FeeFrac tail_feerate={0, 1});
 
 #endif // BITCOIN_UTIL_FEEFRAC_H

took in a modified form since it does seem to read cleaner to me, left the direct exposure of tail_feerate as a YNGNI extension

Question: is the idea that in the future we'll use the same function but loosen it beyond cluster <=2? Otherwise, I wonder why it isn't called LimitTopology1P1C or LimitClusterSize2 or something.

Potentially yes. I suspect it will become fully unrestricted next post-cluster mempool, but we don't know anything for sure.

We have Shuffle() in random.h, which is more efficient than std::shuffle (but only works with FastRandomContext).

removed, since I stripped out the sorting function from BuildDiagramFromUnsortedChunks

Nit: no need to reimplement FeeFrac addition:

diagram.push_back(diagram.back() + chunk);

done

I think the slope of AB can be negative, because a user could use the prioritisetransaction to give a transaction a negative fee?

one weird trick! will remove the comment

Suhas' comment is still present.

un-resolved comment(oops), will add to follow-up

opened in follow-up

    // You can have more than two direct conflicts if the there are multiple effected clusters, all of size 2 or less

done

nit: inconsistent use of the spaces between operators and operands here and other places

    BOOST_CHECK(p1 + p2 == sum);
    BOOST_CHECK(p1 - p2 == diff);

done

nit: static cast

    FeeFrac busted{static_cast<int64_t>(INT32_MAX) + 1, INT32_MAX};

done

nit: wrong dates

fixed

nit: I see you use BOOST_CHECK(x == y) a lot. BOOST_CHECK_EQUAL is nice since it prints more helpfully

seems I have to implement overloaded operator std::ostream& operator<<(std::ostream& os, const FeeFrac& type) to support it, and seems somewhat rare in the codebase. I can do it of course. Thoughts?

Just a nit, so feel free to ignore.

ignoring for now

nit: you skipped err_string2, maybe you could give them descriptive names like result_cpfp_replace_cpfp, result_replace_3gen result_replace_3independent, etc.

an attempt was made!

5f6ddba2635ca2100ed46560f338b64a58f61b73 Maybe mention can contain multiple clusters?

done

Did you consider using util::Result for this instead? Seems like you want std::pair<std::vector<FeeFrac>, std::vector<FeeFrac>> on success or a std::string on failure.

done

Would you consider creating an alias using FeerateDiagram = std::vector<FeeFrac>? Could be a bit easier to write/read.

doesn't seem to save much typing/reading if we're using Span, leaving as is for now

In commit "Add FeeFrac utils"

Nit: the const before Span<const FeeFrac> doesn't do anything (it's ignored in the declaration of by-value function arguments). You can have it be const in the function definition (in feefrac.cpp) without having it const here (where it does have the effect that the function body cannot modify the copy it receives).

I probably should just be passing a reference here anyways? Changed to pass by reference

The general advice is to pass arguments not larger than 2 pointers by value, which is the case for spans.

got it, double checked, taking your suggestion to remove const from declaration instead

Nothing failed when I commented out this chunk, maybe need some 1p2c or 2p1c CheckConflictTopology tests?

oops, bad test setup was missing this. Fixed and added string assertions to check what it's actually catching.

I see you've added coverage for the "not the only parent" case, but I don't see a test for "not the only child" case. Also nothing failed when I commented it out.

I presume you mean the multi-child case didn't trigger failure when removed? multi-parent should

typo: s/be/by

If you're taking suggestions,

    // low feerate parent with normal feerate child

taken

What does "for now" mean in this context?

    // Adding a grandchild makes the cluster size 3, which is uncalculable

we could expand acceptable topologies later. Took language.

nit 5661fbaec3cb2f8d8790e8c347889a6dea29f324

mempool_txs would be a helpful name

done

Is there any reason to unlock and lock in the loop? Why not just hold throughout?

changed to hold it throughout

I don't think you need * 2

removed

It seems like the 10000 mempool setup could be reused for multiple iterations of replacement tests?

I guess the question is if unique mempools per run are worth the overhead. I think it's pretty fast still?

Why make this ahead of time instead of just creating a new CMutableTransaction for each child?

Aping the current rbf tests, probably. Picks a valid transaction structure, then sticks with it for the run. Suggestions for follow-up improvements maybe?

Maybe "same as above, but start with chunks instead of diagrams" ? Can any of the code maybe be helper funcitoned?

removed the more limited fuzz test, as I don't think it adds additional coverage

Nit:

    // they have a strict topology of one or two connected transactions.

or

    // they have a strict topology of 1 or 2 connected transactions.

opened in follow-up

In commit "Implement ImprovesFeerateDiagram"

I'm confused about this. If diagram_results has no value, does it make sense to pass it to util::ErrorString below?

util::Result lets you pass an error string in lieu of a std::nullopt, and based on the docs it seems I'm using this right. @glozow ?

//! `std::optional<T>` can be updated to return `util::Result<T>` and return
//! error strings usually just replacing `return std::nullopt;` with `return
//! util::Error{error_string};`.

But you aren't passing it an error string, you're passing it diagram_results, which is at this stage known to be std::nullopt?

Nevermind, I missed that diagram_results is an util::Result, not an std::optional, so the !diagram_results.has_value() means it does contain an error. Sorry!

this is what it's returning instead of a std::nullopt: https://github.com/bitcoin/bitcoin/pull/29242/files#diff-c065d4cd2398ad0dbcef393c5dfc53f465bf44723348892395fffd2fb3bac522R1290

(we might be talking past each other)

Right, just discovered I missed what type this was all along. See update above.

In commit "Implement ImprovesFeerateDiagram"

Nit: shorter as:

std::sort(old_chunks.begin(), old_chunks.end(), std::greater{});

(here and below)

done

In commit "Add FeeFrac utils":

Self-nit: CompareFeeFrac -> FeeRateCompare

opened in follow-up

In commit "Implement ImprovesFeerateDiagram"

Nit: improves

opened in follow-up

e9c5aeb11d641b8cae373452339760809625021d could do the reciprocal checks everywhere i.e.

BOOST_CHECK(std::is_lt(CompareFeerateDiagram(old_diagram, new_diagram)));
BOOST_CHECK(std::is_gt(CompareFeerateDiagram(new_diagram, old_diagram)));

...
BOOST_CHECK(std::is_eq(CompareFeerateDiagram(old_diagram, new_diagram)));
BOOST_CHECK(std::is_eq(CompareFeerateDiagram(new_diagram, old_diagram)));

opened in follow-up

e9c5aeb11d641b8cae373452339760809625021d could have been 3 commits

• rename entry{1...8} to entry{1...8}_{normal,low,high, etc} in rbf_tests
• unit tests for CheckConflictTopology
• unit tests for CompareFeerateDiagram

Check the value of the string as well, i.e. "%s has 23 descendants, max 1 allowed"

opened in follow-up

b767e6bd47cb0fb8f7aea3fb10c597e59a35bf74 This is perhaps the place to add coverage for the fact that modified feerate is used, e.g. PrioritiseTransaction here and check that using a replacement_fee between modified and base makes a difference in the result.

opened in follow-up

Similar to previous comment, could do a random PrioritiseTransaction here

if (fuzzed_data_provider.ConsumeBool()) {
    pool.PrioritiseTransaction(mempool_txs.back().GetHash().ToUint256(), fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(-100000, 100000));
}

opened in follow-up

72959867784098137a50c34f86deca8235eef4f8 Nit, but this old_diagram, new_diagram assignment setup is

• making a copies of everything
• brittle / easy for the tests to bleed into each other, e.g. if you forgot to reset the variables (and, previously, if you forgot to clear them between tests)
• repetitive
• checking size + each element of a vector when you could just compare it to an expected vector

Something cleaner might e.g. look like:

{
    const auto replace_one{pool.CalculateFeerateDiagramsForRBF(/*replacement_fees=*/0, /*replacement_vsize=*/1, {entry_low}, {entry_low})};
    BOOST_CHECK(replace_one.has_value());
    std::vector<FeeFrac> expected_old_diagram{FeeFrac(0, 0), FeeFrac(low_fee, low_size)};
    BOOST_CHECK(replace_one->first == expected_old_diagram);
    std::vector<FeeFrac> expected_new_diagram{FeeFrac(0, 0), FeeFrac(0, 1)};
    BOOST_CHECK(replace_one->second == expected_new_diagram);
}

opened in follow-up

    // With one less vB it does
    BOOST_CHECK(ImprovesFeerateDiagram(pool, {entry1}, {entry1, entry2}, tx1_fee + tx2_fee, tx1_size + tx2_size - 1) == std::nullopt);

opened in follow-up

I think we can be a bit more specific than this, i.e. if !calc_results.has_value() then err_tuple.value().first == DiagramCheckError::UNCALCULABLE

opened in follow-up

This test for ImprovesFeerateDiagram doesn't seem very strict beyond checking NEW = OLD - CON + replacement and that internal errors = wrapper errors. For example, if I swap !is_gt for a !is_eq in ImprovesFeerateDiagram, this fuzzer is still happy with everything. There is coverage for that in other places, but it seems like we could be writing stronger assertions?

Can we perhaps add a check that the result is consistent with what CompareFeerateDiagram says when comparing the diagrams returned in calc_results? Or some kind of sanity check that when the new diagram ends with lower fees, we should be getting DiagramCheckError::FAILURE?

I added a couple more checks where I could clearly add them in followup

In "Add FeeFrac utils" (ce8e22542ed0b4fa5794d3203207146418d59473):

Is there a special reason why this is an int64_t instead of a CAmount?

I'll answer because this is my code: I consider this class to be a low-level utility class for representing monetary fractions, without needing a dependency on consensus code.

In "Implement ImprovesFeerateDiagram" (2079b80854e2595f6f696e7c13a56c7f2a7da9f4):

I’m not sure I understand why there are "No topology restrictions post-chunking". I am guessing that this is alluding to all affected clusters at most having two transactions and therefore each having only two possible configurations: child has higher feerate and the cluster is one chunk, or child has lower feerate and the cluster has two chunks, but the chunk with the child naturally sorts after the chunk with the parent. If that’s what is being alluded to here, perhaps you could elaborate in the comment if you touch this again.

Also, I have one open question here. It is my understanding that we do not combine two transactions into one chunk if they tie in feerate. If we have a parent and a child that have the same feerate, and the child is smaller, would that not mean that the chunk with the child could be sorted in front of the chunk with the parent incorrectly?

Thinking more about this, I think this does not matter here, because even if the child were sorted in front of the parent, given them having the same feerate, it would result in the same feerate diagram.

Also, it seems to me that this problem could be sidestepped by chunking together a parent and a child on equal feerate for the purpose of the diagram, if you used if (individual >= package) { in line 1320 instead of if (individual > package) {.

It'd need to be if (!(individual << package)) {, because >= and > use size as tie breaker when comparing FeeFracs. I think that's generally an improvement, actually, because size shouldn't matter here.

If that’s what is being alluded to here, perhaps you could elaborate in the comment if you touch this again.

Will elaborate a bit on the chunk construction comments in a follow-up.

I think that's generally an improvement, actually, because size shouldn't matter here.

Agreed, at a minimum I'd change to individual >> package to get rid of the tie-breaking behavior which is confusing to have here. Will take on a chosen change in follow-up.

opened in follow-up with >> as noted

In "Add FeeFrac utils" (ce8e22542ed0b4fa5794d3203207146418d59473):

Nit: I noticed that in CalculateFeerateDiagramsForRBF(…) you explicitly use vsize, but here you use size. Perhaps vsize should be used consistently? Using vsize for the FeeFrac member would also have the added benefit that the member name doesn’t collide with the use of size referring to the count of objects in the diagram.

    int32_t vsize;

Hmm, I was hoping that this class could be used in contexts where the size is WU rather than vsize too. I do agree with the confusion w.r.t. the size() member functions.

Should they perhaps just be called numerator and denominator?

Should they perhaps just be called numerator and denominator?

I'll mull this over a bit

If it were weight that would also differentiate well.