40 static constexpr auto MISSING = Pos(-1);
48 std::array<std::shared_ptr<TxGraph::Ref>, MAX_TRANSACTIONS> simmap;
50 std::map<const TxGraph::Ref*, Pos> simrevmap;
52 std::vector<std::shared_ptr<TxGraph::Ref>> removed;
54 std::optional<bool> oversized;
61 uint64_t max_cluster_size;
63 bool real_is_optimal{
false};
66 explicit SimTxGraph(
DepGraphIndex cluster_count, uint64_t cluster_size) :
67 max_cluster_count(cluster_count), max_cluster_size(cluster_size) {}
70 SimTxGraph(
const SimTxGraph&)
noexcept =
default;
71 SimTxGraph& operator=(
const SimTxGraph&)
noexcept =
default;
72 SimTxGraph(SimTxGraph&&) noexcept = default;
73 SimTxGraph& operator=(SimTxGraph&&) noexcept = default;
76 std::vector<SetType> GetComponents()
79 std::vector<SetType>
ret;
83 ret.push_back(component);
93 if (!oversized.has_value()) {
96 for (
auto component : GetComponents()) {
97 if (component.Count() > max_cluster_count) oversized =
true;
98 uint64_t component_size{0};
99 for (
auto i : component) component_size += graph.
FeeRate(i).
size;
100 if (component_size > max_cluster_size) oversized =
true;
127 auto it = simrevmap.find(ref);
128 if (it != simrevmap.end())
return it->second;
137 return simmap[pos].get();
145 real_is_optimal =
false;
146 MakeModified(simpos);
148 simmap[simpos] = std::make_shared<TxGraph::Ref>();
149 auto ptr = simmap[simpos].get();
150 simrevmap[ptr] = simpos;
152 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
159 auto par_pos =
Find(parent);
160 if (par_pos ==
MISSING)
return;
161 auto chl_pos =
Find(child);
162 if (chl_pos ==
MISSING)
return;
164 MakeModified(par_pos);
165 real_is_optimal =
false;
167 if (oversized.has_value() && !*oversized) oversized = std::nullopt;
173 auto pos =
Find(ref);
176 real_is_optimal =
false;
183 auto pos =
Find(ref);
186 real_is_optimal =
false;
188 simrevmap.erase(simmap[pos].get());
191 removed.push_back(std::move(simmap[pos]));
194 if (oversized.has_value() && *oversized) oversized = std::nullopt;
201 void DestroyTransaction(
TxGraph::Ref* ref,
bool reset_oversize)
203 auto pos =
Find(ref);
208 auto remove = std::partition(removed.begin(), removed.end(), [&](
auto& arg) { return arg.get() != ref; });
209 removed.erase(remove, removed.end());
213 real_is_optimal =
false;
214 simrevmap.erase(simmap[pos].get());
217 if (reset_oversize && oversized.has_value() && *oversized) {
218 oversized = std::nullopt;
225 SetType MakeSet(std::span<TxGraph::Ref* const> arg)
229 auto pos =
Find(ptr);
239 auto pos =
Find(arg);
246 void IncludeAncDesc(std::vector<TxGraph::Ref*>& arg,
bool desc)
248 std::vector<TxGraph::Ref*>
ret;
249 for (
auto ptr : arg) {
250 auto simpos =
Find(ptr);
253 ret.push_back(simmap[i].get());
262 for (
auto ptr :
ret) {
263 if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
272 bool MatchesOversizedClusters(
const SetType& set)
274 if (set.Any() && !IsOversized())
return false;
277 if (!set.IsSubsetOf(todo))
return false;
283 bool is_oversized = component.Count() > max_cluster_count;
284 uint64_t component_size{0};
285 for (
auto i : component) component_size += graph.
FeeRate(i).
size;
286 is_oversized |= component_size > max_cluster_size;
288 if (is_oversized != set.Overlaps(component))
return false;
324 auto real =
MakeTxGraph(max_cluster_count, max_cluster_size, acceptable_iters);
325 std::vector<SimTxGraph> sims;
327 sims.emplace_back(max_cluster_count, max_cluster_size);
330 struct BlockBuilderData
333 std::unique_ptr<TxGraph::BlockBuilder> builder;
335 SimTxGraph::SetType included;
337 SimTxGraph::SetType done;
341 BlockBuilderData(std::unique_ptr<TxGraph::BlockBuilder> builder_in) : builder(std::move(builder_in)) {}
345 std::vector<BlockBuilderData> block_builders;
350 size_t tx_count[2] = {sims[0].GetTransactionCount(), 0};
352 size_t choices = tx_count[0] + sims[0].removed.size() + 1;
353 if (sims.size() == 2) {
354 tx_count[1] = sims[1].GetTransactionCount();
355 choices += tx_count[1] + sims[1].removed.size();
360 for (
size_t level = 0; level < sims.size(); ++level) {
361 auto& sim = sims[level];
362 if (choice < tx_count[level]) {
364 for (
auto i : sim.graph.Positions()) {
365 if (choice == 0)
return sim.GetRef(i);
370 choice -= tx_count[level];
372 if (choice < sim.removed.size()) {
374 return sim.removed[choice].get();
376 choice -= sim.removed.size();
386 auto get_diagram_fn = [&](
TxGraph::Level level_select) -> std::vector<FeeFrac> {
388 auto& sim = sims[level];
390 std::set<std::vector<TxGraph::Ref*>> clusters;
391 for (
auto i : sim.graph.Positions()) {
392 auto ref = sim.GetRef(i);
393 clusters.insert(real->GetCluster(*ref, level_select));
397 std::vector<FeeFrac> chunk_feerates;
398 for (
const auto& cluster : clusters) {
399 num_tx += cluster.size();
400 std::vector<SimTxGraph::Pos> linearization;
401 linearization.reserve(cluster.size());
402 for (
auto refptr : cluster) linearization.push_back(sim.Find(refptr));
404 chunk_feerates.push_back(chunk_feerate);
410 assert(num_tx == sim.GetTransactionCount());
413 std::sort(chunk_feerates.begin(), chunk_feerates.end(), std::greater{});
414 return chunk_feerates;
432 int builder_idx = block_builders.empty() ? -1 : int((orig_command & 3) % block_builders.size());
437 auto& top_sim = sims.back();
439 auto& main_sim = sims[0];
444 if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() < SimTxGraph::MAX_TRANSACTIONS &&
command-- == 0) {
460 auto ref = real->AddTransaction(feerate);
462 auto ref_loc = top_sim.AddTransaction(feerate);
464 *ref_loc = std::move(ref);
466 }
else if ((block_builders.empty() || sims.size() > 1) && top_sim.GetTransactionCount() + top_sim.removed.size() > 1 &&
command-- == 0) {
468 auto par = pick_fn();
469 auto chl = pick_fn();
470 auto pos_par = top_sim.Find(par);
471 auto pos_chl = top_sim.Find(chl);
475 if (top_sim.graph.Ancestors(pos_par)[pos_chl])
break;
477 top_sim.AddDependency(par, chl);
478 top_sim.real_is_optimal =
false;
479 real->AddDependency(*par, *chl);
481 }
else if ((block_builders.empty() || sims.size() > 1) && top_sim.removed.size() < 100 &&
command-- == 0) {
485 std::vector<TxGraph::Ref*> to_remove;
486 to_remove.push_back(pick_fn());
487 top_sim.IncludeAncDesc(to_remove, alt);
490 std::shuffle(to_remove.begin(), to_remove.end(), rng);
492 real->RemoveTransaction(*ptr);
493 top_sim.RemoveTransaction(ptr);
496 }
else if (sel_sim.removed.size() > 0 &&
command-- == 0) {
506 if (removed_pos != sel_sim.removed.size() - 1) {
507 std::swap(sel_sim.removed[removed_pos], sel_sim.removed.back());
509 sel_sim.removed.pop_back();
511 }
else if (block_builders.empty() &&
command-- == 0) {
513 std::vector<TxGraph::Ref*> to_destroy;
514 to_destroy.push_back(pick_fn());
520 auto old_size = to_destroy.size();
521 for (
auto& sim : sims) sim.IncludeAncDesc(to_destroy, alt);
522 if (to_destroy.size() == old_size)
break;
526 std::shuffle(to_destroy.begin(), to_destroy.end(), rng);
528 for (
size_t level = 0; level < sims.size(); ++level) {
529 sims[level].DestroyTransaction(ptr, level == sims.size() - 1);
533 }
else if (block_builders.empty() &&
command-- == 0) {
541 auto ref = pick_fn();
542 real->SetTransactionFee(*ref,
fee);
543 for (
auto& sim : sims) {
544 sim.SetTransactionFee(ref,
fee);
549 assert(real->GetTransactionCount(level_select) == sel_sim.GetTransactionCount());
553 auto ref = pick_fn();
554 bool exists = real->Exists(*ref, level_select);
556 assert(exists == should_exist);
560 assert(sel_sim.IsOversized() == real->IsOversized(level_select));
564 auto ref = pick_fn();
565 auto feerate = real->GetIndividualFeerate(*ref);
567 for (
auto& sim : sims) {
568 auto simpos = sim.Find(ref);
571 assert(feerate == sim.graph.FeeRate(simpos));
576 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
578 auto ref = pick_fn();
579 auto feerate = real->GetMainChunkFeerate(*ref);
580 auto simpos = main_sim.Find(ref);
586 assert(feerate.
size >= main_sim.graph.FeeRate(simpos).size);
587 assert(feerate.
size <= main_sim.SumAll().size);
590 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
592 auto ref = pick_fn();
593 auto result = alt ? real->GetDescendants(*ref, level_select)
594 : real->GetAncestors(*ref, level_select);
595 assert(result.size() <= max_cluster_count);
596 auto result_set = sel_sim.MakeSet(result);
597 assert(result.size() == result_set.Count());
598 auto expect_set = sel_sim.GetAncDesc(ref, alt);
599 assert(result_set == expect_set);
601 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
603 std::vector<TxGraph::Ref*> refs;
607 for (
size_t i = 0; i <
count; ++i) {
611 std::shuffle(refs.begin(), refs.end(), rng);
613 auto result = alt ? real->GetDescendantsUnion(refs, level_select)
614 : real->GetAncestorsUnion(refs, level_select);
615 auto result_set = sel_sim.MakeSet(result);
616 assert(result.size() == result_set.Count());
618 SimTxGraph::SetType expect_set;
619 for (
TxGraph::Ref* ref : refs) expect_set |= sel_sim.GetAncDesc(ref, alt);
621 assert(result_set == expect_set);
623 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
625 auto ref = pick_fn();
626 auto result = real->GetCluster(*ref, level_select);
628 assert(result.size() <= max_cluster_count);
630 auto left = sel_sim.graph.Positions();
631 uint64_t total_size{0};
632 for (
auto refptr : result) {
633 auto simpos = sel_sim.Find(refptr);
634 total_size += sel_sim.graph.FeeRate(simpos).size;
638 assert(!sel_sim.graph.Ancestors(simpos).Overlaps(left));
641 assert(total_size <= max_cluster_size);
643 auto result_set = sel_sim.MakeSet(result);
644 assert(sel_sim.graph.IsConnected(result_set));
646 auto simpos = sel_sim.Find(ref);
648 assert(result_set[simpos]);
650 assert(result_set.None());
653 for (
auto i : result_set) {
654 assert(sel_sim.graph.Ancestors(i).IsSubsetOf(result_set));
655 assert(sel_sim.graph.Descendants(i).IsSubsetOf(result_set));
660 assert((sims.size() == 2) == real->HaveStaging());
662 }
else if (sims.size() < 2 &&
command-- == 0) {
664 sims.emplace_back(sims.back());
665 sims.back().modified = SimTxGraph::SetType{};
666 real->StartStaging();
668 }
else if (block_builders.empty() && sims.size() > 1 &&
command-- == 0) {
670 real->CommitStaging();
672 const bool main_optimal = std::all_of(sims.cbegin(), sims.cend(), [](
const auto &sim) { return sim.real_is_optimal; });
673 sims.erase(sims.begin());
674 sims.front().real_is_optimal = main_optimal;
676 }
else if (sims.size() > 1 &&
command-- == 0) {
678 real->AbortStaging();
683 sims.back().oversized = std::nullopt;
685 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
687 auto ref_a = pick_fn();
688 auto ref_b = pick_fn();
689 auto sim_a = main_sim.Find(ref_a);
690 auto sim_b = main_sim.Find(ref_b);
693 auto cmp = real->CompareMainOrder(*ref_a, *ref_b);
695 if (sim_a != sim_b)
assert(cmp != 0);
697 if (main_sim.graph.Ancestors(sim_a)[sim_b])
assert(cmp >= 0);
698 if (main_sim.graph.Descendants(sim_a)[sim_b])
assert(cmp <= 0);
703 }
else if (!sel_sim.IsOversized() &&
command-- == 0) {
705 std::vector<TxGraph::Ref*> refs;
709 for (
size_t i = 0; i <
count; ++i) {
713 std::shuffle(refs.begin(), refs.end(), rng);
715 auto result = real->CountDistinctClusters(refs, level_select);
719 SimTxGraph::SetType sim_reps;
720 for (
auto ref : refs) {
722 auto simpos = sel_sim.Find(ref);
725 auto component = sel_sim.graph.GetConnectedComponent(sel_sim.graph.Positions(), simpos);
728 sim_reps.Set(component.First());
732 assert(result == sim_reps.Count());
737 bool ret = real->DoWork(iters);
738 uint64_t iters_for_optimal{0};
739 for (
unsigned level = 0; level < sims.size(); ++level) {
744 if (sims[level].IsOversized())
continue;
745 if (level == 0 && !block_builders.empty())
continue;
749 sims[level].real_is_optimal =
true;
752 for (
auto component : sims[level].GetComponents()) {
753 auto iters_opt_this_cluster = MaxOptimalLinearizationIters(component.Count());
754 if (iters_opt_this_cluster > acceptable_iters) {
758 iters_for_optimal += iters_opt_this_cluster + acceptable_iters;
760 iters_for_optimal += iters_opt_this_cluster;
768 assert(iters <= iters_for_optimal);
771 }
else if (sims.size() == 2 && !sims[0].IsOversized() && !sims[1].IsOversized() &&
command-- == 0) {
773 auto [real_main_diagram, real_staged_diagram] = real->GetMainStagingDiagrams();
774 auto real_sum_main = std::accumulate(real_main_diagram.begin(), real_main_diagram.end(),
FeeFrac{});
775 auto real_sum_staged = std::accumulate(real_staged_diagram.begin(), real_staged_diagram.end(),
FeeFrac{});
776 auto real_gain = real_sum_staged - real_sum_main;
777 auto sim_gain = sims[1].SumAll() - sims[0].SumAll();
781 assert(sim_gain == real_gain);
783 for (
size_t i = 1; i < real_main_diagram.size(); ++i) {
784 assert(FeeRateCompare(real_main_diagram[i], real_main_diagram[i - 1]) <= 0);
786 for (
size_t i = 1; i < real_staged_diagram.size(); ++i) {
787 assert(FeeRateCompare(real_staged_diagram[i], real_staged_diagram[i - 1]) <= 0);
790 }
else if (block_builders.size() < 4 && !main_sim.IsOversized() &&
command-- == 0) {
792 block_builders.emplace_back(real->GetBlockBuilder());
794 }
else if (!block_builders.empty() &&
command-- == 0) {
796 block_builders.erase(block_builders.begin() + builder_idx);
798 }
else if (!block_builders.empty() &&
command-- == 0) {
800 auto& builder_data = block_builders[builder_idx];
801 auto new_included = builder_data.included;
802 auto new_done = builder_data.done;
803 auto chunk = builder_data.builder->GetCurrentChunk();
806 if (!builder_data.last_feerate.IsEmpty()) {
807 assert(!(chunk->second >> builder_data.last_feerate));
809 builder_data.last_feerate = chunk->second;
814 auto simpos = main_sim.Find(ref);
817 sum_feerate += main_sim.graph.FeeRate(simpos);
819 assert(!new_done[simpos]);
820 new_done.Set(simpos);
822 new_included.Set(simpos);
823 assert(main_sim.graph.Ancestors(simpos).IsSubsetOf(new_included));
825 assert(sum_feerate == chunk->second);
829 if (builder_data.done == builder_data.included) {
830 assert(builder_data.done.Count() == main_sim.GetTransactionCount());
834 if ((orig_command % 7) >= 5) {
835 auto chunk2 = builder_data.builder->GetCurrentChunk();
839 if ((orig_command % 5) >= 3) {
841 builder_data.builder->Skip();
844 builder_data.builder->Include();
845 builder_data.included = new_included;
847 builder_data.done = new_done;
849 }
else if (!main_sim.IsOversized() &&
command-- == 0) {
851 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
854 if (main_sim.GetTransactionCount() == 0) {
855 assert(worst_chunk.empty());
856 assert(worst_chunk_feerate.IsEmpty());
858 assert(!worst_chunk.empty());
859 SimTxGraph::SetType done;
863 auto simpos = main_sim.Find(ref);
865 sum += main_sim.graph.FeeRate(simpos);
870 assert(main_sim.graph.Descendants(simpos).IsSubsetOf(done));
875 }
else if ((block_builders.empty() || sims.size() > 1) &&
command-- == 0) {
877 bool was_oversized = top_sim.IsOversized();
878 auto removed = real->Trim();
880 assert(was_oversized == !removed.empty());
881 if (!was_oversized)
break;
882 auto removed_set = top_sim.MakeSet(removed);
884 for (
auto simpos : removed_set) {
885 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
889 assert(top_sim.MatchesOversizedClusters(removed_set));
894 for (
auto simpos : removed_set) {
895 top_sim.RemoveTransaction(top_sim.GetRef(simpos));
897 assert(!top_sim.IsOversized());
899 }
else if ((block_builders.empty() || sims.size() > 1) &&
900 top_sim.GetTransactionCount() > max_cluster_count && !top_sim.IsOversized() &&
command-- == 0) {
911 auto clusters = top_sim.GetComponents();
914 bool made_oversized =
false;
915 auto merges_left = clusters.size() - 1;
916 while (merges_left > 0) {
919 auto par_cl = rng.
randrange(clusters.size());
920 auto chl_cl = rng.
randrange(clusters.size() - 1);
921 chl_cl += (chl_cl >= par_cl);
928 for (
int i = 0; i < num_deps; ++i) {
930 auto par_idx = rng.
randrange(clusters[par_cl].Count());
931 SimTxGraph::Pos par_pos = 0;
932 for (
auto j : clusters[par_cl]) {
940 auto chl_idx = rng.
randrange(clusters[chl_cl].Count());
941 SimTxGraph::Pos chl_pos = 0;
942 for (
auto j : clusters[chl_cl]) {
950 auto par_ref = top_sim.GetRef(par_pos);
951 auto chl_ref = top_sim.GetRef(chl_pos);
952 top_sim.AddDependency(par_ref, chl_ref);
953 real->AddDependency(*par_ref, *chl_ref);
956 auto par_cluster = clusters[par_cl];
957 auto chl_cluster = clusters[chl_cl];
958 auto new_cluster = par_cluster | chl_cluster;
960 std::erase_if(clusters, [&](
const auto& cl)
noexcept {
return cl == par_cluster || cl == chl_cluster; });
962 clusters.push_back(new_cluster);
965 if (!made_oversized) {
966 made_oversized = new_cluster.Count() > max_cluster_count;
967 if (!made_oversized) {
969 for (
auto i : new_cluster) total += top_sim.graph.FeeRate(i);
970 if (uint32_t(total.
size) > max_cluster_size) made_oversized =
true;
972 if (made_oversized) merges_left = rng.
randrange(clusters.size());
977 uint32_t max_removed = 0;
978 for (
auto& cluster : clusters) {
980 std::vector<uint32_t> sizes;
981 for (
auto i : cluster) sizes.push_back(top_sim.graph.FeeRate(i).size);
982 auto sum_sizes = std::accumulate(sizes.begin(), sizes.end(), uint64_t{0});
984 std::sort(sizes.begin(), sizes.end(), std::greater{});
986 while (sizes.size() > max_cluster_count || sum_sizes > max_cluster_size) {
987 sum_sizes -= sizes.back();
994 auto removed = real->Trim();
996 assert(removed.size() >= 1);
997 assert(removed.size() <= max_removed);
999 auto removed_set = top_sim.MakeSet(removed);
1000 for (
auto simpos : removed_set) {
1001 assert(top_sim.graph.Descendants(simpos).IsSubsetOf(removed_set));
1005 assert(top_sim.MatchesOversizedClusters(removed_set));
1010 for (
auto simpos : removed_set) {
1011 top_sim.RemoveTransaction(top_sim.GetRef(simpos));
1013 assert(!top_sim.IsOversized());
1017 auto usage = real->GetMainMemoryUsage();
1020 auto usage2 = real->GetMainMemoryUsage();
1024 if (main_sim.GetTransactionCount() == 0) {
1036 real->SanityCheck();
1038 if (!sims[0].IsOversized()) {
1042 std::vector<SimTxGraph::Pos> vec1;
1043 for (
auto i : sims[0].graph.
Positions()) vec1.push_back(i);
1044 std::shuffle(vec1.begin(), vec1.end(), rng);
1046 std::shuffle(vec2.begin(), vec2.end(), rng);
1047 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
1050 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b)
noexcept {
1051 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
1053 std::sort(vec1.begin(), vec1.end(), cmp);
1054 std::sort(vec2.begin(), vec2.end(), cmp);
1061 auto todo = sims[0].graph.Positions();
1062 for (
auto i : vec1) {
1070 if (sims[0].real_is_optimal) {
1072 auto [sim_lin, _optimal, _cost] =
Linearize(sims[0].graph, 300000, rng.
rand64(), vec1);
1080 for (
size_t pos = 0; pos < vec1.size(); ++pos) {
1081 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
1083 size_t before = rng.
randrange<
size_t>(pos);
1084 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
1085 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
1087 if (pos + 1 < vec1.size()) {
1088 size_t after = pos + 1 + rng.
randrange<
size_t>(vec1.size() - 1 - pos);
1089 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
1090 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
1096 auto builder = real->GetBlockBuilder();
1097 std::vector<SimTxGraph::Pos> vec_builder;
1098 std::vector<TxGraph::Ref*> last_chunk;
1100 while (
auto chunk = builder->GetCurrentChunk()) {
1105 assert(real->GetMainChunkFeerate(*ref) == chunk->second);
1107 sum += real->GetIndividualFeerate(*ref);
1109 auto simpos = sims[0].Find(ref);
1111 vec_builder.push_back(simpos);
1114 last_chunk = std::move(chunk->first);
1115 last_chunk_feerate = chunk->second;
1118 assert(vec_builder == vec1);
1121 std::reverse(last_chunk.begin(), last_chunk.end());
1122 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
1123 assert(last_chunk == worst_chunk);
1124 assert(last_chunk_feerate == worst_chunk_feerate);
1132 if (sims.size() >= 2 && !sims[1].IsOversized()) {
1135 auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
1137 for (
size_t i = 1; i < main_cmp_diagram.size(); ++i) {
1138 assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
1140 for (
size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
1141 assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
1147 std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
1148 std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});
1152 std::vector<FeeFrac> missing_main_cmp;
1153 std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
1154 main_cmp_diagram.begin(), main_cmp_diagram.end(),
1155 std::inserter(missing_main_cmp, missing_main_cmp.end()),
1157 assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
1160 std::vector<FeeFrac> missing_stage_cmp;
1161 std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
1162 stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
1163 std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
1165 assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
1168 assert(missing_main_cmp == missing_stage_cmp);
1175 for (
const auto& feerate : missing_main_cmp) missing_real += feerate;
1176 FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
1183 assert(real->HaveStaging() == (sims.size() > 1));
1190 assert(real->IsOversized(level) == sim.IsOversized());
1191 assert(real->GetTransactionCount(level) == sim.GetTransactionCount());
1193 if (!sim.IsOversized()) {
1194 auto todo = sim.graph.Positions();
1197 while (todo.Any()) {
1198 auto component = sim.graph.FindConnectedComponent(todo);
1201 for (
auto i : component) {
1203 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
1205 auto expect_anc = sim.graph.Ancestors(i);
1206 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), level));
1207 assert(anc.Count() <= max_cluster_count);
1208 assert(anc == expect_anc);
1210 auto expect_desc = sim.graph.Descendants(i);
1211 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), level));
1212 assert(desc.Count() <= max_cluster_count);
1213 assert(desc == expect_desc);
1215 auto cluster = real->GetCluster(*sim.GetRef(i), level);
1216 assert(cluster.size() <= max_cluster_count);
1217 assert(sim.MakeSet(cluster) == component);
1220 std::vector<DepGraphIndex> simlin;
1221 SimTxGraph::SetType done;
1222 uint64_t total_size{0};
1224 auto simpos = sim.Find(ptr);
1225 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
1227 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
1228 simlin.push_back(simpos);
1229 total_size += sim.graph.FeeRate(simpos).size;
1232 assert(total_size <= max_cluster_size);
1238 for (
unsigned chunknum = 0; chunknum < simlinchunk.
NumChunksLeft(); ++chunknum) {
1239 auto chunk = simlinchunk.
GetChunk(chunknum);
1242 assert(sim.graph.IsConnected(chunk.transactions));
1244 while (chunk.transactions.Any()) {
1245 assert(chunk.transactions[simlin[idx]]);
1246 chunk.transactions.Reset(simlin[idx]);
1247 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
1258 real->SanityCheck();
1261 block_builders.clear();
std::conditional_t<(BITS<=32), bitset_detail::IntBitSet< uint32_t >, std::conditional_t<(BITS<=std::numeric_limits< size_t >::digits), bitset_detail::IntBitSet< size_t >, bitset_detail::MultiIntBitSet< size_t,(BITS+std::numeric_limits< size_t >::digits - 1)/std::numeric_limits< size_t >::digits > > > BitSet
#define Assume(val)
Assume is the identity function.
T ConsumeIntegralInRange(T min, T max)
constexpr uint64_t rand64() noexcept
I randrange(I range) noexcept
Generate a random integer in the range [0..range), with range > 0.
@ MAIN
Always refers to the main graph, whether staging is present or not.
@ TOP
Refers to staging if it exists, main otherwise.
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.
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).
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.
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.
constexpr MaybeCoin MISSING
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Value Find(const std::map< Key, Value > &map, const Key &key)
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.
uint32_t DepGraphIndex
Data type to represent transaction indices in DepGraphs and the clusters they represent.
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).
Tagged wrapper around FeeFrac to avoid unit confusion.
void SeedRandomStateForTest(SeedRand seedtype)
Seed the global RNG state for testing and log the seed value.
@ ZEROS
Seed with a compile time constant of zeros.
std::unique_ptr< TxGraph > MakeTxGraph(unsigned max_cluster_count, uint64_t max_cluster_size, uint64_t acceptable_iters) noexcept
Construct a new TxGraph with the specified limit on the number of transactions within a cluster,...
static constexpr unsigned MAX_CLUSTER_COUNT_LIMIT
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.