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 = [&](
bool main_only) -> std::vector<FeeFrac> {
387 int level = main_only ? 0 : sims.size() - 1;
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, main_only));
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();
438 auto& sel_sim = use_main ? sims[0] : top_sim;
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(use_main) == sel_sim.GetTransactionCount());
553 auto ref = pick_fn();
554 bool exists = real->Exists(*ref, use_main);
556 assert(exists == should_exist);
560 assert(sel_sim.IsOversized() == real->IsOversized(use_main));
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, use_main)
594 : real->GetAncestors(*ref, use_main);
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, use_main)
614 : real->GetAncestorsUnion(refs, use_main);
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, use_main);
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, use_main);
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) {
908 real->CountDistinctClusters({},
false);
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());
1021 real->SanityCheck();
1023 if (!sims[0].IsOversized()) {
1027 std::vector<SimTxGraph::Pos> vec1;
1028 for (
auto i : sims[0].graph.
Positions()) vec1.push_back(i);
1029 std::shuffle(vec1.begin(), vec1.end(), rng);
1031 std::shuffle(vec2.begin(), vec2.end(), rng);
1032 if (vec1 == vec2) std::next_permutation(vec2.begin(), vec2.end());
1035 auto cmp = [&](SimTxGraph::Pos a, SimTxGraph::Pos b)
noexcept {
1036 return real->CompareMainOrder(*sims[0].GetRef(a), *sims[0].GetRef(b)) < 0;
1038 std::sort(vec1.begin(), vec1.end(), cmp);
1039 std::sort(vec2.begin(), vec2.end(), cmp);
1046 auto todo = sims[0].graph.Positions();
1047 for (
auto i : vec1) {
1055 if (sims[0].real_is_optimal) {
1057 auto [sim_lin, _optimal, _cost] =
Linearize(sims[0].graph, 300000, rng.
rand64(), vec1);
1065 for (
size_t pos = 0; pos < vec1.size(); ++pos) {
1066 auto pos_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[pos]));
1068 size_t before = rng.
randrange<
size_t>(pos);
1069 auto before_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[before]));
1070 assert(FeeRateCompare(before_feerate, pos_feerate) >= 0);
1072 if (pos + 1 < vec1.size()) {
1073 size_t after = pos + 1 + rng.
randrange<
size_t>(vec1.size() - 1 - pos);
1074 auto after_feerate = real->GetMainChunkFeerate(*sims[0].GetRef(vec1[after]));
1075 assert(FeeRateCompare(after_feerate, pos_feerate) <= 0);
1081 auto builder = real->GetBlockBuilder();
1082 std::vector<SimTxGraph::Pos> vec_builder;
1083 std::vector<TxGraph::Ref*> last_chunk;
1085 while (
auto chunk = builder->GetCurrentChunk()) {
1090 assert(real->GetMainChunkFeerate(*ref) == chunk->second);
1092 sum += real->GetIndividualFeerate(*ref);
1094 auto simpos = sims[0].Find(ref);
1096 vec_builder.push_back(simpos);
1099 last_chunk = std::move(chunk->first);
1100 last_chunk_feerate = chunk->second;
1103 assert(vec_builder == vec1);
1106 std::reverse(last_chunk.begin(), last_chunk.end());
1107 auto [worst_chunk, worst_chunk_feerate] = real->GetWorstMainChunk();
1108 assert(last_chunk == worst_chunk);
1109 assert(last_chunk_feerate == worst_chunk_feerate);
1113 auto main_real_diagram = get_diagram_fn(
true);
1117 if (sims.size() >= 2 && !sims[1].IsOversized()) {
1120 auto [main_cmp_diagram, stage_cmp_diagram] = real->GetMainStagingDiagrams();
1122 for (
size_t i = 1; i < main_cmp_diagram.size(); ++i) {
1123 assert(FeeRateCompare(main_cmp_diagram[i], main_cmp_diagram[i - 1]) <= 0);
1125 for (
size_t i = 1; i < stage_cmp_diagram.size(); ++i) {
1126 assert(FeeRateCompare(stage_cmp_diagram[i], stage_cmp_diagram[i - 1]) <= 0);
1132 std::sort(main_cmp_diagram.begin(), main_cmp_diagram.end(), std::greater{});
1133 std::sort(stage_cmp_diagram.begin(), stage_cmp_diagram.end(), std::greater{});
1137 std::vector<FeeFrac> missing_main_cmp;
1138 std::set_difference(main_real_diagram.begin(), main_real_diagram.end(),
1139 main_cmp_diagram.begin(), main_cmp_diagram.end(),
1140 std::inserter(missing_main_cmp, missing_main_cmp.end()),
1142 assert(main_cmp_diagram.size() + missing_main_cmp.size() == main_real_diagram.size());
1144 auto stage_real_diagram = get_diagram_fn(
false);
1145 std::vector<FeeFrac> missing_stage_cmp;
1146 std::set_difference(stage_real_diagram.begin(), stage_real_diagram.end(),
1147 stage_cmp_diagram.begin(), stage_cmp_diagram.end(),
1148 std::inserter(missing_stage_cmp, missing_stage_cmp.end()),
1150 assert(stage_cmp_diagram.size() + missing_stage_cmp.size() == stage_real_diagram.size());
1153 assert(missing_main_cmp == missing_stage_cmp);
1160 for (
const auto& feerate : missing_main_cmp) missing_real += feerate;
1161 FeeFrac missing_expected = sims[1].graph.FeeRate(sims[1].graph.Positions() - sims[1].modified);
1168 assert(real->HaveStaging() == (sims.size() > 1));
1172 for (
int main_only = 0; main_only < 2; ++main_only) {
1173 auto& sim = main_only ? sims[0] : sims.back();
1175 assert(real->IsOversized(main_only) == sim.IsOversized());
1176 assert(real->GetTransactionCount(main_only) == sim.GetTransactionCount());
1178 if (!sim.IsOversized()) {
1179 auto todo = sim.graph.Positions();
1182 while (todo.Any()) {
1183 auto component = sim.graph.FindConnectedComponent(todo);
1186 for (
auto i : component) {
1188 assert(sim.graph.FeeRate(i) == real->GetIndividualFeerate(*sim.GetRef(i)));
1190 auto expect_anc = sim.graph.Ancestors(i);
1191 auto anc = sim.MakeSet(real->GetAncestors(*sim.GetRef(i), main_only));
1192 assert(anc.Count() <= max_cluster_count);
1193 assert(anc == expect_anc);
1195 auto expect_desc = sim.graph.Descendants(i);
1196 auto desc = sim.MakeSet(real->GetDescendants(*sim.GetRef(i), main_only));
1197 assert(desc.Count() <= max_cluster_count);
1198 assert(desc == expect_desc);
1200 auto cluster = real->GetCluster(*sim.GetRef(i), main_only);
1201 assert(cluster.size() <= max_cluster_count);
1202 assert(sim.MakeSet(cluster) == component);
1205 std::vector<DepGraphIndex> simlin;
1206 SimTxGraph::SetType done;
1207 uint64_t total_size{0};
1209 auto simpos = sim.Find(ptr);
1210 assert(sim.graph.Descendants(simpos).IsSubsetOf(component - done));
1212 assert(sim.graph.Ancestors(simpos).IsSubsetOf(done));
1213 simlin.push_back(simpos);
1214 total_size += sim.graph.FeeRate(simpos).size;
1217 assert(total_size <= max_cluster_size);
1220 if (sims.size() == 1 || main_only) {
1223 for (
unsigned chunknum = 0; chunknum < simlinchunk.
NumChunksLeft(); ++chunknum) {
1224 auto chunk = simlinchunk.
GetChunk(chunknum);
1227 assert(sim.graph.IsConnected(chunk.transactions));
1229 while (chunk.transactions.Any()) {
1230 assert(chunk.transactions[simlin[idx]]);
1231 chunk.transactions.Reset(simlin[idx]);
1232 assert(chunk.feerate == real->GetMainChunkFeerate(*cluster[idx]));
1243 real->SanityCheck();
1246 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.
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.