feefrac: add support for evaluating at given size #30535

pull sipa wants to merge 6 commits into bitcoin:master from sipa:202407_feefrac_eval changing 4 files +267 −59
  1. sipa commented at 7:34 pm on July 26, 2024: member

    The FeeFrac type represents a fraction, intended to be used for sats/vbyte or sats/WU. This PR adds functionality to evaluate that feerate for a given size, in order to obtain the fee it corresponds with (rounding down).

    The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics, but in principle this makes it possible to use FeeFrac as a more accurate replacement for CFeeRate.

    Unit tests are included for known-correct values, plus a fuzz test that verifies the result using arith_uint256.

  2. DrahtBot commented at 7:34 pm on July 26, 2024: contributor

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Code Coverage

    For detailed information about the code coverage, see the test coverage report.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK paplorinc, ismaelsadeeq
    Concept ACK tdb3, ceffikhan, glozow, brunoerg

    If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

  3. sipa force-pushed on Jul 26, 2024
  4. ismaelsadeeq commented at 9:03 pm on July 26, 2024: member

    Concept ACK

    I think we should also have GetFeePerK or GetFeePerS method in FeeFrac similar to CFeeRate

  5. sipa commented at 9:52 pm on July 27, 2024: member
    @ismaelsadeeq It’s a possibility, if we’d want to replace CFeeRate entirely. Another possibility is keeping CFeeRate and its interface, but make it be an encapsulated FeeFrac object (that e.g. on serialization converts to sats/kvb, but that otherwise keeps exact fractions).
  6. sipa force-pushed on Jul 28, 2024
  7. tdb3 commented at 6:32 pm on July 28, 2024: contributor
    Concept ACK Seems like a helpful improvement. Would like to circle back to take a deeper look. Out of curiosity, why the adjustment from 0x200000004 to 0x200000000? (nothing immediately popped out to me)
  8. sipa commented at 6:41 pm on July 28, 2024: member

    @tdb3 0x200000004 is the more accurate number (it equals floor((2^64-1)/(2^31-1))) but 0x200000000 obviously also works, and:

    • It compiles to slightly simpler asm code (it computes fee » 33, rather than comparing fee with a literal).
    • The difference is so small that it shouldn’t matter.
    • I would think it’s more obviously correct to a reviewer.
  9. in src/util/feefrac.h:196 in 5a4c01c4b2 outdated 
    148+    /** Compute, at this object's feerate, how much fee does at_size correspond to.
149+     *
150+     * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
151+     * result rounded down (even for negative feerates).
152+     *
153+     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
    paplorinc commented at 7:14 pm on July 28, 2024:
    nit: if you think the preconditions already stated in the Assumes is worth repeating in the comments, consider swapping their order to match the order in the code.
    sipa commented at 8:21 pm on July 29, 2024:
    Done.
  10. in src/util/feefrac.h:181 in 5a4c01c4b2 outdated 
    176+            // this division to round down however, while the / operator rounds towards zero. In
177+            // case low64 is negative and not a multiple of size, we thus need a correction.
178+            int64_t low64_div = low64 / size;
179+            low64_div -= (low64 % size) < 0;
180+            // Evaluate and return the result
181+            return (high64_div << 32) + low64_div;
    paplorinc commented at 5:43 am on July 29, 2024:

    would it make sense to extract this into a DivFallback - and test it independently, like we do with MulFallback? This would make it independently testable and we could extend it to 128 bit division seamlessly, e.g.:

     0diff --git a/src/util/feefrac.h b/src/util/feefrac.h
 1--- a/src/util/feefrac.h	(revision 5a4c01c4b29b7a2542e43222fa64cdb4ca6ee3dc)
 2+++ b/src/util/feefrac.h	(date 1722234628938)
 3@@ -41,23 +41,56 @@
 4      *
 5      * Separate to permit testing on platforms where it isn't actually needed.
 6      */
 7-    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t a, int32_t b) noexcept
 8+    static inline std::pair<int64_t, uint32_t> MulFallback(int64_t high, int32_t low) noexcept
 9     {
10-        // Otherwise, emulate 96-bit multiplication using two 64-bit multiplies.
11-        int64_t low = int64_t{static_cast<uint32_t>(a)} * b;
12-        int64_t high = (a >> 32) * b;
13-        return {high + (low >> 32), static_cast<uint32_t>(low)};
14+        // Emulate 96-bit multiplication using two 64-bit multiplies.
15+        int64_t low_mul = int64_t{static_cast<uint32_t>(high)} * low;
16+        int64_t high_mul = (high >> 32) * low;
17+        return {high_mul + (low_mul >> 32), static_cast<uint32_t>(low_mul)};
18+    }
19+
20+    /** Fallback version for Div (see below).
21+     *
22+     * Separate to permit testing on platforms where it isn't actually needed.
23+     */
24+    static inline int64_t DivFallback(int64_t high, uint32_t low, int32_t divisor) noexcept
25+    {
26+        Assume(divisor != 0);
27+        // Compute high / divisor, so the result becomes
28+        // (low + (high - high_div * divisor) * 2**32) / divisor + (high_div * 2**32).
29+        int64_t high_div = high / divisor;
30+        // Evaluate the parenthesized expression above, so the result becomes
31+        // low64 / divisor + (high_div * 2**32)
32+        int64_t low64 = ((high - high_div * divisor) << 32) | low;
33+        // Evaluate the division so the result becomes low64_div + high_div * 2**32.
34+        int64_t low64_div = low64 / divisor;
35+        // Round towards negative infinity
36+        low64_div -= (low64 % divisor) < 0;
37+        return (high_div << 32) + low64_div;
38     }
39 
40     // Compute a * b, returning an unspecified but totally ordered type.
41 #ifdef __SIZEOF_INT128__
42     static inline __int128 Mul(int64_t a, int32_t b) noexcept
43     {
44-        // If __int128 is available, use 128-bit wide multiply.
45         return __int128{a} * b;
46     }
47+
48+    // Compute product / divisor, rounding towards negative infinity.
49+    static inline int64_t Div(__int128 product, int32_t divisor) noexcept
50+    {
51+        auto quotient = product / divisor;
52+        // Round towards negative infinity
53+        quotient -= (product % divisor) < 0;
54+        return quotient;
55+    }
56 #else
57     static constexpr auto Mul = MulFallback;
58+    // Compute (high << 64 | low) / divisor, rounding towards negative infinity.
59+    static inline int64_t Div(std::pair<int64_t, uint32_t> product, int32_t divisor) noexcept
60+    {
61+        return DivFallback(product.first, product.second, divisor);
62+    }
63 #endif
64 
65     int64_t fee;
66@@ -162,23 +195,7 @@
67             return (uint64_t(fee) * at_size) / uint32_t(size);
68         } else {
69             // If not, use a custom 96-bit division.
70-
71-            // Write (this->fee * at_size) as (low32 + high64 * 2**32), so the result can be stated
72-            // as (low32 + high64 * 2**32) / this->size.
73-            auto [high64, low32] = MulFallback(fee, at_size);
74-            // Compute high64 / this->size, so the result becomes
75-            // (low32 + (high64 - high64_div * size) * 2**32) / this->size + (high64_div * 2**32).
76-            int64_t high64_div = high64 / size;
77-            // Evaluate the parenthesized expression above, so the result becomes
78-            // low64 / this->size + (high64_div * 2**32)
79-            int64_t low64 = ((high64 - high64_div * size) << 32) + low32;
80-            // Evaluate the division so the result becomes low64_div + high64_div * 2**32. We need
81-            // this division to round down however, while the / operator rounds towards zero. In
82-            // case low64 is negative and not a multiple of size, we thus need a correction.
83-            int64_t low64_div = low64 / size;
84-            low64_div -= (low64 % size) < 0;
85-            // Evaluate and return the result
86-            return (high64_div << 32) + low64_div;
87+            return Div(Mul(fee, at_size), size);
88         }
89     }
90 };
    sipa commented at 8:22 pm on July 29, 2024:
    I didn’t do something like this initially, as the Evaluate / Div operations are far less performance critical than Mul, but I’ve now adopted code like this (plus adding an __int128-based Div as well) for consistency and testability.
  11. in src/util/feefrac.h:179 in 5a4c01c4b2 outdated 
    174+            int64_t low64 = ((high64 - high64_div * size) << 32) + low32;
175+            // Evaluate the division so the result becomes low64_div + high64_div * 2**32. We need
176+            // this division to round down however, while the / operator rounds towards zero. In
177+            // case low64 is negative and not a multiple of size, we thus need a correction.
178+            int64_t low64_div = low64 / size;
179+            low64_div -= (low64 % size) < 0;
    paplorinc commented at 6:11 am on July 29, 2024:
    oh, wow, I had to look at this twice :D
  12. in src/util/feefrac.h:174 in 5a4c01c4b2 outdated 
    169+            // Compute high64 / this->size, so the result becomes
170+            // (low32 + (high64 - high64_div * size) * 2**32) / this->size + (high64_div * 2**32).
171+            int64_t high64_div = high64 / size;
172+            // Evaluate the parenthesized expression above, so the result becomes
173+            // low64 / this->size + (high64_div * 2**32)
174+            int64_t low64 = ((high64 - high64_div * size) << 32) + low32;
    paplorinc commented at 6:41 am on July 29, 2024:
    nit: while the return value needs a +, I think this would work with a | low32 as well (which would provide better documentation about them not overlapping)
    sipa commented at 8:23 pm on July 29, 2024:
    I’d rather not. I find the use of bitwise operations with signed integers a bit unintuitive.
  13. in src/test/feefrac_tests.cpp:32 in 5a4c01c4b2 outdated 
    27+    BOOST_CHECK_EQUAL(p1.Evaluate(100000000), 1000000000);
28+    BOOST_CHECK_EQUAL(p1.Evaluate(0x7fffffff), int64_t(0x7fffffff) * 10);
29+
30+    FeeFrac neg{-1001, 100};
31+    BOOST_CHECK_EQUAL(neg.Evaluate(0), 0);
32+    BOOST_CHECK_EQUAL(neg.Evaluate(1), -11);
    paplorinc commented at 6:53 am on July 29, 2024:
    how often would we get negative fee in reality? If rounding towards negative infinity just a theoretical exercise or is it an important usecase?
    sipa commented at 8:27 pm on July 29, 2024:

    I only added the logic for rounding towards negative infinity because of consistency, not because of a hard requirement. I’ve added a comment too.

    But just to clarify, without the correction step, the behavior is essentially arbitrary for negative fees. low64 (now renamed to n_low) can be both positive or negative with negative n (positive when n.second is positive, and n.first is a multiple of d; negative when n.first is non-multiple of d). That’s just too hard to specify and test.

  14. paplorinc changes_requested
  15. paplorinc commented at 6:57 am on July 29, 2024: contributor
    I think we could make the code more testable by extracting the 96 bit division like we did for the multiplication
  16. ceffikhan commented at 8:47 am on July 29, 2024: none
    Concept ACK
  17. instagibbs commented at 1:41 pm on July 29, 2024: member

    The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics

    for end-of-block packing reasons I assume?

  18. glozow commented at 3:51 pm on July 29, 2024: member

    Concept ACK

    Also concept ack to changing CFeeRate to use a FeeFrac internally. Did it locally to see what the quirks are - CFeeRate rounds up, is that maybe worth matching?

  19. sipa force-pushed on Jul 29, 2024
  20. sipa force-pushed on Jul 29, 2024
  21. sipa force-pushed on Jul 29, 2024
  22. sipa commented at 9:43 pm on July 29, 2024: member

    I’ve made a number of changes, mostly in response to @paplorinc’s suggestion, which involves:

    • Rewriting all of feefrac’s fuzz tests to test against arith_uint256 (rather than using its own ad-hoc 128-bit bigint logic), which also involved adding an arith_uint256::operator<=>.
    • Separating out a FeeFrac::Div (with FeeFrac::DivFallback, like Mul) for 96-bit division, which is tested directly.
    • Writing FeeFrac::Evaluate in terms of FeeFrac::Div and FeeFrac::Mul.

    In addition, a bunch of comment change and code simplifications.

    @instagibbs

    The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics

    for end-of-block packing reasons I assume?

    The thing I have in mind, is the following algorithm for finding out an upper bound on the maximum fee a block template can gather (assuming optimally-linearized clusters):

    0weight_left = 4000000
1fee_collected = 0
2for chunk in sorted(mempool.all_chunks, by_decreasing_feerate):
3    if chunk.weight <= weight_left:
4        weight_left -= chunk.weight
5        fee_collected += chunk.fee
6    else:
7        fee_collected += chunk.Evaluate(weight)
8        break

    Assuming optimally-linearized clusters, this gives a correct upper bound on total collectable fee, which may be useful in heuristics to determine whether it’s worth spending time on searching more for example, or in statistics. It’s really a super simple operation, but the multiplication being able to exceed 64-bit integers makes it a whole lot more complicated.

    @glozow

    Concept ACK

    Also concept ack to changing CFeeRate to use a FeeFrac internally. Did it locally to see what the quirks are - CFeeRate rounds up, is that maybe worth matching?

    Ha, nice catch. See above why I do actually want rounding-down behavior here. Perhaps we’ll need to add a boolean argument for controlling up/down rounding behavior?

  23. DrahtBot added the label CI failed on Jul 30, 2024
  24. DrahtBot removed the label CI failed on Jul 30, 2024
  25. sipa force-pushed on Jul 30, 2024
  26. sipa commented at 4:01 pm on July 30, 2024: member
    I have added a commit that splits FeeFrac::Evaluate into an EvaluateDown and an EvaluateUp, corresponding to the rounding modes they implement (plus tests for both behaviors).
  27. in src/util/feefrac.h:75 in 1cc0d5475a outdated 
    76+        // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
77+        // correction.
78+        int64_t quot_low = n_low / d;
79+        int64_t mod_low = n_low % d;
80+        if (mod_low) [[likely]] {
81+            quot_low += (mod_low > 0) - round_down;
    paplorinc commented at 5:27 pm on July 31, 2024:

    Looks like this isn’t covered by dedicated tests - only by fuzz and on platforms where !__SIZEOF_INT128__, right?

    Since the rounding should be the same for both implementations, we could consider pulling the rounding into Evaluate to make sure these lines are always tested:

     0diff --git a/src/util/feefrac.h b/src/util/feefrac.h
 1--- a/src/util/feefrac.h	(revision 1cc0d5475a578a8299c24c008c0080a6006cae28)
 2+++ b/src/util/feefrac.h	(date 1722450548560)
 3@@ -55,7 +55,7 @@
 4      * to be consistent for testability reasons.
 5      *
 6      * The result must fit in an int64_t, and d must be strictly positive. */
 7-    static inline int64_t DivFallback(std::pair<int64_t, uint32_t> n, int32_t d, bool round_down) noexcept
 8+    static inline std::pair<int64_t, int64_t> DivFallback(std::pair<int64_t, uint32_t> n, int32_t d) noexcept
 9     {
10         Assume(d > 0);
11         // Compute quot_high = n.first / d, so the result becomes
12@@ -69,13 +69,7 @@
13         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
14         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
15         // correction.
16-        int64_t quot_low = n_low / d;
17-        int64_t mod_low = n_low % d;
18-        if (mod_low) [[likely]] {
19-            quot_low += (mod_low > 0) - round_down;
20-        }
21-        // Combine and return the result
22-        return (quot_high << 32) + quot_low;
23+        return {(quot_high << 32) + n_low / d, n_low % d};
24     }
25 
26 #ifdef __SIZEOF_INT128__
27@@ -90,17 +84,10 @@
28      *  version relying on __int128.
29      *
30      * The result must fit in an int64_t, and d must be strictly positive. */
31-    static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
32+    static inline std::pair<int64_t, int32_t> Div(__int128 n, int32_t d) noexcept
33     {
34         Assume(d > 0);
35-        // Compute the division.
36-        int64_t quot = n / d;
37-        int32_t mod = n % d;
38-        // Correct result if the / operator above rounded in the wrong direction.
39-        if (mod) [[likely]] {
40-            quot += (mod > 0) - round_down;
41-        }
42-        return quot;
43+        return {n / d, n % d};
44     }
45 #else
46     static constexpr auto Mul = MulFallback;
47@@ -216,7 +203,9 @@
48             }
49         } else {
50             // Otherwise, use Mul and Div.
51-            return Div(Mul(fee, at_size), size, RoundDown);
52+            auto [quot, mod] = Div(Mul(fee, at_size), size);
53+            auto round = (mod > 0) - (mod && RoundDown);
54+            return quot + round;
55         }
56     }

    It seems to me both are already using combined division/modulo anyway (i.e. __divmodti4 on gcc), so the performance should be similar https://godbolt.org/z/Es5o8b3qo.

    sipa commented at 8:51 pm on July 31, 2024:

    Looks like this isn’t covered by dedicated tests - only by fuzz and on platforms where !SIZEOF_INT128, right?

    The feefrac_mul_div fuzz test tests this code on every platform (only for n inputs which are themselves the product of a 32-bit integer times a 64-bit integer, but given that those are the only ones that matter for production that seems sufficient to me).

    Also note that we build fuzz corpora only on platforms that support libfuzzer, but the constructed fuzz inputs then do get tested (in CI even) on other test environments too.

    sipa commented at 9:25 pm on July 31, 2024:

    Since the rounding should be the same for both implementations, we could consider pulling the rounding into Evaluate to make sure these lines are always tested:

    I like that idea, but it’s a bigger change than I’m willing to make to this code now.

  28. in src/util/feefrac.h:103 in 1cc0d5475a outdated 
    105+        int32_t mod = n % d;
106+        // Correct result if the / operator above rounded in the wrong direction.
107+        if (mod) [[likely]] {
108+            quot += (mod > 0) - round_down;
109+        }
110+        return quot;
    paplorinc commented at 6:36 pm on July 31, 2024:

    If we want to avoid branching here, I think we can avoid the jump i.e.

    0        test    eax, eax
1        je      .L4
2        setg    al
3        movzx   eax, al
4        sub     eax, ebx
5        cdqe
6        add     rbp, rax

    by doing something like

    0        auto round = (mod > 0) - (mod && round_down);
1        return quot + round;

    which looks like

    0        test    eax, eax
1        setne   al
2        setg    bl
3        movzx   eax, al
4        and     eax, ecx
5        sub     ebx, eax
6        movsx   rbx, ebx
7        add     rbx, rdx

    (see: https://godbolt.org/z/Es5o8b3qo)

    sipa commented at 9:23 pm on July 31, 2024:
    Neat! Will incorporate.
    sipa commented at 10:13 pm on July 31, 2024:
    Done.
  29. in src/util/feefrac.h:213 in 1cc0d5475a outdated 
    214+            } else {
215+                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
216+            }
217+        } else {
218+            // Otherwise, use Mul and Div.
219+            return Div(Mul(fee, at_size), size, RoundDown);
    paplorinc commented at 7:46 pm on July 31, 2024:
    +1, feefrac_tests pass if I delete the first part of the if and use this for the small values as well! (would be nice if we could automate this)
    sipa commented at 8:52 pm on July 31, 2024:
    That is what the feefrac_mul_div test does effectively.
    paplorinc commented at 8:58 pm on July 31, 2024:
    Does it test return Div(Mul(fee, at_size), size, RoundDown) when fee < 0x200000000? I don’t think that can happen in reality, I just tested it to make sure it’s correct for small values as well.
    sipa commented at 9:00 pm on July 31, 2024:

    Yes, it invokes Div(Mul(mul64, mul32), div), which is effectively that.

    It’s not running this exact line inside Evaluate, but instead contains a copy of the code we want to behave correctly. But please, it’s one line.

    paplorinc commented at 9:14 pm on July 31, 2024:

    But please, it’s one line.

    +1 meant that I like this, maybe I should use a 👍 next time :)

    sipa commented at 9:16 pm on July 31, 2024:
    My line of commenting here was in response to your “(would be nice if we could automate this)”. My point is that to a large extent, the feefrac_mul_div test does this (even for small values), with the minor limitation that it does it by effectively copying the line rather than invoking it directly (so over time it’s possible in theory that the two diverge, and this doesn’t remain tested; but right now you need but look at the test and see it does the same thing to get confidence Div/Mul also work for this purpose for small values).
    paplorinc commented at 9:27 pm on July 31, 2024:
    Thanks!
  30. in src/test/fuzz/feefrac.cpp:165 in 1cc0d5475a outdated 
    160+    // rounding down or positive and we rounding up, the absolute value of the quotient is the
161+    // rounded-up quotient of the absolute values.
162+    auto prod_abs = Abs256(mul32) * Abs256(mul64);
163+    auto div_abs = Abs256(div);
164+    auto quot_abs = (is_negative == round_down) ?
165+        (prod_abs + div_abs - 1) / div_abs :
    paplorinc commented at 7:48 pm on July 31, 2024:
    nit: this is very useful way to test the big divisions - but it repeats the production code logic for the small ones.
    sipa commented at 8:47 pm on July 31, 2024:
    I don’t understand what you mean by big and small divisions.
    paplorinc commented at 8:54 pm on July 31, 2024:
    I meant that in https://github.com/bitcoin/bitcoin/pull/30535/files#diff-09e6cf871236bf03d32cca9405837d9b7927690b2296a2de17c9be6ea0e75959R215 we’re using the same A + (B - 1) / B equation for rounding, i.e. the test and production code may be too similar. I think it’s fine since the big fee rounding is the more complicated one.
    sipa commented at 8:56 pm on July 31, 2024:
    Ah, I see, yes. I mean it’s really the only way of implementing a rounding-up division that I know. And while conceptually the algorithm is the same, it is being done on arith_uint256 rather than the types used in production.
    paplorinc commented at 9:29 pm on July 31, 2024:
    Indeed, thanks for checking
  31. in src/test/fuzz/feefrac.cpp:63 in 1cc0d5475a outdated 
    71+        return mul_abs_a <=> mul_abs_b;
72     }
73 }
74 
75+/** The maximum absolute value of an int64_t, as an arith_uint256 (2^63). */
76+const auto MAX_ABS_INT64 = arith_uint256{1} << 63;
    paplorinc commented at 7:50 pm on July 31, 2024:
    can we move this to the top to make it available for Abs256?
    sipa commented at 10:13 pm on July 31, 2024:
    Done.
  32. in src/test/fuzz/feefrac.cpp:28 in 1cc0d5475a outdated 
    51+    } else if (x > std::numeric_limits<int64_t>::min()) {
52+        // For negative numbers, negate first.
53+        return arith_uint256{static_cast<uint64_t>(-x)};
54+    } else {
55+        // Special case for x == -2^63 (for which -x results in integer overflow).
56+        return arith_uint256{1} << 63;
    paplorinc commented at 7:51 pm on July 31, 2024: 
    0        return MAX_ABS_INT64;
    sipa commented at 10:13 pm on July 31, 2024:
    Done.
  33. in src/util/feefrac.h:196 in 1cc0d5475a outdated 
    190@@ -144,6 +191,38 @@ struct FeeFrac
191         std::swap(a.fee, b.fee);
192         std::swap(a.size, b.size);
193     }
194+
195+private:
196+    /** Compute, at this object's feerate, how much fee does at_size correspond to.
    paplorinc commented at 7:55 pm on July 31, 2024:

    nit (sounds a bit weird to me):

    0    /** Compute the fee for a given `at_size` using this object's feerate.
    sipa commented at 10:13 pm on July 31, 2024:
    Done.
  34. in src/test/fuzz/feefrac.cpp:146 in 1cc0d5475a outdated 
    141+
142+FUZZ_TARGET(feefrac_mul_div)
143+{
144+    // Verify the behavior of:
145+    // - The combination of FeeFrac::Mul + FeeFrac::Div.
146+    // - The combination of FeeFrac::MulFallback + FeeFrac::DivFallback.
    paplorinc commented at 7:58 pm on July 31, 2024:
    how are we testing both? Not on the same platform, right? And we’re also testing the small value calculations here, right?
    sipa commented at 8:54 pm on July 31, 2024:
    The test directly invokes both Div(Mul(mul64, mul32), div) and DivFallback(MulFallback(mul64, mul32), div).
    paplorinc commented at 8:58 pm on July 31, 2024:
    My mistake, thanks for clarifying
  35. in src/arith_uint256.h:215 in 1cc0d5475a outdated 
    210@@ -210,13 +211,8 @@ class base_uint
211     friend inline base_uint operator<<(const base_uint& a, int shift) { return base_uint(a) <<= shift; }
212     friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
213     friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
214-    friend inline bool operator!=(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) != 0; }
215-    friend inline bool operator>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) > 0; }
216-    friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
217-    friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
218-    friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
219+    friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
    paplorinc commented at 7:59 pm on July 31, 2024:
    nice!
  36. in src/test/fuzz/feefrac.cpp:54 in bcf879056d outdated 
    55-    // intentional here.
56-    if (a1 < 0) abs_a1 = ~abs_a1 + 1;
57-    if (a2 < 0) abs_a2 = ~abs_a2 + 1;
58-    if (b1 < 0) abs_b1 = ~abs_b1 + 1;
59-    if (b2 < 0) abs_b2 = ~abs_b2 + 1;
60+    // Compute absolute values of products.
    paplorinc commented at 8:16 pm on July 31, 2024:

    Is it important to distinguish the 0 values from the positive ones when comparing the signs? If not, maybe we can simplify a bit:

    0    // Compute and compare signs.
1    int sign_a = (a1 < 0) ^ (a2 < 0) ? -1 : 1;
2    int sign_b = (b1 < 0) ^ (b2 < 0) ? -1 : 1;
3    if (sign_a != sign_b) return sign_a <=> sign_b;
4
5    auto result = Abs256(a1) * Abs256(a2) <=> Abs256(b1) * Abs256(b2);
6    return (sign_a >= 0) ? result : 0 <=> result;
    sipa commented at 9:38 pm on July 31, 2024:
    I believe that’s correct, but it’s less obviously correct than the existing code IMO, which I think is the more relevant criterion for tests.
    paplorinc commented at 9:46 pm on July 31, 2024:

    In that case consider only the second part of the suggestion:

    0    auto result = Abs256(a1) * Abs256(a2) <=> Abs256(b1) * Abs256(b2);
1    return (sign_a >= 0) ? result : 0 <=> result;

    (obviously non-blocker)

    paplorinc commented at 10:10 pm on July 31, 2024:

    Or a local lambda, for the first part to make it cleaner:

    0    auto sign = [](int64_t x) { return x == 0 ? 0 : x < 0 ? -1 : 1; };
1    int sign_a = sign(a1) * sign(a2);
2    int sign_b = sign(b1) * sign(b2);
3    if (sign_a != sign_b) return sign_a <=> sign_b;
    sipa commented at 10:14 pm on July 31, 2024:
    I prefer not changing this code except to the extent needed for the switch to arith_uint256. The existing code already works.
  37. in src/util/feefrac.h:204 in 80711ef01b outdated 
    193+     */
194+    int64_t Evaluate(int32_t at_size) const noexcept
195+    {
196+        Assume(size > 0);
197+        Assume(at_size >= 0);
198+        if (fee >= 0 && fee < 0x200000000) [[likely]] {
    paplorinc commented at 8:32 pm on July 31, 2024:
    would it make sense to add non-fuzz 0x1ffffffff, 0x200000000 and 0x200000001 test cases for this boundary?
    sipa commented at 10:14 pm on July 31, 2024:
    Done.
  38. paplorinc approved
  39. paplorinc commented at 8:36 pm on July 31, 2024: contributor

    ACK 1cc0d5475a578a8299c24c008c0080a6006cae28

    I left a few recommendations and questions, was really fun reviewing this change - though it took me a lot of time.

    If you think our contributions have affected the change, please consider adding us as co-authors.

  40. DrahtBot requested review from tdb3 on Jul 31, 2024
  41. DrahtBot requested review from glozow on Jul 31, 2024
  42. DrahtBot requested review from ismaelsadeeq on Jul 31, 2024
  43. sipa force-pushed on Jul 31, 2024
  44. paplorinc commented at 7:50 am on August 1, 2024: contributor
    ACK 9590cdd1afc78ff73fdccd2d016075bf40b6b0e2
  45. glozow added the label Utils/log/libs on Aug 2, 2024
  46. brunoerg commented at 1:16 pm on August 6, 2024: contributor
    Concept ACK
  47. brunoerg commented at 2:22 pm on August 7, 2024: contributor

    I didn’t review it in depth but I used this PR to test my “mutation testing tool”, which creates mutations based on diff, and the tests are REALLY great! The only two mutants that were not killed seems to be “equivalent mutants”, so we can ignore them. See:

    Bitcoin Core (#30535 - feefrac: add support for evaluating at given size)

    • make && ./src/test/test_bitcoin --run_test=feefrac_tests

    • Mutation score: 94.4% (Excelent)

    MUTANTS NOT KILLED

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.22.h
 1index dbb03bbccc..0930d12846 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.22.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+        if (fee >= 0 && fee <= 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.13.h
 1index dbb03bbccc..71cb90757e 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.13.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+        if (fee > 0 && fee < 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.27.h
 1index dbb03bbccc..1f9ca50a5e 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.27.h
 4@@ -69,7 +69,7 @@ struct FeeFrac
 5         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
 6         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
 7         // correction.
 8-        int64_t quot_low = n_low / d;
 9+                int64_t quot_low = (n_low / d) + 1;
10         int32_t mod_low = n_low % d;
11         quot_low += (mod_low > 0) - (mod_low && round_down);
12         // Combine and return the result

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.29.h
 1index dbb03bbccc..96f39cdd74 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.29.h
 4@@ -92,7 +92,7 @@ struct FeeFrac
 5     {
 6         Assume(d > 0);
 7         // Compute the division.
 8-        int64_t quot = n / d;
 9+                int64_t quot = (n / d) + 1;
10         int32_t mod = n % d;
11         // Correct result if the / operator above rounded in the wrong direction.
12         return quot + (mod > 0) - (mod && round_down);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.23.h
 1index dbb03bbccc..eb87c9c3b6 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.23.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+                if (fee >= 0 && fee > 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.0.h
 1index dbb03bbccc..41599bcccd 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.0.h
 4@@ -216,7 +216,7 @@ struct FeeFrac
 5 
 6 public:
 7     /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
 8-    int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
 9+        int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
10     /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
11     int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
12 };

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.33.h
 1index dbb03bbccc..7776bb61da 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.33.h
 4@@ -69,7 +69,7 @@ struct FeeFrac
 5         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
 6         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
 7         // correction.
 8-        int64_t quot_low = n_low / d;
 9+                int64_t quot_low = (n_low / d) - 1;
10         int32_t mod_low = n_low % d;
11         quot_low += (mod_low > 0) - (mod_low && round_down);
12         // Combine and return the result

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.16.h
 1index dbb03bbccc..ec3adc87bf 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.16.h
 4@@ -71,7 +71,7 @@ struct FeeFrac
 5         // correction.
 6         int64_t quot_low = n_low / d;
 7         int32_t mod_low = n_low % d;
 8-        quot_low += (mod_low > 0) - (mod_low && round_down);
 9+                quot_low += (mod_low > 0) - (mod_low || round_down);
10         // Combine and return the result
11         return (quot_high << 32) + quot_low;
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.12.h
 1index dbb03bbccc..92848b64d3 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.12.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+                if (fee <= 0 && fee < 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.18.h
 1index dbb03bbccc..08f5b1fd81 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.18.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+                if (fee >= 0 || fee < 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.4.h
 1index dbb03bbccc..2177b00401 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.4.h
 4@@ -92,7 +92,7 @@ struct FeeFrac
 5     {
 6         Assume(d > 0);
 7         // Compute the division.
 8-        int64_t quot = n / d;
 9+                int64_t quot = n * d;
10         int32_t mod = n % d;
11         // Correct result if the / operator above rounded in the wrong direction.
12         return quot + (mod > 0) - (mod && round_down);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.24.h
 1index dbb03bbccc..ac4672aa71 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.24.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+                if (fee >= 0 && fee >= 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.20.h
 1index dbb03bbccc..abc34f1f78 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.20.h
 4@@ -95,7 +95,7 @@ struct FeeFrac
 5         int64_t quot = n / d;
 6         int32_t mod = n % d;
 7         // Correct result if the / operator above rounded in the wrong direction.
 8-        return quot + (mod > 0) - (mod && round_down);
 9+                return quot + (mod > 0) + (mod && round_down);
10     }
11 #else
12     static constexpr auto Mul = MulFallback;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.15.h
 1index dbb03bbccc..ce3a513935 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.15.h
 4@@ -95,7 +95,7 @@ struct FeeFrac
 5         int64_t quot = n / d;
 6         int32_t mod = n % d;
 7         // Correct result if the / operator above rounded in the wrong direction.
 8-        return quot + (mod > 0) - (mod && round_down);
 9+                return quot + (mod <= 0) - (mod && round_down);
10     }
11 #else
12     static constexpr auto Mul = MulFallback;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.9.h
 1index dbb03bbccc..b3563eb3a6 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.9.h
 4@@ -71,7 +71,7 @@ struct FeeFrac
 5         // correction.
 6         int64_t quot_low = n_low / d;
 7         int32_t mod_low = n_low % d;
 8-        quot_low += (mod_low > 0) - (mod_low && round_down);
 9+                quot_low += (mod_low >= 0) - (mod_low && round_down);
10         // Combine and return the result
11         return (quot_high << 32) + quot_low;
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.3.h
 1index dbb03bbccc..001523cad9 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.3.h
 4@@ -69,7 +69,7 @@ struct FeeFrac
 5         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
 6         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
 7         // correction.
 8-        int64_t quot_low = n_low / d;
 9+                int64_t quot_low = n_low * d;
10         int32_t mod_low = n_low % d;
11         quot_low += (mod_low > 0) - (mod_low && round_down);
12         // Combine and return the result

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.30.h
 1index dbb03bbccc..814f0fc845 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.30.h
 4@@ -93,7 +93,7 @@ struct FeeFrac
 5         Assume(d > 0);
 6         // Compute the division.
 7         int64_t quot = n / d;
 8-        int32_t mod = n % d;
 9+                int32_t mod = (n % d) + 1;
10         // Correct result if the / operator above rounded in the wrong direction.
11         return quot + (mod > 0) - (mod && round_down);
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.7.h
 1index dbb03bbccc..13bbadc2e3 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.7.h
 4@@ -71,7 +71,7 @@ struct FeeFrac
 5         // correction.
 6         int64_t quot_low = n_low / d;
 7         int32_t mod_low = n_low % d;
 8-        quot_low += (mod_low > 0) - (mod_low && round_down);
 9+                quot_low += (mod_low < 0) - (mod_low && round_down);
10         // Combine and return the result
11         return (quot_high << 32) + quot_low;
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.34.h
 1index dbb03bbccc..00f6e048f6 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.34.h
 4@@ -70,7 +70,7 @@ struct FeeFrac
 5         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
 6         // correction.
 7         int64_t quot_low = n_low / d;
 8-        int32_t mod_low = n_low % d;
 9+                int32_t mod_low = (n_low % d) - 1;
10         quot_low += (mod_low > 0) - (mod_low && round_down);
11         // Combine and return the result
12         return (quot_high << 32) + quot_low;

    11.h

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.11.h
 1index dbb03bbccc..eb87c9c3b6 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.11.h
 4@@ -201,7 +201,7 @@ struct FeeFrac
 5     {
 6         Assume(size > 0);
 7         Assume(at_size >= 0);
 8-        if (fee >= 0 && fee < 0x200000000) [[likely]] {
 9+                if (fee >= 0 && fee > 0x200000000) [[likely]] {
10             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
11             if constexpr (RoundDown) {
12                 return (uint64_t(fee) * at_size) / uint32_t(size);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.25.h
 1index dbb03bbccc..0c3ddaee86 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.25.h
 4@@ -61,7 +61,7 @@ struct FeeFrac
 5         // Compute quot_high = n.first / d, so the result becomes
 6         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
 7         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
 8-        int64_t quot_high = n.first / d;
 9+                int64_t quot_high = (n.first / d) + 1;
10         // Evaluate the parenthesized expression above, so the result becomes
11         // n_low / d + (quot_high * 2**32)
12         int64_t n_low = ((n.first % d) << 32) + n.second;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.21.h
 1index dbb03bbccc..657f9144d4 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.21.h
 4@@ -206,7 +206,7 @@ struct FeeFrac
 5             if constexpr (RoundDown) {
 6                 return (uint64_t(fee) * at_size) / uint32_t(size);
 7             } else {
 8-                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
 9+                                return (uint64_t(fee) * at_size + size + 1U) / uint32_t(size);
10             }
11         } else {
12             // Otherwise, use Mul and Div.

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.14.h
 1index dbb03bbccc..e5cdb1f96f 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.14.h
 4@@ -71,7 +71,7 @@ struct FeeFrac
 5         // correction.
 6         int64_t quot_low = n_low / d;
 7         int32_t mod_low = n_low % d;
 8-        quot_low += (mod_low > 0) - (mod_low && round_down);
 9+                quot_low += (mod_low <= 0) - (mod_low && round_down);
10         // Combine and return the result
11         return (quot_high << 32) + quot_low;
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.31.h
 1index dbb03bbccc..fcddd25bb4 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.31.h
 4@@ -61,7 +61,7 @@ struct FeeFrac
 5         // Compute quot_high = n.first / d, so the result becomes
 6         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
 7         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
 8-        int64_t quot_high = n.first / d;
 9+                int64_t quot_high = (n.first / d) - 1;
10         // Evaluate the parenthesized expression above, so the result becomes
11         // n_low / d + (quot_high * 2**32)
12         int64_t n_low = ((n.first % d) << 32) + n.second;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.2.h
 1index dbb03bbccc..071fc90a19 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.2.h
 4@@ -61,7 +61,7 @@ struct FeeFrac
 5         // Compute quot_high = n.first / d, so the result becomes
 6         // (n.second + (n.first - quot_high * d) * 2**32) / d + (quot_high * 2**32), or
 7         // (n.second + (n.first % d) * 2**32) / d + (quot_high * 2**32).
 8-        int64_t quot_high = n.first / d;
 9+                int64_t quot_high = n.first * d;
10         // Evaluate the parenthesized expression above, so the result becomes
11         // n_low / d + (quot_high * 2**32)
12         int64_t n_low = ((n.first % d) << 32) + n.second;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.8.h
 1index dbb03bbccc..084326c37d 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.8.h
 4@@ -95,7 +95,7 @@ struct FeeFrac
 5         int64_t quot = n / d;
 6         int32_t mod = n % d;
 7         // Correct result if the / operator above rounded in the wrong direction.
 8-        return quot + (mod > 0) - (mod && round_down);
 9+                return quot + (mod < 0) - (mod && round_down);
10     }
11 #else
12     static constexpr auto Mul = MulFallback;

    35.h

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.35.h
 1index dbb03bbccc..ae18b13a15 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.35.h
 4@@ -92,7 +92,7 @@ struct FeeFrac
 5     {
 6         Assume(d > 0);
 7         // Compute the division.
 8-        int64_t quot = n / d;
 9+                int64_t quot = (n / d) - 1;
10         int32_t mod = n % d;
11         // Correct result if the / operator above rounded in the wrong direction.
12         return quot + (mod > 0) - (mod && round_down);

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.6.h
 1index dbb03bbccc..6c98522329 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.6.h
 4@@ -206,7 +206,7 @@ struct FeeFrac
 5             if constexpr (RoundDown) {
 6                 return (uint64_t(fee) * at_size) / uint32_t(size);
 7             } else {
 8-                return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
 9+                                return (uint64_t(fee) * at_size + size - 1U) * uint32_t(size);
10             }
11         } else {
12             // Otherwise, use Mul and Div.

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.10.h
 1index dbb03bbccc..92b2c76d10 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.10.h
 4@@ -95,7 +95,7 @@ struct FeeFrac
 5         int64_t quot = n / d;
 6         int32_t mod = n % d;
 7         // Correct result if the / operator above rounded in the wrong direction.
 8-        return quot + (mod > 0) - (mod && round_down);
 9+                return quot + (mod >= 0) - (mod && round_down);
10     }
11 #else
12     static constexpr auto Mul = MulFallback;

    26.h

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.26.h
 1index dbb03bbccc..6b8d17594c 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.26.h
 4@@ -64,7 +64,7 @@ struct FeeFrac
 5         int64_t quot_high = n.first / d;
 6         // Evaluate the parenthesized expression above, so the result becomes
 7         // n_low / d + (quot_high * 2**32)
 8-        int64_t n_low = ((n.first % d) << 32) + n.second;
 9+                int64_t n_low = (((n.first % d) << 32) + n.second) + 1;
10         // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
11         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
12         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.28.h
 1index dbb03bbccc..e1b7b34e80 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.28.h
 4@@ -70,7 +70,7 @@ struct FeeFrac
 5         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a
 6         // correction.
 7         int64_t quot_low = n_low / d;
 8-        int32_t mod_low = n_low % d;
 9+                int32_t mod_low = (n_low % d) + 1;
10         quot_low += (mod_low > 0) - (mod_low && round_down);
11         // Combine and return the result
12         return (quot_high << 32) + quot_low;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.32.h
 1index dbb03bbccc..384b3f294d 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.32.h
 4@@ -64,7 +64,7 @@ struct FeeFrac
 5         int64_t quot_high = n.first / d;
 6         // Evaluate the parenthesized expression above, so the result becomes
 7         // n_low / d + (quot_high * 2**32)
 8-        int64_t n_low = ((n.first % d) << 32) + n.second;
 9+                int64_t n_low = (((n.first % d) << 32) + n.second) - 1;
10         // Evaluate the division so the result becomes quot_low + quot_high * 2**32. It is possible
11         // that the / operator here rounds in the wrong direction (if n_low is not a multiple of
12         // size, and is (if round_down) negative, or (if !round_down) positive). If so, make a

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.1.h
 1index dbb03bbccc..f2991cb61f 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.1.h
 4@@ -218,7 +218,7 @@ public:
 5     /** Compute the fee for a given size `at_size` using this object's feerate, rounding down. */
 6     int64_t EvaluateDown(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
 7     /** Compute the fee for a given size `at_size` using this object's feerate, rounding up. */
 8-    int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<false>(at_size); }
 9+        int64_t EvaluateUp(int32_t at_size) const noexcept { return Evaluate<true>(at_size); }
10 };
11 
12 /** Compare the feerate diagrams implied by the provided sorted chunks data.

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.17.h
 1index dbb03bbccc..b4f0590650 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.17.h
 4@@ -95,7 +95,7 @@ struct FeeFrac
 5         int64_t quot = n / d;
 6         int32_t mod = n % d;
 7         // Correct result if the / operator above rounded in the wrong direction.
 8-        return quot + (mod > 0) - (mod && round_down);
 9+                return quot + (mod > 0) - (mod || round_down);
10     }
11 #else
12     static constexpr auto Mul = MulFallback;

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.19.h
 1index dbb03bbccc..c421f87da4 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.19.h
 4@@ -71,7 +71,7 @@ struct FeeFrac
 5         // correction.
 6         int64_t quot_low = n_low / d;
 7         int32_t mod_low = n_low % d;
 8-        quot_low += (mod_low > 0) - (mod_low && round_down);
 9+                quot_low += (mod_low > 0) + (mod_low && round_down);
10         // Combine and return the result
11         return (quot_high << 32) + quot_low;
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.36.h
 1index dbb03bbccc..3a52d4728e 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.36.h
 4@@ -93,7 +93,7 @@ struct FeeFrac
 5         Assume(d > 0);
 6         // Compute the division.
 7         int64_t quot = n / d;
 8-        int32_t mod = n % d;
 9+                int32_t mod = (n % d) - 1;
10         // Correct result if the / operator above rounded in the wrong direction.
11         return quot + (mod > 0) - (mod && round_down);
12     }

     0diff --git a/src/util/feefrac.h b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.5.h
 1index dbb03bbccc..587cfedecd 100644
 2--- a/src/util/feefrac.h
 3+++ b/Users/brunogarcia/projects/bitcoin-core-dev/muts-pr-30535-feefrac-h/feefrac.mutant.5.h
 4@@ -204,7 +204,7 @@ struct FeeFrac
 5         if (fee >= 0 && fee < 0x200000000) [[likely]] {
 6             // Common case where (this->fee * at_size) is guaranteed to fit in a uint64_t.
 7             if constexpr (RoundDown) {
 8-                return (uint64_t(fee) * at_size) / uint32_t(size);
 9+                                return (uint64_t(fee) * at_size) * uint32_t(size);
10             } else {
11                 return (uint64_t(fee) * at_size + size - 1U) / uint32_t(size);
12             }
  48. sipa commented at 2:39 pm on August 7, 2024: member
    @brunoerg Cool!
  49. in src/util/feefrac.h:194 in 97f319e68a outdated 
    189+     * result rounded down (even for negative feerates).
190+     *
191+     * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
192+     * is guaranteed to be the case when 0 <= at_size <= this->size.
193+     */
194+    int64_t Evaluate(int32_t at_size) const noexcept
    ismaelsadeeq commented at 8:47 am on August 8, 2024:
    nit: It might be worth renaming this to EvaluateFee. The helper function and fuzzing comments refer to Evaluate to explain the calculations. While it’s clear they aren’t the same, differentiating explicitly by stating whats being evaluated might be better.
    sipa commented at 8:55 pm on August 16, 2024:
    Done!
  50. ismaelsadeeq approved
  51. ismaelsadeeq commented at 12:33 pm on August 8, 2024: member

    Code review ACK 9590cdd1afc78ff73fdccd2d016075bf40b6b0e2

    @ismaelsadeeq It’s a possibility, if we’d want to replace CFeeRate entirely. Another possibility is keeping CFeeRate and its interface, but make it be an encapsulated FeeFrac object (that e.g. on serialization converts to sats/kvb, but that otherwise keeps exact fractions).

    I prefer the idea of encapsulating FeeFrac within CFeeRate given how widely CFeeRate is relied upon. I’ve attempt to implement this approach on top of this PR. If this aligns with your idea, I can create a PR for it although the test currently assumes CFeeRate represents a fee rate per kb rather than a fraction, so I had to touch the test a bit.

    Note: A few mempool tests are failing with this diff, which I haven’t yet investigated.

      0diff --git a/src/policy/feerate.cpp b/src/policy/feerate.cpp
  1index eb0cba5c67a..05b4905b5e3 100644
  2--- a/src/policy/feerate.cpp
  3+++ b/src/policy/feerate.cpp
  4@@ -9,37 +9,24 @@
  5 
  6 #include <cmath>
  7 
  8-CFeeRate::CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes)
  9+CAmount CFeeRate::GetFee(uint32_t num_bytes) const
 10 {
 11-    const int64_t nSize{num_bytes};
 12-
 13-    if (nSize > 0) {
 14-        nSatoshisPerK = nFeePaid * 1000 / nSize;
 15-    } else {
 16-        nSatoshisPerK = 0;
 17-    }
 18+    return feerate.EvaluateUp(num_bytes);
 19 }
 20 
 21-CAmount CFeeRate::GetFee(uint32_t num_bytes) const
 22+CAmount CFeeRate::GetFeePerK() const
 23 {
 24-    const int64_t nSize{num_bytes};
 25-
 26-    // Be explicit that we're converting from a double to int64_t (CAmount) here.
 27-    // We've previously had issues with the silent double->int64_t conversion.
 28-    CAmount nFee{static_cast<CAmount>(std::ceil(nSatoshisPerK * nSize / 1000.0))};
 29-
 30-    if (nFee == 0 && nSize != 0) {
 31-        if (nSatoshisPerK > 0) nFee = CAmount(1);
 32-        if (nSatoshisPerK < 0) nFee = CAmount(-1);
 33+    if (feerate.size > 0) {
 34+        return feerate.fee * kvb / feerate.size;
 35     }
 36-
 37-    return nFee;
 38+    return 0;
 39 }
 40 
 41 std::string CFeeRate::ToString(const FeeEstimateMode& fee_estimate_mode) const
 42 {
 43+    CAmount nSatoshisPerK = GetFeePerK();
 44     switch (fee_estimate_mode) {
 45-    case FeeEstimateMode::SAT_VB: return strprintf("%d.%03d %s/vB", nSatoshisPerK / 1000, nSatoshisPerK % 1000, CURRENCY_ATOM);
 46+    case FeeEstimateMode::SAT_VB: return strprintf("%d.%03d %s/vB", nSatoshisPerK / kvb, nSatoshisPerK % kvb, CURRENCY_ATOM);
 47     default:                      return strprintf("%d.%08d %s/kvB", nSatoshisPerK / COIN, nSatoshisPerK % COIN, CURRENCY_UNIT);
 48     }
 49 }
 50diff --git a/src/policy/feerate.h b/src/policy/feerate.h
 51index 2e501729148..16c76fa71e5 100644
 52--- a/src/policy/feerate.h
 53+++ b/src/policy/feerate.h
 54@@ -8,6 +8,7 @@
 55 
 56 #include <consensus/amount.h>
 57 #include <serialize.h>
 58+#include <util/feefrac.h>
 59 
 60 
 61 #include <cstdint>
 62@@ -26,20 +27,21 @@ enum class FeeEstimateMode {
 63     SAT_VB,       //!< Use sat/vB fee rate unit
 64 };
 65 
 66+const int32_t kvb{1000};
 67 /**
 68  * Fee rate in satoshis per kilovirtualbyte: CAmount / kvB
 69  */
 70 class CFeeRate
 71 {
 72 private:
 73-    /** Fee rate in sat/kvB (satoshis per 1000 virtualbytes) */
 74-    CAmount nSatoshisPerK;
 75+    FeeFrac feerate;
 76 
 77 public:
 78     /** Fee rate of 0 satoshis per kvB */
 79-    CFeeRate() : nSatoshisPerK(0) { }
 80+    CFeeRate() : feerate(0, kvb) { }
 81+    /** Fee rate of _nSatoshisPerK satoshis per kvB */
 82     template<typename I>
 83-    explicit CFeeRate(const I _nSatoshisPerK): nSatoshisPerK(_nSatoshisPerK) {
 84+    explicit CFeeRate(const I _nSatoshisPerK): feerate(_nSatoshisPerK, kvb) {
 85         // We've previously had bugs creep in from silent double->int conversion...
 86         static_assert(std::is_integral<I>::value, "CFeeRate should be used without floats");
 87     }
 88@@ -50,7 +52,7 @@ public:
 89      * param@[in]   nFeePaid    The fee paid by a transaction, in satoshis
 90      * param@[in]   num_bytes   The vsize of a transaction, in vbytes
 91      */
 92-    CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes);
 93+    CFeeRate(const CAmount& nFeePaid, uint32_t num_bytes) : feerate(nFeePaid, num_bytes) {};
 94 
 95     /**
 96      * Return the fee in satoshis for the given vsize in vbytes.
 97@@ -62,19 +64,19 @@ public:
 98     /**
 99      * Return the fee in satoshis for a vsize of 1000 vbytes
100      */
101-    CAmount GetFeePerK() const { return nSatoshisPerK; }
102-    friend bool operator<(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK < b.nSatoshisPerK; }
103-    friend bool operator>(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK > b.nSatoshisPerK; }
104-    friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK == b.nSatoshisPerK; }
105-    friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK <= b.nSatoshisPerK; }
106-    friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK >= b.nSatoshisPerK; }
107-    friend bool operator!=(const CFeeRate& a, const CFeeRate& b) { return a.nSatoshisPerK != b.nSatoshisPerK; }
108-    CFeeRate& operator+=(const CFeeRate& a) { nSatoshisPerK += a.nSatoshisPerK; return *this; }
109+    CAmount GetFeePerK() const;
110+    friend bool operator<(const CFeeRate& a, const CFeeRate& b) { return a.feerate < b.feerate; }
111+    friend bool operator>(const CFeeRate& a, const CFeeRate& b) { return a.feerate > b.feerate; }
112+    friend bool operator==(const CFeeRate& a, const CFeeRate& b) { return a.feerate == b.feerate; }
113+    friend bool operator<=(const CFeeRate& a, const CFeeRate& b) { return a.feerate <= b.feerate; }
114+    friend bool operator>=(const CFeeRate& a, const CFeeRate& b) { return a.feerate >= b.feerate; }
115+    friend bool operator!=(const CFeeRate& a, const CFeeRate& b) { return a.feerate != b.feerate; }
116+    CFeeRate& operator+=(const CFeeRate& a) { feerate += a.feerate; return *this; }
117     std::string ToString(const FeeEstimateMode& fee_estimate_mode = FeeEstimateMode::BTC_KVB) const;
118-    friend CFeeRate operator*(const CFeeRate& f, int a) { return CFeeRate(a * f.nSatoshisPerK); }
119-    friend CFeeRate operator*(int a, const CFeeRate& f) { return CFeeRate(a * f.nSatoshisPerK); }
120+    friend CFeeRate operator*(const CFeeRate& f, int a) { return CFeeRate(a * f.GetFeePerK()); }
121+    friend CFeeRate operator*(int a, const CFeeRate& f) { return CFeeRate(a * f.GetFeePerK()); }
122 
123-    SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.nSatoshisPerK); }
124+    SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.GetFeePerK()); }
125 };
126 
127 #endif // BITCOIN_POLICY_FEERATE_H
128diff --git a/src/test/amount_tests.cpp b/src/test/amount_tests.cpp
129index e5ab1cfb902..ce8aa7f7515 100644
130--- a/src/test/amount_tests.cpp
131+++ b/src/test/amount_tests.cpp
132@@ -50,7 +50,7 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
133     feeRate = CFeeRate(123);
134     // Rounds up the result, if not integer
135     BOOST_CHECK_EQUAL(feeRate.GetFee(0), CAmount(0));
136-    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(1)); // Special case: returns 1 instead of 0
137+    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(1)); // returns 1 instead of 0; because we are rounding up
138     BOOST_CHECK_EQUAL(feeRate.GetFee(9), CAmount(2));
139     BOOST_CHECK_EQUAL(feeRate.GetFee(121), CAmount(15));
140     BOOST_CHECK_EQUAL(feeRate.GetFee(122), CAmount(16));
141@@ -61,7 +61,7 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
142     feeRate = CFeeRate(-123);
143     // Truncates the result, if not integer
144     BOOST_CHECK_EQUAL(feeRate.GetFee(0), CAmount(0));
145-    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(-1)); // Special case: returns -1 instead of 0
146+    BOOST_CHECK_EQUAL(feeRate.GetFee(8), CAmount(0));
147     BOOST_CHECK_EQUAL(feeRate.GetFee(9), CAmount(-1));
148 
149     // check alternate constructor
150@@ -70,21 +70,21 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
151     BOOST_CHECK_EQUAL(feeRate.GetFee(100), altFeeRate.GetFee(100));
152 
153     // Check full constructor
154-    BOOST_CHECK(CFeeRate(CAmount(-1), 0) == CFeeRate(0));
155-    BOOST_CHECK(CFeeRate(CAmount(0), 0) == CFeeRate(0));
156-    BOOST_CHECK(CFeeRate(CAmount(1), 0) == CFeeRate(0));
157+    BOOST_CHECK(CFeeRate(CAmount(-1)).GetFeePerK() == -1);
158+    BOOST_CHECK(CFeeRate(CAmount(0)).GetFeePerK() == 0);
159+    BOOST_CHECK(CFeeRate(CAmount(1), kvb).GetFeePerK() == 1);
160     // default value
161     BOOST_CHECK(CFeeRate(CAmount(-1), 1000) == CFeeRate(-1));
162     BOOST_CHECK(CFeeRate(CAmount(0), 1000) == CFeeRate(0));
163     BOOST_CHECK(CFeeRate(CAmount(1), 1000) == CFeeRate(1));
164     // lost precision (can only resolve satoshis per kB)
165-    BOOST_CHECK(CFeeRate(CAmount(1), 1001) == CFeeRate(0));
166-    BOOST_CHECK(CFeeRate(CAmount(2), 1001) == CFeeRate(1));
167+    BOOST_CHECK(CFeeRate(CAmount(1), 1001).GetFeePerK() == 0);
168+    BOOST_CHECK(CFeeRate(CAmount(2), 1001).GetFeePerK() == 1);
169     // some more integer checks
170-    BOOST_CHECK(CFeeRate(CAmount(26), 789) == CFeeRate(32));
171-    BOOST_CHECK(CFeeRate(CAmount(27), 789) == CFeeRate(34));
172+    BOOST_CHECK(CFeeRate(CAmount(26), 789).GetFeePerK() == CFeeRate(32).GetFeePerK());
173+    BOOST_CHECK(CFeeRate(CAmount(27), 789).GetFeePerK() == CFeeRate(34).GetFeePerK());
174     // Maximum size in bytes, should not crash
175-    CFeeRate(MAX_MONEY, std::numeric_limits<uint32_t>::max()).GetFeePerK();
176+    CFeeRate(MAX_MONEY, std::numeric_limits<int32_t>::max()).GetFeePerK();
177 
178     // check multiplication operator
179     // check multiplying by zero
180@@ -105,8 +105,8 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
181     // check boundary values
182     int maxInt = std::numeric_limits<int>::max();
183     feeRate = CFeeRate(maxInt);
184-    BOOST_CHECK(feeRate * 2 == CFeeRate(static_cast<int64_t>(maxInt) * 2));
185-    BOOST_CHECK(2 * feeRate == CFeeRate(static_cast<int64_t>(maxInt) * 2));
186+    BOOST_CHECK((feeRate * 2).GetFeePerK() == CFeeRate(static_cast<int64_t>(maxInt) * 2).GetFeePerK());
187+    BOOST_CHECK((2 * feeRate).GetFeePerK() == CFeeRate(static_cast<int64_t>(maxInt) * 2).GetFeePerK());
188     // check with zero fee rate
189     feeRate = CFeeRate(0);
190     BOOST_CHECK(feeRate * 5 == CFeeRate(0));
191@@ -125,9 +125,9 @@ BOOST_AUTO_TEST_CASE(BinaryOperatorTest)
192     BOOST_CHECK(a <= a);
193     BOOST_CHECK(b >= a);
194     BOOST_CHECK(b >= b);
195-    // a should be 0.00000002 BTC/kvB now
196+    // a is still 0.00000001 BTC/kvB because the size is added also
197     a += a;
198-    BOOST_CHECK(a == b);
199+    BOOST_CHECK_EQUAL(a.GetFeePerK(), a.GetFeePerK());
200 }
201 
202 BOOST_AUTO_TEST_CASE(ToStringTest)
  52. DrahtBot requested review from brunoerg on Aug 8, 2024
  53. in src/arith_uint256.h:220 in c8b7cc2300 outdated 
    216-    friend inline bool operator<(const base_uint& a, const base_uint& b) { return a.CompareTo(b) < 0; }
217-    friend inline bool operator>=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) >= 0; }
218-    friend inline bool operator<=(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <= 0; }
219+    friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
220     friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
221-    friend inline bool operator!=(const base_uint& a, uint64_t b) { return !a.EqualTo(b); }
    maflcko commented at 1:23 pm on August 8, 2024:

    Can you explain why you remove this line of code? IIUC, this means that != with uint64_t will now go through the implicit constructor call, and then through the new operator<=>.

    If it is intentional, then removing operator == with uint64_t should be done as well for the same reason? If not, it may be better to keep them?

    Mostly a consistency style-question, feel free to ignore.

    sipa commented at 2:07 pm on August 8, 2024:

    I don’t think so: https://godbolt.org/z/vYr4Tsbde

    The implicitly-defined operator!= falls back to using operator==. Only the implicitly defined operator<, operator>, operator<=, operator>= fall back to using operator<=>.

    paplorinc commented at 6:32 pm on August 8, 2024:

    Checked the same with a simple logging to make sure the reproducer is representative:

     0diff --git a/src/arith_uint256.h b/src/arith_uint256.h
 1index d91689c3b3..0198edbbbe 100644
 2--- a/src/arith_uint256.h
 3+++ b/src/arith_uint256.h
 4@@ -12,6 +12,7 @@
 5 #include <limits>
 6 #include <stdexcept>
 7 #include <string>
 8+#include <iostream>
 9 
10 class uint256;
11 
12@@ -212,7 +213,10 @@ public:
13     friend inline base_uint operator*(const base_uint& a, uint32_t b) { return base_uint(a) *= b; }
14     friend inline bool operator==(const base_uint& a, const base_uint& b) { return memcmp(a.pn, b.pn, sizeof(a.pn)) == 0; }
15     friend inline std::strong_ordering operator<=>(const base_uint& a, const base_uint& b) { return a.CompareTo(b) <=> 0; }
16-    friend inline bool operator==(const base_uint& a, uint64_t b) { return a.EqualTo(b); }
17+    friend inline bool operator==(const base_uint& a, uint64_t b) {
18+        std::cout << "base_uint::operator==(const base_uint& a, uint64_t b)" << std::endl;
19+        return a.EqualTo(b);
20+    }
21 
22     std::string GetHex() const;
23     std::string ToString() const;
24diff --git a/src/test/feefrac_tests.cpp b/src/test/feefrac_tests.cpp
25index 3bbc7450ea..255e96af01 100644
26--- a/src/test/feefrac_tests.cpp
27+++ b/src/test/feefrac_tests.cpp
28@@ -6,9 +6,19 @@
29 #include <random.h>
30 
31 #include <boost/test/unit_test.hpp>
32+#include "arith_uint256.h"
33+#include <iostream>
34 
35 BOOST_AUTO_TEST_SUITE(feefrac_tests)
36 
37+BOOST_AUTO_TEST_CASE(feefrac_operators_ne)
38+{
39+    auto x = arith_uint256{};
40+    std::cout << x.ToString() << std::endl;
41+    std::cout << (x == uint64_t(123)) << std::endl;
42+    std::cout << (x != uint64_t(123)) << std::endl;
43+}
44+
45 BOOST_AUTO_TEST_CASE(feefrac_operators)
46 {
47     FeeFrac p1{1000, 100}, p2{500, 300};

    % make -j10 && src/test/test_bitcoin –run_test=feefrac_tests/feefrac_operators_ne

    which prints:

    0000000000000000000000000000000000000000000000000000000000000000 base_uint::operator==(const base_uint& a, uint64_t b) 0 base_uint::operator==(const base_uint& a, uint64_t b) 1

  54. in src/util/feefrac.h:199 in 9590cdd1af outdated 
    195+     * (if !RoundDown).
196      *
197      * Requires this->size > 0, at_size >= 0, and that the correct result fits in a int64_t. This
198      * is guaranteed to be the case when 0 <= at_size <= this->size.
199      */
200+    template<bool RoundDown>
    glozow commented at 1:45 pm on August 8, 2024:
    Question: why did you make this a templated function instead of adding a bool parameter? Is it a compile-time optimization?
    sipa commented at 1:53 pm on August 8, 2024:
    Yeah, exactly. I think we want this function to be fast (and the rounding mode is always known at compile time anyway), while the Div functions are only needed in exceptional cases (negative fees, or >20 BTC fees) anyway.
    glozow commented at 1:55 pm on August 8, 2024:
    Makes sense!
  55. DrahtBot requested review from glozow on Aug 8, 2024
  56. arith_uint256: modernize comparison operators 31f1979a3d
  57. feefrac fuzz: use arith_uint256 instead of ad-hoc multiply ebd0daa74a
  58. feefrac: rework comments around Mul/MulFallback 4b923b602c
  59. feefrac: add helper functions for 96-bit division 78e16b4f53
  60. feefrac: add support for evaluating at given size 1f142c8b88
  61. feefrac: support both rounding up and down for Evaluate 
    Co-Authored-By: l0rinc <pap.lorinc@gmail.com>
    eff5bf7d67
  62. in src/util/feefrac.h:204 in 9590cdd1af outdated 
    199+    template<bool RoundDown>
200+    int64_t Evaluate(int32_t at_size) const noexcept
201+    {
202+        Assume(size > 0);
203+        Assume(at_size >= 0);
204+        if (fee >= 0 && fee < 0x200000000) [[likely]] {
    fanquake commented at 3:55 pm on August 8, 2024:

    Was curious how much difference using [[likely]] may/may-not have, as I’ve seen mixed discussions around it’s usage. For a single call to EvaluateDown (from the profile_estimate pass):

    combined

    paplorinc commented at 5:53 pm on August 8, 2024:

    I was also wondering, checked the actual execution for both paths (with & without [[likely]]), and if the benchmarks are accurate, AppleClang 15 doesn’t seem to make any change in this case (yet?).

    cmake –build build && ./build/src/bench/bench_bitcoin -filter=‘FeeFracEvaluate.*’ –min-time=10000

    // tried a few different ways of testing it, none of them showed any difference

     0#include <bench/bench.h>
 1#include <util/feefrac.h>
 2#include <random.h>
 3#include <vector>
 4
 5static void FeeFracEvaluate_likely(benchmark::Bench& bench)
 6{
 7    FastRandomContext rng(true);
 8
 9    constexpr size_t NUM_SAMPLES = 1'000'000;
10    std::vector<int64_t> fees(NUM_SAMPLES);
11    std::vector<int32_t> sizes(NUM_SAMPLES);
12    std::vector<int32_t> at_sizes(NUM_SAMPLES);
13
14    for (size_t i = 0; i < NUM_SAMPLES; ++i) {
15        fees[i] = rng.randrange(0x200000000);
16        sizes[i] = 1 + rng.randrange(INT32_MAX - 1);
17        at_sizes[i] = rng.randrange(INT32_MAX);
18    }
19
20    bench.run([&] {
21        for (size_t i = 0; i < NUM_SAMPLES; ++i) {
22            FeeFrac ff{fees[i], sizes[i]};
23            auto fee = i % 2 ? ff.EvaluateDown(at_sizes[i]) : ff.EvaluateUp(at_sizes[i]);
24            ankerl::nanobench::doNotOptimizeAway(fee);
25        }
26    });
27}
28
29static void FeeFracEvaluate_unlikely(benchmark::Bench& bench)
30{
31    FastRandomContext rng(true);
32
33    constexpr size_t NUM_SAMPLES = 1'000'000;
34    std::vector<int64_t> fees(NUM_SAMPLES);
35    std::vector<int32_t> sizes(NUM_SAMPLES);
36    std::vector<int32_t> at_sizes(NUM_SAMPLES);
37
38    for (size_t i = 0; i < NUM_SAMPLES; ++i) {
39        fees[i] = 0x200000000 + rng.randrange(0x200000000);
40        sizes[i] = 1 + rng.randrange(INT32_MAX - 1);
41        at_sizes[i] = rng.randrange(INT32_MAX);
42    }
43
44    bench.run([&] {
45        for (size_t i = 0; i < NUM_SAMPLES; ++i) {
46            FeeFrac ff{fees[i], sizes[i]};
47            auto fee = i % 2 ? ff.EvaluateDown(at_sizes[i]) : ff.EvaluateUp(at_sizes[i]);
48            ankerl::nanobench::doNotOptimizeAway(fee);
49        }
50    });
51}
52
53BENCHMARK(FeeFracEvaluate_likely, benchmark::PriorityLevel::HIGH);
54BENCHMARK(FeeFracEvaluate_unlikely, benchmark::PriorityLevel::HIGH);

    with [[likely]] (2x):

    ns/op op/s err% total benchmark
    1,133,642.20 882.11 0.1% 11.01 FeeFracEvaluate_likely
    6,809,775.64 146.85 0.1% 10.62 FeeFracEvaluate_unlikely
    ns/op op/s err% total benchmark
    1,132,721.68 882.83 0.0% 11.00 FeeFracEvaluate_likely
    6,811,900.44 146.80 0.1% 10.62 FeeFracEvaluate_unlikely

    without any attributes (2x):

    ns/op op/s err% total benchmark
    1,133,687.15 882.08 0.1% 11.00 FeeFracEvaluate_likely
    6,807,422.74 146.90 0.0% 10.62 FeeFracEvaluate_unlikely
    ns/op op/s err% total benchmark
    1,133,233.44 882.43 0.1% 11.04 FeeFracEvaluate_likely
    6,809,800.59 146.85 0.1% 10.63 FeeFracEvaluate_unlikely
    sipa commented at 7:46 pm on August 16, 2024:

    Looking at the actual code generated by GCC 14.2 (https://godbolt.org/z/8oTfPKE4q), I get the following diff from adding [[likely]]:

     0@@ -1,6 +1,13 @@
 1         mov     rax, rdi
 2         shr     rax, 33
 3-        je      .L8
 4+        jne     .L2
 5+        movsx   rax, edx
 6+        mov     esi, esi
 7+        xor     edx, edx
 8+        imul    rax, rdi
 9+        div     rsi
10+        ret
11+.L2:
12         movsx   r10, edx
13         sub     rsp, 24
14         mov     rax, r10
15@@ -24,10 +31,3 @@
16         adc     rax, -1
17         add     rsp, 24
18         ret
19-.L8:
20-        movsx   rax, edx
21-        mov     esi, esi
22-        xor     edx, edx
23-        imul    rax, rdi
24-        div     rsi
25-        ret

    which is exactly what I’d expect. The default branch prediction (before observations are available) is to assume that a conditional jump backwards will happen, while a conditional jump forward will not happen, so we want the likely branch to be emitted first; adding the [[likely]] does indeed result in that.

    It may be hard to observe this effect in a micro-benchmark as we expect that after a few iterations the CPU branch predictor will guess 100% correctly anyway.

    I think that’s sufficient reason to keep the [[likely]] here because (1) it is semantically correct (it is the only branch relevant in production code) (2) it documents this fact to human readers (3) it does not measurably worsen the code and (4) it appears to make at least some compilers produce marginally better code, but if people feel it should only be used when backed by observably better benchmarks, I’m okay with dropping it.

    paplorinc commented at 7:59 pm on August 16, 2024:
    I personally view it as documentation and would definitely keep it here
  63. sipa force-pushed on Aug 16, 2024
  64. paplorinc commented at 9:24 am on August 17, 2024: contributor
    ACK eff5bf7d673c797d63c5ad15ac18b8316dea5ffe (diff only contains Evaluate* -> EvaluateFee* changes)
  65. DrahtBot requested review from ismaelsadeeq on Aug 17, 2024
  66. ismaelsadeeq commented at 8:49 am on August 19, 2024: member
    re-ACK eff5bf7d673c797d63c5ad15ac18b8316dea5ffe


sipa DrahtBot ismaelsadeeq tdb3 paplorinc ceffikhan instagibbs glozow brunoerg maflcko fanquake


brunoerg glozow tdb3

Labels
Utils/log/libs

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-09-08 01:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me