Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_CLUSTER_LINEARIZE_H
6 : : #define BITCOIN_CLUSTER_LINEARIZE_H
7 : :
8 : : #include <algorithm>
9 : : #include <cstdint>
10 : : #include <numeric>
11 : : #include <optional>
12 : : #include <ranges>
13 : : #include <utility>
14 : : #include <vector>
15 : :
16 : : #include <attributes.h>
17 : : #include <memusage.h>
18 : : #include <random.h>
19 : : #include <span.h>
20 : : #include <util/feefrac.h>
21 : : #include <util/vecdeque.h>
22 : :
23 : : namespace cluster_linearize {
24 : :
25 : : /** Data type to represent transaction indices in DepGraphs and the clusters they represent. */
26 : : using DepGraphIndex = uint32_t;
27 : :
28 : : /** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
29 : : * descendants). */
30 : : template<typename SetType>
31 [ + + + - : 547543 : class DepGraph
+ - ][ + - ]
32 : : {
33 : : /** Information about a single transaction. */
34 : : struct Entry
35 : : {
36 : : /** Fee and size of transaction itself. */
37 : 23920 : FeeFrac feerate;
38 : : /** All ancestors of the transaction (including itself). */
39 : 23920 : SetType ancestors;
40 : : /** All descendants of the transaction (including itself). */
41 : 23920 : SetType descendants;
42 : :
43 : : /** Equality operator (primarily for testing purposes). */
44 [ + - + - : 47840 : friend bool operator==(const Entry&, const Entry&) noexcept = default;
- + ]
45 : :
46 : : /** Construct an empty entry. */
47 : 123061 : Entry() noexcept = default;
48 : : /** Construct an entry with a given feerate, ancestor set, descendant set. */
49 : 2727174 : Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
50 : : };
51 : :
52 : : /** Data for each transaction. */
53 : : std::vector<Entry> entries;
54 : :
55 : : /** Which positions are used. */
56 : : SetType m_used;
57 : :
58 : : public:
59 : : /** Equality operator (primarily for testing purposes). */
60 : 1386 : friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
61 : : {
62 [ + - ]: 1386 : if (a.m_used != b.m_used) return false;
63 : : // Only compare the used positions within the entries vector.
64 [ + + + + ]: 26618 : for (auto idx : a.m_used) {
65 [ + - ]: 23920 : if (a.entries[idx] != b.entries[idx]) return false;
66 : : }
67 : : return true;
68 : : }
69 : :
70 : : // Default constructors.
71 : 1133927 : DepGraph() noexcept = default;
72 : 18560 : DepGraph(const DepGraph&) noexcept = default;
73 : 0 : DepGraph(DepGraph&&) noexcept = default;
74 : 485006 : DepGraph& operator=(const DepGraph&) noexcept = default;
75 : 547649 : DepGraph& operator=(DepGraph&&) noexcept = default;
76 : :
77 : : /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
78 : : *
79 : : * @param depgraph The original DepGraph that is being remapped.
80 : : *
81 : : * @param mapping A span such that mapping[i] gives the position in the new DepGraph
82 : : * for position i in the old depgraph. Its size must be equal to
83 : : * depgraph.PositionRange(). The value of mapping[i] is ignored if
84 : : * position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
85 : : *
86 : : * @param pos_range The PositionRange() for the new DepGraph. It must equal the largest
87 : : * value in mapping for any used position in depgraph plus 1, or 0 if
88 : : * depgraph.TxCount() == 0.
89 : : *
90 : : * Complexity: O(N^2) where N=depgraph.TxCount().
91 : : */
92 [ - + ]: 4517 : DepGraph(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> mapping, DepGraphIndex pos_range) noexcept : entries(pos_range)
93 : : {
94 [ - + ]: 4517 : Assume(mapping.size() == depgraph.PositionRange());
95 : 9034 : Assume((pos_range == 0) == (depgraph.TxCount() == 0));
96 [ + + ]: 87707 : for (DepGraphIndex i : depgraph.Positions()) {
97 [ - + ]: 83190 : auto new_idx = mapping[i];
98 [ - + ]: 83190 : Assume(new_idx < pos_range);
99 : : // Add transaction.
100 : 83190 : entries[new_idx].ancestors = SetType::Singleton(new_idx);
101 : 83190 : entries[new_idx].descendants = SetType::Singleton(new_idx);
102 : 83190 : m_used.Set(new_idx);
103 : : // Fill in fee and size.
104 : 83190 : entries[new_idx].feerate = depgraph.entries[i].feerate;
105 : : }
106 [ + + ]: 87707 : for (DepGraphIndex i : depgraph.Positions()) {
107 : : // Fill in dependencies by mapping direct parents.
108 : 83190 : SetType parents;
109 [ + + + + ]: 190985 : for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
110 : 83190 : AddDependencies(parents, mapping[i]);
111 : : }
112 : : // Verify that the provided pos_range was correct (no unused positions at the end).
113 [ + + - + ]: 4517 : Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
114 : 4517 : }
115 : :
116 : : /** Get the set of transactions positions in use. Complexity: O(1). */
117 [ + + + + : 11077754 : const SetType& Positions() const noexcept { return m_used; }
+ + + + +
+ + + + +
+ + + + +
- + + +
+ ]
118 : : /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */
119 [ - + - + : 1122875 : DepGraphIndex PositionRange() const noexcept { return entries.size(); }
- + - + -
+ ][ - + +
- # # # #
# # # # #
# # # # #
# # # # #
# ][ - + -
+ - + + +
- + - + -
+ + - - +
+ - - + +
+ ]
120 : : /** Get the number of transactions in the graph. Complexity: O(1). */
121 [ - + ][ - + : 493276 : auto TxCount() const noexcept { return m_used.Count(); }
+ - + + -
+ - + + +
+ + + + +
- + + + +
+ - - + ]
122 : : /** Get the feerate of a given transaction i. Complexity: O(1). */
123 [ + - + + ]: 7405741 : const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; }
124 : : /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
125 [ + + + - ]: 18184991 : FeeFrac& FeeRate(DepGraphIndex i) noexcept { return entries[i].feerate; }
[ + - - +
- + + - +
- ][ - + -
+ + + + -
# # ]
126 : : /** Get the ancestors of a given transaction i. Complexity: O(1). */
127 [ + - + + : 146322530 : const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; }
- + ][ + +
+ + + + +
- - + + +
+ + + + +
- - + + -
+ + + + -
+ - + + +
- + ]
128 : : /** Get the descendants of a given transaction i. Complexity: O(1). */
129 [ + - ][ + + : 51644785 : const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; }
- + + - -
+ ]
130 : :
131 : : /** Add a new unconnected transaction to this transaction graph (in the first available
132 : : * position), and return its DepGraphIndex.
133 : : *
134 : : * Complexity: O(1) (amortized, due to resizing of backing vector).
135 : : */
136 : 2769826 : DepGraphIndex AddTransaction(const FeeFrac& feefrac) noexcept
137 : : {
138 : : static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
139 [ - + ]: 2769826 : auto available = ALL_POSITIONS - m_used;
140 [ - + ]: 3054787 : Assume(available.Any());
141 : 2769826 : DepGraphIndex new_idx = available.First();
142 [ - + + + ]: 2769826 : if (new_idx == entries.size()) {
143 : 2727174 : entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
144 : : } else {
145 : 42652 : entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
146 : : }
147 : 2769826 : m_used.Set(new_idx);
148 : 2769826 : return new_idx;
149 : : }
150 : :
151 : : /** Remove the specified positions from this DepGraph.
152 : : *
153 : : * The specified positions will no longer be part of Positions(), and dependencies with them are
154 : : * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct
155 : : * dependencies), if a parent is removed while a grandparent remains, the grandparent will
156 : : * remain an ancestor.
157 : : *
158 : : * Complexity: O(N) where N=TxCount().
159 : : */
160 : 778756 : void RemoveTransactions(const SetType& del) noexcept
161 : : {
162 : 778756 : m_used -= del;
163 : : // Remove now-unused trailing entries.
164 [ + + - + : 1749883 : while (!entries.empty() && !m_used[entries.size() - 1]) {
+ + ]
165 : 971127 : entries.pop_back();
166 : : }
167 : : // Remove the deleted transactions from ancestors/descendants of other transactions. Note
168 : : // that the deleted positions will retain old feerate and dependency information. This does
169 : : // not matter as they will be overwritten by AddTransaction if they get used again.
170 [ + + ]: 21949680 : for (auto& entry : entries) {
171 [ + + ]: 61532754 : entry.ancestors &= m_used;
172 [ + + ]: 61532754 : entry.descendants &= m_used;
173 : : }
174 : 778756 : }
175 : :
176 : : /** Modify this transaction graph, adding multiple parents to a specified child.
177 : : *
178 : : * Complexity: O(N) where N=TxCount().
179 : : */
180 : 5097494 : void AddDependencies(const SetType& parents, DepGraphIndex child) noexcept
181 : : {
182 [ - + ]: 5097494 : Assume(m_used[child]);
183 [ - + ]: 6534824 : Assume(parents.IsSubsetOf(m_used));
184 : : // Compute the ancestors of parents that are not already ancestors of child.
185 [ + + ]: 5097494 : SetType par_anc;
186 [ + + + + ]: 9948824 : for (auto par : parents - Ancestors(child)) {
[ + + ]
187 : 4209524 : par_anc |= Ancestors(par);
188 : : }
189 [ + + ]: 5097494 : par_anc -= Ancestors(child);
190 : : // Bail out if there are no such ancestors.
191 [ + + ]: 5097494 : if (par_anc.None()) return;
192 : : // To each such ancestor, add as descendants the descendants of the child.
193 : 2536032 : const auto& chl_des = entries[child].descendants;
194 [ + + ]: 9485744 : for (auto anc_of_par : par_anc) {
195 : 8659439 : entries[anc_of_par].descendants |= chl_des;
196 : : }
197 : : // To each descendant of the child, add those ancestors.
198 [ + - + + ]: 7946950 : for (auto dec_of_chl : Descendants(child)) {
[ + + ]
199 : 5654935 : entries[dec_of_chl].ancestors |= par_anc;
200 : : }
201 : : }
202 : :
203 : : /** Compute the (reduced) set of parents of node i in this graph.
204 : : *
205 : : * This returns the minimal subset of the parents of i whose ancestors together equal all of
206 : : * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not
207 : : * store the set of parents; this information is inferred from the ancestor sets.
208 : : *
209 : : * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).
210 : : */
211 : 7523637 : SetType GetReducedParents(DepGraphIndex i) const noexcept
212 : : {
213 : 7523637 : SetType parents = Ancestors(i);
214 : 7523637 : parents.Reset(i);
215 [ + + + + ]: 37155282 : for (auto parent : parents) {
[ + + ]
216 [ + + ]: 24592133 : if (parents[parent]) {
217 : 22904226 : parents -= Ancestors(parent);
218 : 22904226 : parents.Set(parent);
219 : : }
220 : : }
221 : 7523637 : return parents;
222 : : }
223 : :
224 : : /** Compute the (reduced) set of children of node i in this graph.
225 : : *
226 : : * This returns the minimal subset of the children of i whose descendants together equal all of
227 : : * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not
228 : : * store the set of children; this information is inferred from the descendant sets.
229 : : *
230 : : * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).
231 : : */
232 : 204975 : SetType GetReducedChildren(DepGraphIndex i) const noexcept
233 : : {
234 : 204975 : SetType children = Descendants(i);
235 : 204975 : children.Reset(i);
236 [ + + + + ]: 1118282 : for (auto child : children) {
237 [ + + ]: 784730 : if (children[child]) {
238 : 310759 : children -= Descendants(child);
239 : 310759 : children.Set(child);
240 : : }
241 : : }
242 : 204975 : return children;
243 : : }
244 : :
245 : : /** Compute the aggregate feerate of a set of nodes in this graph.
246 : : *
247 : : * Complexity: O(N) where N=elems.Count().
248 : : **/
249 : 34593861 : FeeFrac FeeRate(const SetType& elems) const noexcept
250 : : {
251 : 34593861 : FeeFrac ret;
252 [ + + # # ]: 655480458 : for (auto pos : elems) ret += entries[pos].feerate;
[ + - + + ]
253 : 34593861 : return ret;
254 : : }
255 : :
256 : : /** Get the connected component within the subset "todo" that contains tx (which must be in
257 : : * todo).
258 : : *
259 : : * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
260 : : * of the other in the entire graph (so not just within `todo`), or transitively there is a
261 : : * path of transactions connecting them. This does mean that if `todo` contains a transaction
262 : : * and a grandparent, but misses the parent, they will still be part of the same component.
263 : : *
264 : : * Complexity: O(ret.Count()).
265 : : */
266 : 8835458 : SetType GetConnectedComponent(const SetType& todo, DepGraphIndex tx) const noexcept
267 : : {
268 [ - + ]: 8835458 : Assume(todo[tx]);
269 [ - + ]: 17238757 : Assume(todo.IsSubsetOf(m_used));
270 : 8835458 : auto to_add = SetType::Singleton(tx);
271 : 8835458 : SetType ret;
272 : : do {
273 : 19801660 : SetType old = ret;
274 [ + - + + ]: 61571455 : for (auto add : to_add) {
[ + + ]
275 : 79322678 : ret |= Descendants(add);
276 : 79322678 : ret |= Ancestors(add);
277 : : }
278 [ + + ]: 19801660 : ret &= todo;
279 : 19801660 : to_add = ret - old;
280 [ + + ]: 38626090 : } while (to_add.Any());
281 : 8835458 : return ret;
282 : : }
283 : :
284 : : /** Find some connected component within the subset "todo" of this graph.
285 : : *
286 : : * Specifically, this finds the connected component which contains the first transaction of
287 : : * todo (if any).
288 : : *
289 : : * Complexity: O(ret.Count()).
290 : : */
291 [ + + ]: 6648241 : SetType FindConnectedComponent(const SetType& todo) const noexcept
292 : : {
293 [ + + ]: 6648241 : if (todo.None()) return todo;
294 : 6644616 : return GetConnectedComponent(todo, todo.First());
295 : : }
296 : :
297 : : /** Determine if a subset is connected.
298 : : *
299 : : * Complexity: O(subset.Count()).
300 : : */
301 : 1895205 : bool IsConnected(const SetType& subset) const noexcept
302 : : {
303 [ + + ]: 1895205 : return FindConnectedComponent(subset) == subset;
304 : : }
305 : :
306 : : /** Determine if this entire graph is connected.
307 : : *
308 : : * Complexity: O(TxCount()).
309 : : */
310 : 327 : bool IsConnected() const noexcept { return IsConnected(m_used); }
311 : :
312 : : /** Append the entries of select to list in a topologically valid order.
313 : : *
314 : : * Complexity: O(select.Count() * log(select.Count())).
315 : : */
316 [ - + ]: 19056 : void AppendTopo(std::vector<DepGraphIndex>& list, const SetType& select) const noexcept
317 : : {
318 : 19056 : DepGraphIndex old_len = list.size();
319 [ + - + + ]: 72763 : for (auto i : select) list.push_back(i);
320 [ - + ]: 19056 : std::ranges::sort(std::span{list}.subspan(old_len), [&](DepGraphIndex a, DepGraphIndex b) noexcept {
321 [ + + ]: 83387 : const auto a_anc_count = entries[a].ancestors.Count();
322 : 83387 : const auto b_anc_count = entries[b].ancestors.Count();
323 [ + + ]: 83387 : if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
324 : 27716 : return a < b;
325 : : });
326 : 19056 : }
327 : :
328 : : /** Check if this graph is acyclic. */
329 : 57329 : bool IsAcyclic() const noexcept
330 : : {
331 [ + + + + ]: 457438 : for (auto i : Positions()) {
332 [ + + ]: 343263 : if ((Ancestors(i) & Descendants(i)) != SetType::Singleton(i)) {
333 : : return false;
334 : : }
335 : : }
336 : : return true;
337 : : }
338 : :
339 : : unsigned CountDependencies() const noexcept
340 : : {
341 : : unsigned ret = 0;
342 : : for (auto i : Positions()) {
343 : : ret += GetReducedParents(i).Count();
344 : : }
345 : : return ret;
346 : : }
347 : :
348 : : /** Reduce memory usage if possible. No observable effect. */
349 : 1353221 : void Compact() noexcept
350 : : {
351 [ - + ]: 1353221 : entries.shrink_to_fit();
352 : : }
353 : :
354 : 3198094 : size_t DynamicMemoryUsage() const noexcept
355 : : {
356 [ - + ][ - + : 3211479 : return memusage::DynamicUsage(entries);
- + - + ]
357 : : }
358 : : };
359 : :
360 : : /** A set of transactions together with their aggregate feerate. */
361 : : template<typename SetType>
362 : : struct SetInfo
363 : : {
364 : : /** The transactions in the set. */
365 : 561 : SetType transactions;
366 : : /** Their combined fee and size. */
367 : 561 : FeeFrac feerate;
368 : :
369 : : /** Construct a SetInfo for the empty set. */
370 : 6613639 : SetInfo() noexcept = default;
371 : :
372 : : /** Construct a SetInfo for a specified set and feerate. */
373 : 1096 : SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
374 : :
375 : : /** Construct a SetInfo for a given transaction in a depgraph. */
376 : 16391695 : explicit SetInfo(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept :
377 : 16391695 : transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
378 : :
379 : : /** Construct a SetInfo for a set of transactions in a depgraph. */
380 : 34499225 : explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
381 : 34499225 : transactions(txn), feerate(depgraph.FeeRate(txn)) {}
382 : :
383 : : /** Add a transaction to this SetInfo (which must not yet be in it). */
384 : 6925 : void Set(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept
385 : : {
386 [ - + ]: 6925 : Assume(!transactions[pos]);
387 : 6925 : transactions.Set(pos);
388 : 6925 : feerate += depgraph.FeeRate(pos);
389 : 6925 : }
390 : :
391 : : /** Add the transactions of other to this SetInfo (no overlap allowed). */
392 : 14568009 : SetInfo& operator|=(const SetInfo& other) noexcept
393 : : {
394 [ - + ]: 15893938 : Assume(!transactions.Overlaps(other.transactions));
395 : 14568009 : transactions |= other.transactions;
396 : 14568009 : feerate += other.feerate;
397 : 14568009 : return *this;
398 : : }
399 : :
400 : : /** Remove the transactions of other from this SetInfo (which must be a subset). */
401 : 3252923 : SetInfo& operator-=(const SetInfo& other) noexcept
402 : : {
403 [ - + ]: 3275420 : Assume(other.transactions.IsSubsetOf(transactions));
404 : 3252923 : transactions -= other.transactions;
405 : 3252923 : feerate -= other.feerate;
406 : 3252923 : return *this;
407 : : }
408 : :
409 : : /** Compute the difference between this and other SetInfo (which must be a subset). */
410 : : SetInfo operator-(const SetInfo& other) const noexcept
411 : : {
412 : : Assume(other.transactions.IsSubsetOf(transactions));
413 : : return {transactions - other.transactions, feerate - other.feerate};
414 : : }
415 : :
416 : : /** Swap two SetInfo objects. */
417 : : friend void swap(SetInfo& a, SetInfo& b) noexcept
418 : : {
419 : : swap(a.transactions, b.transactions);
420 : : swap(a.feerate, b.feerate);
421 : : }
422 : :
423 : : /** Permit equality testing. */
424 [ + - + - ]: 1122 : friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
425 : : };
426 : :
427 : : /** Compute the chunks of linearization as SetInfos. */
428 : : template<typename SetType>
429 : 1627846 : std::vector<SetInfo<SetType>> ChunkLinearizationInfo(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
430 : : {
431 : 1627846 : std::vector<SetInfo<SetType>> ret;
432 [ + + ]: 11405902 : for (DepGraphIndex i : linearization) {
433 : : /** The new chunk to be added, initially a singleton. */
434 : 9778056 : SetInfo<SetType> new_chunk(depgraph, i);
435 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
436 [ + + + + ]: 13297440 : while (!ret.empty() && ByRatio{new_chunk.feerate} > ByRatio{ret.back().feerate}) {
437 : 3519384 : new_chunk |= ret.back();
438 : 3519384 : ret.pop_back();
439 : : }
440 : : // Actually move that new chunk into the chunking.
441 : 9778056 : ret.emplace_back(std::move(new_chunk));
442 : : }
443 : 1627846 : return ret;
444 : : }
445 : :
446 : : /** Compute the feerates of the chunks of linearization. Identical to ChunkLinearizationInfo, but
447 : : * only returns the chunk feerates, not the corresponding transaction sets. */
448 : : template<typename SetType>
449 : 1668269 : std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
450 : : {
451 : 1668269 : std::vector<FeeFrac> ret;
452 [ + + ]: 9907692 : for (DepGraphIndex i : linearization) {
453 : : /** The new chunk to be added, initially a singleton. */
454 : 8239423 : auto new_chunk = depgraph.FeeRate(i);
455 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
456 [ + + + + ]: 11812926 : while (!ret.empty() && ByRatio{new_chunk} > ByRatio{ret.back()}) {
457 : 3573503 : new_chunk += ret.back();
458 : 3573503 : ret.pop_back();
459 : : }
460 : : // Actually move that new chunk into the chunking.
461 : 8239423 : ret.push_back(std::move(new_chunk));
462 : : }
463 : 1668269 : return ret;
464 : : }
465 : :
466 : : /** Concept for function objects that return std::strong_ordering when invoked with two Args. */
467 : : template<typename F, typename Arg>
468 : : concept StrongComparator =
469 : : std::regular_invocable<F, Arg, Arg> &&
470 : : std::is_same_v<std::invoke_result_t<F, Arg, Arg>, std::strong_ordering>;
471 : :
472 : : /** Simple default transaction ordering function for SpanningForestState::GetLinearization() and
473 : : * Linearize(), which just sorts by DepGraphIndex. */
474 : : using IndexTxOrder = std::compare_three_way;
475 : :
476 : : /** A default cost model for SFL for SetType=BitSet<64>, based on benchmarks.
477 : : *
478 : : * The numbers here were obtained in February 2026 by:
479 : : * - For a variety of machines:
480 : : * - Running a fixed collection of ~385000 clusters found through random generation and fuzzing,
481 : : * optimizing for difficulty of linearization.
482 : : * - Linearize each ~3000 times, with different random seeds. Sometimes without input
483 : : * linearization, sometimes with a bad one.
484 : : * - Gather cycle counts for each of the operations included in this cost model,
485 : : * broken down by their parameters.
486 : : * - Correct the data by subtracting the runtime of obtaining the cycle count.
487 : : * - Drop the 5% top and bottom samples from each cycle count dataset, and compute the average
488 : : * of the remaining samples.
489 : : * - For each operation, fit a least-squares linear function approximation through the samples.
490 : : * - Rescale all machine expressions to make their total time match, as we only care about
491 : : * relative cost of each operation.
492 : : * - Take the per-operation average of operation expressions across all machines, to construct
493 : : * expressions for an average machine.
494 : : * - Approximate the result with integer coefficients. Each cost unit corresponds to somewhere
495 : : * between 0.5 ns and 2.5 ns, depending on the hardware.
496 : : */
497 : : class SFLDefaultCostModel
498 : : {
499 : : uint64_t m_cost{0};
500 : :
501 : : public:
502 : 1352954 : inline void InitializeBegin() noexcept {}
503 : 1352954 : inline void InitializeEnd(int num_txns, int num_deps) noexcept
504 : : {
505 : : // Cost of initialization.
506 : 1352954 : m_cost += 39 * num_txns;
507 : : // Cost of producing linearization at the end.
508 : 1352954 : m_cost += 48 * num_txns + 4 * num_deps;
509 : : }
510 : : inline void GetLinearizationBegin() noexcept {}
511 : : inline void GetLinearizationEnd(int num_txns, int num_deps) noexcept
512 : : {
513 : : // Note that we account for the cost of the final linearization at the beginning (see
514 : : // InitializeEnd), because the cost budget decision needs to be made before calling
515 : : // GetLinearization.
516 : : // This function exists here to allow overriding it easily for benchmark purposes.
517 : : }
518 : : inline void MakeTopologicalBegin() noexcept {}
519 : 795935 : inline void MakeTopologicalEnd(int num_chunks, int num_steps) noexcept
520 : : {
521 : 795935 : m_cost += 20 * num_chunks + 28 * num_steps;
522 : : }
523 : : inline void StartOptimizingBegin() noexcept {}
524 : 1319831 : inline void StartOptimizingEnd(int num_chunks) noexcept { m_cost += 13 * num_chunks; }
525 : : inline void ActivateBegin() noexcept {}
526 : 3054499 : inline void ActivateEnd(int num_deps) noexcept { m_cost += 10 * num_deps + 1; }
527 : : inline void DeactivateBegin() noexcept {}
528 : 751007 : inline void DeactivateEnd(int num_deps) noexcept { m_cost += 11 * num_deps + 8; }
529 : : inline void MergeChunksBegin() noexcept {}
530 : 3054499 : inline void MergeChunksMid(int num_txns) noexcept { m_cost += 2 * num_txns; }
531 : 3054499 : inline void MergeChunksEnd(int num_steps) noexcept { m_cost += 3 * num_steps + 5; }
532 : : inline void PickMergeCandidateBegin() noexcept {}
533 : 12004594 : inline void PickMergeCandidateEnd(int num_steps) noexcept { m_cost += 8 * num_steps; }
534 : : inline void PickChunkToOptimizeBegin() noexcept {}
535 : 3558367 : inline void PickChunkToOptimizeEnd(int num_steps) noexcept { m_cost += num_steps + 4; }
536 : : inline void PickDependencyToSplitBegin() noexcept {}
537 : 3558314 : inline void PickDependencyToSplitEnd(int num_txns) noexcept { m_cost += 8 * num_txns + 9; }
538 : : inline void StartMinimizingBegin() noexcept {}
539 : 1318291 : inline void StartMinimizingEnd(int num_chunks) noexcept { m_cost += 18 * num_chunks; }
540 : : inline void MinimizeStepBegin() noexcept {}
541 : 5049166 : inline void MinimizeStepMid(int num_txns) noexcept { m_cost += 11 * num_txns + 11; }
542 : 680781 : inline void MinimizeStepEnd(bool split) noexcept { m_cost += 17 * split + 7; }
543 : :
544 : 11315459 : inline uint64_t GetCost() const noexcept { return m_cost; }
545 : : };
546 : :
547 : : /** Class to represent the internal state of the spanning-forest linearization (SFL) algorithm.
548 : : *
549 : : * At all times, each dependency is marked as either "active" or "inactive". The subset of active
550 : : * dependencies is the state of the SFL algorithm. The implementation maintains several other
551 : : * values to speed up operations, but everything is ultimately a function of what that subset of
552 : : * active dependencies is.
553 : : *
554 : : * Given such a subset, define a chunk as the set of transactions that are connected through active
555 : : * dependencies (ignoring their parent/child direction). Thus, every state implies a particular
556 : : * partitioning of the graph into chunks (including potential singletons). In the extreme, each
557 : : * transaction may be in its own chunk, or in the other extreme all transactions may form a single
558 : : * chunk. A chunk's feerate is its total fee divided by its total size.
559 : : *
560 : : * The algorithm consists of switching dependencies between active and inactive. The final
561 : : * linearization that is produced at the end consists of these chunks, sorted from high to low
562 : : * feerate, each individually sorted in an arbitrary but topological (= no child before parent)
563 : : * way.
564 : : *
565 : : * We define four quality properties the state can have:
566 : : *
567 : : * - acyclic: The state is acyclic whenever no cycle of active dependencies exists within the
568 : : * graph, ignoring the parent/child direction. This is equivalent to saying that within
569 : : * each chunk the set of active dependencies form a tree, and thus the overall set of
570 : : * active dependencies in the graph form a spanning forest, giving the algorithm its
571 : : * name. Being acyclic is also equivalent to every chunk of N transactions having
572 : : * exactly N-1 active dependencies.
573 : : *
574 : : * For example in a diamond graph, D->{B,C}->A, the 4 dependencies cannot be
575 : : * simultaneously active. If at least one is inactive, the state is acyclic.
576 : : *
577 : : * The algorithm maintains an acyclic state at *all* times as an invariant. This implies
578 : : * that activating a dependency always corresponds to merging two chunks, and that
579 : : * deactivating one always corresponds to splitting two chunks.
580 : : *
581 : : * - topological: We say the state is topological whenever it is acyclic and no inactive dependency
582 : : * exists between two distinct chunks such that the child chunk has higher or equal
583 : : * feerate than the parent chunk.
584 : : *
585 : : * The relevance is that whenever the state is topological, the produced output
586 : : * linearization will be topological too (i.e., not have children before parents).
587 : : * Note that the "or equal" part of the definition matters: if not, one can end up
588 : : * in a situation with mutually-dependent equal-feerate chunks that cannot be
589 : : * linearized. For example C->{A,B} and D->{A,B}, with C->A and D->B active. The AC
590 : : * chunk depends on DB through C->B, and the BD chunk depends on AC through D->A.
591 : : * Merging them into a single ABCD chunk fixes this.
592 : : *
593 : : * The algorithm attempts to keep the state topological as much as possible, so it
594 : : * can be interrupted to produce an output whenever, but will sometimes need to
595 : : * temporarily deviate from it when improving the state.
596 : : *
597 : : * - optimal: For every active dependency, define its top and bottom set as the set of transactions
598 : : * in the chunks that would result if the dependency were deactivated; the top being the
599 : : * one with the dependency's parent, and the bottom being the one with the child. Note
600 : : * that due to acyclicity, every deactivation splits a chunk exactly in two.
601 : : *
602 : : * We say the state is optimal whenever it is topological and it has no active
603 : : * dependency whose top feerate is strictly higher than its bottom feerate. The
604 : : * relevance is that it can be proven that whenever the state is optimal, the produced
605 : : * linearization will also be optimal (in the convexified feerate diagram sense). It can
606 : : * also be proven that for every graph at least one optimal state exists.
607 : : *
608 : : * Note that it is possible for the SFL state to not be optimal, but the produced
609 : : * linearization to still be optimal. This happens when the chunks of a state are
610 : : * identical to those of an optimal state, but the exact set of active dependencies
611 : : * within a chunk differ in such a way that the state optimality condition is not
612 : : * satisfied. Thus, the state being optimal is more a "the eventual output is *known*
613 : : * to be optimal".
614 : : *
615 : : * - minimal: We say the state is minimal when it is:
616 : : * - acyclic
617 : : * - topological, except that inactive dependencies between equal-feerate chunks are
618 : : * allowed as long as they do not form a loop.
619 : : * - like optimal, no active dependencies whose top feerate is strictly higher than
620 : : * the bottom feerate are allowed.
621 : : * - no chunk contains a proper non-empty subset which includes all its own in-chunk
622 : : * dependencies of the same feerate as the chunk itself.
623 : : *
624 : : * A minimal state effectively corresponds to an optimal state, where every chunk has
625 : : * been split into its minimal equal-feerate components.
626 : : *
627 : : * The algorithm terminates whenever a minimal state is reached.
628 : : *
629 : : *
630 : : * This leads to the following high-level algorithm:
631 : : * - Start with all dependencies inactive, and thus all transactions in their own chunk. This is
632 : : * definitely acyclic.
633 : : * - Activate dependencies (merging chunks) until the state is topological.
634 : : * - Loop until optimal (no dependencies with higher-feerate top than bottom), or time runs out:
635 : : * - Deactivate a violating dependency, potentially making the state non-topological.
636 : : * - Activate other dependencies to make the state topological again.
637 : : * - If there is time left and the state is optimal:
638 : : * - Attempt to split chunks into equal-feerate parts without mutual dependencies between them.
639 : : * When this succeeds, recurse into them.
640 : : * - If no such chunks can be found, the state is minimal.
641 : : * - Output the chunks from high to low feerate, each internally sorted topologically.
642 : : *
643 : : * When merging, we always either:
644 : : * - Merge upwards: merge a chunk with the lowest-feerate other chunk it depends on, among those
645 : : * with lower or equal feerate than itself.
646 : : * - Merge downwards: merge a chunk with the highest-feerate other chunk that depends on it, among
647 : : * those with higher or equal feerate than itself.
648 : : *
649 : : * Using these strategies in the improvement loop above guarantees that the output linearization
650 : : * after a deactivate + merge step is never worse or incomparable (in the convexified feerate
651 : : * diagram sense) than the output linearization that would be produced before the step. With that,
652 : : * we can refine the high-level algorithm to:
653 : : * - Start with all dependencies inactive.
654 : : * - Perform merges as described until none are possible anymore, making the state topological.
655 : : * - Loop until optimal or time runs out:
656 : : * - Pick a dependency D to deactivate among those with higher feerate top than bottom.
657 : : * - Deactivate D, causing the chunk it is in to split into top T and bottom B.
658 : : * - Do an upwards merge of T, if possible. If so, repeat the same with the merged result.
659 : : * - Do a downwards merge of B, if possible. If so, repeat the same with the merged result.
660 : : * - Split chunks further to obtain a minimal state, see below.
661 : : * - Output the chunks from high to low feerate, each internally sorted topologically.
662 : : *
663 : : * Instead of performing merges arbitrarily to make the initial state topological, it is possible
664 : : * to do so guided by an existing linearization. This has the advantage that the state's would-be
665 : : * output linearization is immediately as good as the existing linearization it was based on:
666 : : * - Start with all dependencies inactive.
667 : : * - For each transaction t in the existing linearization:
668 : : * - Find the chunk C that transaction is in (which will be singleton).
669 : : * - Do an upwards merge of C, if possible. If so, repeat the same with the merged result.
670 : : * No downwards merges are needed in this case.
671 : : *
672 : : * After reaching an optimal state, it can be transformed into a minimal state by attempting to
673 : : * split chunks further into equal-feerate parts. To do so, pick a specific transaction in each
674 : : * chunk (the pivot), and rerun the above split-then-merge procedure again:
675 : : * - first, while pretending the pivot transaction has an infinitesimally higher (or lower) fee
676 : : * than it really has. If a split exists with the pivot in the top part (or bottom part), this
677 : : * will find it.
678 : : * - if that fails to split, repeat while pretending the pivot transaction has an infinitesimally
679 : : * lower (or higher) fee. If a split exists with the pivot in the bottom part (or top part), this
680 : : * will find it.
681 : : * - if either succeeds, repeat the procedure for the newly found chunks to split them further.
682 : : * If not, the chunk is already minimal.
683 : : * If the chunk can be split into equal-feerate parts, then the pivot must exist in either the top
684 : : * or bottom part of that potential split. By trying both with the same pivot, if a split exists,
685 : : * it will be found.
686 : : *
687 : : * What remains to be specified are a number of heuristics:
688 : : *
689 : : * - How to decide which chunks to merge:
690 : : * - The merge upwards and downward rules specify that the lowest-feerate respectively
691 : : * highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate
692 : : * candidates, a uniformly random one among them is picked.
693 : : *
694 : : * - How to decide what dependency to activate (when merging chunks):
695 : : * - After picking two chunks to be merged (see above), a uniformly random dependency between the
696 : : * two chunks is activated.
697 : : *
698 : : * - How to decide which chunk to find a dependency to split in:
699 : : * - A round-robin queue of chunks to improve is maintained. The initial ordering of this queue
700 : : * is uniformly randomly permuted.
701 : : *
702 : : * - How to decide what dependency to deactivate (when splitting chunks):
703 : : * - Inside the selected chunk (see above), among the dependencies whose top feerate is strictly
704 : : * higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency
705 : : * is deactivated.
706 : : * - After every split, it is possible that the top and the bottom chunk merge with each other
707 : : * again in the merge sequence (through a top->bottom dependency, not through the deactivated
708 : : * one, which was bottom->top). Call this a self-merge. If a self-merge does not occur after
709 : : * a split, the resulting linearization is strictly improved (the area under the convexified
710 : : * feerate diagram increases by at least gain/2), while self-merges do not change it.
711 : : *
712 : : * - How to decide the exact output linearization:
713 : : * - When there are multiple equal-feerate chunks with no dependencies between them, pick the
714 : : * smallest one first. If there are multiple smallest ones, pick the one that contains the
715 : : * last transaction (according to the provided fallback order) last (note that this is not the
716 : : * same as picking the chunk with the first transaction first).
717 : : * - Within chunks, pick among all transactions without missing dependencies the one with the
718 : : * highest individual feerate. If there are multiple ones with the same individual feerate,
719 : : * pick the smallest first. If there are multiple with the same fee and size, pick the one
720 : : * that sorts first according to the fallback order first.
721 : : */
722 : : template<typename SetType, typename CostModel = SFLDefaultCostModel>
723 : : class SpanningForestState
724 : : {
725 : : private:
726 : : /** Internal RNG. */
727 : : InsecureRandomContext m_rng;
728 : :
729 : : /** Data type to represent indexing into m_tx_data. */
730 : : using TxIdx = DepGraphIndex;
731 : : /** Data type to represent indexing into m_set_info. Use the smallest type possible to improve
732 : : * cache locality. */
733 : : using SetIdx = std::conditional_t<(SetType::Size() <= 0xff),
734 : : uint8_t,
735 : : std::conditional_t<(SetType::Size() <= 0xffff),
736 : : uint16_t,
737 : : uint32_t>>;
738 : : /** An invalid SetIdx. */
739 : : static constexpr SetIdx INVALID_SET_IDX = SetIdx(-1);
740 : :
741 : : /** Structure with information about a single transaction. */
742 : 6631936 : struct TxData {
743 : : /** The top set for every active child dependency this transaction has, indexed by child
744 : : * TxIdx. Only defined for indexes in active_children. */
745 : : std::array<SetIdx, SetType::Size()> dep_top_idx;
746 : : /** The set of parent transactions of this transaction. Immutable after construction. */
747 : : SetType parents;
748 : : /** The set of child transactions of this transaction. Immutable after construction. */
749 : : SetType children;
750 : : /** The set of child transactions reachable through an active dependency. */
751 : : SetType active_children;
752 : : /** Which chunk this transaction belongs to. */
753 : : SetIdx chunk_idx;
754 : : };
755 : :
756 : : /** The set of all TxIdx's of transactions in the cluster indexing into m_tx_data. */
757 : : SetType m_transaction_idxs;
758 : : /** The set of all chunk SetIdx's. This excludes the SetIdxs that refer to active
759 : : * dependencies' tops. */
760 : : SetType m_chunk_idxs;
761 : : /** The set of all SetIdx's that appear in m_suboptimal_chunks. Note that they do not need to
762 : : * be chunks: some of these sets may have been converted to a dependency's top set since being
763 : : * added to m_suboptimal_chunks. */
764 : : SetType m_suboptimal_idxs;
765 : : /** Information about each transaction (and chunks). Keeps the "holes" from DepGraph during
766 : : * construction. Indexed by TxIdx. */
767 : : std::vector<TxData> m_tx_data;
768 : : /** Information about each set (chunk, or active dependency top set). Indexed by SetIdx. */
769 : : std::vector<SetInfo<SetType>> m_set_info;
770 : : /** For each chunk, indexed by SetIdx, the set of out-of-chunk reachable transactions, in the
771 : : * upwards (.first) and downwards (.second) direction. */
772 : : std::vector<std::pair<SetType, SetType>> m_reachable;
773 : : /** A FIFO of chunk SetIdxs for chunks that may be improved still. */
774 : : VecDeque<SetIdx> m_suboptimal_chunks;
775 : : /** A FIFO of chunk indexes with a pivot transaction in them, and a flag to indicate their
776 : : * status:
777 : : * - bit 1: currently attempting to move the pivot down, rather than up.
778 : : * - bit 2: this is the second stage, so we have already tried moving the pivot in the other
779 : : * direction.
780 : : */
781 : : VecDeque<std::tuple<SetIdx, TxIdx, unsigned>> m_nonminimal_chunks;
782 : :
783 : : /** The DepGraph we are trying to linearize. */
784 : : const DepGraph<SetType>& m_depgraph;
785 : :
786 : : /** Accounting for the cost of this computation. */
787 : : CostModel m_cost;
788 : :
789 : : /** Pick a random transaction within a set (which must be non-empty). */
790 : 4126099 : TxIdx PickRandomTx(const SetType& tx_idxs) noexcept
791 : : {
792 [ - + ]: 4156387 : Assume(tx_idxs.Any());
793 : 4126099 : unsigned pos = m_rng.randrange<unsigned>(tx_idxs.Count());
794 [ + - + - ]: 9581657 : for (auto tx_idx : tx_idxs) {
[ + - ]
795 [ + + ]: 5485846 : if (pos == 0) return tx_idx;
796 : 1359747 : --pos;
797 : : }
798 : 0 : Assume(false);
799 : 0 : return TxIdx(-1);
800 : : }
801 : :
802 : : /** Find the set of out-of-chunk transactions reachable from tx_idxs, both in upwards and
803 : : * downwards direction. Only used by SanityCheck to verify the precomputed reachable sets in
804 : : * m_reachable that are maintained by Activate/Deactivate. */
805 : 48250 : std::pair<SetType, SetType> GetReachable(const SetType& tx_idxs) const noexcept
806 : : {
807 : 48250 : SetType parents, children;
808 [ + - + + ]: 184864 : for (auto tx_idx : tx_idxs) {
809 : 88364 : const auto& tx_data = m_tx_data[tx_idx];
810 : 88364 : parents |= tx_data.parents;
811 : 88364 : children |= tx_data.children;
812 : : }
813 : 48250 : return {parents - tx_idxs, children - tx_idxs};
814 : : }
815 : :
816 : : /** Make the inactive dependency from child to parent, which must not be in the same chunk
817 : : * already, active. Returns the merged chunk idx. */
818 : 3054499 : SetIdx Activate(TxIdx parent_idx, TxIdx child_idx) noexcept
819 : : {
820 : : m_cost.ActivateBegin();
821 : : // Gather and check information about the parent and child transactions.
822 : 3054499 : auto& parent_data = m_tx_data[parent_idx];
823 : 3054499 : auto& child_data = m_tx_data[child_idx];
824 [ - + ]: 3054499 : Assume(parent_data.children[child_idx]);
825 [ - + ]: 3054499 : Assume(!parent_data.active_children[child_idx]);
826 : : // Get the set index of the chunks the parent and child are currently in. The parent chunk
827 : : // will become the top set of the newly activated dependency, while the child chunk will be
828 : : // grown to become the merged chunk.
829 : 3054499 : auto parent_chunk_idx = parent_data.chunk_idx;
830 : 3054499 : auto child_chunk_idx = child_data.chunk_idx;
831 [ - + ]: 3054499 : Assume(parent_chunk_idx != child_chunk_idx);
832 [ - + ]: 3054499 : Assume(m_chunk_idxs[parent_chunk_idx]);
833 [ - + ]: 3054499 : Assume(m_chunk_idxs[child_chunk_idx]);
834 [ + - ]: 3054499 : auto& top_info = m_set_info[parent_chunk_idx];
835 : 3054499 : auto& bottom_info = m_set_info[child_chunk_idx];
836 : :
837 : : // Consider the following example:
838 : : //
839 : : // A A There are two chunks, ABC and DEF, and the inactive E->C dependency
840 : : // / \ / \ is activated, resulting in a single chunk ABCDEF.
841 : : // B C B C
842 : : // : ==> | Dependency | top set before | top set after | change
843 : : // D E D E B->A | AC | ACDEF | +DEF
844 : : // \ / \ / C->A | AB | AB |
845 : : // F F F->D | D | D |
846 : : // F->E | E | ABCE | +ABC
847 : : //
848 : : // The common pattern here is that any dependency which has the parent or child of the
849 : : // dependency being activated (E->C here) in its top set, will have the opposite part added
850 : : // to it. This is true for B->A and F->E, but not for C->A and F->D.
851 : : //
852 : : // Traverse the old parent chunk top_info (ABC in example), and add bottom_info (DEF) to
853 : : // every dependency's top set which has the parent (C) in it. At the same time, change the
854 : : // chunk_idx for each to be child_chunk_idx, which becomes the set for the merged chunk.
855 [ + - + + ]: 20981079 : for (auto tx_idx : top_info.transactions) {
[ + + ]
856 [ + + ]: 14885703 : auto& tx_data = m_tx_data[tx_idx];
857 : 14885703 : tx_data.chunk_idx = child_chunk_idx;
858 [ + + + + ]: 34487157 : for (auto dep_child_idx : tx_data.active_children) {
[ + + ]
859 : 11831204 : auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
860 [ + + ]: 11831204 : if (dep_top_info.transactions[parent_idx]) dep_top_info |= bottom_info;
861 : : }
862 : : }
863 : : // Traverse the old child chunk bottom_info (DEF in example), and add top_info (ABC) to
864 : : // every dependency's top set which has the child (E) in it.
865 [ + - + + ]: 12800660 : for (auto tx_idx : bottom_info.transactions) {
[ + + ]
866 [ + + ]: 6705284 : auto& tx_data = m_tx_data[tx_idx];
867 [ + + + + ]: 13393266 : for (auto dep_child_idx : tx_data.active_children) {
[ + + ]
868 : 3650785 : auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
869 [ + + ]: 3650785 : if (dep_top_info.transactions[child_idx]) dep_top_info |= top_info;
870 : : }
871 : : }
872 : : // Merge top_info into bottom_info, which becomes the merged chunk.
873 : 3054499 : bottom_info |= top_info;
874 : : // Compute merged sets of reachable transactions from the new chunk, based on the input
875 : : // chunks' reachable sets.
876 : 3054499 : m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first;
877 : 3054499 : m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second;
878 : 3054499 : m_reachable[child_chunk_idx].first -= bottom_info.transactions;
879 : 3054499 : m_reachable[child_chunk_idx].second -= bottom_info.transactions;
880 : : // Make parent chunk the set for the new active dependency.
881 : 3054499 : parent_data.dep_top_idx[child_idx] = parent_chunk_idx;
882 : 3054499 : parent_data.active_children.Set(child_idx);
883 : 3054499 : m_chunk_idxs.Reset(parent_chunk_idx);
884 : : // Return the newly merged chunk.
885 : 3054499 : m_cost.ActivateEnd(/*num_deps=*/bottom_info.transactions.Count() - 1);
886 : 3054499 : return child_chunk_idx;
887 : : }
888 : :
889 : : /** Make a specified active dependency inactive. Returns the created parent and child chunk
890 : : * indexes. */
891 : 751007 : std::pair<SetIdx, SetIdx> Deactivate(TxIdx parent_idx, TxIdx child_idx) noexcept
892 : : {
893 : : m_cost.DeactivateBegin();
894 : : // Gather and check information about the parent transactions.
895 : 751007 : auto& parent_data = m_tx_data[parent_idx];
896 [ - + ]: 751007 : Assume(parent_data.children[child_idx]);
897 [ - + ]: 751007 : Assume(parent_data.active_children[child_idx]);
898 : : // Get the top set of the active dependency (which will become the parent chunk) and the
899 : : // chunk set the transactions are currently in (which will become the bottom chunk).
900 [ - + ]: 751007 : auto parent_chunk_idx = parent_data.dep_top_idx[child_idx];
901 : 751007 : auto child_chunk_idx = parent_data.chunk_idx;
902 [ - + ]: 751007 : Assume(parent_chunk_idx != child_chunk_idx);
903 [ - + ]: 751007 : Assume(m_chunk_idxs[child_chunk_idx]);
904 [ - + ]: 751007 : Assume(!m_chunk_idxs[parent_chunk_idx]); // top set, not a chunk
905 : 751007 : auto& top_info = m_set_info[parent_chunk_idx];
906 : 751007 : auto& bottom_info = m_set_info[child_chunk_idx];
907 : :
908 : : // Remove the active dependency.
909 : 751007 : parent_data.active_children.Reset(child_idx);
910 : 751007 : m_chunk_idxs.Set(parent_chunk_idx);
911 : 751007 : auto ntx = bottom_info.transactions.Count();
912 : : // Subtract the top_info from the bottom_info, as it will become the child chunk.
913 : 751007 : bottom_info -= top_info;
914 : : // See the comment above in Activate(). We perform the opposite operations here, removing
915 : : // instead of adding. Simultaneously, aggregate the top/bottom's union of parents/children.
916 : 751007 : SetType top_parents, top_children;
917 [ + - + + ]: 5108556 : for (auto tx_idx : top_info.transactions) {
[ + + ]
918 [ + + ]: 3614652 : auto& tx_data = m_tx_data[tx_idx];
919 : 3614652 : tx_data.chunk_idx = parent_chunk_idx;
920 [ + + ]: 3688338 : top_parents |= tx_data.parents;
921 : 3614652 : top_children |= tx_data.children;
922 [ + + + + ]: 8158103 : for (auto dep_child_idx : tx_data.active_children) {
[ + + ]
923 : 2863645 : auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
924 [ + + ]: 2863645 : if (dep_top_info.transactions[parent_idx]) dep_top_info -= bottom_info;
925 : : }
926 : : }
927 : 751007 : SetType bottom_parents, bottom_children;
928 [ + - + + ]: 3086089 : for (auto tx_idx : bottom_info.transactions) {
[ + + ]
929 [ + + ]: 1592185 : auto& tx_data = m_tx_data[tx_idx];
930 [ + + ]: 1651141 : bottom_parents |= tx_data.parents;
931 : 1592185 : bottom_children |= tx_data.children;
932 [ + + + + ]: 3037952 : for (auto dep_child_idx : tx_data.active_children) {
[ + + ]
933 : 841178 : auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
934 [ + + ]: 841178 : if (dep_top_info.transactions[child_idx]) dep_top_info -= top_info;
935 : : }
936 : : }
937 : : // Compute the new sets of reachable transactions for each new chunk, based on the
938 : : // top/bottom parents and children computed above.
939 : 751007 : m_reachable[parent_chunk_idx].first = top_parents - top_info.transactions;
940 : 751007 : m_reachable[parent_chunk_idx].second = top_children - top_info.transactions;
941 : 751007 : m_reachable[child_chunk_idx].first = bottom_parents - bottom_info.transactions;
942 : 751007 : m_reachable[child_chunk_idx].second = bottom_children - bottom_info.transactions;
943 : : // Return the two new set idxs.
944 : 751007 : m_cost.DeactivateEnd(/*num_deps=*/ntx - 1);
945 : 751007 : return {parent_chunk_idx, child_chunk_idx};
946 : : }
947 : :
948 : : /** Activate a dependency from the bottom set to the top set, which must exist. Return the
949 : : * index of the merged chunk. */
950 : 3054499 : SetIdx MergeChunks(SetIdx top_idx, SetIdx bottom_idx) noexcept
951 : : {
952 : : m_cost.MergeChunksBegin();
953 [ - + ]: 3054499 : Assume(m_chunk_idxs[top_idx]);
954 [ - + ]: 3054499 : Assume(m_chunk_idxs[bottom_idx]);
955 [ + - ]: 3054499 : auto& top_chunk_info = m_set_info[top_idx];
956 : 3054499 : auto& bottom_chunk_info = m_set_info[bottom_idx];
957 : : // Count the number of dependencies between bottom_chunk and top_chunk, remembering the
958 : : // per-transaction counts so the picking loop below does not need to recompute the
959 : : // intersections.
960 : 3054499 : unsigned num_deps{0};
961 : : std::array<SetIdx, SetType::Size()> counts;
962 [ + - + + ]: 20981079 : for (auto tx_idx : top_chunk_info.transactions) {
[ + + ]
963 : 14885703 : auto& tx_data = m_tx_data[tx_idx];
964 : 14885703 : auto count = (tx_data.children & bottom_chunk_info.transactions).Count();
965 : 14885703 : counts[tx_idx] = count;
966 : 14885703 : num_deps += count;
967 : : }
968 [ - + ]: 3054499 : m_cost.MergeChunksMid(/*num_txns=*/top_chunk_info.transactions.Count());
969 [ - + ]: 3054499 : Assume(num_deps > 0);
970 : : // Uniformly randomly pick one of them and activate it.
971 : 3054499 : unsigned pick = m_rng.randrange(num_deps);
972 : 3054499 : unsigned num_steps = 0;
973 [ + - + - ]: 13568601 : for (auto tx_idx : top_chunk_info.transactions) {
[ + - ]
974 : 10527724 : ++num_steps;
975 [ + + ]: 10527724 : auto count = counts[tx_idx];
976 [ + + ]: 10527724 : if (pick < count) {
977 [ + - ]: 3054499 : auto& tx_data = m_tx_data[tx_idx];
978 [ + - ]: 3054499 : auto intersect = tx_data.children & bottom_chunk_info.transactions;
979 [ + - + - ]: 6108944 : for (auto child_idx : intersect) {
[ + - ]
980 [ + + ]: 3068067 : if (pick == 0) {
981 : 3054499 : m_cost.MergeChunksEnd(/*num_steps=*/num_steps);
982 : 3054499 : return Activate(tx_idx, child_idx);
983 : : }
984 : 13568 : --pick;
985 : : }
986 : 0 : Assume(false);
987 : : break;
988 : : }
989 : 7473225 : pick -= count;
990 : : }
991 : 0 : Assume(false);
992 : 0 : return INVALID_SET_IDX;
993 : : }
994 : :
995 : : /** Activate a dependency from chunk_idx to merge_chunk_idx (if !DownWard), or a dependency
996 : : * from merge_chunk_idx to chunk_idx (if DownWard). Return the index of the merged chunk. */
997 : : template<bool DownWard>
998 : 2985589 : SetIdx MergeChunksDirected(SetIdx chunk_idx, SetIdx merge_chunk_idx) noexcept
999 : : {
1000 : : if constexpr (DownWard) {
1001 : 18546 : return MergeChunks(chunk_idx, merge_chunk_idx);
1002 : : } else {
1003 : 2967043 : return MergeChunks(merge_chunk_idx, chunk_idx);
1004 : : }
1005 : : }
1006 : :
1007 : : /** Determine which chunk to merge chunk_idx with, or INVALID_SET_IDX if none. */
1008 : : template<bool DownWard>
1009 : 12004594 : SetIdx PickMergeCandidate(SetIdx chunk_idx) noexcept
1010 : : {
1011 : : m_cost.PickMergeCandidateBegin();
1012 : : /** Information about the chunk. */
1013 [ - + ]: 12004594 : Assume(m_chunk_idxs[chunk_idx]);
1014 : 12004594 : auto& chunk_info = m_set_info[chunk_idx];
1015 : : // Iterate over all chunks reachable from this one. For those depended-on chunks,
1016 : : // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one.
1017 : : // If multiple equal-feerate candidate chunks to merge with exist, pick a random one
1018 : : // among them.
1019 : :
1020 : : /** The minimum feerate (if downward) or maximum feerate (if upward) to consider when
1021 : : * looking for candidate chunks to merge with. Initially, this is the original chunk's
1022 : : * feerate, but is updated to be the current best candidate whenever one is found. */
1023 : 12004594 : FeeFrac best_other_chunk_feerate = chunk_info.feerate;
1024 : : /** The chunk index for the best candidate chunk to merge with. INVALID_SET_IDX if none. */
1025 : 12004594 : SetIdx best_other_chunk_idx = INVALID_SET_IDX;
1026 : : /** We generate random tiebreak values to pick between equal-feerate candidate chunks.
1027 : : * This variable stores the tiebreak of the current best candidate. */
1028 : 12004594 : uint64_t best_other_chunk_tiebreak{0};
1029 : :
1030 : : /** Which parent/child transactions we still need to process the chunks for. */
1031 : 12004594 : auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first;
1032 : 12004594 : unsigned steps = 0;
1033 [ + + ]: 23108563 : while (todo.Any()) {
1034 : 11027794 : ++steps;
1035 : : // Find a chunk for a transaction in todo, and remove all its transactions from todo.
1036 [ + + ]: 11027794 : auto reached_chunk_idx = m_tx_data[todo.First()].chunk_idx;
1037 : 11027794 : auto& reached_chunk_info = m_set_info[reached_chunk_idx];
1038 [ + + ]: 11027794 : todo -= reached_chunk_info.transactions;
1039 : : // See if it has an acceptable feerate.
1040 [ + + ]: 854590 : auto cmp = DownWard ? ByRatio{best_other_chunk_feerate} <=> ByRatio{reached_chunk_info.feerate}
1041 [ + + ]: 10173204 : : ByRatio{reached_chunk_info.feerate} <=> ByRatio{best_other_chunk_feerate};
1042 [ + + ]: 11027794 : if (cmp > 0) continue;
1043 [ + + ]: 3611172 : uint64_t tiebreak = m_rng.rand64();
1044 [ + + + + ]: 3611172 : if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) {
1045 : 3360715 : best_other_chunk_feerate = reached_chunk_info.feerate;
1046 : 3360715 : best_other_chunk_idx = reached_chunk_idx;
1047 : 3360715 : best_other_chunk_tiebreak = tiebreak;
1048 : : }
1049 : : }
1050 [ - + - + ]: 12004594 : Assume(steps <= m_set_info.size());
1051 : :
1052 : 12004594 : m_cost.PickMergeCandidateEnd(/*num_steps=*/steps);
1053 : 12004594 : return best_other_chunk_idx;
1054 : : }
1055 : :
1056 : : /** Perform an upward or downward merge step, on the specified chunk. Returns the merged chunk,
1057 : : * or INVALID_SET_IDX if no merge took place. */
1058 : : template<bool DownWard>
1059 : 12004594 : SetIdx MergeStep(SetIdx chunk_idx) noexcept
1060 : : {
1061 : 12004594 : auto merge_chunk_idx = PickMergeCandidate<DownWard>(chunk_idx);
1062 [ + + ]: 12004594 : if (merge_chunk_idx == INVALID_SET_IDX) return INVALID_SET_IDX;
1063 : 2985589 : chunk_idx = MergeChunksDirected<DownWard>(chunk_idx, merge_chunk_idx);
1064 [ - + ]: 2985589 : Assume(chunk_idx != INVALID_SET_IDX);
1065 : : return chunk_idx;
1066 : : }
1067 : :
1068 : : /** Perform an upward or downward merge sequence on the specified chunk. */
1069 : : template<bool DownWard>
1070 : 65280 : void MergeSequence(SetIdx chunk_idx) noexcept
1071 : : {
1072 [ - + ]: 65280 : Assume(m_chunk_idxs[chunk_idx]);
1073 : 11602 : while (true) {
1074 : 76882 : auto merged_chunk_idx = MergeStep<DownWard>(chunk_idx);
1075 [ + + ]: 76882 : if (merged_chunk_idx == INVALID_SET_IDX) break;
1076 : 11602 : chunk_idx = merged_chunk_idx;
1077 : : }
1078 : : // Add the chunk to the queue of improvable chunks, if it wasn't already there.
1079 [ + + ]: 65280 : if (!m_suboptimal_idxs[chunk_idx]) {
1080 : 62146 : m_suboptimal_idxs.Set(chunk_idx);
1081 : 62146 : m_suboptimal_chunks.push_back(chunk_idx);
1082 : : }
1083 : 65280 : }
1084 : :
1085 : : /** Split a chunk, and then merge the resulting two chunks to make the graph topological
1086 : : * again. */
1087 : 70226 : void Improve(TxIdx parent_idx, TxIdx child_idx) noexcept
1088 : : {
1089 : : // Deactivate the specified dependency, splitting it into two new chunks: a top containing
1090 : : // the parent, and a bottom containing the child. The top should have a higher feerate.
1091 [ + + ]: 70226 : auto [parent_chunk_idx, child_chunk_idx] = Deactivate(parent_idx, child_idx);
1092 : :
1093 : : // At this point we have exactly two chunks which may violate topology constraints (the
1094 : : // parent chunk and child chunk that were produced by deactivation). We can fix
1095 : : // these using just merge sequences, one upwards and one downwards, avoiding the need for a
1096 : : // full MakeTopological.
1097 [ + + ]: 70226 : const auto& parent_reachable = m_reachable[parent_chunk_idx].first;
1098 [ + + ]: 70226 : const auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
1099 [ + + ]: 70226 : if (parent_reachable.Overlaps(child_chunk_txn)) {
1100 : : // The parent chunk has a dependency on a transaction in the child chunk. In this case,
1101 : : // the parent needs to merge back with the child chunk (a self-merge), and no other
1102 : : // merges are needed. Special-case this, so the overhead of PickMergeCandidate and
1103 : : // MergeSequence can be avoided.
1104 : :
1105 : : // In the self-merge, the roles reverse: the parent chunk (from the split) depends
1106 : : // on the child chunk, so child_chunk_idx is the "top" and parent_chunk_idx is the
1107 : : // "bottom" for MergeChunks.
1108 : 37586 : auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
1109 [ + + ]: 37586 : if (!m_suboptimal_idxs[merged_chunk_idx]) {
1110 : 37573 : m_suboptimal_idxs.Set(merged_chunk_idx);
1111 : 37573 : m_suboptimal_chunks.push_back(merged_chunk_idx);
1112 : : }
1113 : : } else {
1114 : : // Merge the top chunk with lower-feerate chunks it depends on.
1115 : 32640 : MergeSequence<false>(parent_chunk_idx);
1116 : : // Merge the bottom chunk with higher-feerate chunks that depend on it.
1117 : 32640 : MergeSequence<true>(child_chunk_idx);
1118 : : }
1119 : 70226 : }
1120 : :
1121 : : /** Determine the next chunk to optimize, or INVALID_SET_IDX if none. */
1122 : 3558367 : SetIdx PickChunkToOptimize() noexcept
1123 : : {
1124 : : m_cost.PickChunkToOptimizeBegin();
1125 : 3558367 : unsigned steps{0};
1126 [ + + ]: 3560066 : while (!m_suboptimal_chunks.empty()) {
1127 : 3560013 : ++steps;
1128 : : // Pop an entry from the potentially-suboptimal chunk queue.
1129 : 3560013 : SetIdx chunk_idx = m_suboptimal_chunks.front();
1130 [ - + ]: 3560013 : Assume(m_suboptimal_idxs[chunk_idx]);
1131 : 3560013 : m_suboptimal_idxs.Reset(chunk_idx);
1132 : 3560013 : m_suboptimal_chunks.pop_front();
1133 [ + + ]: 3560013 : if (m_chunk_idxs[chunk_idx]) {
1134 : 3558314 : m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
1135 : 3558314 : return chunk_idx;
1136 : : }
1137 : : // If what was popped is not currently a chunk, continue. This may
1138 : : // happen when a split chunk merges in Improve() with one or more existing chunks that
1139 : : // are themselves on the suboptimal queue already.
1140 : : }
1141 : 53 : m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps);
1142 : 53 : return INVALID_SET_IDX;
1143 : : }
1144 : :
1145 : : /** Find a (parent, child) dependency to deactivate in chunk_idx, or (-1, -1) if none. */
1146 : 3558314 : std::pair<TxIdx, TxIdx> PickDependencyToSplit(SetIdx chunk_idx) noexcept
1147 : : {
1148 : : m_cost.PickDependencyToSplitBegin();
1149 [ - + ]: 3558314 : Assume(m_chunk_idxs[chunk_idx]);
1150 [ + - ]: 3558314 : auto& chunk_info = m_set_info[chunk_idx];
1151 : :
1152 : : // Remember the best dependency {par, chl} seen so far.
1153 : 3558314 : std::pair<TxIdx, TxIdx> candidate_dep = {TxIdx(-1), TxIdx(-1)};
1154 : 3558314 : uint64_t candidate_tiebreak = 0;
1155 : : // Iterate over all transactions.
1156 [ + - + + ]: 14613473 : for (auto tx_idx : chunk_info.transactions) {
[ + + ]
1157 [ + + ]: 7520166 : const auto& tx_data = m_tx_data[tx_idx];
1158 : : // Iterate over all active child dependencies of the transaction.
1159 [ + + + + ]: 14571341 : for (auto child_idx : tx_data.active_children) {
[ + + ]
1160 [ + + ]: 3961852 : auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
1161 : : // Skip if this dependency is ineligible (the top chunk that would be created
1162 : : // does not have higher feerate than the chunk it is currently part of).
1163 [ + + ]: 3961852 : auto cmp = ByRatio{dep_top_info.feerate} <=> ByRatio{chunk_info.feerate};
1164 [ + + ]: 3961852 : if (cmp <= 0) continue;
1165 : : // Generate a random tiebreak for this dependency, and reject it if its tiebreak
1166 : : // is worse than the best so far. This means that among all eligible
1167 : : // dependencies, a uniformly random one will be chosen.
1168 : 311942 : uint64_t tiebreak = m_rng.rand64();
1169 [ + + ]: 311942 : if (tiebreak < candidate_tiebreak) continue;
1170 : : // Remember this as our (new) candidate dependency.
1171 : 123197 : candidate_dep = {tx_idx, child_idx};
1172 : 123197 : candidate_tiebreak = tiebreak;
1173 : : }
1174 : : }
1175 : 3558314 : m_cost.PickDependencyToSplitEnd(/*num_txns=*/chunk_info.transactions.Count());
1176 : 3558314 : return candidate_dep;
1177 : : }
1178 : :
1179 : : public:
1180 : : /** Construct a spanning forest for the given DepGraph, with every transaction in its own chunk
1181 : : * (not topological). */
1182 : 1352954 : explicit SpanningForestState(const DepGraph<SetType>& depgraph LIFETIMEBOUND, uint64_t rng_seed, const CostModel& cost = CostModel{}) noexcept :
1183 [ - + ]: 1352954 : m_rng(rng_seed), m_depgraph(depgraph), m_cost(cost)
1184 : : {
1185 : 1352954 : m_cost.InitializeBegin();
1186 : 1352954 : m_transaction_idxs = depgraph.Positions();
1187 [ - + ]: 1352954 : auto num_transactions = m_transaction_idxs.Count();
1188 [ - + ]: 1352954 : m_tx_data.resize(depgraph.PositionRange());
1189 : 1352954 : m_set_info.resize(num_transactions);
1190 : 1352954 : m_reachable.resize(num_transactions);
1191 [ + + ]: 1352954 : m_suboptimal_chunks.reserve(num_transactions);
1192 : 1352954 : size_t num_chunks = 0;
1193 : 1352954 : size_t num_deps = 0;
1194 [ + + + + ]: 9318898 : for (auto tx_idx : m_transaction_idxs) {
[ + + ]
1195 : : // Fill in transaction data.
1196 : 6613639 : auto& tx_data = m_tx_data[tx_idx];
1197 : 6613639 : tx_data.parents = depgraph.GetReducedParents(tx_idx);
1198 [ + + + + ]: 16819049 : for (auto parent_idx : tx_data.parents) {
[ + + ]
1199 : 5675518 : m_tx_data[parent_idx].children.Set(tx_idx);
1200 : : }
1201 : 6613639 : num_deps += tx_data.parents.Count();
1202 : : // Create a singleton chunk for it.
1203 : 6613639 : tx_data.chunk_idx = num_chunks;
1204 : 6613639 : m_set_info[num_chunks++] = SetInfo(depgraph, tx_idx);
1205 : : }
1206 : : // Set the reachable transactions for each chunk to the transactions' parents and children.
1207 [ + + ]: 7966593 : for (SetIdx chunk_idx = 0; chunk_idx < num_transactions; ++chunk_idx) {
1208 : 6613639 : auto& tx_data = m_tx_data[m_set_info[chunk_idx].transactions.First()];
1209 : 6613639 : m_reachable[chunk_idx].first = tx_data.parents;
1210 : 6613639 : m_reachable[chunk_idx].second = tx_data.children;
1211 : : }
1212 [ - + ]: 1352954 : Assume(num_chunks == num_transactions);
1213 : : // Mark all chunk sets as chunks.
1214 : 1352954 : m_chunk_idxs = SetType::Fill(num_chunks);
1215 : 1352954 : m_cost.InitializeEnd(/*num_txns=*/num_chunks, /*num_deps=*/num_deps);
1216 : 1352954 : }
1217 : :
1218 : : /** Load an existing linearization. Must be called immediately after constructor. The result is
1219 : : * topological if the linearization is valid. Otherwise, MakeTopological still needs to be
1220 : : * called. */
1221 : 1351923 : void LoadLinearization(std::span<const DepGraphIndex> old_linearization) noexcept
1222 : : {
1223 : : // Add transactions one by one, in order of existing linearization.
1224 [ + + ]: 7941182 : for (DepGraphIndex tx_idx : old_linearization) {
1225 : 6589259 : auto chunk_idx = m_tx_data[tx_idx].chunk_idx;
1226 : : // Merge the chunk upwards, as long as merging succeeds.
1227 : : while (true) {
1228 : 9539919 : chunk_idx = MergeStep<false>(chunk_idx);
1229 [ + + ]: 9539919 : if (chunk_idx == INVALID_SET_IDX) break;
1230 : : }
1231 : : }
1232 : 1351923 : }
1233 : :
1234 : : /** Make state topological. Can be called after constructing, or after LoadLinearization. */
1235 : 795935 : void MakeTopological() noexcept
1236 : : {
1237 : : m_cost.MakeTopologicalBegin();
1238 [ - + ]: 795935 : Assume(m_suboptimal_chunks.empty());
1239 : : /** What direction to initially merge chunks in; one of the two directions is enough. This
1240 : : * is sufficient because if a non-topological inactive dependency exists between two
1241 : : * chunks, at least one of the two chunks will eventually be processed in a direction that
1242 : : * discovers it - either the lower chunk tries upward, or the upper chunk tries downward.
1243 : : * Chunks that are the result of the merging are always tried in both directions. */
1244 : 795935 : unsigned init_dir = m_rng.randbool();
1245 : : /** Which chunks are the result of merging, and thus need merge attempts in both
1246 : : * directions. */
1247 : 795935 : SetType merged_chunks;
1248 : : // Mark chunks as suboptimal.
1249 : 795935 : m_suboptimal_idxs = m_chunk_idxs;
1250 [ + + + + ]: 3961960 : for (auto chunk_idx : m_chunk_idxs) {
[ - + ]
1251 : 2370143 : m_suboptimal_chunks.emplace_back(chunk_idx);
1252 : : // Randomize the initial order of suboptimal chunks in the queue.
1253 : 2370143 : SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
1254 [ + + ]: 2370143 : if (j != m_suboptimal_chunks.size() - 1) {
1255 : 1262747 : std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1256 : : }
1257 : : }
1258 : 795935 : unsigned chunks = m_chunk_idxs.Count();
1259 : 795935 : unsigned steps = 0;
1260 [ + + ]: 3182836 : while (!m_suboptimal_chunks.empty()) {
1261 : 2386901 : ++steps;
1262 : : // Pop an entry from the potentially-suboptimal chunk queue.
1263 : 2386901 : SetIdx chunk_idx = m_suboptimal_chunks.front();
1264 : 2386901 : m_suboptimal_chunks.pop_front();
1265 [ - + ]: 2386901 : Assume(m_suboptimal_idxs[chunk_idx]);
1266 : 2386901 : m_suboptimal_idxs.Reset(chunk_idx);
1267 : : // If what was popped is not currently a chunk, continue. This may
1268 : : // happen when it was merged with something else since being added.
1269 [ + + ]: 2386901 : if (!m_chunk_idxs[chunk_idx]) continue;
1270 : : /** What direction(s) to attempt merging in. 1=up, 2=down, 3=both. */
1271 [ + + ]: 2378443 : unsigned direction = merged_chunks[chunk_idx] ? 3 : init_dir + 1;
1272 : 2378443 : int flip = m_rng.randbool();
1273 [ + + ]: 7099275 : for (int i = 0; i < 2; ++i) {
1274 [ + + ]: 4744159 : if (i ^ flip) {
1275 [ + + ]: 2372754 : if (!(direction & 1)) continue;
1276 : : // Attempt to merge the chunk upwards.
1277 : 1209804 : auto result_up = MergeStep<false>(chunk_idx);
1278 [ + + ]: 1209804 : if (result_up != INVALID_SET_IDX) {
1279 [ + - ]: 12802 : if (!m_suboptimal_idxs[result_up]) {
1280 : 12802 : m_suboptimal_idxs.Set(result_up);
1281 : 12802 : m_suboptimal_chunks.push_back(result_up);
1282 : : }
1283 : 12802 : merged_chunks.Set(result_up);
1284 : 12802 : break;
1285 : : }
1286 : : } else {
1287 [ + + ]: 2371405 : if (!(direction & 2)) continue;
1288 : : // Attempt to merge the chunk downwards.
1289 : 1177989 : auto result_down = MergeStep<true>(chunk_idx);
1290 [ + + ]: 1177989 : if (result_down != INVALID_SET_IDX) {
1291 [ + + ]: 10525 : if (!m_suboptimal_idxs[result_down]) {
1292 : 3956 : m_suboptimal_idxs.Set(result_down);
1293 : 3956 : m_suboptimal_chunks.push_back(result_down);
1294 : : }
1295 : 10525 : merged_chunks.Set(result_down);
1296 : 10525 : break;
1297 : : }
1298 : : }
1299 : : }
1300 : : }
1301 : 795935 : m_cost.MakeTopologicalEnd(/*num_chunks=*/chunks, /*num_steps=*/steps);
1302 : 795935 : }
1303 : :
1304 : : /** Initialize the data structure for optimization. It must be topological already. */
1305 : 1319831 : void StartOptimizing() noexcept
1306 : : {
1307 : : m_cost.StartOptimizingBegin();
1308 [ - + ]: 1319831 : Assume(m_suboptimal_chunks.empty());
1309 : : // Mark chunks suboptimal.
1310 : 1319831 : m_suboptimal_idxs = m_chunk_idxs;
1311 [ + + + + ]: 6105835 : for (auto chunk_idx : m_chunk_idxs) {
[ + + ]
1312 : 3466822 : m_suboptimal_chunks.push_back(chunk_idx);
1313 : : // Randomize the initial order of suboptimal chunks in the queue.
1314 : 3466822 : SetIdx j = m_rng.randrange<SetIdx>(m_suboptimal_chunks.size());
1315 [ + + ]: 3466822 : if (j != m_suboptimal_chunks.size() - 1) {
1316 : 1600603 : std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1317 : : }
1318 : : }
1319 : 1319831 : m_cost.StartOptimizingEnd(/*num_chunks=*/m_suboptimal_chunks.size());
1320 : 1319831 : }
1321 : :
1322 : : /** Try to improve the forest. Returns false if it is optimal, true otherwise. */
1323 : 3558367 : bool OptimizeStep() noexcept
1324 : : {
1325 : 3558367 : auto chunk_idx = PickChunkToOptimize();
1326 [ + + ]: 3558367 : if (chunk_idx == INVALID_SET_IDX) {
1327 : : // No improvable chunk was found, we are done.
1328 : : return false;
1329 : : }
1330 [ + + ]: 3558314 : auto [parent_idx, child_idx] = PickDependencyToSplit(chunk_idx);
1331 [ + + ]: 3558314 : if (parent_idx == TxIdx(-1)) {
1332 : : // Nothing to improve in chunk_idx. Need to continue with other chunks, if any.
1333 : 3488088 : return !m_suboptimal_chunks.empty();
1334 : : }
1335 : : // Deactivate the found dependency and then make the state topological again with a
1336 : : // sequence of merges.
1337 : 70226 : Improve(parent_idx, child_idx);
1338 : 70226 : return true;
1339 : : }
1340 : :
1341 : : /** Initialize data structure for minimizing the chunks. Can only be called if state is known
1342 : : * to be optimal. OptimizeStep() cannot be called anymore afterwards. */
1343 : 1318291 : void StartMinimizing() noexcept
1344 : : {
1345 : : m_cost.StartMinimizingBegin();
1346 : 1318291 : m_nonminimal_chunks.clear();
1347 [ + + ]: 1318291 : m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
1348 : : // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
1349 : : // direction, to m_nonminimal_chunks.
1350 [ + + + + ]: 6112575 : for (auto chunk_idx : m_chunk_idxs) {
[ + + ]
1351 : 3476642 : TxIdx pivot_idx = PickRandomTx(m_set_info[chunk_idx].transactions);
1352 : 3476642 : m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, m_rng.randbits<1>());
1353 : : // Randomize the initial order of nonminimal chunks in the queue.
1354 : 3476642 : SetIdx j = m_rng.randrange<SetIdx>(m_nonminimal_chunks.size());
1355 [ + + ]: 3476642 : if (j != m_nonminimal_chunks.size() - 1) {
1356 : 1610683 : std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
1357 : : }
1358 : : }
1359 : 1318291 : m_cost.StartMinimizingEnd(/*num_chunks=*/m_nonminimal_chunks.size());
1360 : 1318291 : }
1361 : :
1362 : : /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
1363 : 6364489 : bool MinimizeStep() noexcept
1364 : : {
1365 : : // If the queue of potentially-non-minimal chunks is empty, we are done.
1366 [ + + ]: 6364489 : if (m_nonminimal_chunks.empty()) return false;
1367 : : m_cost.MinimizeStepBegin();
1368 : : // Pop an entry from the potentially-non-minimal chunk queue.
1369 : 5049166 : auto [chunk_idx, pivot_idx, flags] = m_nonminimal_chunks.front();
1370 : 5049166 : m_nonminimal_chunks.pop_front();
1371 [ + - ]: 5049166 : auto& chunk_info = m_set_info[chunk_idx];
1372 : : /** Whether to move the pivot down rather than up. */
1373 : 5049166 : bool move_pivot_down = flags & 1;
1374 : : /** Whether this is already the second stage. */
1375 : 5049166 : bool second_stage = flags & 2;
1376 : :
1377 : : // Find a random dependency whose top and bottom set feerates are equal, and which has
1378 : : // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down).
1379 : 5049166 : std::pair<TxIdx, TxIdx> candidate_dep;
1380 : 5049166 : uint64_t candidate_tiebreak{0};
1381 : 5049166 : bool have_any = false;
1382 : : // Iterate over all transactions.
1383 [ + - + + ]: 20223943 : for (auto tx_idx : chunk_info.transactions) {
[ + + ]
1384 [ + + ]: 10165856 : const auto& tx_data = m_tx_data[tx_idx];
1385 : : // Iterate over all active child dependencies of the transaction.
1386 [ + + + + ]: 18859514 : for (auto child_idx : tx_data.active_children) {
[ + + ]
1387 [ + + ]: 5116690 : const auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]];
1388 : : // Skip if this dependency does not have equal top and bottom set feerates. Note
1389 : : // that the top cannot have higher feerate than the bottom, or OptimizeSteps would
1390 : : // have dealt with it.
1391 [ + + ]: 5116690 : if (ByRatio{dep_top_info.feerate} < ByRatio{chunk_info.feerate}) continue;
1392 : 3270111 : have_any = true;
1393 : : // Skip if this dependency does not have pivot in the right place.
1394 [ + + ]: 3270111 : if (move_pivot_down == dep_top_info.transactions[pivot_idx]) continue;
1395 : : // Remember this as our chosen dependency if it has a better tiebreak.
1396 : 2011751 : uint64_t tiebreak = m_rng.rand64() | 1;
1397 [ + + ]: 2011751 : if (tiebreak > candidate_tiebreak) {
1398 : 927779 : candidate_tiebreak = tiebreak;
1399 : 927779 : candidate_dep = {tx_idx, child_idx};
1400 : : }
1401 : : }
1402 : : }
1403 [ + + ]: 5049166 : m_cost.MinimizeStepMid(/*num_txns=*/chunk_info.transactions.Count());
1404 : : // If no dependencies have equal top and bottom set feerate, this chunk is minimal.
1405 [ + + ]: 5049166 : if (!have_any) return true;
1406 : : // If all found dependencies have the pivot in the wrong place, try moving it in the other
1407 : : // direction. If this was the second stage already, we are done.
1408 [ + + ]: 935713 : if (candidate_tiebreak == 0) {
1409 : : // Switch to other direction, and to second phase.
1410 : 254932 : flags ^= 3;
1411 [ + + ]: 254932 : if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, flags);
1412 : 254932 : return true;
1413 : : }
1414 : :
1415 : : // Otherwise, deactivate the dependency that was found.
1416 [ + + ]: 680781 : auto [parent_chunk_idx, child_chunk_idx] = Deactivate(candidate_dep.first, candidate_dep.second);
1417 : : // Determine if there is a dependency from the new bottom to the new top (opposite from the
1418 : : // dependency that was just deactivated).
1419 [ + + ]: 680781 : auto& parent_reachable = m_reachable[parent_chunk_idx].first;
1420 [ + + ]: 680781 : auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions;
1421 [ + + ]: 680781 : if (parent_reachable.Overlaps(child_chunk_txn)) {
1422 : : // A self-merge is needed. Note that the child_chunk_idx is the top, and
1423 : : // parent_chunk_idx is the bottom, because we activate a dependency in the reverse
1424 : : // direction compared to the deactivation above.
1425 : 31324 : auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx);
1426 : : // Re-insert the chunk into the queue, in the same direction. Note that the chunk_idx
1427 : : // will have changed.
1428 : 31324 : m_nonminimal_chunks.emplace_back(merged_chunk_idx, pivot_idx, flags);
1429 : 31324 : m_cost.MinimizeStepEnd(/*split=*/false);
1430 : : } else {
1431 : : // No self-merge happens, and thus we have found a way to split the chunk. Create two
1432 : : // smaller chunks, and add them to the queue. The one that contains the current pivot
1433 : : // gets to continue with it in the same direction, to minimize the number of times we
1434 : : // alternate direction. If we were in the second phase already, the newly created chunk
1435 : : // inherits that too, because we know no split with the pivot on the other side is
1436 : : // possible already. The new chunk without the current pivot gets a new randomly-chosen
1437 : : // one.
1438 [ + + ]: 649457 : if (move_pivot_down) {
1439 : 300662 : auto parent_pivot_idx = PickRandomTx(m_set_info[parent_chunk_idx].transactions);
1440 : 300662 : m_nonminimal_chunks.emplace_back(parent_chunk_idx, parent_pivot_idx, m_rng.randbits<1>());
1441 : 300662 : m_nonminimal_chunks.emplace_back(child_chunk_idx, pivot_idx, flags);
1442 : : } else {
1443 : 348795 : auto child_pivot_idx = PickRandomTx(m_set_info[child_chunk_idx].transactions);
1444 : 348795 : m_nonminimal_chunks.emplace_back(parent_chunk_idx, pivot_idx, flags);
1445 : 348795 : m_nonminimal_chunks.emplace_back(child_chunk_idx, child_pivot_idx, m_rng.randbits<1>());
1446 : : }
1447 [ + + ]: 649457 : if (m_rng.randbool()) {
1448 : 323797 : std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[m_nonminimal_chunks.size() - 2]);
1449 : : }
1450 : 649457 : m_cost.MinimizeStepEnd(/*split=*/true);
1451 : : }
1452 : : return true;
1453 : : }
1454 : :
1455 : : /** Construct a topologically-valid linearization from the current forest state. Must be
1456 : : * topological. fallback_order is a comparator that defines a strong order for DepGraphIndexes
1457 : : * in this cluster, used to order equal-feerate transactions and chunks.
1458 : : *
1459 : : * Specifically, the resulting order consists of:
1460 : : * - The chunks of the current SFL state, sorted by (in decreasing order of priority):
1461 : : * - topology (parents before children)
1462 : : * - highest chunk feerate first
1463 : : * - smallest chunk size first
1464 : : * - the chunk with the lowest maximum transaction, by fallback_order, first
1465 : : * - The transactions within a chunk, sorted by (in decreasing order of priority):
1466 : : * - topology (parents before children)
1467 : : * - highest tx feerate first
1468 : : * - smallest tx size first
1469 : : * - the lowest transaction, by fallback_order, first
1470 : : */
1471 : 1355497 : std::vector<DepGraphIndex> GetLinearization(const StrongComparator<DepGraphIndex> auto& fallback_order) noexcept
1472 : : {
1473 : : m_cost.GetLinearizationBegin();
1474 : : /** The output linearization. */
1475 : 1355497 : std::vector<DepGraphIndex> ret;
1476 [ - + ]: 1355497 : ret.reserve(m_set_info.size());
1477 : : /** A heap with all chunks (by set index) that can currently be included, sorted by
1478 : : * chunk feerate (high to low), chunk size (small to large), and by least maximum element
1479 : : * according to the fallback order (which is the second pair element). */
1480 : 1355497 : std::array<std::pair<SetIdx, TxIdx>, SetType::Size()> ready_chunks;
1481 : : /** The number of entries of ready_chunks in use. */
1482 : 1355497 : unsigned num_ready_chunks{0};
1483 : : /** For every chunk, indexed by SetIdx, the number of unmet dependencies the chunk has on
1484 : : * other chunks (not including dependencies within the chunk itself). */
1485 : : std::array<TxIdx, SetType::Size()> chunk_deps;
1486 [ - + + + ]: 1355497 : std::fill_n(chunk_deps.begin(), m_set_info.size(), TxIdx{0});
1487 : : /** For every transaction, indexed by TxIdx, the number of unmet dependencies the
1488 : : * transaction has. */
1489 : : std::array<TxIdx, SetType::Size()> tx_deps;
1490 [ - + + + ]: 1355497 : std::fill_n(tx_deps.begin(), m_tx_data.size(), TxIdx{0});
1491 : : /** A heap with all transactions within the current chunk that can be included, sorted by
1492 : : * tx feerate (high to low), tx size (small to large), and fallback order. */
1493 : : std::array<TxIdx, SetType::Size()> ready_tx;
1494 : : /** The number of entries of ready_tx in use. */
1495 : 1355497 : unsigned num_ready_tx{0};
1496 : : // Populate chunk_deps and tx_deps.
1497 : 1355497 : unsigned num_deps{0};
1498 [ + + + + ]: 9397640 : for (TxIdx chl_idx : m_transaction_idxs) {
[ + + ]
1499 : 6687295 : const auto& chl_data = m_tx_data[chl_idx];
1500 : 6687295 : tx_deps[chl_idx] = chl_data.parents.Count();
1501 : 6687295 : num_deps += tx_deps[chl_idx];
1502 : 6687295 : auto chl_chunk_idx = chl_data.chunk_idx;
1503 : 6687295 : auto& chl_chunk_info = m_set_info[chl_chunk_idx];
1504 : 6687295 : chunk_deps[chl_chunk_idx] += (chl_data.parents - chl_chunk_info.transactions).Count();
1505 : : }
1506 : : /** Function to compute the highest element of a chunk, by fallback_order. */
1507 : 5702622 : auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept {
1508 [ + - ]: 4347125 : auto& chunk = m_set_info[chunk_idx].transactions;
1509 : 4347125 : auto it = chunk.begin();
1510 : 4347125 : DepGraphIndex ret = *it;
1511 : 4347125 : ++it;
1512 [ + + ]: 6687295 : while (it != chunk.end()) {
1513 [ + + ]: 2398995 : if (fallback_order(*it, ret) > 0) ret = *it;
[ + - + - ]
1514 : 2340170 : ++it;
1515 : : }
1516 : 4347125 : return ret;
1517 : : };
1518 : : /** Comparison function for the transaction heap. Note that it is a max-heap, so
1519 : : * tx_cmp_fn(a, b) == true means "a appears after b in the linearization". */
1520 : 3710954 : auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept {
1521 : : // Bail out for identical transactions.
1522 [ + - ]: 2355457 : if (a == b) return false;
1523 : : // First sort by increasing transaction feerate.
1524 [ + + ]: 2355457 : auto& a_feerate = m_depgraph.FeeRate(a);
1525 [ + + ]: 2355457 : auto& b_feerate = m_depgraph.FeeRate(b);
1526 [ + + ]: 2355457 : auto feerate_cmp = ByRatio{a_feerate} <=> ByRatio{b_feerate};
1527 [ + + ]: 2355457 : if (feerate_cmp != 0) return feerate_cmp < 0;
1528 : : // Then by decreasing transaction size.
1529 [ + + ]: 1256948 : if (a_feerate.size != b_feerate.size) {
1530 : 156999 : return a_feerate.size > b_feerate.size;
1531 : : }
1532 : : // Tie-break by decreasing fallback_order.
1533 [ + - + - ]: 1155380 : auto fallback_cmp = fallback_order(a, b);
1534 [ + - ]: 1099949 : if (fallback_cmp != 0) return fallback_cmp > 0;
1535 : : // This should not be hit, because fallback_order defines a strong ordering.
1536 : 0 : Assume(false);
1537 : 0 : return a < b;
1538 : : };
1539 : : // Construct a heap with all chunks that have no out-of-chunk dependencies.
1540 : : /** Comparison function for the chunk heap. Note that it is a max-heap, so
1541 : : * chunk_cmp_fn(a, b) == true means "a appears after b in the linearization". */
1542 : 8576335 : auto chunk_cmp_fn = [&](const auto& a, const auto& b) noexcept {
1543 : : // Bail out for identical chunks.
1544 [ + - ]: 7220838 : if (a.first == b.first) return false;
1545 : : // First sort by increasing chunk feerate.
1546 [ + + ]: 7220838 : auto& chunk_feerate_a = m_set_info[a.first].feerate;
1547 [ + + ]: 7220838 : auto& chunk_feerate_b = m_set_info[b.first].feerate;
1548 [ + + ]: 7220838 : auto feerate_cmp = ByRatio{chunk_feerate_a} <=> ByRatio{chunk_feerate_b};
1549 [ + + ]: 7220838 : if (feerate_cmp != 0) return feerate_cmp < 0;
1550 : : // Then by decreasing chunk size.
1551 [ + + ]: 3804026 : if (chunk_feerate_a.size != chunk_feerate_b.size) {
1552 : 347938 : return chunk_feerate_a.size > chunk_feerate_b.size;
1553 : : }
1554 : : // Tie-break by decreasing fallback_order.
1555 [ + - + - ]: 3544328 : auto fallback_cmp = fallback_order(a.second, b.second);
1556 [ + - ]: 3456088 : if (fallback_cmp != 0) return fallback_cmp > 0;
1557 : : // This should not be hit, because fallback_order defines a strong ordering.
1558 : 0 : Assume(false);
1559 : 0 : return a.second < b.second;
1560 : : };
1561 : : // Construct a heap with all chunks that have no out-of-chunk dependencies.
1562 [ + + + + ]: 7057470 : for (SetIdx chunk_idx : m_chunk_idxs) {
[ + + ]
1563 [ + + ]: 4347125 : if (chunk_deps[chunk_idx] == 0) {
1564 : 1778860 : ready_chunks[num_ready_chunks++] = {chunk_idx, max_fallback_fn(chunk_idx)};
1565 : : }
1566 : : }
1567 : 1355497 : std::make_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1568 : : // Pop chunks off the heap.
1569 [ + + ]: 5702622 : while (num_ready_chunks > 0) {
1570 : 4347125 : auto [chunk_idx, _rnd] = ready_chunks.front();
1571 : 4347125 : std::pop_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1572 : 4347125 : --num_ready_chunks;
1573 [ - + ]: 4347125 : Assume(chunk_deps[chunk_idx] == 0);
1574 [ - + ]: 4347125 : const auto& chunk_txn = m_set_info[chunk_idx].transactions;
1575 : : // Build heap of all includable transactions in chunk.
1576 [ - + ]: 4347125 : Assume(num_ready_tx == 0);
1577 [ + - + + ]: 15351257 : for (TxIdx tx_idx : chunk_txn) {
[ + + ]
1578 [ + + ]: 6687295 : if (tx_deps[tx_idx] == 0) ready_tx[num_ready_tx++] = tx_idx;
1579 : : }
1580 [ - + ]: 4347125 : Assume(num_ready_tx > 0);
1581 : 4347125 : std::make_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1582 : : // Pick transactions from the ready heap, append them to linearization, and decrement
1583 : : // dependency counts.
1584 [ + + ]: 11034420 : while (num_ready_tx > 0) {
1585 : : // Pop an element from the tx_ready heap.
1586 : 6687295 : auto tx_idx = ready_tx.front();
1587 : 6687295 : std::pop_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1588 : 6687295 : --num_ready_tx;
1589 : : // Append to linearization.
1590 : 6687295 : ret.push_back(tx_idx);
1591 : : // Decrement dependency counts.
1592 [ + + ]: 6687295 : auto& tx_data = m_tx_data[tx_idx];
1593 [ + + + + ]: 16228767 : for (TxIdx chl_idx : tx_data.children) {
[ + + ]
1594 [ - + ]: 5759523 : auto& chl_data = m_tx_data[chl_idx];
1595 : : // Decrement tx dependency count.
1596 [ - + ]: 5759523 : Assume(tx_deps[chl_idx] > 0);
1597 [ + + + + ]: 5759523 : if (--tx_deps[chl_idx] == 0 && chunk_txn[chl_idx]) {
1598 : : // Child tx has no dependencies left, and is in this chunk. Add it to the tx heap.
1599 : 2078412 : ready_tx[num_ready_tx++] = chl_idx;
1600 : 2078412 : std::push_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn);
1601 : : }
1602 : : // Decrement chunk dependency count if this is out-of-chunk dependency.
1603 [ + + ]: 5759523 : if (chl_data.chunk_idx != chunk_idx) {
1604 [ - + ]: 3233655 : Assume(chunk_deps[chl_data.chunk_idx] > 0);
1605 [ + + ]: 3233655 : if (--chunk_deps[chl_data.chunk_idx] == 0) {
1606 : : // Child chunk has no dependencies left. Add it to the chunk heap.
1607 : 2568265 : ready_chunks[num_ready_chunks++] = {chl_data.chunk_idx, max_fallback_fn(chl_data.chunk_idx)};
1608 : 2568265 : std::push_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn);
1609 : : }
1610 : : }
1611 : : }
1612 : : }
1613 : : }
1614 [ - + - + : 1355497 : Assume(ret.size() == m_set_info.size());
- + ]
1615 [ - + ]: 1355497 : m_cost.GetLinearizationEnd(/*num_txns=*/m_set_info.size(), /*num_deps=*/num_deps);
1616 : 1355497 : return ret;
1617 : : }
1618 : :
1619 : : /** Get the diagram for the current state, which must be topological. Test-only.
1620 : : *
1621 : : * The linearization produced by GetLinearization() is always at least as good (in the
1622 : : * CompareChunks() sense) as this diagram, but may be better.
1623 : : *
1624 : : * After an OptimizeStep(), the diagram will always be at least as good as before. Once
1625 : : * OptimizeStep() returns false, the diagram will be equivalent to that produced by
1626 : : * GetLinearization(), and optimal.
1627 : : *
1628 : : * After a MinimizeStep(), the diagram cannot change anymore (in the CompareChunks() sense),
1629 : : * but its number of segments can increase still. Once MinimizeStep() returns false, the number
1630 : : * of chunks of the produced linearization will match the number of segments in the diagram.
1631 : : */
1632 : 34619 : std::vector<FeeFrac> GetDiagram() const noexcept
1633 : : {
1634 : 34619 : std::vector<FeeFrac> ret;
1635 [ + - + + ]: 609941 : for (auto chunk_idx : m_chunk_idxs) {
1636 : 540703 : ret.push_back(m_set_info[chunk_idx].feerate);
1637 : : }
1638 : 34619 : std::ranges::sort(ret, std::greater<ByRatioNegSize<FeeFrac>>{});
1639 : 34619 : return ret;
1640 : : }
1641 : :
1642 : : /** Determine how much work was performed so far. */
1643 : 11276968 : uint64_t GetCost() const noexcept { return m_cost.GetCost(); }
1644 : :
1645 : : /** Verify internal consistency of the data structure. */
1646 : 3221 : void SanityCheck() const
1647 : : {
1648 : : //
1649 : : // Verify dependency parent/child information, and build list of (active) dependencies.
1650 : : //
1651 : 3221 : std::vector<std::pair<TxIdx, TxIdx>> expected_dependencies;
1652 : 3221 : std::vector<std::pair<TxIdx, TxIdx>> all_dependencies;
1653 : 3221 : std::vector<std::pair<TxIdx, TxIdx>> active_dependencies;
1654 [ + - + + ]: 94806 : for (auto parent_idx : m_depgraph.Positions()) {
1655 [ + + + + ]: 240193 : for (auto child_idx : m_depgraph.GetReducedChildren(parent_idx)) {
1656 [ + - ]: 96977 : expected_dependencies.emplace_back(parent_idx, child_idx);
1657 : : }
1658 : : }
1659 [ + - + + ]: 94806 : for (auto tx_idx : m_transaction_idxs) {
1660 [ + + + + ]: 240193 : for (auto child_idx : m_tx_data[tx_idx].children) {
1661 [ + - ]: 96977 : all_dependencies.emplace_back(tx_idx, child_idx);
1662 [ + + ]: 96977 : if (m_tx_data[tx_idx].active_children[child_idx]) {
1663 [ + - ]: 40114 : active_dependencies.emplace_back(tx_idx, child_idx);
1664 : : }
1665 : : }
1666 : : }
1667 : 3221 : std::ranges::sort(expected_dependencies);
1668 : 3221 : std::ranges::sort(all_dependencies);
1669 [ - + ]: 3221 : assert(expected_dependencies == all_dependencies);
1670 : :
1671 : : //
1672 : : // Verify the chunks against the list of active dependencies
1673 : : //
1674 : 3221 : SetType chunk_cover;
1675 [ + - + + ]: 54692 : for (auto chunk_idx : m_chunk_idxs) {
1676 [ + - ]: 48250 : const auto& chunk_info = m_set_info[chunk_idx];
1677 : : // Verify that transactions in the chunk point back to it. This guarantees
1678 : : // that chunks are non-overlapping.
1679 [ + - + + ]: 184864 : for (auto tx_idx : chunk_info.transactions) {
1680 [ - + ]: 88364 : assert(m_tx_data[tx_idx].chunk_idx == chunk_idx);
1681 : : }
1682 [ - + ]: 48250 : assert(!chunk_cover.Overlaps(chunk_info.transactions));
1683 [ - + ]: 48250 : chunk_cover |= chunk_info.transactions;
1684 : : // Verify the chunk's transaction set: start from an arbitrary chunk transaction,
1685 : : // and for every active dependency, if it contains the parent or child, add the
1686 : : // other. It must have exactly N-1 active dependencies in it, guaranteeing it is
1687 : : // acyclic.
1688 [ - + ]: 48250 : assert(chunk_info.transactions.Any());
1689 : 48250 : SetType expected_chunk = SetType::Singleton(chunk_info.transactions.First());
1690 : : while (true) {
1691 : 61783 : auto old = expected_chunk;
1692 : 61783 : size_t active_dep_count{0};
1693 [ + + ]: 678127 : for (const auto& [par, chl] : active_dependencies) {
1694 [ + + + + ]: 616344 : if (expected_chunk[par] || expected_chunk[chl]) {
1695 : 131488 : expected_chunk.Set(par);
1696 : 131488 : expected_chunk.Set(chl);
1697 : 131488 : ++active_dep_count;
1698 : : }
1699 : : }
1700 [ + + ]: 61783 : if (old == expected_chunk) {
1701 [ - + ]: 48250 : assert(expected_chunk.Count() == active_dep_count + 1);
1702 : : break;
1703 : : }
1704 : : }
1705 [ - + ]: 48250 : assert(chunk_info.transactions == expected_chunk);
1706 : : // Verify the chunk's feerate.
1707 [ + - ]: 48250 : assert(chunk_info.feerate == m_depgraph.FeeRate(chunk_info.transactions));
1708 : : // Verify the chunk's reachable transactions.
1709 [ + - ]: 48250 : assert(m_reachable[chunk_idx] == GetReachable(expected_chunk));
1710 : : // Verify that the chunk's reachable transactions don't include its own transactions.
1711 [ - + ]: 48250 : assert(!m_reachable[chunk_idx].first.Overlaps(chunk_info.transactions));
1712 [ - + ]: 48250 : assert(!m_reachable[chunk_idx].second.Overlaps(chunk_info.transactions));
1713 : : }
1714 : : // Verify that together, the chunks cover all transactions.
1715 [ - + ]: 3221 : assert(chunk_cover == m_depgraph.Positions());
1716 : :
1717 : : //
1718 : : // Verify transaction data.
1719 : : //
1720 [ - + ]: 3221 : assert(m_transaction_idxs == m_depgraph.Positions());
1721 [ + - + + ]: 94806 : for (auto tx_idx : m_transaction_idxs) {
1722 : 88364 : const auto& tx_data = m_tx_data[tx_idx];
1723 : : // Verify it has a valid chunk index, and that chunk includes this transaction.
1724 [ - + ]: 88364 : assert(m_chunk_idxs[tx_data.chunk_idx]);
1725 [ - + ]: 88364 : assert(m_set_info[tx_data.chunk_idx].transactions[tx_idx]);
1726 : : // Verify parents/children.
1727 [ - + ]: 88364 : assert(tx_data.parents == m_depgraph.GetReducedParents(tx_idx));
1728 [ - + ]: 88364 : assert(tx_data.children == m_depgraph.GetReducedChildren(tx_idx));
1729 : : // Verify active_children is a subset of children.
1730 [ - + ]: 88364 : assert(tx_data.active_children.IsSubsetOf(tx_data.children));
1731 : : // Verify each active child's dep_top_idx points to a valid non-chunk set.
1732 [ + + + + ]: 160946 : for (auto child_idx : tx_data.active_children) {
1733 [ - + - + ]: 40114 : assert(tx_data.dep_top_idx[child_idx] < m_set_info.size());
1734 [ - + ]: 40114 : assert(!m_chunk_idxs[tx_data.dep_top_idx[child_idx]]);
1735 : : }
1736 : : }
1737 : :
1738 : : //
1739 : : // Verify active dependencies' top sets.
1740 : : //
1741 [ + + ]: 43335 : for (const auto& [par_idx, chl_idx] : active_dependencies) {
1742 : : // Verify the top set's transactions: it must contain the parent, and for every
1743 : : // active dependency, except the chl_idx->par_idx dependency itself, if it contains the
1744 : : // parent or child, it must contain both. It must have exactly N-1 active dependencies
1745 : : // in it, guaranteeing it is acyclic.
1746 : 40114 : SetType expected_top = SetType::Singleton(par_idx);
1747 : : while (true) {
1748 : 131286 : auto old = expected_top;
1749 : 131286 : size_t active_dep_count{0};
1750 [ + + + + ]: 3047753 : for (const auto& [par2_idx, chl2_idx] : active_dependencies) {
1751 [ + + + + ]: 2916467 : if (par_idx == par2_idx && chl_idx == chl2_idx) continue;
1752 [ + + + + ]: 2785181 : if (expected_top[par2_idx] || expected_top[chl2_idx]) {
1753 : 1052249 : expected_top.Set(par2_idx);
1754 : 1052249 : expected_top.Set(chl2_idx);
1755 : 1052249 : ++active_dep_count;
1756 : : }
1757 : : }
1758 [ + + ]: 131286 : if (old == expected_top) {
1759 [ - + ]: 40114 : assert(expected_top.Count() == active_dep_count + 1);
1760 : : break;
1761 : : }
1762 : : }
1763 [ - + ]: 40114 : assert(!expected_top[chl_idx]);
1764 [ - + ]: 40114 : auto& dep_top_info = m_set_info[m_tx_data[par_idx].dep_top_idx[chl_idx]];
1765 [ - + ]: 40114 : assert(dep_top_info.transactions == expected_top);
1766 : : // Verify the top set's feerate.
1767 [ + - ]: 80228 : assert(dep_top_info.feerate == m_depgraph.FeeRate(dep_top_info.transactions));
1768 : : }
1769 : :
1770 : : //
1771 : : // Verify m_suboptimal_chunks.
1772 : : //
1773 : 3221 : SetType suboptimal_idxs;
1774 [ + + ]: 11102 : for (size_t i = 0; i < m_suboptimal_chunks.size(); ++i) {
1775 : 7881 : auto chunk_idx = m_suboptimal_chunks[i];
1776 [ - + ]: 7881 : assert(!suboptimal_idxs[chunk_idx]);
1777 : 7881 : suboptimal_idxs.Set(chunk_idx);
1778 : : }
1779 [ - + ]: 3221 : assert(m_suboptimal_idxs == suboptimal_idxs);
1780 : :
1781 : : //
1782 : : // Verify m_nonminimal_chunks.
1783 : : //
1784 : 3221 : SetType nonminimal_idxs;
1785 [ + + ]: 14163 : for (size_t i = 0; i < m_nonminimal_chunks.size(); ++i) {
1786 [ - + ]: 10942 : auto [chunk_idx, pivot, flags] = m_nonminimal_chunks[i];
1787 [ - + ]: 10942 : assert(m_tx_data[pivot].chunk_idx == chunk_idx);
1788 [ - + ]: 10942 : assert(!nonminimal_idxs[chunk_idx]);
1789 : 10942 : nonminimal_idxs.Set(chunk_idx);
1790 : : }
1791 [ - + ]: 3221 : assert(nonminimal_idxs.IsSubsetOf(m_chunk_idxs));
1792 : 3221 : }
1793 : : };
1794 : :
1795 : : /** Find or improve a linearization for a cluster.
1796 : : *
1797 : : * @param[in] depgraph Dependency graph of the cluster to be linearized.
1798 : : * @param[in] max_cost Upper bound on the amount of work that will be done.
1799 : : * @param[in] rng_seed A random number seed to control search order. This prevents peers
1800 : : * from predicting exactly which clusters would be hard for us to
1801 : : * linearize.
1802 : : * @param[in] fallback_order A comparator to order transactions, used to sort equal-feerate
1803 : : * chunks and transactions. See SpanningForestState::GetLinearization
1804 : : * for details.
1805 : : * @param[in] old_linearization An existing linearization for the cluster, or empty.
1806 : : * @param[in] is_topological (Only relevant if old_linearization is not empty) Whether
1807 : : * old_linearization is topologically valid.
1808 : : * @return A tuple of:
1809 : : * - The resulting linearization. It is guaranteed to be at least as
1810 : : * good (in the feerate diagram sense) as old_linearization.
1811 : : * - A boolean indicating whether the result is guaranteed to be
1812 : : * optimal with minimal chunks.
1813 : : * - How many optimization steps were actually performed.
1814 : : */
1815 : : template<typename SetType>
1816 : 1352182 : std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(
1817 : : const DepGraph<SetType>& depgraph,
1818 : : uint64_t max_cost,
1819 : : uint64_t rng_seed,
1820 : : const StrongComparator<DepGraphIndex> auto& fallback_order,
1821 : : std::span<const DepGraphIndex> old_linearization = {},
1822 : : bool is_topological = true) noexcept
1823 : : {
1824 : : /** Initialize a spanning forest data structure for this cluster. */
1825 [ + + ]: 1352182 : SpanningForestState forest(depgraph, rng_seed);
1826 [ + + ]: 1352182 : if (!old_linearization.empty()) {
1827 : 1351593 : forest.LoadLinearization(old_linearization);
1828 [ + + ]: 1351593 : if (!is_topological) forest.MakeTopological();
1829 : : } else {
1830 : 589 : forest.MakeTopological();
1831 : : }
1832 : : // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
1833 : : // is found.
1834 [ + + ]: 1352182 : if (forest.GetCost() < max_cost) {
1835 : 1319059 : forest.StartOptimizing();
1836 : : do {
1837 [ + + ]: 3545119 : if (!forest.OptimizeStep()) break;
1838 [ + + ]: 2227258 : } while (forest.GetCost() < max_cost);
1839 : : }
1840 : : // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
1841 : : // minimal.
1842 : 1352182 : bool optimal = false;
1843 [ + + ]: 1352182 : if (forest.GetCost() < max_cost) {
1844 : 1317519 : forest.StartMinimizing();
1845 : : do {
1846 [ + + ]: 6345434 : if (!forest.MinimizeStep()) {
1847 : : optimal = true;
1848 : : break;
1849 : : }
1850 [ + + ]: 5030883 : } while (forest.GetCost() < max_cost);
1851 : : }
1852 : 1352182 : return {forest.GetLinearization(fallback_order), optimal, forest.GetCost()};
1853 : 1352182 : }
1854 : :
1855 : : /** Improve a given linearization.
1856 : : *
1857 : : * @param[in] depgraph Dependency graph of the cluster being linearized.
1858 : : * @param[in,out] linearization On input, an existing linearization for depgraph. On output, a
1859 : : * potentially better linearization for the same graph.
1860 : : *
1861 : : * Postlinearization guarantees:
1862 : : * - The resulting chunks are connected.
1863 : : * - If the input has a tree shape (either all transactions have at most one child, or all
1864 : : * transactions have at most one parent), the result is optimal.
1865 : : * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
1866 : : * optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
1867 : : * as good as L1. This means that replacing transactions with same-size higher-fee transactions
1868 : : * will not worsen linearizations through a "drop conflicts, append new transactions,
1869 : : * postlinearize" process.
1870 : : */
1871 : : template<typename SetType>
1872 [ - + ]: 1351936 : void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization)
1873 : : {
1874 : : // This algorithm performs a number of passes (currently 2); the even ones operate from back to
1875 : : // front, the odd ones from front to back. Each results in an equal-or-better linearization
1876 : : // than the one started from.
1877 : : // - One pass in either direction guarantees that the resulting chunks are connected.
1878 : : // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
1879 : : // guarantee this for graphs where each transaction has at most one child; backward passes
1880 : : // guarantee this for graphs where each transaction has at most one parent).
1881 : : // - Starting with a backward pass guarantees the moved-tree property.
1882 : : //
1883 : : // During an odd (forward) pass, the high-level operation is:
1884 : : // - Start with an empty list of groups L=[].
1885 : : // - For every transaction i in the old linearization, from front to back:
1886 : : // - Append a new group C=[i], containing just i, to the back of L.
1887 : : // - While L has at least one group before C, and the group immediately before C has feerate
1888 : : // lower than C:
1889 : : // - If C depends on P:
1890 : : // - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
1891 : : // - Otherwise:
1892 : : // - Swap P with C, continuing with the now-moved C.
1893 : : // - The output linearization is the concatenation of the groups in L.
1894 : : //
1895 : : // During even (backward) passes, i iterates from the back to the front of the existing
1896 : : // linearization, and new groups are prepended instead of appended to the list L. To enable
1897 : : // more code reuse, both passes append groups, but during even passes the meanings of
1898 : : // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
1899 : : // on output.
1900 : : //
1901 : : // In the implementation below, the groups are represented by singly-linked lists (pointing
1902 : : // from the back to the front), which are themselves organized in a singly-linked circular
1903 : : // list (each group pointing to its predecessor, with a special sentinel group at the front
1904 : : // that points back to the last group).
1905 : : //
1906 : : // Information about transaction t is stored in entries[t + 1], while the sentinel is in
1907 : : // entries[0].
1908 : :
1909 : : /** Index of the sentinel in the entries array below. */
1910 : : static constexpr DepGraphIndex SENTINEL{0};
1911 : : /** Indicator that a group has no previous transaction. */
1912 : : static constexpr DepGraphIndex NO_PREV_TX{0};
1913 : :
1914 : :
1915 : : /** Data structure per transaction entry. */
1916 : 7949620 : struct TxEntry
1917 : : {
1918 : : /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
1919 : : * entry of a group. */
1920 : : DepGraphIndex prev_tx;
1921 : :
1922 : : // The fields below are only used for transactions that are the last one in a group
1923 : : // (referred to as tail transactions below).
1924 : :
1925 : : /** Index of the first transaction in this group, possibly itself. */
1926 : : DepGraphIndex first_tx;
1927 : : /** Index of the last transaction in the previous group. The first group (the sentinel)
1928 : : * points back to the last group here, making it a singly-linked circular list. */
1929 : : DepGraphIndex prev_group;
1930 : : /** All transactions in the group. Empty for the sentinel. */
1931 : : SetType group;
1932 : : /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
1933 : : SetType deps;
1934 : : /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
1935 : : FeeFrac feerate;
1936 : : };
1937 : :
1938 : : // As an example, consider the state corresponding to the linearization [1,0,3,2], with
1939 : : // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
1940 : : //
1941 : : // +-----+
1942 : : // 0<-P-- | 0 S | ---\ Legend:
1943 : : // +-----+ |
1944 : : // ^ | - digit in box: entries index
1945 : : // /--------------F---------+ G | (note: one more than tx value)
1946 : : // v \ | | - S: sentinel group
1947 : : // +-----+ +-----+ +-----+ | (empty feerate)
1948 : : // 0<-P-- | 2 | <--P-- | 1 | <--P-- | 4 T | | - T: tail transaction, contains
1949 : : // +-----+ +-----+ +-----+ | fields beyond prev_tv.
1950 : : // ^ | - P: prev_tx reference
1951 : : // G G - F: first_tx reference
1952 : : // | | - G: prev_group reference
1953 : : // +-----+ |
1954 : : // 0<-P-- | 3 T | <--/
1955 : : // +-----+
1956 : : // ^ |
1957 : : // \-F-/
1958 : : //
1959 : : // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
1960 : : // groups [2] and [3,0,1].
1961 : :
1962 : 1351936 : std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
1963 : :
1964 : : // Perform two passes over the linearization.
1965 [ + + ]: 4055808 : for (int pass = 0; pass < 2; ++pass) {
1966 [ - + ]: 2703872 : int rev = !(pass & 1);
1967 : : // Construct a sentinel group, identifying the start of the list.
1968 : 2703872 : entries[SENTINEL].prev_group = SENTINEL;
1969 [ - + ]: 2703872 : Assume(entries[SENTINEL].feerate.IsEmpty());
1970 : :
1971 : : // Iterate over all elements in the existing linearization.
1972 [ + + ]: 15868156 : for (DepGraphIndex i = 0; i < linearization.size(); ++i) {
1973 : : // Even passes are from back to front; odd passes from front to back.
1974 [ + + ]: 13164284 : DepGraphIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
1975 : : // Construct a new group containing just idx. In even passes, the meaning of
1976 : : // parent/child and high/low feerate are swapped.
1977 : 13164284 : DepGraphIndex cur_group = idx + 1;
1978 [ + + ]: 13164284 : entries[cur_group].group = SetType::Singleton(idx);
1979 [ + + + + ]: 13164284 : entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
1980 : 13164284 : entries[cur_group].feerate = depgraph.FeeRate(idx);
1981 [ + + ]: 13164284 : if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
1982 : 13164284 : entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
1983 : 13164284 : entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
1984 : : // Insert the new group at the back of the groups linked list.
1985 : 13164284 : entries[cur_group].prev_group = entries[SENTINEL].prev_group;
1986 : 13164284 : entries[SENTINEL].prev_group = cur_group;
1987 : :
1988 : : // Start merge/swap cycle.
1989 : 13164284 : DepGraphIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
1990 : 13164284 : DepGraphIndex prev_group = entries[cur_group].prev_group;
1991 : : // Continue as long as the current group has higher feerate than the previous one.
1992 [ + + ]: 17723238 : while (ByRatio{entries[cur_group].feerate} > ByRatio{entries[prev_group].feerate}) {
1993 : : // prev_group/cur_group/next_group refer to (the last transactions of) 3
1994 : : // consecutive entries in groups list.
1995 [ - + ]: 4558954 : Assume(cur_group == entries[next_group].prev_group);
1996 [ - + ]: 4558954 : Assume(prev_group == entries[cur_group].prev_group);
1997 : : // The sentinel has empty feerate, which is neither higher or lower than other
1998 : : // feerates. Thus, the while loop we are in here guarantees that cur_group and
1999 : : // prev_group are not the sentinel.
2000 [ - + ]: 4558954 : Assume(cur_group != SENTINEL);
2001 [ - + ]: 4558954 : Assume(prev_group != SENTINEL);
2002 [ + + ]: 4570717 : if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
2003 : : // There is a dependency between cur_group and prev_group; merge prev_group
2004 : : // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
2005 : : // but become unused.
2006 [ + + ]: 4241088 : entries[cur_group].group |= entries[prev_group].group;
2007 [ + + ]: 4241088 : entries[cur_group].deps |= entries[prev_group].deps;
2008 : 4219040 : entries[cur_group].feerate += entries[prev_group].feerate;
2009 : : // Make the first of the current group point to the tail of the previous group.
2010 : 4219040 : entries[entries[cur_group].first_tx].prev_tx = prev_group;
2011 : : // The first of the previous group becomes the first of the newly-merged group.
2012 : 4219040 : entries[cur_group].first_tx = entries[prev_group].first_tx;
2013 : : // The previous group becomes whatever group was before the former one.
2014 : 4219040 : prev_group = entries[prev_group].prev_group;
2015 : 4219040 : entries[cur_group].prev_group = prev_group;
2016 : : } else {
2017 : : // There is no dependency between cur_group and prev_group; swap them.
2018 : 339914 : DepGraphIndex preprev_group = entries[prev_group].prev_group;
2019 : : // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
2020 : : // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
2021 : 339914 : entries[next_group].prev_group = prev_group;
2022 : 339914 : entries[prev_group].prev_group = cur_group;
2023 : 339914 : entries[cur_group].prev_group = preprev_group;
2024 : : // The current group remains the same, but the groups before/after it have
2025 : : // changed.
2026 : 339914 : next_group = prev_group;
2027 : 339914 : prev_group = preprev_group;
2028 : : }
2029 : : }
2030 : : }
2031 : :
2032 : : // Convert the entries back to linearization (overwriting the existing one).
2033 : 2703872 : DepGraphIndex cur_group = entries[0].prev_group;
2034 : 2703872 : DepGraphIndex done = 0;
2035 [ + + ]: 11649116 : while (cur_group != SENTINEL) {
2036 : 8945244 : DepGraphIndex cur_tx = cur_group;
2037 : : // Traverse the transactions of cur_group (from back to front), and write them in the
2038 : : // same order during odd passes, and reversed (front to back) in even passes.
2039 [ + + ]: 8945244 : if (rev) {
2040 : : do {
2041 [ + + ]: 6582142 : *(linearization.begin() + (done++)) = cur_tx - 1;
2042 [ + + ]: 6582142 : cur_tx = entries[cur_tx].prev_tx;
2043 [ + + ]: 6582142 : } while (cur_tx != NO_PREV_TX);
2044 : : } else {
2045 : : do {
2046 [ + + ]: 6582142 : *(linearization.end() - (++done)) = cur_tx - 1;
2047 [ + + ]: 6582142 : cur_tx = entries[cur_tx].prev_tx;
2048 [ + + ]: 6582142 : } while (cur_tx != NO_PREV_TX);
2049 : : }
2050 : 8945244 : cur_group = entries[cur_group].prev_group;
2051 : : }
2052 [ - + ]: 2703872 : Assume(done == linearization.size());
2053 : : }
2054 : 1351936 : }
2055 : :
2056 : : } // namespace cluster_linearize
2057 : :
2058 : : #endif // BITCOIN_CLUSTER_LINEARIZE_H
|
