29template<
typename SetType>
30class SimpleCandidateFinder
40 m_depgraph(depgraph), m_todo{depgraph.
Positions()} {}
43 void MarkDone(SetType select)
noexcept { m_todo -= select; }
46 bool AllDone() const noexcept {
return m_todo.None(); }
54 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations)
const noexcept
56 uint64_t iterations_left = max_iterations;
60 std::vector<std::pair<SetType, SetType>> queue;
62 queue.emplace_back(SetType{}, m_todo);
64 SetInfo best(m_depgraph, m_todo);
66 while (!queue.empty() && iterations_left) {
69 auto [inc, und] = queue.back();
72 bool inc_none = inc.None();
73 for (
auto split : und) {
80 queue.emplace_back(new_inc.transactions, und - new_inc.transactions);
84 if (new_inc.feerate > best.feerate) best = new_inc;
89 return {std::move(best), max_iterations - iterations_left};
99template<
typename SetType>
100class ExhaustiveCandidateFinder
110 m_depgraph(depgraph), m_todo{depgraph.
Positions()} {}
113 void MarkDone(SetType select)
noexcept { m_todo -= select; }
116 bool AllDone() const noexcept {
return m_todo.None(); }
127 uint64_t limit = (uint64_t{1} << m_todo.Count()) - 1;
129 for (uint64_t x = 1; x < limit; ++x) {
134 for (
auto i : m_todo) {
135 if (x_shifted & 1) txn |= m_depgraph.
Ancestors(i);
138 SetInfo cur(m_depgraph, txn & m_todo);
139 if (cur.feerate > best.feerate) best = cur;
151template<
typename SetType>
152std::pair<std::vector<DepGraphIndex>,
bool> SimpleLinearize(
const DepGraph<SetType>& depgraph, uint64_t max_iterations)
154 std::vector<DepGraphIndex> linearization;
155 SimpleCandidateFinder finder(depgraph);
159 auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations);
160 if (iterations_done == max_iterations) optimal =
false;
161 depgraph.
AppendTopo(linearization, candidate.transactions);
162 todo -= candidate.transactions;
163 finder.MarkDone(candidate.transactions);
164 max_iterations -= iterations_done;
166 return {std::move(linearization), optimal};
180 depgraph.
AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
187template<
typename SetType>
193 }
catch(
const std::ios_base::failure&) {}
195 for (
auto i : todo) {
208 std::vector<DepGraphIndex> linearization;
213 TestBitSet potential_next;
214 for (
auto j : todo) {
215 if ((depgraph.
Ancestors(j) & todo) == TestBitSet::Singleton(j)) {
216 potential_next.Set(j);
220 assert(potential_next.Any());
225 }
catch (
const std::ios_base::failure&) {}
226 idx %= potential_next.Count();
228 for (
auto j : potential_next) {
231 linearization.push_back(j);
239 return linearization;
254 std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim;
259 auto idx_fn = [&]() {
262 if (!sim[i].has_value())
continue;
263 if (offset == 0)
return i;
271 auto subset_fn = [&]() {
272 auto range = (uint64_t{1} << num_tx_sim) - 1;
274 auto mask_shifted = mask;
277 if (!sim[i].has_value())
continue;
278 if (mask_shifted & 1) {
283 assert(mask_shifted == 0);
288 auto set_fn = [&]() {
289 auto range = (uint64_t{1} << sim.size()) - 1;
293 if ((mask >> i) & 1) {
301 auto anc_update_fn = [&]() {
305 if (!sim[chl].has_value())
continue;
306 for (
auto par : sim[chl]->second) {
307 if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) {
308 sim[chl]->second |= sim[par]->second;
321 if (sim[i].has_value()) {
332 if (num_tx_sim == 0 || ((
command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) {
340 assert(!sim[idx].has_value());
342 if (!sim[i].has_value()) {
348 sim[idx] = {feerate, TestBitSet::Singleton(idx)};
352 if ((
command % 3) <= 1 && num_tx_sim > 0) {
355 auto parents = subset_fn();
359 sim[child]->second |= parents;
362 if (num_tx_sim > 0) {
369 for (
auto i : del) check_fn(i);
374 if (sim[i].has_value()) {
377 sim[i] = std::nullopt;
379 sim[i]->second -= del;
406 reader >> Using<DepGraphFormatter>(depgraph) >>
VARINT(par_code) >>
VARINT(chl_code);
407 }
catch (
const std::ios_base::failure&) {}
408 SanityCheck(depgraph);
414 if (depgraph.
TxCount() < 2)
return;
417 par_code %= depgraph.
TxCount();
426 auto ancestors = depgraph.
Ancestors(par) - TestBitSet::Singleton(par);
427 if (ancestors.None())
return;
428 chl_code %= ancestors.Count();
429 for (
auto i : ancestors) {
449 std::vector<DepGraphIndex> linearization;
451 reader >> Using<DepGraphFormatter>(depgraph);
452 }
catch (
const std::ios_base::failure&) {}
457 std::optional<DepGraphIndex> picked;
459 uint64_t picked_num{0};
461 reader >>
VARINT(picked_num);
462 }
catch (
const std::ios_base::failure&) {}
463 if (picked_num < todo.Size() && todo[picked_num]) {
473 assert(component.IsSubsetOf(todo));
477 if (picked)
assert(component[*picked]);
489 for (
auto i : component) {
495 for (
auto i : component) {
497 TestBitSet reachable = TestBitSet::Singleton(i);
500 TestBitSet new_reachable = reachable;
501 for (
auto j : new_reachable) {
502 new_reachable |= depgraph.
Ancestors(j) & todo;
505 if (new_reachable == reachable)
break;
506 reachable = new_reachable;
509 assert(component == reachable);
513 uint64_t subset_bits{0};
515 reader >>
VARINT(subset_bits);
516 }
catch (
const std::ios_base::failure&) {}
520 if (subset_bits & 1) subset.Set(i);
525 if (subset.None()) subset = TestBitSet::Singleton(todo.First());
541 reader >> Using<DepGraphFormatter>(depgraph);
542 }
catch (
const std::ios_base::failure&) {}
543 MakeConnected(depgraph);
544 SanityCheck(depgraph);
556 reader >> Using<DepGraphFormatter>(depgraph);
557 }
catch (
const std::ios_base::failure&) {}
560 auto linearization = ReadLinearization(depgraph, reader);
566 for (
size_t i = 1; i < chunking.size(); ++i) {
567 assert(!(chunking[i] >> chunking[i - 1]));
572 for (
const auto& chunk_feerate : chunking) {
577 accumulator.
Set(depgraph, idx);
598 reader >> Using<DepGraphFormatter>(depgraph);
599 }
catch (
const std::ios_base::failure&) {}
609 assert(best_anc.transactions.Any());
610 assert(best_anc.transactions.IsSubsetOf(todo));
611 assert(depgraph.
FeeRate(best_anc.transactions) == best_anc.feerate);
614 for (
auto i : best_anc.transactions) {
615 assert((depgraph.
Ancestors(i) & todo).IsSubsetOf(best_anc.transactions));
619 std::optional<SetInfo<TestBitSet>> real_best_anc;
620 for (
auto i : todo) {
622 if (!real_best_anc.has_value() || info.
feerate > real_best_anc->feerate) {
623 real_best_anc = info;
627 assert(real_best_anc.has_value());
628 assert(*real_best_anc == best_anc);
631 auto del_set = ReadTopologicalSet(depgraph, todo, reader);
633 if (del_set.None()) del_set = best_anc.transactions;
652 uint64_t rng_seed{0};
653 uint8_t make_connected{1};
655 reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
656 }
catch (
const std::ios_base::failure&) {}
659 if (make_connected) MakeConnected(depgraph);
663 SimpleCandidateFinder smp_finder(depgraph);
664 ExhaustiveCandidateFinder exh_finder(depgraph);
670 assert(!smp_finder.AllDone());
671 assert(!exh_finder.AllDone());
676 uint64_t max_iterations = 1;
678 reader >>
VARINT(max_iterations);
679 }
catch (
const std::ios_base::failure&) {}
680 max_iterations &= 0xfffff;
683 SetInfo init_best(depgraph, ReadTopologicalSet(depgraph, todo, reader));
686 auto [found, iterations_done] = src_finder.
FindCandidateSet(max_iterations, init_best);
689 assert(iterations_done <= max_iterations);
690 assert(found.transactions.Any());
691 assert(found.transactions.IsSubsetOf(todo));
692 assert(depgraph.
FeeRate(found.transactions) == found.feerate);
695 for (
auto i : found.transactions) {
703 assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1)));
707 if (iterations_done >= 1 && todo.Count() <= 63) {
708 Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count());
712 if (iterations_done < max_iterations) {
718 assert(found.feerate >= simple.feerate);
720 assert(found.feerate == simple.feerate);
725 assert(found.feerate >= anc.feerate);
729 if (todo.Count() <= 12) {
730 auto exhaustive = exh_finder.FindCandidateSet();
731 assert(exhaustive.feerate == found.feerate);
734 assert(exhaustive.feerate >= simple.feerate);
736 assert(exhaustive.feerate == simple.feerate);
742 auto del_set = ReadTopologicalSet(depgraph, todo, reader);
744 if (del_set.None()) del_set = found.transactions;
747 smp_finder.MarkDone(del_set);
748 exh_finder.MarkDone(del_set);
753 assert(smp_finder.AllDone());
754 assert(exh_finder.AllDone());
767 reader >> Using<DepGraphFormatter>(depgraph);
768 }
catch (
const std::ios_base::failure&) {}
772 auto subset =
SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader));
775 auto linearization = ReadLinearization(depgraph, reader);
786 std::vector<DepGraphIndex> linearization_left;
787 for (
auto i : linearization) {
788 if (todo[i]) linearization_left.push_back(i);
803 const auto& chunk_info = chunking.
GetChunk(i);
805 assert(chunk_info.transactions.Any());
807 if (i > 0)
assert(!(chunk_info.feerate >> chunking.
GetChunk(i - 1).feerate));
809 assert(chunk_info.transactions.IsSubsetOf(todo));
811 assert(depgraph.
FeeRate(chunk_info.transactions) == chunk_info.feerate);
814 for (
auto j : linearization) {
815 if (todo[j] && !combined[j]) {
816 accumulator.
Set(depgraph, j);
825 assert(!chunk_info.transactions.Overlaps(combined));
826 combined |= chunk_info.transactions;
828 for (
auto idx : chunk_info.transactions) {
839 TestBitSet intersect_anc;
840 for (
auto idx : intersect.transactions) {
841 intersect_anc |= (depgraph.
Ancestors(idx) & todo);
843 assert(intersect.transactions == intersect_anc);
845 assert(intersect.feerate == depgraph.
FeeRate(intersect.transactions));
847 assert(intersect.transactions.Any() == subset.transactions.Any());
849 assert(intersect.feerate >= subset.feerate);
855 auto reintersect =
SetInfo(depgraph,
prefix & intersect.transactions);
856 if (!reintersect.feerate.IsEmpty()) {
857 assert(reintersect.feerate <= intersect.feerate);
862 auto done = ReadTopologicalSet(depgraph, todo, reader);
866 done = depgraph.
Ancestors(todo.First()) & todo;
870 subset =
SetInfo(depgraph, subset.transactions - done);
884 uint64_t rng_seed{0};
885 uint64_t iter_count{0};
886 uint8_t make_connected{1};
888 reader >>
VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected;
889 }
catch (
const std::ios_base::failure&) {}
892 if (make_connected) MakeConnected(depgraph);
895 std::vector<DepGraphIndex> old_linearization;
897 uint8_t have_old_linearization{0};
899 reader >> have_old_linearization;
900 }
catch(
const std::ios_base::failure&) {}
901 if (have_old_linearization & 1) {
902 old_linearization = ReadLinearization(depgraph, reader);
903 SanityCheck(depgraph, old_linearization);
908 iter_count &= 0x7ffff;
909 auto [linearization, optimal] =
Linearize(depgraph, iter_count, rng_seed, old_linearization);
910 SanityCheck(depgraph, linearization);
914 if (!old_linearization.empty()) {
923 const uint64_t n = depgraph.
TxCount();
924 if (n <= 19 && iter_count > (uint64_t{1} << n)) {
931 static constexpr uint64_t MAX_OPTIMAL_ITERS[] = {
932 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545,
933 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936,
936 if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) {
944 SanityCheck(depgraph, simple_linearization);
950 if (simple_optimal)
assert(cmp == 0);
954 std::vector<DepGraphIndex> perm_linearization;
959 TestBitSet perm_done;
960 bool perm_is_topo{
true};
961 for (
auto i : perm_linearization) {
963 if (!depgraph.
Ancestors(i).IsSubsetOf(perm_done)) {
964 perm_is_topo =
false;
974 }
while(std::next_permutation(perm_linearization.begin(), perm_linearization.end()));
987 reader >> Using<DepGraphFormatter>(depgraph);
988 }
catch (
const std::ios_base::failure&) {}
991 std::vector<DepGraphIndex> linearization;
992 linearization = ReadLinearization(depgraph, reader);
993 SanityCheck(depgraph, linearization);
996 auto post_linearization = linearization;
998 SanityCheck(depgraph, post_linearization);
1007 auto post_post_linearization = post_linearization;
1009 SanityCheck(depgraph, post_post_linearization);
1029 uint64_t rng_seed{0};
1031 uint8_t direction{0};
1033 reader >> direction >> rng_seed >> Using<DepGraphFormatter>(depgraph_gen);
1034 }
catch (
const std::ios_base::failure&) {}
1050 if (direction & 1) {
1053 if (children.Any()) {
1054 depgraph_tree.
AddDependencies(TestBitSet::Singleton(i), children.First());
1060 if (parents.Any()) {
1061 depgraph_tree.
AddDependencies(TestBitSet::Singleton(parents.First()), i);
1067 std::vector<DepGraphIndex> linearization;
1068 linearization = ReadLinearization(depgraph_tree, reader);
1069 SanityCheck(depgraph_tree, linearization);
1072 auto post_linearization = linearization;
1074 SanityCheck(depgraph_tree, post_linearization);
1084 auto post_post_linearization = post_linearization;
1086 SanityCheck(depgraph_tree, post_linearization);
1087 auto post_post_chunking =
ChunkLinearization(depgraph_tree, post_post_linearization);
1088 auto cmp_post =
CompareChunks(post_post_chunking, post_chunking);
1093 auto [opt_linearization, _optimal] =
Linearize(depgraph_tree, 100000, rng_seed, post_linearization);
1112 uint64_t fee_inc_code;
1113 reader >> Using<DepGraphFormatter>(depgraph) >>
VARINT(fee_inc_code);
1114 fee_inc = fee_inc_code & 0x3ffff;
1115 }
catch (
const std::ios_base::failure&) {}
1116 if (depgraph.
TxCount() == 0)
return;
1119 auto lin = ReadLinearization(depgraph, reader);
1120 auto lin_leaf = ReadLinearization(depgraph, reader);
1124 std::vector<DepGraphIndex> lin_moved;
1125 for (
auto i : lin) {
1126 if (i != lin_leaf.back()) lin_moved.push_back(i);
1128 lin_moved.push_back(lin_leaf.back());
1132 SanityCheck(depgraph, lin_moved);
1136 depgraph.
FeeRate(lin_leaf.back()).
fee += fee_inc;
1148 reader >> Using<DepGraphFormatter>(depgraph);
1149 }
catch (
const std::ios_base::failure&) {}
1152 auto lin1 = ReadLinearization(depgraph, reader);
1153 auto lin2 = ReadLinearization(depgraph, reader);
1176 reader >> Using<DepGraphFormatter>(depgraph);
1177 }
catch (
const std::ios_base::failure&) {}
1180 std::vector<DepGraphIndex> linearization;
1183 while (todo.Any()) {
1188 }
catch (
const std::ios_base::failure&) {}
1189 val %= todo.Count();
1191 for (
auto idx : todo) {
1193 linearization.push_back(idx);
1205 size_t topo_prefix = 0;
1207 while (topo_prefix < linearization.size()) {
1210 if (todo.Overlaps(depgraph.
Ancestors(idx)))
break;
1215 auto linearization_fixed = linearization;
1218 SanityCheck(depgraph, linearization_fixed);
1221 assert(std::equal(linearization.begin(), linearization.begin() + topo_prefix,
1222 linearization_fixed.begin()));
1225 if (topo_prefix == linearization.size()) {
1226 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.
const SetType & Positions() const noexcept
Get the set of transactions positions in use.
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::pair< std::vector< DepGraphIndex >, bool > 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.