86template<
typename SetType>
87class SimpleCandidateFinder
97 m_depgraph(depgraph), m_todo{depgraph.
Positions()} {}
100 void MarkDone(SetType select)
noexcept { m_todo -= select; }
103 bool AllDone() const noexcept {
return m_todo.None(); }
113 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations)
const noexcept
115 uint64_t iterations_left = max_iterations;
119 std::vector<std::pair<SetType, SetType>> queue;
121 queue.emplace_back(SetType{}, m_todo);
126 while (!queue.empty() && iterations_left) {
128 auto [inc, und] = queue.back();
131 bool inc_none = inc.None();
132 for (
auto split : und) {
140 queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
144 if (new_inc.feerate > best.feerate) best = new_inc;
149 return {std::move(best), max_iterations - iterations_left};
158template<
typename SetType>
159class ExhaustiveCandidateFinder
169 m_depgraph(depgraph), m_todo{depgraph.
Positions()} {}
172 void MarkDone(SetType select)
noexcept { m_todo -= select; }
175 bool AllDone() const noexcept {
return m_todo.None(); }
186 uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
188 for (uint64_t x = 1; x < limit; ++x) {
193 for (
auto i : m_todo) {
194 if (x_shifted & 1) txn |= m_depgraph.
Ancestors(i);
197 SetInfo cur(m_depgraph, txn & m_todo);
198 if (cur.feerate > best.feerate) best = cur;
210template<
typename SetType>
211std::pair<std::vector<DepGraphIndex>,
bool> SimpleLinearize(
const DepGraph<SetType>& depgraph, uint64_t max_iterations)
213 std::vector<DepGraphIndex> linearization;
214 SimpleCandidateFinder finder(depgraph);
218 auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
219 if (iterations_done == max_iterations) optimal =
false;
220 depgraph.
AppendTopo(linearization, candidate.transactions);
221 todo -= candidate.transactions;
222 finder.MarkDone(candidate.transactions);
223 max_iterations -= iterations_done;
225 return {std::move(linearization), optimal};
235template<
typename SetType>
239 std::vector<DepGraphIndex> linearization;
240 std::vector<FeeFrac> chunking;
242 std::vector<DepGraphIndex> perm_linearization;
249 TestBitSet perm_done;
250 while (topo_length < perm_linearization.size()) {
251 auto i = perm_linearization[topo_length];
253 if (!depgraph.
Ancestors(i).IsSubsetOf(perm_done))
break;
256 if (topo_length == perm_linearization.size()) {
263 if (linearization.empty() || cmp > 0 || (cmp == 0 && perm_chunking.size() > chunking.size())) {
264 linearization = perm_linearization;
265 chunking = perm_chunking;
270 auto first_non_topo = perm_linearization.begin() + topo_length;
271 assert(std::is_sorted(first_non_topo + 1, perm_linearization.end()));
272 std::reverse(first_non_topo + 1, perm_linearization.end());
274 }
while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
276 return linearization;
291 depgraph.
AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
298template<
typename SetType>
306 }
catch(
const std::ios_base::failure&) {}
307 if (mask != uint64_t(-1)) mask += non_empty;
310 for (
auto i : todo) {
321 if (non_empty &&
ret.None()) {
333 std::vector<DepGraphIndex> linearization;
338 TestBitSet potential_next;
339 for (
auto j : todo) {
340 if ((depgraph.
Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
341 potential_next.Set(j);
345 assert(potential_next.Any());
350 }
catch (
const std::ios_base::failure&) {}
351 idx %= potential_next.Count();
353 for (
auto j : potential_next) {
356 linearization.push_back(j);
364 return linearization;
379 std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
384 auto idx_fn = [&]() {
387 if (!sim[i].has_value())
continue;
388 if (offset == 0)
return i;
396 auto subset_fn = [&]() {
397 auto range = (uint64_t{1} << num_tx_sim) - 1;
399 auto mask_shifted = mask;
402 if (!sim[i].has_value())
continue;
403 if (mask_shifted & 1) {
408 assert(mask_shifted == 0);
413 auto set_fn = [&]() {
414 auto range = (uint64_t{1} << sim.size()) - 1;
418 if ((mask >> i) & 1) {
426 auto anc_update_fn = [&]() {
430 if (!sim[chl].has_value())
continue;
431 for (
auto par : sim[chl]->second) {
432 if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
433 sim[chl]->second |= sim[par]->second;
446 if (sim[i].has_value()) {
461 if (num_tx_sim < TestBitSet::Size() &&
command-- == 0) {
469 assert(!sim[idx].has_value());
471 if (!sim[i].has_value()) {
477 sim[idx] = {feerate, TestBitSet::Singleton(idx)};
480 }
else if (num_tx_sim > 0 &&
command-- == 0) {
483 auto parents = subset_fn();
487 sim[child]->second |= parents;
489 }
else if (num_tx_sim > 0 &&
command-- == 0) {
496 for (
auto i : del) check_fn(i);
501 if (sim[i].has_value()) {
504 sim[i] = std::nullopt;
506 sim[i]->second -= del;
516 assert(real.
PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
540 reader >> Using<DepGraphFormatter>(depgraph) >>
VARINT(par_code) >>
VARINT(chl_code);
541 }
catch (
const std::ios_base::failure&) {}
542 SanityCheck(depgraph);
548 if (depgraph.
TxCount() < 2)
return;
551 par_code %= depgraph.
TxCount();
560 auto ancestors = depgraph.
Ancestors(par) - TestBitSet::Singleton(par);
561 if (ancestors.None())
return;
562 chl_code %= ancestors.Count();
563 for (
auto i : ancestors) {
583 std::vector<DepGraphIndex> linearization;
585 reader >> Using<DepGraphFormatter>(depgraph);
586 }
catch (
const std::ios_base::failure&) {}
591 std::optional<DepGraphIndex> picked;
593 uint64_t picked_num{0};
595 reader >>
VARINT(picked_num);
596 }
catch (
const std::ios_base::failure&) {}
597 if (picked_num < todo.Size() && todo[picked_num]) {
607 assert(component.IsSubsetOf(todo));
611 if (picked)
assert(component[*picked]);
623 for (
auto i : component) {
629 for (
auto i : component) {
631 TestBitSet reachable = TestBitSet::Singleton(i);
634 TestBitSet new_reachable = reachable;
635 for (
auto j : new_reachable) {
636 new_reachable |= depgraph.
Ancestors(j) & todo;
639 if (new_reachable == reachable)
break;
640 reachable = new_reachable;
643 assert(component == reachable);
647 uint64_t subset_bits{0};
649 reader >>
VARINT(subset_bits);
650 }
catch (
const std::ios_base::failure&) {}
654 if (subset_bits & 1) subset.Set(i);
659 if (subset.None()) subset = TestBitSet::Singleton(todo.First());
675 reader >> Using<DepGraphFormatter>(depgraph);
676 }
catch (
const std::ios_base::failure&) {}
677 MakeConnected(depgraph);
678 SanityCheck(depgraph);
690 reader >> Using<DepGraphFormatter>(depgraph);
691 }
catch (
const std::ios_base::failure&) {}
694 auto linearization = ReadLinearization(depgraph, reader);
700 for (
size_t i = 1; i < chunking.size(); ++i) {
701 assert(!(chunking[i] >> chunking[i - 1]));
706 for (
const auto& chunk_feerate : chunking) {
711 accumulator.
Set(depgraph, idx);
732 reader >> Using<DepGraphFormatter>(depgraph);
733 }
catch (
const std::ios_base::failure&) {}
743 assert(best_anc.transactions.Any());
744 assert(best_anc.transactions.IsSubsetOf(todo));
745 assert(depgraph.
FeeRate(best_anc.transactions) == best_anc.feerate);
748 for (
auto i : best_anc.transactions) {
749 assert((depgraph.
Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
753 std::optional<SetInfo<TestBitSet>> real_best_anc;
754 for (
auto i : todo) {
756 if (!real_best_anc.has_value() || info.
feerate > real_best_anc->feerate) {
757 real_best_anc = info;
761 assert(real_best_anc.has_value());
762 assert(*real_best_anc == best_anc);
767 auto del_set = ReadTopologicalSet(depgraph, todo, reader,
true);
791 reader >> Using<DepGraphFormatter>(depgraph);
792 }
catch (
const std::ios_base::failure&) {}
796 SimpleCandidateFinder smp_finder(depgraph);
797 ExhaustiveCandidateFinder exh_finder(depgraph);
802 assert(!smp_finder.AllDone());
803 assert(!exh_finder.AllDone());
813 assert(found.transactions.Any());
814 assert(found.transactions.IsSubsetOf(todo));
815 assert(depgraph.
FeeRate(found.transactions) == found.feerate);
817 for (
auto i : found.transactions) {
824 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
834 assert(anc.feerate <= found.feerate);
836 if (todo.Count() <= 12) {
839 auto exhaustive = exh_finder.FindCandidateSet();
840 assert(exhaustive.feerate == found.feerate);
845 auto read_topo = ReadTopologicalSet(depgraph, todo, reader,
true);
852 auto del_set = ReadTopologicalSet(depgraph, todo, reader,
true);
854 smp_finder.MarkDone(del_set);
855 exh_finder.MarkDone(del_set);
859 assert(smp_finder.AllDone());
860 assert(exh_finder.AllDone());
874 uint64_t rng_seed{0};
875 uint8_t make_connected{1};
877 reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
878 }
catch (
const std::ios_base::failure&) {}
881 if (make_connected) MakeConnected(depgraph);
885 SimpleCandidateFinder smp_finder(depgraph);
891 assert(!smp_finder.AllDone());
896 uint64_t max_iterations = 1;
898 reader >>
VARINT(max_iterations);
899 }
catch (
const std::ios_base::failure&) {}
900 max_iterations &= 0xfffff;
903 auto init_set = ReadTopologicalSet(depgraph, todo, reader,
false);
904 SetInfo init_best(depgraph, init_set);
907 auto [found, iterations_done] = src_finder.
FindCandidateSet(max_iterations, init_best);
908 bool optimal = iterations_done < max_iterations;
911 assert(iterations_done <= max_iterations);
912 assert(found.transactions.Any());
913 assert(found.transactions.IsSubsetOf(todo));
914 assert(depgraph.
FeeRate(found.transactions) == found.feerate);
917 for (
auto i : found.transactions) {
925 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
929 if (iterations_done >= 1 && todo.Count() <= 63) {
930 Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
940 assert(found.feerate >= simple.feerate);
942 assert(found.feerate == simple.feerate);
947 assert(found.feerate >= anc.feerate);
951 auto read_topo = ReadTopologicalSet(depgraph, todo, reader,
true);
958 auto del_set = ReadTopologicalSet(depgraph, todo, reader,
true);
961 smp_finder.MarkDone(del_set);
966 assert(smp_finder.AllDone());
979 reader >> Using<DepGraphFormatter>(depgraph);
980 }
catch (
const std::ios_base::failure&) {}
985 auto subset =
SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader,
false));
988 auto linearization = ReadLinearization(depgraph, reader);
999 std::vector<DepGraphIndex> linearization_left;
1000 for (
auto i : linearization) {
1001 if (todo[i]) linearization_left.push_back(i);
1014 TestBitSet combined;
1016 const auto& chunk_info = chunking.
GetChunk(i);
1018 assert(chunk_info.transactions.Any());
1020 if (i > 0)
assert(!(chunk_info.feerate >> chunking.
GetChunk(i - 1).feerate));
1022 assert(chunk_info.transactions.IsSubsetOf(todo));
1024 assert(depgraph.
FeeRate(chunk_info.transactions) == chunk_info.feerate);
1027 for (
auto j : linearization) {
1028 if (todo[j] && !combined[j]) {
1029 accumulator.
Set(depgraph, j);
1038 assert(!chunk_info.transactions.Overlaps(combined));
1039 combined |= chunk_info.transactions;
1041 for (
auto idx : chunk_info.transactions) {
1045 assert(combined == todo);
1052 TestBitSet intersect_anc;
1053 for (
auto idx : intersect.transactions) {
1054 intersect_anc |= (depgraph.
Ancestors(idx) & todo);
1056 assert(intersect.transactions == intersect_anc);
1058 assert(intersect.feerate == depgraph.
FeeRate(intersect.transactions));
1060 assert(intersect.transactions.Any() == subset.transactions.Any());
1062 assert(intersect.feerate >= subset.feerate);
1068 auto reintersect =
SetInfo(depgraph,
prefix & intersect.transactions);
1069 if (!reintersect.feerate.IsEmpty()) {
1070 assert(reintersect.feerate <= intersect.feerate);
1077 auto done = ReadTopologicalSet(depgraph, todo, reader,
true);
1080 subset =
SetInfo(depgraph, subset.transactions - done);
1094 uint64_t iter_count{0};
1097 reader >>
VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph);
1098 }
catch (
const std::ios_base::failure&) {}
1102 auto [linearization, optimal] = SimpleLinearize(depgraph, iter_count);
1103 SanityCheck(depgraph, linearization);
1109 const uint64_t n = depgraph.
TxCount();
1110 if (n <= 63 && (iter_count >> n)) {
1116 if (optimal && depgraph.
TxCount() <= 8) {
1117 auto exh_linearization = ExhaustiveLinearize(depgraph);
1121 assert(simple_chunking.size() == exh_chunking.size());
1126 auto read = ReadLinearization(depgraph, reader);
1141 uint64_t rng_seed{0};
1142 uint64_t iter_count{0};
1143 uint8_t make_connected{1};
1145 reader >>
VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
1146 }
catch (
const std::ios_base::failure&) {}
1149 if (make_connected) MakeConnected(depgraph);
1152 std::vector<DepGraphIndex> old_linearization;
1154 uint8_t have_old_linearization{0};
1156 reader >> have_old_linearization;
1157 }
catch(
const std::ios_base::failure&) {}
1158 if (have_old_linearization & 1) {
1159 old_linearization = ReadLinearization(depgraph, reader);
1160 SanityCheck(depgraph, old_linearization);
1165 iter_count &= 0x7ffff;
1166 auto [linearization, optimal, cost] =
Linearize(depgraph, iter_count, rng_seed, old_linearization);
1167 assert(cost <= iter_count);
1168 SanityCheck(depgraph, linearization);
1172 if (!old_linearization.empty()) {
1179 if (iter_count >= MaxOptimalLinearizationIters(depgraph.
TxCount())) {
1187 SanityCheck(depgraph, simple_linearization);
1193 if (simple_optimal)
assert(cmp == 0);
1196 if (cmp == 0)
assert(chunking.size() >= simple_chunking.size());
1199 auto read = ReadLinearization(depgraph, reader);
1214 reader >> Using<DepGraphFormatter>(depgraph);
1215 }
catch (
const std::ios_base::failure&) {}
1218 std::vector<DepGraphIndex> linearization;
1219 linearization = ReadLinearization(depgraph, reader);
1220 SanityCheck(depgraph, linearization);
1223 auto post_linearization = linearization;
1225 SanityCheck(depgraph, post_linearization);
1234 auto post_post_linearization = post_linearization;
1236 SanityCheck(depgraph, post_post_linearization);
1256 uint64_t rng_seed{0};
1258 uint8_t direction{0};
1260 reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
1261 }
catch (
const std::ios_base::failure&) {}
1277 if (direction & 1) {
1280 if (children.Any()) {
1281 depgraph_tree.
AddDependencies(TestBitSet::Singleton(i), children.First());
1287 if (parents.Any()) {
1288 depgraph_tree.
AddDependencies(TestBitSet::Singleton(parents.First()), i);
1294 std::vector<DepGraphIndex> linearization;
1295 linearization = ReadLinearization(depgraph_tree, reader);
1296 SanityCheck(depgraph_tree, linearization);
1299 auto post_linearization = linearization;
1301 SanityCheck(depgraph_tree, post_linearization);
1311 auto post_post_linearization = post_linearization;
1313 SanityCheck(depgraph_tree, post_linearization);
1314 auto post_post_chunking =
ChunkLinearization(depgraph_tree, post_post_linearization);
1315 auto cmp_post =
CompareChunks(post_post_chunking, post_chunking);
1320 auto [opt_linearization, _optimal, _cost] =
Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1339 uint64_t fee_inc_code;
1340 reader >> Using<DepGraphFormatter>(depgraph) >>
VARINT(fee_inc_code);
1341 fee_inc = fee_inc_code & 0x3ffff;
1342 }
catch (
const std::ios_base::failure&) {}
1343 if (depgraph.
TxCount() == 0)
return;
1346 auto lin = ReadLinearization(depgraph, reader);
1347 auto lin_leaf = ReadLinearization(depgraph, reader);
1351 std::vector<DepGraphIndex> lin_moved;
1352 for (
auto i : lin) {
1353 if (i != lin_leaf.back()) lin_moved.push_back(i);
1355 lin_moved.push_back(lin_leaf.back());
1359 SanityCheck(depgraph, lin_moved);
1363 depgraph.
FeeRate(lin_leaf.back()).
fee += fee_inc;
1375 reader >> Using<DepGraphFormatter>(depgraph);
1376 }
catch (
const std::ios_base::failure&) {}
1379 auto lin1 = ReadLinearization(depgraph, reader);
1380 auto lin2 = ReadLinearization(depgraph, reader);
1403 reader >> Using<DepGraphFormatter>(depgraph);
1404 }
catch (
const std::ios_base::failure&) {}
1407 std::vector<DepGraphIndex> linearization;
1410 while (todo.Any()) {
1415 }
catch (
const std::ios_base::failure&) {}
1416 val %= todo.Count();
1418 for (
auto idx : todo) {
1420 linearization.push_back(idx);
1432 size_t topo_prefix = 0;
1434 while (topo_prefix < linearization.size()) {
1437 if (todo.Overlaps(depgraph.
Ancestors(idx)))
break;
1442 auto linearization_fixed = linearization;
1445 SanityCheck(depgraph, linearization_fixed);
1448 assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1449 linearization_fixed.begin()));
1452 if (topo_prefix == linearization.size()) {
1453 assert(linearization == linearization_fixed);
#define Assume(val)
Assume is the identity function.
T ConsumeIntegralInRange(T min, T max)
Minimal stream for reading from an existing byte array by std::span.
Class encapsulating the state needed to find the best remaining ancestor set.
void MarkDone(SetType select) noexcept
Remove a set of transactions from the set of to-be-linearized ones.
DepGraphIndex NumRemaining() const noexcept
Count the number of remaining unlinearized transactions.
SetInfo< SetType > FindCandidateSet() const noexcept
Find the best (highest-feerate, smallest among those in case of a tie) ancestor set among the remaini...
bool AllDone() const noexcept
Check whether any unlinearized transactions remain.
Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,...
const SetType & Ancestors(DepGraphIndex i) const noexcept
Get the ancestors of a given transaction i.
SetType GetReducedChildren(DepGraphIndex i) const noexcept
Compute the (reduced) set of children of node i in this graph.
SetType GetReducedParents(DepGraphIndex i) const noexcept
Compute the (reduced) set of parents of node i in this graph.
void AppendTopo(std::vector< DepGraphIndex > &list, const SetType &select) const noexcept
Append the entries of select to list in a topologically valid order.
const FeeFrac & FeeRate(DepGraphIndex i) const noexcept
Get the feerate of a given transaction i.
SetType GetConnectedComponent(const SetType &todo, DepGraphIndex tx) const noexcept
Get the connected component within the subset "todo" that contains tx (which must be in todo).
bool IsConnected(const SetType &subset) const noexcept
Determine if a subset is connected.
DepGraphIndex PositionRange() const noexcept
Get the range of positions in this DepGraph.
SetType FindConnectedComponent(const SetType &todo) const noexcept
Find some connected component within the subset "todo" of this graph.
DepGraphIndex AddTransaction(const FeeFrac &feefrac) noexcept
Add a new unconnected transaction to this transaction graph (in the first available position),...
void RemoveTransactions(const SetType &del) noexcept
Remove the specified positions from this DepGraph.
auto TxCount() const noexcept
Get the number of transactions in the graph.
const SetType & Descendants(DepGraphIndex i) const noexcept
Get the descendants of a given transaction i.
size_t DynamicMemoryUsage() const noexcept
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
void Compact() noexcept
Reduce memory usage if possible.
void AddDependencies(const SetType &parents, DepGraphIndex child) noexcept
Modify this transaction graph, adding multiple parents to a specified child.
bool IsAcyclic() const noexcept
Check if this graph is acyclic.
Data structure encapsulating the chunking of a linearization, permitting removal of subsets.
DepGraphIndex NumChunksLeft() const noexcept
Determine how many chunks remain in the linearization.
const SetInfo< SetType > & GetChunk(DepGraphIndex n) const noexcept
Access a chunk.
SetInfo< SetType > IntersectPrefixes(const SetInfo< SetType > &subset) const noexcept
Find the shortest intersection between subset and the prefixes of remaining chunks of the linearizati...
void MarkDone(SetType subset) noexcept
Remove some subset of transactions from the linearization.
Class encapsulating the state needed to perform search for good candidate sets.
bool AllDone() const noexcept
Check whether any unlinearized transactions remain.
void MarkDone(const SetType &done) noexcept
Remove a subset of transactions from the cluster being linearized.
std::pair< SetInfo< SetType >, uint64_t > FindCandidateSet(uint64_t max_iterations, SetInfo< SetType > best) noexcept
Find a high-feerate topologically-valid subset of what remains of the cluster.
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
std::vector< FeeFrac > ChunkLinearization(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > linearization) noexcept
Compute the feerates of the chunks of linearization.
std::tuple< std::vector< DepGraphIndex >, bool, uint64_t > Linearize(const DepGraph< SetType > &depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span< const DepGraphIndex > old_linearization={}) noexcept
Find or improve a linearization for a cluster.
void FixLinearization(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization) noexcept
Make linearization topological, retaining its ordering where possible.
std::vector< DepGraphIndex > MergeLinearizations(const DepGraph< SetType > &depgraph, std::span< const DepGraphIndex > lin1, std::span< const DepGraphIndex > lin2)
Merge two linearizations for the same cluster into one that is as good as both.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
void PostLinearize(const DepGraph< SetType > &depgraph, std::span< DepGraphIndex > linearization)
Improve a given linearization.
static std::vector< std::string > split(const std::string &str, const std::string &delims=" \t")
Data structure storing a fee and size, ordered by increasing fee/size.
bool IsEmpty() const noexcept
Check if this is empty (size and fee are 0).
A set of transactions together with their aggregate feerate.
FeeFrac feerate
Their combined fee and size.
void Set(const DepGraph< SetType > &depgraph, DepGraphIndex pos) noexcept
Add a transaction to this SetInfo (which must not yet be in it).
SetType transactions
The transactions in the set.
FUZZ_TARGET(clusterlin_depgraph_sim)
static constexpr auto MAX_SIMPLE_ITERATIONS
std::partial_ordering CompareChunks(std::span< const FeeFrac > chunks0, std::span< const FeeFrac > chunks1)
Compare the feerate diagrams implied by the provided sorted chunks data.