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, or rounding up).
The motivation here is being able to do accurate feerate evaluations in cluster mempool block building heuristics (where rounding down is needed), but in principle this makes it possible to use FeeFrac as a more accurate replacement for CFeeRate (where for feerate estimation rounding up is desirable). Because of this, both rounding modes are implemented.
Unit tests are included for known-correct values, plus a fuzz test that verifies the result using arith_uint256.
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.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
sipa force-pushed
on Jul 26, 2024
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
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).
sipa force-pushed
on Jul 28, 2024
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)
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.
in
src/util/feefrac.h:197
in
5a4c01c4b2outdated
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
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.
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;
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 }
3940 // 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
6465 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 };
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.
in
src/util/feefrac.h:174
in
5a4c01c4b2outdated
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;
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)
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.
l0rinc changes_requested
l0rinc
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
ceffikhan
commented at 8:47 am on July 29, 2024:
none
Concept ACK
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?
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?
sipa force-pushed
on Jul 29, 2024
sipa force-pushed
on Jul 29, 2024
sipa force-pushed
on Jul 29, 2024
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.
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):
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.
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?
DrahtBot added the label
CI failed
on Jul 30, 2024
DrahtBot removed the label
CI failed
on Jul 30, 2024
sipa force-pushed
on Jul 30, 2024
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).
in
src/util/feefrac.h:75
in
1cc0d5475aoutdated
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;
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 }
2526 #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.
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.
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.
in
src/util/feefrac.h:103
in
1cc0d5475aoutdated
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;
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.
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).
in
src/test/fuzz/feefrac.cpp:181
in
1cc0d5475aoutdated
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 :
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.
in
src/test/fuzz/feefrac.cpp:63
in
1cc0d5475aoutdated
71+ return mul_abs_a <=> mul_abs_b;
72 }
73 }
7475+/** The maximum absolute value of an int64_t, as an arith_uint256 (2^63). */
76+const auto MAX_ABS_INT64 = arith_uint256{1} << 63;
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.
l0rinc
commented at 8:36 pm on July 31, 2024:
contributor
ACK1cc0d5475a578a8299c24c008c0080a6006cae28
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.
DrahtBot requested review from tdb3
on Jul 31, 2024
DrahtBot requested review from glozow
on Jul 31, 2024
DrahtBot requested review from ismaelsadeeq
on Jul 31, 2024
sipa force-pushed
on Jul 31, 2024
l0rinc
commented at 7:50 am on August 1, 2024:
contributor
ACK9590cdd1afc78ff73fdccd2d016075bf40b6b0e2
glozow added the label
Utils/log/libs
on Aug 2, 2024
brunoerg
commented at 1:16 pm on August 6, 2024:
contributor
Concept ACK
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.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.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 };
1112 /** 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;
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.
@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()); }
122123- SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.nSatoshisPerK); }
124+ SERIALIZE_METHODS(CFeeRate, obj) { READWRITE(obj.GetFeePerK()); }
125 };
126127 #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));
148149 // check alternate constructor
150@@ -70,21 +70,21 @@ BOOST_AUTO_TEST_CASE(GetFeeTest)
151 BOOST_CHECK_EQUAL(feeRate.GetFee(100), altFeeRate.GetFee(100));
152153 // 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();
177178 // 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 }
201202 BOOST_AUTO_TEST_CASE(ToStringTest)
DrahtBot requested review from brunoerg
on Aug 8, 2024
in
src/arith_uint256.h:221
in
c8b7cc2300outdated
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); }
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.
The implicitly-defined operator!= falls back to using operator==. Only the implicitly defined operator<, operator>, operator<=, operator>= fall back to using operator<=>.
% 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
in
src/util/feefrac.h:200
in
9590cdd1afoutdated
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>
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.
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):
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?).
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.
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.
I think after this and #31363 making CFeeRate a wrapper around FeePerVSize will be a good follow-up.
instagibbs
commented at 2:14 pm on February 6, 2025:
member
I did some very light fuzzing against CFeeRate results to make sure the “gap” between the two values is never huge, would there be some value in adding coverage to confirm that results aren’t wildly off from what we have today if we use it more widely?
sipa
commented at 2:25 pm on February 6, 2025:
member
would there be some value in adding coverage to confirm that results aren’t wildly off from what we have today if we use it more widely?
Sure, happy to add a commit for tests with that.
instagibbs
commented at 2:51 pm on February 6, 2025:
member
Bounding difference to “100 sats”, seems to work ok to a 500BTC fee, feel free to take or leave it since these numbers are kind of made up.
concept ACK anyways
laanwj approved
laanwj
commented at 3:13 pm on February 6, 2025:
member
Code review ACKf6aa28cf8fad6a3240498b500524bb380855b18e, mul/division code looks correct, testing and fuzzing coverage seems very good
DrahtBot requested review from instagibbs
on Feb 6, 2025
DrahtBot requested review from murchandamus
on Feb 6, 2025
in
src/test/fuzz/feefrac.cpp:130
in
f6aa28cf8foutdated
123+ // rounding down, or positive and we are rounding up, the absolute value of the quotient is
124+ // the rounded-up quotient of the absolute values.
125+ auto num_abs = Abs256(num);
126+ auto den_abs = Abs256(den);
127+ auto quot_abs = (is_negative == round_down) ?
128+ (num_abs + den_abs - 1) / den_abs :
yancyribbens
commented at 3:32 pm on February 7, 2025:
At first glance this is confusing. It looks like quot_abs is being computed differently depending on if num_high is negative or not, although it’s not apparent why right away. Maybe I will take these fuzz tests for a spin and look at some example values. As a side note, it’s interesting that fuzz tests are used to test for program correctness where I thought the main objective for fuzz tests was to find crashes and panics.
Modern C++ integer division always truncates toward zero. For positive numbers, that’s equivalent to rounding down, but for negatives it rounds up.
Since we need controlled rounding (toward negative infinity when round_down is true, or toward positive infinity otherwise), we need to take the sign of the numerator into account to adjust the result when necessary
For example, in feefrac_tests.cpp, tests like the following verify the rounding behavior:
For a positive fee (p1 initialized as {1000, 100}):
Right. The variables this code operates on are arith_uint256, which represent integers in range $[0, 2^{256}-1]$, and whose division operator rounds down (whether that means towards $-\infty$ or towards 0 does not matter, since only non-negative numbers can be represented anyway).
However, these values reason about the absolute value of what Div is expected to do. If we want to round down (towards $-\infty$), but the value being divided is negative, that means the absolute value of the result is rounded up (e.g. -5/3 = -1.6, if we want to round down would be -2, whose absolute value is 2, which is the rounded-up value of 5/3).
As a side note, it’s interesting that fuzz tests are used to test for program correctness where I thought the main objective for fuzz tests was to find crashes and panics.
They’re an amazing tool for this purpose. Any time you write a well-contained, well-specified piece of code, you can essentially write a less efficient simulator for its behavior, and compare the two in a fuzz test. We have many such examples in the codebase.
yancyribbens
commented at 1:09 am on February 8, 2025:
They’re an amazing tool for this purpose. Any time you write a well-contained, well-specified piece of code, you can essentially write a less efficient simulator for its behavior, and compare the two in a fuzz test. We have many such examples in the codebase.
However property tests, which like fuzz tests generate random input, although the inputs are truly random, which may be desirable for testing program correctness. From what I understand about fuzz tests, the random inputs are generated in such a way that new code paths are discovered with the goal of producing an overflow or crash.
Fuzzing is still random, it’s just biased towards increasing coverage. It’s not specifically intended to trigger bugs, it just aims to maximize coverage (code coverage, branch coverage, and “values being compared” coverage). And typically, this is exactly what you want in correctness tests too, as it may result in far more edge/special cases being exercised than uniformly random inputs may trigger.
Also note that coverage include the test harness itself, so if you add branches/cases to the test code, those too will be biased towards. In a way, this removes (or at least reduces, in typical cases) the need for the test designer to reason about what probability distributions of inputs are likely to trigger bugs.
in
src/test/feefrac_tests.cpp:18
in
f6aa28cf8foutdated
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
in
src/test/fuzz/feefrac.cpp:146
in
cf00540f54outdated
141+ assert(Abs256(res) == quot_abs);
142+
143+ // Compare approximately with floating-point.
144+ long double expect = round_down ? std::floor(num_high * 4294967296.0L + num_low) / den
145+ : std::ceil(num_high * 4294967296.0L + num_low) / den;
146+ // Expect to be accurate within 50 bits of precision, +- 1 sat.
Honestly, I think the code I included here already is more complicated than what I think was worth writing. But it’s just test code, and it’s already written, and it works.
Its added value is adding confidence for anyone looking at the test who has difficulty following, the exact arith_uint256-based test code, or otherwise doubts its correctness. The exact precision used here won’t make much difference I think - it should just be enough so someone can a single glance say “ok, if this test doesn’t fail, at least the result won’t be wildly off from what i expect it to do”.
instagibbs
commented at 8:12 pm on February 10, 2025:
I think there’s also some value in knowing we’re not diverging wildly from what already exists if we’re planning on swapping functionality later. Agreed on the rest.
@instagibbs Note that this is about a separate addition I made, which compares the behaviour with a pure floating-point simulation. The comparison with CFeeRate is elsewhere.
instagibbs
commented at 8:15 pm on February 10, 2025:
oh right, I conflated the two threads here
l0rinc approved
l0rinc
commented at 7:47 pm on February 10, 2025:
contributor
ACKcf00540f54302e37f8af08f15fce16cbcab0f8c9
Added approximately floating point comparisons to fuzz tests and removed the lingering [[maybe_unused]] in feefrac_tests.cpp
DrahtBot requested review from laanwj
on Feb 10, 2025
sipa
commented at 8:07 pm on February 10, 2025:
member
@instagibbs I incorporated a variant of your commit into the existing feefrac_mul_div fuzz test, with the tightest bounds I could make work.
DrahtBot removed the label
CI failed
on Feb 10, 2025
glozow removed this from the milestone 29.0
on Feb 13, 2025
ryanofsky
commented at 2:34 pm on April 1, 2025:
contributor
PR may be ready for merge if @ismaelsadeeq and @laanwj want to re-ack or others want to ACK
ismaelsadeeq
commented at 11:47 am on April 2, 2025:
member
I will review soon.
in
src/test/fuzz/feefrac.cpp:36
in
c71afe6a04outdated
ismaelsadeeq
commented at 1:53 pm on April 7, 2025:
in “feefrac: add helper functions for 96-bit division” c71afe6a041e557b403159d0a974965a06b6fc43
can be a util function since exact same thing is repeated twice.
87@@ -85,13 +88,14 @@ struct FeeFrac
88 * version relying on __int128.
89 *
90 * The result must fit in an int64_t, and d must be strictly positive. */
91- static inline int64_t Div(__int128 n, int32_t d) noexcept
92+ static inline int64_t Div(__int128 n, int32_t d, bool round_down) noexcept
ismaelsadeeq
commented at 1:59 pm on April 7, 2025:
In “feefrac: support both rounding up and down for Evaluate” 486e816bd7d68f4411b35330907ce42812c5c71b
Div method description needs to be updated we round toward positive infinity when round down is false.
I just tried things until the tests pass. As pointed out elsewhere, I don’t think the exact accuracy promises are all that relevant - the point is convincing a reviewer (who isn’t convinced by the other tests) that the result is never going to be hugely off.
ismaelsadeeq
commented at 2:39 pm on April 7, 2025:
member
I have reviewed each commit it looks good, my comments below are not serious just a question on last commit and some suggestions that improve doc, making fuzz test dry and improving commit message.
DrahtBot requested review from ryanofsky
on Apr 7, 2025
arith_uint256: modernize comparison operators
Since C++20, operator!= is implicitly defaulted using operator==, and
operator<, operator<=, operator>, and operator>= are defaulted using
operator<=>, so it suffices to just provide these two.
46ff4220bf
feefrac fuzz: use arith_uint256 instead of ad-hoc multiply
Rather than use an ad-hoc reimplementation of wide multiplication inside the
fuzz test, reuse arith_uint256, which already has this. It's larger than what we
need here, but performance isn't a concern in this test, and it does what we need.
fcfe008db2
feefrac: rework comments around Mul/MulFallback800c0dea9a
feefrac: add helper functions for 96-bit division
These functions are needed to implement FeeFrac evaluation later: given a
FeeFrac{fee, size}, its fee at at_size is (fee * at_size / size).
7963aecead
feefrac: add support for evaluating at given sizeecf956ec9d
feefrac: support both rounding up and down for Evaluate
Co-Authored-By: l0rinc <pap.lorinc@gmail.com>
0c6bcfd8f7
fuzz: assert min diff between FeeFrac and CFeeRate
l0rinc
commented at 3:18 pm on April 7, 2025:
contributor
ACK58914ab459c46c518c47c5082aec25ac0d03ab11
Rebased, changing mostly Span to std::span - and a minor comment update.
0diff --git a/src/util/feefrac.h b/src/util/feefrac.h
1--- a/src/util/feefrac.h(revision a9f419ef8aa2d518de1ad87603b82248bf88f864)
2+++ b/src/util/feefrac.h(date 1744038722170)
3@@ -84,7 +84,8 @@
4 return __int128{a} * b;
5 }
6 7- /** Helper function for 96/32 signed division, rounding towards negative infinity. This is a
8+ /** Helper function for 96/32 signed division, rounding towards negative infinity (if
9+ * round_down), or towards positive infinity (if !round_down). This is a
10 * version relying on __int128.
11 *
12 * The result must fit in an int64_t, and d must be strictly positive. */
DrahtBot requested review from ismaelsadeeq
on Apr 7, 2025
ismaelsadeeq
commented at 3:39 pm on April 7, 2025:
member
reACK58914ab459c46c518c47c5082aec25ac0d03ab11
in
src/util/feefrac.h:193
in
58914ab459
186@@ -144,6 +187,39 @@ struct FeeFrac
187 std::swap(a.fee, b.fee);
188 std::swap(a.size, b.size);
189 }
190+
191+ /** Compute the fee for a given size `at_size` using this object's feerate.
192+ *
193+ * This effectively corresponds to evaluating (this->fee * at_size) / this->size, with the
yancyribbens
commented at 7:39 pm on April 7, 2025:
Wouldn’t it save some confusion if there was a type for WU and a type for vbytes? If for example a FeeFrac is created as {sats /vbytes} then one wouldn’t want to accidentally pass an argument calculated using a wu metric for at_size param (possibly). In that case one would want to div by 4 first to get corresponding vbytes metric, however if there where strong types, then it could be converted automagically.
See the FeePerVSize and FeePerWeight types below, which are FeeFrac wrappers that provide some basic type-safety.
I don’t think going as far as having separate types for weights/vsize itself is realistic, given how much they’re used in the codebase already (and in any case, this is unrelated to this PR).
yancyribbens
commented at 8:09 pm on April 7, 2025:
See the FeePerVSize and FeePerWeight types below, which are FeeFrac wrappers that provide some basic type-safety.
Thanks, I didn’t notice the wrappers. Maybe they would enhance some of the tests if they where incorporated.
I don’t think going as far as having separate types for weights/vsize itself is realistic, given how much they’re used in the codebase already (and in any case, this is unrelated to this PR).
Personally I’ve wished for these types when working in the wallet coin-selection test suit for example. Although, this discussion can be saved for elsewhere though since it’s not strictly on topic.
glozow
commented at 9:28 pm on April 7, 2025:
member
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: 2025-07-19 06:12 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me