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