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 <utility>
13 : : #include <vector>
14 : :
15 : : #include <memusage.h>
16 : : #include <random.h>
17 : : #include <span.h>
18 : : #include <util/feefrac.h>
19 : : #include <util/vecdeque.h>
20 : :
21 : : namespace cluster_linearize {
22 : :
23 : : /** Data type to represent transaction indices in DepGraphs and the clusters they represent. */
24 : : using DepGraphIndex = uint32_t;
25 : :
26 : : /** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
27 : : * descendants). */
28 : : template<typename SetType>
29 [ + + + - : 249140 : class DepGraph
+ - ][ + - ]
30 : : {
31 : : /** Information about a single transaction. */
32 : : struct Entry
33 : : {
34 : : /** Fee and size of transaction itself. */
35 : 26718 : FeeFrac feerate;
36 : : /** All ancestors of the transaction (including itself). */
37 : 26718 : SetType ancestors;
38 : : /** All descendants of the transaction (including itself). */
39 : 26718 : SetType descendants;
40 : :
41 : : /** Equality operator (primarily for testing purposes). */
42 [ + - + - : 53436 : friend bool operator==(const Entry&, const Entry&) noexcept = default;
- + ]
43 : :
44 : : /** Construct an empty entry. */
45 : 139050 : Entry() noexcept = default;
46 : : /** Construct an entry with a given feerate, ancestor set, descendant set. */
47 : 2008087 : Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
48 : : };
49 : :
50 : : /** Data for each transaction. */
51 : : std::vector<Entry> entries;
52 : :
53 : : /** Which positions are used. */
54 : : SetType m_used;
55 : :
56 : : public:
57 : : /** Equality operator (primarily for testing purposes). */
58 : 1710 : friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
59 : : {
60 [ + - ]: 1710 : if (a.m_used != b.m_used) return false;
61 : : // Only compare the used positions within the entries vector.
62 [ + + + + ]: 30046 : for (auto idx : a.m_used) {
63 [ + - ]: 26718 : if (a.entries[idx] != b.entries[idx]) return false;
64 : : }
65 : : return true;
66 : : }
67 : :
68 : : // Default constructors.
69 : 527483 : DepGraph() noexcept = default;
70 : 24202 : DepGraph(const DepGraph&) noexcept = default;
71 : 0 : DepGraph(DepGraph&&) noexcept = default;
72 : 204731 : DepGraph& operator=(const DepGraph&) noexcept = default;
73 : 253797 : DepGraph& operator=(DepGraph&&) noexcept = default;
74 : :
75 : : /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
76 : : *
77 : : * @param depgraph The original DepGraph that is being remapped.
78 : : *
79 : : * @param mapping A span such that mapping[i] gives the position in the new DepGraph
80 : : * for position i in the old depgraph. Its size must be equal to
81 : : * depgraph.PositionRange(). The value of mapping[i] is ignored if
82 : : * position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
83 : : *
84 : : * @param pos_range The PositionRange() for the new DepGraph. It must equal the largest
85 : : * value in mapping for any used position in depgraph plus 1, or 0 if
86 : : * depgraph.TxCount() == 0.
87 : : *
88 : : * Complexity: O(N^2) where N=depgraph.TxCount().
89 : : */
90 [ - + ]: 5232 : DepGraph(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> mapping, DepGraphIndex pos_range) noexcept : entries(pos_range)
91 : : {
92 [ - + ]: 5232 : Assume(mapping.size() == depgraph.PositionRange());
93 : 10464 : Assume((pos_range == 0) == (depgraph.TxCount() == 0));
94 [ + + ]: 100385 : for (DepGraphIndex i : depgraph.Positions()) {
95 [ - + ]: 95153 : auto new_idx = mapping[i];
96 [ - + ]: 95153 : Assume(new_idx < pos_range);
97 : : // Add transaction.
98 : 95153 : entries[new_idx].ancestors = SetType::Singleton(new_idx);
99 : 95153 : entries[new_idx].descendants = SetType::Singleton(new_idx);
100 : 95153 : m_used.Set(new_idx);
101 : : // Fill in fee and size.
102 : 95153 : entries[new_idx].feerate = depgraph.entries[i].feerate;
103 : : }
104 [ + + ]: 100385 : for (DepGraphIndex i : depgraph.Positions()) {
105 : : // Fill in dependencies by mapping direct parents.
106 : 95153 : SetType parents;
107 [ + + + + ]: 211350 : for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
108 : 95153 : AddDependencies(parents, mapping[i]);
109 : : }
110 : : // Verify that the provided pos_range was correct (no unused positions at the end).
111 [ + + - + ]: 5232 : Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
112 : 5232 : }
113 : :
114 : : /** Get the set of transactions positions in use. Complexity: O(1). */
115 [ + + + + : 10061488 : const SetType& Positions() const noexcept { return m_used; }
+ + + + +
+ + + + +
+ + + + +
- + + +
+ ]
116 : : /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */
117 [ - + - + : 531030 : DepGraphIndex PositionRange() const noexcept { return entries.size(); }
- + - + -
+ ][ - + -
+ - + + +
- + - + -
+ + - - +
+ - - + +
+ ]
118 : : /** Get the number of transactions in the graph. Complexity: O(1). */
119 [ - + ][ + + : 3347950 : auto TxCount() const noexcept { return m_used.Count(); }
+ + + + -
+ + + + +
+ + + + +
+ + + + +
- + ]
120 : : /** Get the feerate of a given transaction i. Complexity: O(1). */
121 [ + - + + ]: 5619664 : const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; }
122 : : /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
123 [ + + + - ]: 12022372 : FeeFrac& FeeRate(DepGraphIndex i) noexcept { return entries[i].feerate; }
[ + - - +
- + + - +
- ]
124 : : /** Get the ancestors of a given transaction i. Complexity: O(1). */
125 [ + - + + : 146312990 : const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; }
- + ][ + +
+ + + + +
- - + + +
+ + + + +
- - + + -
+ + - + -
+ + + -
+ ]
126 : : /** Get the descendants of a given transaction i. Complexity: O(1). */
127 [ + - ][ + + : 15386966 : const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; }
- + + - -
+ ]
128 : :
129 : : /** Add a new unconnected transaction to this transaction graph (in the first available
130 : : * position), and return its DepGraphIndex.
131 : : *
132 : : * Complexity: O(1) (amortized, due to resizing of backing vector).
133 : : */
134 : 2049247 : DepGraphIndex AddTransaction(const FeeFrac& feefrac) noexcept
135 : : {
136 : : static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
137 [ - + ]: 2049247 : auto available = ALL_POSITIONS - m_used;
138 [ - + ]: 2333452 : Assume(available.Any());
139 : 2049247 : DepGraphIndex new_idx = available.First();
140 [ - + + + ]: 2049247 : if (new_idx == entries.size()) {
141 : 2008087 : entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
142 : : } else {
143 : 41160 : entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
144 : : }
145 : 2049247 : m_used.Set(new_idx);
146 : 2049247 : return new_idx;
147 : : }
148 : :
149 : : /** Remove the specified positions from this DepGraph.
150 : : *
151 : : * The specified positions will no longer be part of Positions(), and dependencies with them are
152 : : * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct
153 : : * dependencies), if a parent is removed while a grandparent remains, the grandparent will
154 : : * remain an ancestor.
155 : : *
156 : : * Complexity: O(N) where N=TxCount().
157 : : */
158 : 344752 : void RemoveTransactions(const SetType& del) noexcept
159 : : {
160 : 344752 : m_used -= del;
161 : : // Remove now-unused trailing entries.
162 [ + + - + : 718633 : while (!entries.empty() && !m_used[entries.size() - 1]) {
+ + ]
163 : 373881 : entries.pop_back();
164 : : }
165 : : // Remove the deleted transactions from ancestors/descendants of other transactions. Note
166 : : // that the deleted positions will retain old feerate and dependency information. This does
167 : : // not matter as they will be overwritten by AddTransaction if they get used again.
168 [ + + ]: 10720309 : for (auto& entry : entries) {
169 [ + + ]: 28927209 : entry.ancestors &= m_used;
170 [ + + ]: 28927209 : entry.descendants &= m_used;
171 : : }
172 : 344752 : }
173 : :
174 : : /** Modify this transaction graph, adding multiple parents to a specified child.
175 : : *
176 : : * Complexity: O(N) where N=TxCount().
177 : : */
178 : 2849365 : void AddDependencies(const SetType& parents, DepGraphIndex child) noexcept
179 : : {
180 [ - + ]: 2849365 : Assume(m_used[child]);
181 [ - + ]: 3304682 : Assume(parents.IsSubsetOf(m_used));
182 : : // Compute the ancestors of parents that are not already ancestors of child.
183 [ + + ]: 2849365 : SetType par_anc;
184 [ + + + + ]: 6158715 : for (auto par : parents - Ancestors(child)) {
[ + + ]
185 : 2439606 : par_anc |= Ancestors(par);
186 : : }
187 [ + + ]: 2849365 : par_anc -= Ancestors(child);
188 : : // Bail out if there are no such ancestors.
189 [ + + ]: 2849365 : if (par_anc.None()) return;
190 : : // To each such ancestor, add as descendants the descendants of the child.
191 : 1469346 : const auto& chl_des = entries[child].descendants;
192 [ + + ]: 6932570 : for (auto anc_of_par : par_anc) {
193 : 6003217 : entries[anc_of_par].descendants |= chl_des;
194 : : }
195 : : // To each descendant of the child, add those ancestors.
196 [ + - + + ]: 4568145 : for (auto dec_of_chl : Descendants(child)) {
[ + + ]
197 : 2509355 : entries[dec_of_chl].ancestors |= par_anc;
198 : : }
199 : : }
200 : :
201 : : /** Compute the (reduced) set of parents of node i in this graph.
202 : : *
203 : : * This returns the minimal subset of the parents of i whose ancestors together equal all of
204 : : * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not
205 : : * store the set of parents; this information is inferred from the ancestor sets.
206 : : *
207 : : * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).
208 : : */
209 : 6803298 : SetType GetReducedParents(DepGraphIndex i) const noexcept
210 : : {
211 : 6803298 : SetType parents = Ancestors(i);
212 : 6803298 : parents.Reset(i);
213 [ + + + + ]: 41269040 : for (auto parent : parents) {
[ + + ]
214 [ + + ]: 29717585 : if (parents[parent]) {
215 : 28145330 : parents -= Ancestors(parent);
216 : 28145330 : parents.Set(parent);
217 : : }
218 : : }
219 : 6803298 : return parents;
220 : : }
221 : :
222 : : /** Compute the (reduced) set of children of node i in this graph.
223 : : *
224 : : * This returns the minimal subset of the children of i whose descendants together equal all of
225 : : * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not
226 : : * store the set of children; this information is inferred from the descendant sets.
227 : : *
228 : : * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).
229 : : */
230 : 179588 : SetType GetReducedChildren(DepGraphIndex i) const noexcept
231 : : {
232 : 179588 : SetType children = Descendants(i);
233 : 179588 : children.Reset(i);
234 [ + + + + ]: 1238245 : for (auto child : children) {
235 [ + + ]: 933961 : if (children[child]) {
236 : 314570 : children -= Descendants(child);
237 : 314570 : children.Set(child);
238 : : }
239 : : }
240 : 179588 : return children;
241 : : }
242 : :
243 : : /** Compute the aggregate feerate of a set of nodes in this graph.
244 : : *
245 : : * Complexity: O(N) where N=elems.Count().
246 : : **/
247 : 27337557 : FeeFrac FeeRate(const SetType& elems) const noexcept
248 : : {
249 : 27337557 : FeeFrac ret;
250 [ + - + + ]: 532697521 : for (auto pos : elems) ret += entries[pos].feerate;
[ + + ]
251 : 27337557 : return ret;
252 : : }
253 : :
254 : : /** Get the connected component within the subset "todo" that contains tx (which must be in
255 : : * todo).
256 : : *
257 : : * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
258 : : * of the other in the entire graph (so not just within `todo`), or transitively there is a
259 : : * path of transactions connecting them. This does mean that if `todo` contains a transaction
260 : : * and a grandparent, but misses the parent, they will still be part of the same component.
261 : : *
262 : : * Complexity: O(ret.Count()).
263 : : */
264 : 6528440 : SetType GetConnectedComponent(const SetType& todo, DepGraphIndex tx) const noexcept
265 : : {
266 [ - + ]: 6528440 : Assume(todo[tx]);
267 [ - + ]: 12714139 : Assume(todo.IsSubsetOf(m_used));
268 : 6528440 : auto to_add = SetType::Singleton(tx);
269 : 6528440 : SetType ret;
270 : : do {
271 : 14097186 : SetType old = ret;
272 [ + - + + ]: 40134480 : for (auto add : to_add) {
[ + + ]
273 : 48002054 : ret |= Descendants(add);
274 : 48002054 : ret |= Ancestors(add);
275 : : }
276 [ + + ]: 14097186 : ret &= todo;
277 : 14097186 : to_add = ret - old;
278 [ + + ]: 27360766 : } while (to_add.Any());
279 : 6528440 : return ret;
280 : : }
281 : :
282 : : /** Find some connected component within the subset "todo" of this graph.
283 : : *
284 : : * Specifically, this finds the connected component which contains the first transaction of
285 : : * todo (if any).
286 : : *
287 : : * Complexity: O(ret.Count()).
288 : : */
289 [ + + ]: 5378731 : SetType FindConnectedComponent(const SetType& todo) const noexcept
290 : : {
291 [ + + ]: 5378731 : if (todo.None()) return todo;
292 : 5371231 : return GetConnectedComponent(todo, todo.First());
293 : : }
294 : :
295 : : /** Determine if a subset is connected.
296 : : *
297 : : * Complexity: O(subset.Count()).
298 : : */
299 : 1964911 : bool IsConnected(const SetType& subset) const noexcept
300 : : {
301 [ + + ]: 1964911 : return FindConnectedComponent(subset) == subset;
302 : : }
303 : :
304 : : /** Determine if this entire graph is connected.
305 : : *
306 : : * Complexity: O(TxCount()).
307 : : */
308 : 367 : bool IsConnected() const noexcept { return IsConnected(m_used); }
309 : :
310 : : /** Append the entries of select to list in a topologically valid order.
311 : : *
312 : : * Complexity: O(select.Count() * log(select.Count())).
313 : : */
314 [ - + ]: 14003 : void AppendTopo(std::vector<DepGraphIndex>& list, const SetType& select) const noexcept
315 : : {
316 : 14003 : DepGraphIndex old_len = list.size();
317 [ + - + + ]: 57043 : for (auto i : select) list.push_back(i);
318 : 14003 : std::sort(list.begin() + old_len, list.end(), [&](DepGraphIndex a, DepGraphIndex b) noexcept {
319 [ + + ]: 69387 : const auto a_anc_count = entries[a].ancestors.Count();
320 : 69387 : const auto b_anc_count = entries[b].ancestors.Count();
321 [ + + ]: 69387 : if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
322 : 20563 : return a < b;
323 : : });
324 : 14003 : }
325 : :
326 : : /** Check if this graph is acyclic. */
327 : 38702 : bool IsAcyclic() const noexcept
328 : : {
329 [ + + + + ]: 357778 : for (auto i : Positions()) {
330 [ + + ]: 280757 : if ((Ancestors(i) & Descendants(i)) != SetType::Singleton(i)) {
331 : : return false;
332 : : }
333 : : }
334 : : return true;
335 : : }
336 : :
337 : : unsigned CountDependencies() const noexcept
338 : : {
339 : : unsigned ret = 0;
340 : : for (auto i : Positions()) {
341 : : ret += GetReducedParents(i).Count();
342 : : }
343 : : return ret;
344 : : }
345 : :
346 : : /** Reduce memory usage if possible. No observable effect. */
347 : 709996 : void Compact() noexcept
348 : : {
349 [ - + ]: 709996 : entries.shrink_to_fit();
350 : : }
351 : :
352 : 1626891 : size_t DynamicMemoryUsage() const noexcept
353 : : {
354 [ - + ][ - + : 1661918 : return memusage::DynamicUsage(entries);
- + - + ]
355 : : }
356 : : };
357 : :
358 : : /** A set of transactions together with their aggregate feerate. */
359 : : template<typename SetType>
360 : : struct SetInfo
361 : : {
362 : : /** The transactions in the set. */
363 : 459 : SetType transactions;
364 : : /** Their combined fee and size. */
365 : 459 : FeeFrac feerate;
366 : :
367 : : /** Construct a SetInfo for the empty set. */
368 : 5820882 : SetInfo() noexcept = default;
369 : :
370 : : /** Construct a SetInfo for a specified set and feerate. */
371 : 347215 : SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
372 : :
373 : : /** Construct a SetInfo for a given transaction in a depgraph. */
374 : 8770325 : explicit SetInfo(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept :
375 : 8770325 : transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
376 : :
377 : : /** Construct a SetInfo for a set of transactions in a depgraph. */
378 : 27258835 : explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
379 : 27258835 : transactions(txn), feerate(depgraph.FeeRate(txn)) {}
380 : :
381 : : /** Add a transaction to this SetInfo (which must not yet be in it). */
382 : 4719 : void Set(const DepGraph<SetType>& depgraph, DepGraphIndex pos) noexcept
383 : : {
384 [ - + ]: 4719 : Assume(!transactions[pos]);
385 : 4719 : transactions.Set(pos);
386 : 4719 : feerate += depgraph.FeeRate(pos);
387 : 4719 : }
388 : :
389 : : /** Add the transactions of other to this SetInfo (no overlap allowed). */
390 : 13356281 : SetInfo& operator|=(const SetInfo& other) noexcept
391 : : {
392 [ - + ]: 15226810 : Assume(!transactions.Overlaps(other.transactions));
393 : 13356281 : transactions |= other.transactions;
394 : 13356281 : feerate += other.feerate;
395 : 13356281 : return *this;
396 : : }
397 : :
398 : : /** Remove the transactions of other from this SetInfo (which must be a subset). */
399 : 1284104 : SetInfo& operator-=(const SetInfo& other) noexcept
400 : : {
401 [ - + ]: 1292334 : Assume(other.transactions.IsSubsetOf(transactions));
402 : 1284104 : transactions -= other.transactions;
403 : 1284104 : feerate -= other.feerate;
404 : 1284104 : return *this;
405 : : }
406 : :
407 : : /** Compute the difference between this and other SetInfo (which must be a subset). */
408 : 354347 : SetInfo operator-(const SetInfo& other) const noexcept
409 : : {
410 [ - + ]: 356927 : Assume(other.transactions.IsSubsetOf(transactions));
411 : 354347 : return {transactions - other.transactions, feerate - other.feerate};
412 : : }
413 : :
414 : : /** Swap two SetInfo objects. */
415 : : friend void swap(SetInfo& a, SetInfo& b) noexcept
416 : : {
417 : : swap(a.transactions, b.transactions);
418 : : swap(a.feerate, b.feerate);
419 : : }
420 : :
421 : : /** Permit equality testing. */
422 [ + - + - ]: 918 : friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
423 : : };
424 : :
425 : : /** Compute the chunks of linearization as SetInfos. */
426 : : template<typename SetType>
427 : 930410 : std::vector<SetInfo<SetType>> ChunkLinearizationInfo(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
428 : : {
429 : 930410 : std::vector<SetInfo<SetType>> ret;
430 [ + + ]: 9700735 : for (DepGraphIndex i : linearization) {
431 : : /** The new chunk to be added, initially a singleton. */
432 : 8770325 : SetInfo<SetType> new_chunk(depgraph, i);
433 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
434 [ + + + + ]: 12909034 : while (!ret.empty() && new_chunk.feerate >> ret.back().feerate) {
435 : 4138709 : new_chunk |= ret.back();
436 : 4138709 : ret.pop_back();
437 : : }
438 : : // Actually move that new chunk into the chunking.
439 : 8770325 : ret.emplace_back(std::move(new_chunk));
440 : : }
441 : 930410 : return ret;
442 : : }
443 : :
444 : : /** Compute the feerates of the chunks of linearization. Identical to ChunkLinearizationInfo, but
445 : : * only returns the chunk feerates, not the corresponding transaction sets. */
446 : : template<typename SetType>
447 : 1137335 : std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, std::span<const DepGraphIndex> linearization) noexcept
448 : : {
449 : 1137335 : std::vector<FeeFrac> ret;
450 [ + + ]: 8656488 : for (DepGraphIndex i : linearization) {
451 : : /** The new chunk to be added, initially a singleton. */
452 : 7519153 : auto new_chunk = depgraph.FeeRate(i);
453 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
454 [ + + + + ]: 11299769 : while (!ret.empty() && new_chunk >> ret.back()) {
455 : 3780616 : new_chunk += ret.back();
456 : 3780616 : ret.pop_back();
457 : : }
458 : : // Actually move that new chunk into the chunking.
459 : 7519153 : ret.push_back(std::move(new_chunk));
460 : : }
461 : 1137335 : return ret;
462 : : }
463 : :
464 : : /** Class to represent the internal state of the spanning-forest linearization (SFL) algorithm.
465 : : *
466 : : * At all times, each dependency is marked as either "active" or "inactive". The subset of active
467 : : * dependencies is the state of the SFL algorithm. The implementation maintains several other
468 : : * values to speed up operations, but everything is ultimately a function of what that subset of
469 : : * active dependencies is.
470 : : *
471 : : * Given such a subset, define a chunk as the set of transactions that are connected through active
472 : : * dependencies (ignoring their parent/child direction). Thus, every state implies a particular
473 : : * partitioning of the graph into chunks (including potential singletons). In the extreme, each
474 : : * transaction may be in its own chunk, or in the other extreme all transactions may form a single
475 : : * chunk. A chunk's feerate is its total fee divided by its total size.
476 : : *
477 : : * The algorithm consists of switching dependencies between active and inactive. The final
478 : : * linearization that is produced at the end consists of these chunks, sorted from high to low
479 : : * feerate, each individually sorted in an arbitrary but topological (= no child before parent)
480 : : * way.
481 : : *
482 : : * We define four quality properties the state can have:
483 : : *
484 : : * - acyclic: The state is acyclic whenever no cycle of active dependencies exists within the
485 : : * graph, ignoring the parent/child direction. This is equivalent to saying that within
486 : : * each chunk the set of active dependencies form a tree, and thus the overall set of
487 : : * active dependencies in the graph form a spanning forest, giving the algorithm its
488 : : * name. Being acyclic is also equivalent to every chunk of N transactions having
489 : : * exactly N-1 active dependencies.
490 : : *
491 : : * For example in a diamond graph, D->{B,C}->A, the 4 dependencies cannot be
492 : : * simultaneously active. If at least one is inactive, the state is acyclic.
493 : : *
494 : : * The algorithm maintains an acyclic state at *all* times as an invariant. This implies
495 : : * that activating a dependency always corresponds to merging two chunks, and that
496 : : * deactivating one always corresponds to splitting two chunks.
497 : : *
498 : : * - topological: We say the state is topological whenever it is acyclic and no inactive dependency
499 : : * exists between two distinct chunks such that the child chunk has higher or equal
500 : : * feerate than the parent chunk.
501 : : *
502 : : * The relevance is that whenever the state is topological, the produced output
503 : : * linearization will be topological too (i.e., not have children before parents).
504 : : * Note that the "or equal" part of the definition matters: if not, one can end up
505 : : * in a situation with mutually-dependent equal-feerate chunks that cannot be
506 : : * linearized. For example C->{A,B} and D->{A,B}, with C->A and D->B active. The AC
507 : : * chunk depends on DB through C->B, and the BD chunk depends on AC through D->A.
508 : : * Merging them into a single ABCD chunk fixes this.
509 : : *
510 : : * The algorithm attempts to keep the state topological as much as possible, so it
511 : : * can be interrupted to produce an output whenever, but will sometimes need to
512 : : * temporarily deviate from it when improving the state.
513 : : *
514 : : * - optimal: For every active dependency, define its top and bottom set as the set of transactions
515 : : * in the chunks that would result if the dependency were deactivated; the top being the
516 : : * one with the dependency's parent, and the bottom being the one with the child. Note
517 : : * that due to acyclicity, every deactivation splits a chunk exactly in two.
518 : : *
519 : : * We say the state is optimal whenever it is topological and it has no active
520 : : * dependency whose top feerate is strictly higher than its bottom feerate. The
521 : : * relevance is that it can be proven that whenever the state is optimal, the produced
522 : : * linearization will also be optimal (in the convexified feerate diagram sense). It can
523 : : * also be proven that for every graph at least one optimal state exists.
524 : : *
525 : : * Note that it is possible for the SFL state to not be optimal, but the produced
526 : : * linearization to still be optimal. This happens when the chunks of a state are
527 : : * identical to those of an optimal state, but the exact set of active dependencies
528 : : * within a chunk differ in such a way that the state optimality condition is not
529 : : * satisfied. Thus, the state being optimal is more a "the eventual output is *known*
530 : : * to be optimal".
531 : : *
532 : : * - minimal: We say the state is minimal when it is:
533 : : * - acyclic
534 : : * - topological, except that inactive dependencies between equal-feerate chunks are
535 : : * allowed as long as they do not form a loop.
536 : : * - like optimal, no active dependencies whose top feerate is strictly higher than
537 : : * the bottom feerate are allowed.
538 : : * - no chunk contains a proper non-empty subset which includes all its own in-chunk
539 : : * dependencies of the same feerate as the chunk itself.
540 : : *
541 : : * A minimal state effectively corresponds to an optimal state, where every chunk has
542 : : * been split into its minimal equal-feerate components.
543 : : *
544 : : * The algorithm terminates whenever a minimal state is reached.
545 : : *
546 : : *
547 : : * This leads to the following high-level algorithm:
548 : : * - Start with all dependencies inactive, and thus all transactions in their own chunk. This is
549 : : * definitely acyclic.
550 : : * - Activate dependencies (merging chunks) until the state is topological.
551 : : * - Loop until optimal (no dependencies with higher-feerate top than bottom), or time runs out:
552 : : * - Deactivate a violating dependency, potentially making the state non-topological.
553 : : * - Activate other dependencies to make the state topological again.
554 : : * - If there is time left and the state is optimal:
555 : : * - Attempt to split chunks into equal-feerate parts without mutual dependencies between them.
556 : : * When this succeeds, recurse into them.
557 : : * - If no such chunks can be found, the state is minimal.
558 : : * - Output the chunks from high to low feerate, each internally sorted topologically.
559 : : *
560 : : * When merging, we always either:
561 : : * - Merge upwards: merge a chunk with the lowest-feerate other chunk it depends on, among those
562 : : * with lower or equal feerate than itself.
563 : : * - Merge downwards: merge a chunk with the highest-feerate other chunk that depends on it, among
564 : : * those with higher or equal feerate than itself.
565 : : *
566 : : * Using these strategies in the improvement loop above guarantees that the output linearization
567 : : * after a deactivate + merge step is never worse or incomparable (in the convexified feerate
568 : : * diagram sense) than the output linearization that would be produced before the step. With that,
569 : : * we can refine the high-level algorithm to:
570 : : * - Start with all dependencies inactive.
571 : : * - Perform merges as described until none are possible anymore, making the state topological.
572 : : * - Loop until optimal or time runs out:
573 : : * - Pick a dependency D to deactivate among those with higher feerate top than bottom.
574 : : * - Deactivate D, causing the chunk it is in to split into top T and bottom B.
575 : : * - Do an upwards merge of T, if possible. If so, repeat the same with the merged result.
576 : : * - Do a downwards merge of B, if possible. If so, repeat the same with the merged result.
577 : : * - Split chunks further to obtain a minimal state, see below.
578 : : * - Output the chunks from high to low feerate, each internally sorted topologically.
579 : : *
580 : : * Instead of performing merges arbitrarily to make the initial state topological, it is possible
581 : : * to do so guided by an existing linearization. This has the advantage that the state's would-be
582 : : * output linearization is immediately as good as the existing linearization it was based on:
583 : : * - Start with all dependencies inactive.
584 : : * - For each transaction t in the existing linearization:
585 : : * - Find the chunk C that transaction is in (which will be singleton).
586 : : * - Do an upwards merge of C, if possible. If so, repeat the same with the merged result.
587 : : * No downwards merges are needed in this case.
588 : : *
589 : : * After reaching an optimal state, it can be transformed into a minimal state by attempting to
590 : : * split chunks further into equal-feerate parts. To do so, pick a specific transaction in each
591 : : * chunk (the pivot), and rerun the above split-then-merge procedure again:
592 : : * - first, while pretending the pivot transaction has an infinitesimally higher (or lower) fee
593 : : * than it really has. If a split exists with the pivot in the top part (or bottom part), this
594 : : * will find it.
595 : : * - if that fails to split, repeat while pretending the pivot transaction has an infinitesimally
596 : : * lower (or higher) fee. If a split exists with the pivot in the bottom part (or top part), this
597 : : * will find it.
598 : : * - if either succeeds, repeat the procedure for the newly found chunks to split them further.
599 : : * If not, the chunk is already minimal.
600 : : * If the chunk can be split into equal-feerate parts, then the pivot must exist in either the top
601 : : * or bottom part of that potential split. By trying both with the same pivot, if a split exists,
602 : : * it will be found.
603 : : *
604 : : * What remains to be specified are a number of heuristics:
605 : : *
606 : : * - How to decide which chunks to merge:
607 : : * - The merge upwards and downward rules specify that the lowest-feerate respectively
608 : : * highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate
609 : : * candidates, a uniformly random one among them is picked.
610 : : *
611 : : * - How to decide what dependency to activate (when merging chunks):
612 : : * - After picking two chunks to be merged (see above), a uniformly random dependency between the
613 : : * two chunks is activated.
614 : : *
615 : : * - How to decide which chunk to find a dependency to split in:
616 : : * - A round-robin queue of chunks to improve is maintained. The initial ordering of this queue
617 : : * is uniformly randomly permuted.
618 : : *
619 : : * - How to decide what dependency to deactivate (when splitting chunks):
620 : : * - Inside the selected chunk (see above), among the dependencies whose top feerate is strictly
621 : : * higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency
622 : : * is deactivated.
623 : : *
624 : : * - How to decide the exact output linearization:
625 : : * - When there are multiple equal-feerate chunks with no dependencies between them, output a
626 : : * uniformly random one among the ones with no missing dependent chunks first.
627 : : * - Within chunks, repeatedly pick a uniformly random transaction among those with no missing
628 : : * dependencies.
629 : : */
630 : : template<typename SetType>
631 : : class SpanningForestState
632 : : {
633 : : private:
634 : : /** Internal RNG. */
635 : : InsecureRandomContext m_rng;
636 : :
637 : : /** Data type to represent indexing into m_tx_data. */
638 : : using TxIdx = uint32_t;
639 : : /** Data type to represent indexing into m_dep_data. */
640 : : using DepIdx = uint32_t;
641 : :
642 : : /** Structure with information about a single transaction. For transactions that are the
643 : : * representative for the chunk they are in, this also stores chunk information. */
644 : 11571404 : struct TxData {
645 : : /** The dependencies to children of this transaction. Immutable after construction. */
646 : : std::vector<DepIdx> child_deps;
647 : : /** The set of parent transactions of this transaction. Immutable after construction. */
648 : : SetType parents;
649 : : /** The set of child transactions of this transaction. Immutable after construction. */
650 : : SetType children;
651 : : /** Which transaction holds the chunk_setinfo for the chunk this transaction is in
652 : : * (the representative for the chunk). */
653 : : TxIdx chunk_rep;
654 : : /** (Only if this transaction is the representative for the chunk it is in) the total
655 : : * chunk set and feerate. */
656 : : SetInfo<SetType> chunk_setinfo;
657 : : };
658 : :
659 : : /** Structure with information about a single dependency. */
660 : 5479733 : struct DepData {
661 : : /** Whether this dependency is active. */
662 : : bool active;
663 : : /** What the parent and child transactions are. Immutable after construction. */
664 : : TxIdx parent, child;
665 : : /** (Only if this dependency is active) the would-be top chunk and its feerate that would
666 : : * be formed if this dependency were to be deactivated. */
667 : : SetInfo<SetType> top_setinfo;
668 : : };
669 : :
670 : : /** The set of all TxIdx's of transactions in the cluster indexing into m_tx_data. */
671 : : SetType m_transaction_idxs;
672 : : /** Information about each transaction (and chunks). Keeps the "holes" from DepGraph during
673 : : * construction. Indexed by TxIdx. */
674 : : std::vector<TxData> m_tx_data;
675 : : /** Information about each dependency. Indexed by DepIdx. */
676 : : std::vector<DepData> m_dep_data;
677 : : /** A FIFO of chunk representatives of chunks that may be improved still. */
678 : : VecDeque<TxIdx> m_suboptimal_chunks;
679 : : /** A FIFO of chunk representatives with a pivot transaction in them, and a flag to indicate
680 : : * their status:
681 : : * - bit 1: currently attempting to move the pivot down, rather than up.
682 : : * - bit 2: this is the second stage, so we have already tried moving the pivot in the other
683 : : * direction.
684 : : */
685 : : VecDeque<std::tuple<TxIdx, TxIdx, unsigned>> m_nonminimal_chunks;
686 : :
687 : : /** The number of updated transactions in activations/deactivations. */
688 : : uint64_t m_cost{0};
689 : :
690 : : /** Pick a random transaction within a set (which must be non-empty). */
691 : 3048824 : TxIdx PickRandomTx(const SetType& tx_idxs) noexcept
692 : : {
693 [ - + ]: 3072039 : Assume(tx_idxs.Any());
694 : 3048824 : unsigned pos = m_rng.randrange<unsigned>(tx_idxs.Count());
695 [ + - + - ]: 7502957 : for (auto tx_idx : tx_idxs) {
[ + - ]
696 [ + + ]: 4477348 : if (pos == 0) return tx_idx;
697 : 1428524 : --pos;
698 : : }
699 : 0 : Assume(false);
700 : 0 : return TxIdx(-1);
701 : : }
702 : :
703 : : /** Update a chunk:
704 : : * - All transactions have their chunk representative set to `chunk_rep`.
705 : : * - All dependencies which have `query` in their top_setinfo get `dep_change` added to it
706 : : * (if `!Subtract`) or removed from it (if `Subtract`).
707 : : */
708 : : template<bool Subtract>
709 : 6753086 : void UpdateChunk(const SetType& chunk, TxIdx query, TxIdx chunk_rep, const SetInfo<SetType>& dep_change) noexcept
710 : : {
711 : : // Iterate over all the chunk's transactions.
712 [ + - + + ]: 37474440 : for (auto tx_idx : chunk) {
[ + + ]
713 [ - + ]: 23996846 : auto& tx_data = m_tx_data[tx_idx];
714 : : // Update the chunk representative.
715 : 23996846 : tx_data.chunk_rep = chunk_rep;
716 : : // Iterate over all active dependencies with tx_idx as parent. Combined with the outer
717 : : // loop this iterates over all internal active dependencies of the chunk.
718 [ - + ]: 23996846 : auto child_deps = std::span{tx_data.child_deps};
719 [ + + ]: 55625755 : for (auto dep_idx : child_deps) {
720 [ - + ]: 31628909 : auto& dep_entry = m_dep_data[dep_idx];
721 [ - + ]: 31628909 : Assume(dep_entry.parent == tx_idx);
722 : : // Skip inactive dependencies.
723 [ + + ]: 31628909 : if (!dep_entry.active) continue;
724 : : // If this dependency's top_setinfo contains query, update it to add/remove
725 : : // dep_change.
726 [ + + ]: 17243760 : if (dep_entry.top_setinfo.transactions[query]) {
727 : : if constexpr (Subtract) {
728 : 1284104 : dep_entry.top_setinfo -= dep_change;
729 : : } else {
730 : 6195376 : dep_entry.top_setinfo |= dep_change;
731 : : }
732 : : }
733 : : }
734 : : }
735 : 6753086 : }
736 : :
737 : : /** Make a specified inactive dependency active. Returns the merged chunk representative. */
738 : 3022196 : TxIdx Activate(DepIdx dep_idx) noexcept
739 : : {
740 [ - + ]: 3022196 : auto& dep_data = m_dep_data[dep_idx];
741 [ - + ]: 3022196 : Assume(!dep_data.active);
742 [ - + ]: 3022196 : auto& child_tx_data = m_tx_data[dep_data.child];
743 : 3022196 : auto& parent_tx_data = m_tx_data[dep_data.parent];
744 : :
745 : : // Gather information about the parent and child chunks.
746 [ - + ]: 3022196 : Assume(parent_tx_data.chunk_rep != child_tx_data.chunk_rep);
747 : 3022196 : auto& par_chunk_data = m_tx_data[parent_tx_data.chunk_rep];
748 : 3022196 : auto& chl_chunk_data = m_tx_data[child_tx_data.chunk_rep];
749 : 3022196 : TxIdx top_rep = parent_tx_data.chunk_rep;
750 : 3022196 : auto top_part = par_chunk_data.chunk_setinfo;
751 : 3022196 : auto bottom_part = chl_chunk_data.chunk_setinfo;
752 : : // Update the parent chunk to also contain the child.
753 : 3022196 : par_chunk_data.chunk_setinfo |= bottom_part;
754 : 3022196 : m_cost += par_chunk_data.chunk_setinfo.transactions.Count();
755 : :
756 : : // Consider the following example:
757 : : //
758 : : // A A There are two chunks, ABC and DEF, and the inactive E->C dependency
759 : : // / \ / \ is activated, resulting in a single chunk ABCDEF.
760 : : // B C B C
761 : : // : ==> | Dependency | top set before | top set after | change
762 : : // D E D E B->A | AC | ACDEF | +DEF
763 : : // \ / \ / C->A | AB | AB |
764 : : // F F F->D | D | D |
765 : : // F->E | E | ABCE | +ABC
766 : : //
767 : : // The common pattern here is that any dependency which has the parent or child of the
768 : : // dependency being activated (E->C here) in its top set, will have the opposite part added
769 : : // to it. This is true for B->A and F->E, but not for C->A and F->D.
770 : : //
771 : : // Let UpdateChunk traverse the old parent chunk top_part (ABC in example), and add
772 : : // bottom_part (DEF) to every dependency's top_set which has the parent (C) in it. The
773 : : // representative of each of these transactions was already top_rep, so that is not being
774 : : // changed here.
775 : 3022196 : UpdateChunk<false>(/*chunk=*/top_part.transactions, /*query=*/dep_data.parent,
776 : : /*chunk_rep=*/top_rep, /*dep_change=*/bottom_part);
777 : : // Let UpdateChunk traverse the old child chunk bottom_part (DEF in example), and add
778 : : // top_part (ABC) to every dependency's top_set which has the child (E) in it. At the same
779 : : // time, change the representative of each of these transactions to be top_rep, which
780 : : // becomes the representative for the merged chunk.
781 : 3022196 : UpdateChunk<false>(/*chunk=*/bottom_part.transactions, /*query=*/dep_data.child,
782 : : /*chunk_rep=*/top_rep, /*dep_change=*/top_part);
783 : : // Make active.
784 : 3022196 : dep_data.active = true;
785 : 3022196 : dep_data.top_setinfo = top_part;
786 : 3022196 : return top_rep;
787 : : }
788 : :
789 : : /** Make a specified active dependency inactive. */
790 : 354347 : void Deactivate(DepIdx dep_idx) noexcept
791 : : {
792 [ - + ]: 354347 : auto& dep_data = m_dep_data[dep_idx];
793 [ - + ]: 354347 : Assume(dep_data.active);
794 : 354347 : auto& parent_tx_data = m_tx_data[dep_data.parent];
795 : : // Make inactive.
796 : 354347 : dep_data.active = false;
797 : : // Update representatives.
798 : 354347 : auto& chunk_data = m_tx_data[parent_tx_data.chunk_rep];
799 : 354347 : m_cost += chunk_data.chunk_setinfo.transactions.Count();
800 : 354347 : auto top_part = dep_data.top_setinfo;
801 : 354347 : auto bottom_part = chunk_data.chunk_setinfo - top_part;
802 : 354347 : TxIdx bottom_rep = dep_data.child;
803 : 354347 : auto& bottom_chunk_data = m_tx_data[bottom_rep];
804 : 354347 : bottom_chunk_data.chunk_setinfo = bottom_part;
805 : 354347 : TxIdx top_rep = dep_data.parent;
806 : 354347 : auto& top_chunk_data = m_tx_data[top_rep];
807 : 354347 : top_chunk_data.chunk_setinfo = top_part;
808 : :
809 : : // See the comment above in Activate(). We perform the opposite operations here,
810 : : // removing instead of adding.
811 : : //
812 : : // Let UpdateChunk traverse the old parent chunk top_part, and remove bottom_part from
813 : : // every dependency's top_set which has the parent in it. At the same time, change the
814 : : // representative of each of these transactions to be top_rep.
815 : 354347 : UpdateChunk<true>(/*chunk=*/top_part.transactions, /*query=*/dep_data.parent,
816 : : /*chunk_rep=*/top_rep, /*dep_change=*/bottom_part);
817 : : // Let UpdateChunk traverse the old child chunk bottom_part, and remove top_part from every
818 : : // dependency's top_set which has the child in it. At the same time, change the
819 : : // representative of each of these transactions to be bottom_rep.
820 : 354347 : UpdateChunk<true>(/*chunk=*/bottom_part.transactions, /*query=*/dep_data.child,
821 : : /*chunk_rep=*/bottom_rep, /*dep_change=*/top_part);
822 : 354347 : }
823 : :
824 : : /** Activate a dependency from the chunk represented by bottom_idx to the chunk represented by
825 : : * top_idx. Return the representative of the merged chunk, or TxIdx(-1) if no merge is
826 : : * possible. */
827 : 3303538 : TxIdx MergeChunks(TxIdx top_rep, TxIdx bottom_rep) noexcept
828 : : {
829 [ - + ]: 3303538 : auto& top_chunk = m_tx_data[top_rep];
830 [ - + ]: 3303538 : Assume(top_chunk.chunk_rep == top_rep);
831 [ - + ]: 3303538 : auto& bottom_chunk = m_tx_data[bottom_rep];
832 [ - + ]: 3303538 : Assume(bottom_chunk.chunk_rep == bottom_rep);
833 : : // Count the number of dependencies between bottom_chunk and top_chunk.
834 : 3303538 : TxIdx num_deps{0};
835 [ + - + + ]: 22181575 : for (auto tx : top_chunk.chunk_setinfo.transactions) {
[ + + ]
836 : 15588398 : auto& tx_data = m_tx_data[tx];
837 : 15588398 : num_deps += (tx_data.children & bottom_chunk.chunk_setinfo.transactions).Count();
838 : : }
839 [ + + ]: 3303538 : if (num_deps == 0) return TxIdx(-1);
840 : : // Uniformly randomly pick one of them and activate it.
841 : 3022196 : TxIdx pick = m_rng.randrange(num_deps);
842 [ + - + - ]: 15197023 : for (auto tx : top_chunk.chunk_setinfo.transactions) {
[ + - ]
843 [ + + ]: 12186536 : auto& tx_data = m_tx_data[tx];
844 [ + + ]: 12186536 : auto intersect = tx_data.children & bottom_chunk.chunk_setinfo.transactions;
845 : 12186536 : auto count = intersect.Count();
846 [ + + ]: 12186536 : if (pick < count) {
847 [ + - ]: 4383622 : for (auto dep : tx_data.child_deps) {
848 : 4383622 : auto& dep_data = m_dep_data[dep];
849 [ + + ]: 4383622 : if (bottom_chunk.chunk_setinfo.transactions[dep_data.child]) {
850 [ + + ]: 3029997 : if (pick == 0) return Activate(dep);
851 : 7801 : --pick;
852 : : }
853 : : }
854 : : break;
855 : : }
856 : 9164340 : pick -= count;
857 : : }
858 : 0 : Assume(false);
859 : 0 : return TxIdx(-1);
860 : : }
861 : :
862 : : /** Perform an upward or downward merge step, on the specified chunk representative. Returns
863 : : * the representative of the merged chunk, or TxIdx(-1) if no merge took place. */
864 : : template<bool DownWard>
865 : 12489581 : TxIdx MergeStep(TxIdx chunk_rep) noexcept
866 : : {
867 : : /** Information about the chunk that tx_idx is currently in. */
868 [ + - ]: 12489581 : auto& chunk_data = m_tx_data[chunk_rep];
869 : 12489581 : SetType chunk_txn = chunk_data.chunk_setinfo.transactions;
870 : : // Iterate over all transactions in the chunk, figuring out which other chunk each
871 : : // depends on, but only testing each other chunk once. For those depended-on chunks,
872 : : // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one.
873 : : // If multiple equal-feerate candidate chunks to merge with exist, pick a random one
874 : : // among them.
875 : :
876 : : /** Which transactions have been reached from this chunk already. Initialize with the
877 : : * chunk itself, so internal dependencies within the chunk are ignored. */
878 : 12489581 : SetType explored = chunk_txn;
879 : : /** The minimum feerate (if downward) or maximum feerate (if upward) to consider when
880 : : * looking for candidate chunks to merge with. Initially, this is the original chunk's
881 : : * feerate, but is updated to be the current best candidate whenever one is found. */
882 : 12489581 : FeeFrac best_other_chunk_feerate = chunk_data.chunk_setinfo.feerate;
883 : : /** The representative for the best candidate chunk to merge with. -1 if none. */
884 : 12489581 : TxIdx best_other_chunk_rep = TxIdx(-1);
885 : : /** We generate random tiebreak values to pick between equal-feerate candidate chunks.
886 : : * This variable stores the tiebreak of the current best candidate. */
887 : 12489581 : uint64_t best_other_chunk_tiebreak{0};
888 [ + - + + ]: 62579550 : for (auto tx : chunk_txn) {
[ + + ]
889 : 37645098 : auto& tx_data = m_tx_data[tx];
890 : : /** The transactions reached by following dependencies from tx that have not been
891 : : * explored before. */
892 : 37645098 : auto newly_reached = (DownWard ? tx_data.children : tx_data.parents) - explored;
893 : 37692930 : explored |= newly_reached;
894 [ + + ]: 51774544 : while (newly_reached.Any()) {
895 : : // Find a chunk inside newly_reached, and remove it from newly_reached.
896 [ + + ]: 13926770 : auto reached_chunk_rep = m_tx_data[newly_reached.First()].chunk_rep;
897 : 13926770 : auto& reached_chunk = m_tx_data[reached_chunk_rep].chunk_setinfo;
898 [ + + ]: 13926770 : newly_reached -= reached_chunk.transactions;
899 : : // See if it has an acceptable feerate.
900 [ + + ]: 1667223 : auto cmp = DownWard ? FeeRateCompare(best_other_chunk_feerate, reached_chunk.feerate)
901 [ + + ]: 12259547 : : FeeRateCompare(reached_chunk.feerate, best_other_chunk_feerate);
902 [ + + ]: 13926770 : if (cmp > 0) continue;
903 [ + + ]: 3713362 : uint64_t tiebreak = m_rng.rand64();
904 [ + + + + ]: 3713362 : if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) {
905 : 3489753 : best_other_chunk_feerate = reached_chunk.feerate;
906 : 3489753 : best_other_chunk_rep = reached_chunk_rep;
907 : 3489753 : best_other_chunk_tiebreak = tiebreak;
908 : : }
909 : : }
910 : : }
911 : : // Stop if there are no candidate chunks to merge with.
912 [ + + ]: 12489581 : if (best_other_chunk_rep == TxIdx(-1)) return TxIdx(-1);
913 : : if constexpr (DownWard) {
914 : 11452 : chunk_rep = MergeChunks(chunk_rep, best_other_chunk_rep);
915 : : } else {
916 : 3000609 : chunk_rep = MergeChunks(best_other_chunk_rep, chunk_rep);
917 : : }
918 [ - + ]: 3012061 : Assume(chunk_rep != TxIdx(-1));
919 : : return chunk_rep;
920 : : }
921 : :
922 : :
923 : : /** Perform an upward or downward merge sequence on the specified transaction. */
924 : : template<bool DownWard>
925 : 125740 : void MergeSequence(TxIdx tx_idx) noexcept
926 : : {
927 : 125740 : auto chunk_rep = m_tx_data[tx_idx].chunk_rep;
928 : 48540 : while (true) {
929 : 174280 : auto merged_rep = MergeStep<DownWard>(chunk_rep);
930 [ + + ]: 174280 : if (merged_rep == TxIdx(-1)) break;
931 : 48540 : chunk_rep = merged_rep;
932 : : }
933 : : // Add the chunk to the queue of improvable chunks.
934 : 125740 : m_suboptimal_chunks.push_back(chunk_rep);
935 : 125740 : }
936 : :
937 : : /** Split a chunk, and then merge the resulting two chunks to make the graph topological
938 : : * again. */
939 : 62870 : void Improve(DepIdx dep_idx) noexcept
940 : : {
941 [ - + ]: 62870 : auto& dep_data = m_dep_data[dep_idx];
942 [ - + ]: 62870 : Assume(dep_data.active);
943 : : // Deactivate the specified dependency, splitting it into two new chunks: a top containing
944 : : // the parent, and a bottom containing the child. The top should have a higher feerate.
945 : 62870 : Deactivate(dep_idx);
946 : :
947 : : // At this point we have exactly two chunks which may violate topology constraints (the
948 : : // parent chunk and child chunk that were produced by deactivating dep_idx). We can fix
949 : : // these using just merge sequences, one upwards and one downwards, avoiding the need for a
950 : : // full MakeTopological.
951 : :
952 : : // Merge the top chunk with lower-feerate chunks it depends on (which may be the bottom it
953 : : // was just split from, or other pre-existing chunks).
954 : 62870 : MergeSequence<false>(dep_data.parent);
955 : : // Merge the bottom chunk with higher-feerate chunks that depend on it.
956 : 62870 : MergeSequence<true>(dep_data.child);
957 : 62870 : }
958 : :
959 : : public:
960 : : /** Construct a spanning forest for the given DepGraph, with every transaction in its own chunk
961 : : * (not topological). */
962 [ - + ]: 709314 : explicit SpanningForestState(const DepGraph<SetType>& depgraph, uint64_t rng_seed) noexcept : m_rng(rng_seed)
963 : : {
964 : 709314 : m_transaction_idxs = depgraph.Positions();
965 [ - + ]: 709314 : auto num_transactions = m_transaction_idxs.Count();
966 [ - + ]: 709314 : m_tx_data.resize(depgraph.PositionRange());
967 : : // Reserve the maximum number of (reserved) dependencies the cluster can have, so
968 : : // m_dep_data won't need any reallocations during construction. For a cluster with N
969 : : // transactions, the worst case consists of two sets of transactions, the parents and the
970 : : // children, where each child depends on each parent and nothing else. For even N, both
971 : : // sets can be sized N/2, which means N^2/4 dependencies. For odd N, one can be (N + 1)/2
972 : : // and the other can be (N - 1)/2, meaning (N^2 - 1)/4 dependencies. Because N^2 is odd in
973 : : // this case, N^2/4 (with rounding-down division) is the correct value in both cases.
974 : 709314 : m_dep_data.reserve((num_transactions * num_transactions) / 4);
975 [ + + + + ]: 7206049 : for (auto tx : m_transaction_idxs) {
[ + + ]
976 : : // Fill in transaction data.
977 : 5788105 : auto& tx_data = m_tx_data[tx];
978 : 5788105 : tx_data.chunk_rep = tx;
979 : 5788105 : tx_data.chunk_setinfo.transactions = SetType::Singleton(tx);
980 : 5788105 : tx_data.chunk_setinfo.feerate = depgraph.FeeRate(tx);
981 : : // Add its dependencies.
982 : 5788105 : SetType parents = depgraph.GetReducedParents(tx);
983 [ + + + + ]: 15390168 : for (auto par : parents) {
[ + + ]
984 [ - + ]: 5479733 : auto& par_tx_data = m_tx_data[par];
985 [ - + ]: 5479733 : auto dep_idx = m_dep_data.size();
986 : : // Construct new dependency.
987 : 5479733 : auto& dep = m_dep_data.emplace_back();
988 : 5479733 : dep.active = false;
989 : 5479733 : dep.parent = par;
990 : 5479733 : dep.child = tx;
991 : : // Add it as parent of the child.
992 : 5479733 : tx_data.parents.Set(par);
993 : : // Add it as child of the parent.
994 : 5479733 : par_tx_data.child_deps.push_back(dep_idx);
995 : 5479733 : par_tx_data.children.Set(tx);
996 : : }
997 : : }
998 : 709314 : }
999 : :
1000 : : /** Load an existing linearization. Must be called immediately after constructor. The result is
1001 : : * topological if the linearization is valid. Otherwise, MakeTopological still needs to be
1002 : : * called. */
1003 : 708793 : void LoadLinearization(std::span<const DepGraphIndex> old_linearization) noexcept
1004 : : {
1005 : : // Add transactions one by one, in order of existing linearization.
1006 [ + + ]: 6485494 : for (DepGraphIndex tx : old_linearization) {
1007 : 5776701 : auto chunk_rep = m_tx_data[tx].chunk_rep;
1008 : : // Merge the chunk upwards, as long as merging succeeds.
1009 : : while (true) {
1010 : 8732649 : chunk_rep = MergeStep<false>(chunk_rep);
1011 [ + + ]: 8732649 : if (chunk_rep == TxIdx(-1)) break;
1012 : : }
1013 : : }
1014 : 708793 : }
1015 : :
1016 : : /** Make state topological. Can be called after constructing, or after LoadLinearization. */
1017 : 429208 : void MakeTopological() noexcept
1018 : : {
1019 [ + + + + ]: 4680239 : for (auto tx : m_transaction_idxs) {
[ - + ]
1020 [ + + ]: 3821900 : auto& tx_data = m_tx_data[tx];
1021 [ + + ]: 3821900 : if (tx_data.chunk_rep == tx) {
1022 : 1791953 : m_suboptimal_chunks.emplace_back(tx);
1023 : : // Randomize the initial order of suboptimal chunks in the queue.
1024 : 1791953 : TxIdx j = m_rng.randrange<TxIdx>(m_suboptimal_chunks.size());
1025 [ + + ]: 1791953 : if (j != m_suboptimal_chunks.size() - 1) {
1026 : 1110589 : std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1027 : : }
1028 : : }
1029 : : }
1030 [ + + ]: 2228734 : while (!m_suboptimal_chunks.empty()) {
1031 : : // Pop an entry from the potentially-suboptimal chunk queue.
1032 : 1799526 : TxIdx chunk = m_suboptimal_chunks.front();
1033 : 1799526 : m_suboptimal_chunks.pop_front();
1034 [ + + ]: 1799526 : auto& chunk_data = m_tx_data[chunk];
1035 : : // If what was popped is not currently a chunk representative, continue. This may
1036 : : // happen when it was merged with something else since being added.
1037 [ + + ]: 1799526 : if (chunk_data.chunk_rep != chunk) continue;
1038 : 1793659 : int flip = m_rng.randbool();
1039 [ + + ]: 5368738 : for (int i = 0; i < 2; ++i) {
1040 [ + + ]: 3582652 : if (i ^ flip) {
1041 : : // Attempt to merge the chunk upwards.
1042 : 1791007 : auto result_up = MergeStep<false>(chunk);
1043 [ + + ]: 1791007 : if (result_up != TxIdx(-1)) {
1044 : 3256 : m_suboptimal_chunks.push_back(result_up);
1045 : : break;
1046 : : }
1047 : : } else {
1048 : : // Attempt to merge the chunk downwards.
1049 : 1791645 : auto result_down = MergeStep<true>(chunk);
1050 [ + + ]: 1791645 : if (result_down != TxIdx(-1)) {
1051 : 4317 : m_suboptimal_chunks.push_back(result_down);
1052 : : break;
1053 : : }
1054 : : }
1055 : : }
1056 : : }
1057 : 429208 : }
1058 : :
1059 : : /** Initialize the data structure for optimization. It must be topological already. */
1060 : 693903 : void StartOptimizing() noexcept
1061 : : {
1062 : : // Mark chunks suboptimal.
1063 [ + + + + ]: 6896709 : for (auto tx : m_transaction_idxs) {
[ + + ]
1064 [ + + ]: 5509583 : auto& tx_data = m_tx_data[tx];
1065 [ + + ]: 5509583 : if (tx_data.chunk_rep == tx) {
1066 : 2760232 : m_suboptimal_chunks.push_back(tx);
1067 : : // Randomize the initial order of suboptimal chunks in the queue.
1068 : 2760232 : TxIdx j = m_rng.randrange<TxIdx>(m_suboptimal_chunks.size());
1069 [ + + ]: 2760232 : if (j != m_suboptimal_chunks.size() - 1) {
1070 : 1651514 : std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]);
1071 : : }
1072 : : }
1073 : : }
1074 : 693903 : }
1075 : :
1076 : : /** Try to improve the forest. Returns false if it is optimal, true otherwise. */
1077 : 2855974 : bool OptimizeStep() noexcept
1078 : : {
1079 [ + + ]: 2882352 : while (!m_suboptimal_chunks.empty()) {
1080 : : // Pop an entry from the potentially-suboptimal chunk queue.
1081 : 2882279 : TxIdx chunk = m_suboptimal_chunks.front();
1082 : 2882279 : m_suboptimal_chunks.pop_front();
1083 [ + + ]: 2882279 : auto& chunk_data = m_tx_data[chunk];
1084 : : // If what was popped is not currently a chunk representative, continue. This may
1085 : : // happen when a split chunk merges in Improve() with one or more existing chunks that
1086 : : // are themselves on the suboptimal queue already.
1087 [ + + ]: 2882279 : if (chunk_data.chunk_rep != chunk) continue;
1088 : : // Remember the best dependency seen so far.
1089 : 2855901 : DepIdx candidate_dep = DepIdx(-1);
1090 : 2855901 : uint64_t candidate_tiebreak = 0;
1091 : : // Iterate over all transactions.
1092 [ + - + + ]: 13024030 : for (auto tx : chunk_data.chunk_setinfo.transactions) {
[ + + ]
1093 [ - + ]: 7333713 : const auto& tx_data = m_tx_data[tx];
1094 : : // Iterate over all active child dependencies of the transaction.
1095 [ - + ]: 7333713 : const auto children = std::span{tx_data.child_deps};
1096 [ + + ]: 15103333 : for (DepIdx dep_idx : children) {
1097 [ + + ]: 7769620 : const auto& dep_data = m_dep_data[dep_idx];
1098 [ + + ]: 7769620 : if (!dep_data.active) continue;
1099 : : // Skip if this dependency is ineligible (the top chunk that would be created
1100 : : // does not have higher feerate than the chunk it is currently part of).
1101 [ + + ]: 4477812 : auto cmp = FeeRateCompare(dep_data.top_setinfo.feerate, chunk_data.chunk_setinfo.feerate);
1102 [ + + ]: 4477812 : if (cmp <= 0) continue;
1103 : : // Generate a random tiebreak for this dependency, and reject it if its tiebreak
1104 : : // is worse than the best so far. This means that among all eligible
1105 : : // dependencies, a uniformly random one will be chosen.
1106 : 220951 : uint64_t tiebreak = m_rng.rand64();
1107 [ + + ]: 220951 : if (tiebreak < candidate_tiebreak) continue;
1108 : : // Remember this as our (new) candidate dependency.
1109 : : candidate_dep = dep_idx;
1110 : : candidate_tiebreak = tiebreak;
1111 : : }
1112 : : }
1113 : : // If a candidate with positive gain was found, deactivate it and then make the state
1114 : : // topological again with a sequence of merges.
1115 [ + + ]: 2855901 : if (candidate_dep != DepIdx(-1)) Improve(candidate_dep);
1116 : : // Stop processing for now, even if nothing was activated, as the loop above may have
1117 : : // had a nontrivial cost.
1118 : 2855901 : return !m_suboptimal_chunks.empty();
1119 : : }
1120 : : // No improvable chunk was found, we are done.
1121 : : return false;
1122 : : }
1123 : :
1124 : : /** Initialize data structure for minimizing the chunks. Can only be called if state is known
1125 : : * to be optimal. OptimizeStep() cannot be called anymore afterwards. */
1126 : 692996 : void StartMinimizing() noexcept
1127 : : {
1128 : 692996 : m_nonminimal_chunks.clear();
1129 [ + + ]: 692996 : m_nonminimal_chunks.reserve(m_transaction_idxs.Count());
1130 : : // Gather all chunks, and for each, add it with a random pivot in it, and a random initial
1131 : : // direction, to m_nonminimal_chunks.
1132 [ + + + + ]: 6856202 : for (auto tx : m_transaction_idxs) {
[ + + ]
1133 [ + + ]: 5470890 : auto& tx_data = m_tx_data[tx];
1134 [ + + ]: 5470890 : if (tx_data.chunk_rep == tx) {
1135 : 2767482 : TxIdx pivot_idx = PickRandomTx(tx_data.chunk_setinfo.transactions);
1136 : 2767482 : m_nonminimal_chunks.emplace_back(tx, pivot_idx, m_rng.randbits<1>());
1137 : : // Randomize the initial order of nonminimal chunks in the queue.
1138 : 2767482 : TxIdx j = m_rng.randrange<TxIdx>(m_nonminimal_chunks.size());
1139 [ + + ]: 2767482 : if (j != m_nonminimal_chunks.size() - 1) {
1140 : 1660487 : std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]);
1141 : : }
1142 : : }
1143 : : }
1144 : 692996 : }
1145 : :
1146 : : /** Try to reduce a chunk's size. Returns false if all chunks are minimal, true otherwise. */
1147 : 4136173 : bool MinimizeStep() noexcept
1148 : : {
1149 : : // If the queue of potentially-non-minimal chunks is empty, we are done.
1150 [ + + ]: 4136173 : if (m_nonminimal_chunks.empty()) return false;
1151 : : // Pop an entry from the potentially-non-minimal chunk queue.
1152 : 3443718 : auto [chunk_rep, pivot_idx, flags] = m_nonminimal_chunks.front();
1153 : 3443718 : m_nonminimal_chunks.pop_front();
1154 [ - + ]: 3443718 : auto& chunk_data = m_tx_data[chunk_rep];
1155 [ - + ]: 3443718 : Assume(chunk_data.chunk_rep == chunk_rep);
1156 : : /** Whether to move the pivot down rather than up. */
1157 : 3443718 : bool move_pivot_down = flags & 1;
1158 : : /** Whether this is already the second stage. */
1159 : 3443718 : bool second_stage = flags & 2;
1160 : :
1161 : : // Find a random dependency whose top and bottom set feerates are equal, and which has
1162 : : // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down).
1163 : 3443718 : DepIdx candidate_dep = DepIdx(-1);
1164 : 3443718 : uint64_t candidate_tiebreak{0};
1165 : 3443718 : bool have_any = false;
1166 : : // Iterate over all transactions.
1167 [ + - + + ]: 14044744 : for (auto tx_idx : chunk_data.chunk_setinfo.transactions) {
[ + + ]
1168 : 7183494 : const auto& tx_data = m_tx_data[tx_idx];
1169 : : // Iterate over all active child dependencies of the transaction.
1170 [ + + ]: 14258342 : for (auto dep_idx : tx_data.child_deps) {
1171 [ + + ]: 7074848 : auto& dep_data = m_dep_data[dep_idx];
1172 : : // Skip inactive child dependencies.
1173 [ + + ]: 7074848 : if (!dep_data.active) continue;
1174 : : // Skip if this dependency does not have equal top and bottom set feerates. Note
1175 : : // that the top cannot have higher feerate than the bottom, or OptimizeSteps would
1176 : : // have dealt with it.
1177 [ + + ]: 3739776 : if (dep_data.top_setinfo.feerate << chunk_data.chunk_setinfo.feerate) continue;
1178 : 1265721 : have_any = true;
1179 : : // Skip if this dependency does not have pivot in the right place.
1180 [ + + ]: 1265721 : if (move_pivot_down == dep_data.top_setinfo.transactions[pivot_idx]) continue;
1181 : : // Remember this as our chosen dependency if it has a better tiebreak.
1182 : 715435 : uint64_t tiebreak = m_rng.rand64() | 1;
1183 [ + + ]: 715435 : if (tiebreak > candidate_tiebreak) {
1184 : 391484 : candidate_tiebreak = tiebreak;
1185 : 391484 : candidate_dep = dep_idx;
1186 : : }
1187 : : }
1188 : : }
1189 : : // If no dependencies have equal top and bottom set feerate, this chunk is minimal.
1190 [ + + ]: 3443718 : if (!have_any) return true;
1191 : : // If all found dependencies have the pivot in the wrong place, try moving it in the other
1192 : : // direction. If this was the second stage already, we are done.
1193 [ + + ]: 397477 : if (candidate_tiebreak == 0) {
1194 : : // Switch to other direction, and to second phase.
1195 : 106000 : flags ^= 3;
1196 [ + + ]: 106000 : if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_rep, pivot_idx, flags);
1197 : 106000 : return true;
1198 : : }
1199 : :
1200 : : // Otherwise, deactivate the dependency that was found.
1201 : 291477 : Deactivate(candidate_dep);
1202 : 291477 : auto& dep_data = m_dep_data[candidate_dep];
1203 : 291477 : auto parent_chunk_rep = m_tx_data[dep_data.parent].chunk_rep;
1204 : 291477 : auto child_chunk_rep = m_tx_data[dep_data.child].chunk_rep;
1205 : : // Try to activate a dependency between the new bottom and the new top (opposite from the
1206 : : // dependency that was just deactivated).
1207 : 291477 : auto merged_chunk_rep = MergeChunks(child_chunk_rep, parent_chunk_rep);
1208 [ + + ]: 291477 : if (merged_chunk_rep != TxIdx(-1)) {
1209 : : // A self-merge happened.
1210 : : // Re-insert the chunk into the queue, in the same direction. Note that the chunk_rep
1211 : : // will have changed.
1212 : 10135 : m_nonminimal_chunks.emplace_back(merged_chunk_rep, pivot_idx, flags);
1213 : : } else {
1214 : : // No self-merge happens, and thus we have found a way to split the chunk. Create two
1215 : : // smaller chunks, and add them to the queue. The one that contains the current pivot
1216 : : // gets to continue with it in the same direction, to minimize the number of times we
1217 : : // alternate direction. If we were in the second phase already, the newly created chunk
1218 : : // inherits that too, because we know no split with the pivot on the other side is
1219 : : // possible already. The new chunk without the current pivot gets a new randomly-chosen
1220 : : // one.
1221 [ + + ]: 281342 : if (move_pivot_down) {
1222 : 136582 : auto parent_pivot_idx = PickRandomTx(m_tx_data[parent_chunk_rep].chunk_setinfo.transactions);
1223 : 136582 : m_nonminimal_chunks.emplace_back(parent_chunk_rep, parent_pivot_idx, m_rng.randbits<1>());
1224 : 136582 : m_nonminimal_chunks.emplace_back(child_chunk_rep, pivot_idx, flags);
1225 : : } else {
1226 : 144760 : auto child_pivot_idx = PickRandomTx(m_tx_data[child_chunk_rep].chunk_setinfo.transactions);
1227 : 144760 : m_nonminimal_chunks.emplace_back(parent_chunk_rep, pivot_idx, flags);
1228 : 144760 : m_nonminimal_chunks.emplace_back(child_chunk_rep, child_pivot_idx, m_rng.randbits<1>());
1229 : : }
1230 [ + + ]: 281342 : if (m_rng.randbool()) {
1231 : 140679 : std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[m_nonminimal_chunks.size() - 2]);
1232 : : }
1233 : : }
1234 : : return true;
1235 : : }
1236 : :
1237 : : /** Construct a topologically-valid linearization from the current forest state. Must be
1238 : : * topological. */
1239 : 710948 : std::vector<DepGraphIndex> GetLinearization() noexcept
1240 : : {
1241 : : /** The output linearization. */
1242 : 710948 : std::vector<DepGraphIndex> ret;
1243 : 710948 : ret.reserve(m_transaction_idxs.Count());
1244 : : /** A heap with all chunks (by representative) that can currently be included, sorted by
1245 : : * chunk feerate and a random tie-breaker. */
1246 : 710948 : std::vector<std::pair<TxIdx, uint64_t>> ready_chunks;
1247 : : /** Information about chunks:
1248 : : * - The first value is only used for chunk representatives, and counts the number of
1249 : : * unmet dependencies this chunk has on other chunks (not including dependencies within
1250 : : * the chunk itself).
1251 : : * - The second value is the number of unmet dependencies overall.
1252 : : */
1253 [ - + + + ]: 710948 : std::vector<std::pair<TxIdx, TxIdx>> chunk_deps(m_tx_data.size(), {0, 0});
[ - + ]
1254 : : /** The set of all chunk representatives. */
1255 : 710948 : SetType chunk_reps;
1256 : : /** A list with all transactions within the current chunk that can be included. */
1257 : 710948 : std::vector<TxIdx> ready_tx;
1258 : : // Populate chunk_deps[c] with the number of {out-of-chunk dependencies, dependencies} the
1259 : : // child has.
1260 [ + + + + ]: 7258042 : for (TxIdx chl_idx : m_transaction_idxs) {
[ + + ]
1261 : 5836830 : const auto& chl_data = m_tx_data[chl_idx];
1262 : 5836830 : chunk_deps[chl_idx].second = chl_data.parents.Count();
1263 : 5836830 : auto chl_chunk_rep = chl_data.chunk_rep;
1264 : 5836830 : chunk_reps.Set(chl_chunk_rep);
1265 [ + + + + ]: 15527686 : for (auto par_idx : chl_data.parents) {
[ + + ]
1266 : 5542806 : auto par_chunk_rep = m_tx_data[par_idx].chunk_rep;
1267 : 5542806 : chunk_deps[chl_chunk_rep].first += (par_chunk_rep != chl_chunk_rep);
1268 : : }
1269 : : }
1270 : : // Construct a heap with all chunks that have no out-of-chunk dependencies.
1271 : : /** Comparison function for the heap. */
1272 : 8096182 : auto chunk_cmp_fn = [&](const std::pair<TxIdx, uint64_t>& a, const std::pair<TxIdx, uint64_t>& b) noexcept {
1273 [ - + ]: 7385234 : auto& chunk_a = m_tx_data[a.first];
1274 : 7385234 : auto& chunk_b = m_tx_data[b.first];
1275 [ - + ]: 7385234 : Assume(chunk_a.chunk_rep == a.first);
1276 [ - + ]: 7385234 : Assume(chunk_b.chunk_rep == b.first);
1277 : : // First sort by chunk feerate.
1278 [ + + ]: 7385234 : if (chunk_a.chunk_setinfo.feerate != chunk_b.chunk_setinfo.feerate) {
1279 : 4653017 : return chunk_a.chunk_setinfo.feerate < chunk_b.chunk_setinfo.feerate;
1280 : : }
1281 : : // Tie-break randomly.
1282 [ + - ]: 2732217 : if (a.second != b.second) return a.second < b.second;
1283 : : // Lastly, tie-break by chunk representative.
1284 : 0 : return a.first < b.first;
1285 : : };
1286 [ + + + + ]: 4564370 : for (TxIdx chunk_rep : chunk_reps) {
[ + + ]
1287 [ + + ]: 3143158 : if (chunk_deps[chunk_rep].first == 0) ready_chunks.emplace_back(chunk_rep, m_rng.rand64());
1288 : : }
1289 : 710948 : std::make_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
1290 : : // Pop chunks off the heap, highest-feerate ones first.
1291 [ + + ]: 3854106 : while (!ready_chunks.empty()) {
1292 : 3143158 : auto [chunk_rep, _rnd] = ready_chunks.front();
1293 [ - + ]: 3143158 : std::pop_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
1294 : 3143158 : ready_chunks.pop_back();
1295 [ - + ]: 3143158 : Assume(m_tx_data[chunk_rep].chunk_rep == chunk_rep);
1296 [ - + ]: 3143158 : Assume(chunk_deps[chunk_rep].first == 0);
1297 [ + - ]: 3143158 : const auto& chunk_txn = m_tx_data[chunk_rep].chunk_setinfo.transactions;
1298 : : // Build heap of all includable transactions in chunk.
1299 [ + - + + ]: 12099931 : for (TxIdx tx_idx : chunk_txn) {
[ + + ]
1300 [ + + ]: 5836830 : if (chunk_deps[tx_idx].second == 0) {
1301 : 3440544 : ready_tx.push_back(tx_idx);
1302 : : }
1303 : : }
1304 [ - + ]: 3143158 : Assume(!ready_tx.empty());
1305 : : // Pick transactions from the ready queue, append them to linearization, and decrement
1306 : : // dependency counts.
1307 [ + + ]: 8979988 : while (!ready_tx.empty()) {
1308 : : // Move a random queue element to the back.
1309 [ - + - + ]: 5836830 : auto pos = m_rng.randrange(ready_tx.size());
1310 [ + + ]: 5836830 : if (pos != ready_tx.size() - 1) std::swap(ready_tx.back(), ready_tx[pos]);
1311 : : // Pop from the back.
1312 : 5836830 : auto tx_idx = ready_tx.back();
1313 [ - + ]: 5836830 : Assume(chunk_txn[tx_idx]);
1314 : 5836830 : ready_tx.pop_back();
1315 : : // Append to linearization.
1316 : 5836830 : ret.push_back(tx_idx);
1317 : : // Decrement dependency counts.
1318 [ + + ]: 5836830 : auto& tx_data = m_tx_data[tx_idx];
1319 [ + + + + ]: 15238561 : for (TxIdx chl_idx : tx_data.children) {
[ + + ]
1320 [ - + ]: 5542806 : auto& chl_data = m_tx_data[chl_idx];
1321 : : // Decrement tx dependency count.
1322 [ - + ]: 5542806 : Assume(chunk_deps[chl_idx].second > 0);
1323 [ + + + + ]: 5542806 : if (--chunk_deps[chl_idx].second == 0 && chunk_txn[chl_idx]) {
1324 : : // Child tx has no dependencies left, and is in this chunk. Add it to the tx queue.
1325 : 2396286 : ready_tx.push_back(chl_idx);
1326 : : }
1327 : : // Decrement chunk dependency count if this is out-of-chunk dependency.
1328 [ + + ]: 5542806 : if (chl_data.chunk_rep != chunk_rep) {
1329 [ - + ]: 2672289 : Assume(chunk_deps[chl_data.chunk_rep].first > 0);
1330 [ + + ]: 2672289 : if (--chunk_deps[chl_data.chunk_rep].first == 0) {
1331 : : // Child chunk has no dependencies left. Add it to the chunk heap.
1332 : 1866367 : ready_chunks.emplace_back(chl_data.chunk_rep, m_rng.rand64());
1333 : 1866367 : std::push_heap(ready_chunks.begin(), ready_chunks.end(), chunk_cmp_fn);
1334 : : }
1335 : : }
1336 : : }
1337 : : }
1338 : : }
1339 [ - + - + ]: 710948 : Assume(ret.size() == m_transaction_idxs.Count());
1340 : 710948 : return ret;
1341 : 710948 : }
1342 : :
1343 : : /** Get the diagram for the current state, which must be topological. Test-only.
1344 : : *
1345 : : * The linearization produced by GetLinearization() is always at least as good (in the
1346 : : * CompareChunks() sense) as this diagram, but may be better.
1347 : : *
1348 : : * After an OptimizeStep(), the diagram will always be at least as good as before. Once
1349 : : * OptimizeStep() returns false, the diagram will be equivalent to that produced by
1350 : : * GetLinearization(), and optimal.
1351 : : *
1352 : : * After a MinimizeStep(), the diagram cannot change anymore (in the CompareChunks() sense),
1353 : : * but its number of segments can increase still. Once MinimizeStep() returns false, the number
1354 : : * of chunks of the produced linearization will match the number of segments in the diagram.
1355 : : */
1356 : 25148 : std::vector<FeeFrac> GetDiagram() const noexcept
1357 : : {
1358 : 25148 : std::vector<FeeFrac> ret;
1359 [ + - + + ]: 758670 : for (auto tx : m_transaction_idxs) {
1360 [ + + ]: 708374 : if (m_tx_data[tx].chunk_rep == tx) {
1361 : 364137 : ret.push_back(m_tx_data[tx].chunk_setinfo.feerate);
1362 : : }
1363 : : }
1364 : 25148 : std::sort(ret.begin(), ret.end(), std::greater{});
1365 : 25148 : return ret;
1366 : : }
1367 : :
1368 : : /** Determine how much work was performed so far. */
1369 : 7683840 : uint64_t GetCost() const noexcept { return m_cost; }
1370 : :
1371 : : /** Verify internal consistency of the data structure. */
1372 : 2540 : void SanityCheck(const DepGraph<SetType>& depgraph) const
1373 : : {
1374 : : //
1375 : : // Verify dependency parent/child information, and build list of (active) dependencies.
1376 : : //
1377 : 2540 : std::vector<std::pair<TxIdx, TxIdx>> expected_dependencies;
1378 : 2540 : std::vector<std::tuple<TxIdx, TxIdx, DepIdx>> all_dependencies;
1379 : 2540 : std::vector<std::tuple<TxIdx, TxIdx, DepIdx>> active_dependencies;
1380 [ + - + + ]: 76796 : for (auto parent_idx : depgraph.Positions()) {
1381 [ + + + + ]: 218786 : for (auto child_idx : depgraph.GetReducedChildren(parent_idx)) {
1382 [ + - ]: 96142 : expected_dependencies.emplace_back(parent_idx, child_idx);
1383 : : }
1384 : : }
1385 [ - + + + ]: 98682 : for (DepIdx dep_idx = 0; dep_idx < m_dep_data.size(); ++dep_idx) {
1386 [ + - ]: 96142 : const auto& dep_data = m_dep_data[dep_idx];
1387 [ + - ]: 96142 : all_dependencies.emplace_back(dep_data.parent, dep_data.child, dep_idx);
1388 : : // Also add to active_dependencies if it is active.
1389 [ + + ]: 96142 : if (m_dep_data[dep_idx].active) {
1390 [ + - ]: 40576 : active_dependencies.emplace_back(dep_data.parent, dep_data.child, dep_idx);
1391 : : }
1392 : : }
1393 : 2540 : std::sort(expected_dependencies.begin(), expected_dependencies.end());
1394 [ - + ]: 2540 : std::sort(all_dependencies.begin(), all_dependencies.end());
1395 [ - + - + ]: 2540 : assert(expected_dependencies.size() == all_dependencies.size());
1396 [ + + ]: 98682 : for (size_t i = 0; i < expected_dependencies.size(); ++i) {
1397 [ + - ]: 192284 : assert(expected_dependencies[i] ==
1398 : : std::make_pair(std::get<0>(all_dependencies[i]),
1399 : : std::get<1>(all_dependencies[i])));
1400 : : }
1401 : :
1402 : : //
1403 : : // Verify the chunks against the list of active dependencies
1404 : : //
1405 [ + - + + ]: 76796 : for (auto tx_idx: depgraph.Positions()) {
1406 : : // Only process chunks for now.
1407 [ + + ]: 71716 : if (m_tx_data[tx_idx].chunk_rep == tx_idx) {
1408 : 31140 : const auto& chunk_data = m_tx_data[tx_idx];
1409 : : // Verify that transactions in the chunk point back to it. This guarantees
1410 : : // that chunks are non-overlapping.
1411 [ + - + + ]: 133996 : for (auto chunk_tx : chunk_data.chunk_setinfo.transactions) {
1412 [ - + ]: 71716 : assert(m_tx_data[chunk_tx].chunk_rep == tx_idx);
1413 : : }
1414 : : // Verify the chunk's transaction set: it must contain the representative, and for
1415 : : // every active dependency, if it contains the parent or child, it must contain
1416 : : // both. It must have exactly N-1 active dependencies in it, guaranteeing it is
1417 : : // acyclic.
1418 : 31140 : SetType expected_chunk = SetType::Singleton(tx_idx);
1419 : : while (true) {
1420 : 45046 : auto old = expected_chunk;
1421 : 45046 : size_t active_dep_count{0};
1422 [ + + ]: 658961 : for (const auto& [par, chl, _dep] : active_dependencies) {
1423 [ + + + + ]: 613915 : if (expected_chunk[par] || expected_chunk[chl]) {
1424 : 145253 : expected_chunk.Set(par);
1425 : 145253 : expected_chunk.Set(chl);
1426 : 145253 : ++active_dep_count;
1427 : : }
1428 : : }
1429 [ + + ]: 45046 : if (old == expected_chunk) {
1430 [ - + ]: 31140 : assert(expected_chunk.Count() == active_dep_count + 1);
1431 : : break;
1432 : : }
1433 : : }
1434 [ - + ]: 31140 : assert(chunk_data.chunk_setinfo.transactions == expected_chunk);
1435 : : // Verify the chunk's feerate.
1436 [ + - ]: 102856 : assert(chunk_data.chunk_setinfo.feerate ==
1437 : : depgraph.FeeRate(chunk_data.chunk_setinfo.transactions));
1438 : : }
1439 : : }
1440 : :
1441 : : //
1442 : : // Verify other transaction data.
1443 : : //
1444 [ - + ]: 2540 : assert(m_transaction_idxs == depgraph.Positions());
1445 [ + - + + ]: 76796 : for (auto tx_idx : m_transaction_idxs) {
1446 [ - + ]: 71716 : const auto& tx_data = m_tx_data[tx_idx];
1447 : : // Verify it has a valid chunk representative, and that chunk includes this
1448 : : // transaction.
1449 [ - + ]: 71716 : assert(m_tx_data[tx_data.chunk_rep].chunk_rep == tx_data.chunk_rep);
1450 [ - + ]: 71716 : assert(m_tx_data[tx_data.chunk_rep].chunk_setinfo.transactions[tx_idx]);
1451 : : // Verify parents/children.
1452 [ - + ]: 71716 : assert(tx_data.parents == depgraph.GetReducedParents(tx_idx));
1453 [ - + ]: 71716 : assert(tx_data.children == depgraph.GetReducedChildren(tx_idx));
1454 : : // Verify list of child dependencies.
1455 : 71716 : std::vector<DepIdx> expected_child_deps;
1456 [ + + + + ]: 3043905 : for (const auto& [par_idx, chl_idx, dep_idx] : all_dependencies) {
1457 [ + + ]: 2972189 : if (tx_idx == par_idx) {
1458 [ - + ]: 96142 : assert(tx_data.children[chl_idx]);
1459 [ + - ]: 96142 : expected_child_deps.push_back(dep_idx);
1460 : : }
1461 : : }
1462 : 71716 : std::sort(expected_child_deps.begin(), expected_child_deps.end());
1463 [ + - ]: 71716 : auto child_deps_copy = tx_data.child_deps;
1464 : 71716 : std::sort(child_deps_copy.begin(), child_deps_copy.end());
1465 [ - + ]: 71716 : assert(expected_child_deps == child_deps_copy);
1466 : : }
1467 : :
1468 : : //
1469 : : // Verify active dependencies' top_setinfo.
1470 : : //
1471 [ + + ]: 43116 : for (const auto& [par_idx, chl_idx, dep_idx] : active_dependencies) {
1472 : 40576 : const auto& dep_data = m_dep_data[dep_idx];
1473 : : // Verify the top_info's transactions: it must contain the parent, and for every
1474 : : // active dependency, except dep_idx itself, if it contains the parent or child, it
1475 : : // must contain both.
1476 : 40576 : SetType expected_top = SetType::Singleton(par_idx);
1477 : : while (true) {
1478 : 133354 : auto old = expected_top;
1479 [ + + + + ]: 3362576 : for (const auto& [par2_idx, chl2_idx, dep2_idx] : active_dependencies) {
1480 [ + + + + : 3229222 : if (dep2_idx != dep_idx && (expected_top[par2_idx] || expected_top[chl2_idx])) {
+ + ]
1481 : 1150550 : expected_top.Set(par2_idx);
1482 : 1150550 : expected_top.Set(chl2_idx);
1483 : : }
1484 : : }
1485 [ + + ]: 133354 : if (old == expected_top) break;
1486 : : }
1487 [ - + ]: 40576 : assert(!expected_top[chl_idx]);
1488 [ - + ]: 40576 : assert(dep_data.top_setinfo.transactions == expected_top);
1489 : : // Verify the top_info's feerate.
1490 [ + - ]: 81152 : assert(dep_data.top_setinfo.feerate ==
1491 : : depgraph.FeeRate(dep_data.top_setinfo.transactions));
1492 : : }
1493 : :
1494 : : //
1495 : : // Verify m_suboptimal_chunks.
1496 : : //
1497 [ + + ]: 10801 : for (size_t i = 0; i < m_suboptimal_chunks.size(); ++i) {
1498 : 8261 : auto tx_idx = m_suboptimal_chunks[i];
1499 [ - + ]: 8261 : assert(m_transaction_idxs[tx_idx]);
1500 : : }
1501 : :
1502 : : //
1503 : : // Verify m_nonminimal_chunks.
1504 : : //
1505 : 2540 : SetType nonminimal_reps;
1506 [ + + ]: 6956 : for (size_t i = 0; i < m_nonminimal_chunks.size(); ++i) {
1507 [ - + ]: 4416 : auto [chunk_rep, pivot, flags] = m_nonminimal_chunks[i];
1508 [ - + ]: 4416 : assert(m_tx_data[chunk_rep].chunk_rep == chunk_rep);
1509 [ - + ]: 4416 : assert(m_tx_data[pivot].chunk_rep == chunk_rep);
1510 [ - + ]: 4416 : assert(!nonminimal_reps[chunk_rep]);
1511 : 4416 : nonminimal_reps.Set(chunk_rep);
1512 : : }
1513 [ - + ]: 2540 : assert(nonminimal_reps.IsSubsetOf(m_transaction_idxs));
1514 : 2540 : }
1515 : : };
1516 : :
1517 : : /** Find or improve a linearization for a cluster.
1518 : : *
1519 : : * @param[in] depgraph Dependency graph of the cluster to be linearized.
1520 : : * @param[in] max_iterations Upper bound on the amount of work that will be done.
1521 : : * @param[in] rng_seed A random number seed to control search order. This prevents peers
1522 : : * from predicting exactly which clusters would be hard for us to
1523 : : * linearize.
1524 : : * @param[in] old_linearization An existing linearization for the cluster, or empty.
1525 : : * @param[in] is_topological (Only relevant if old_linearization is not empty) Whether
1526 : : * old_linearization is topologically valid.
1527 : : * @return A tuple of:
1528 : : * - The resulting linearization. It is guaranteed to be at least as
1529 : : * good (in the feerate diagram sense) as old_linearization.
1530 : : * - A boolean indicating whether the result is guaranteed to be
1531 : : * optimal with minimal chunks.
1532 : : * - How many optimization steps were actually performed.
1533 : : */
1534 : : template<typename SetType>
1535 : 708726 : std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}, bool is_topological = true) noexcept
1536 : : {
1537 : : /** Initialize a spanning forest data structure for this cluster. */
1538 [ + + ]: 708726 : SpanningForestState forest(depgraph, rng_seed);
1539 [ + + ]: 708726 : if (!old_linearization.empty()) {
1540 : 708582 : forest.LoadLinearization(old_linearization);
1541 [ + + ]: 708582 : if (!is_topological) forest.MakeTopological();
1542 : : } else {
1543 : 144 : forest.MakeTopological();
1544 : : }
1545 : : // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
1546 : : // is found.
1547 [ + + ]: 708726 : if (forest.GetCost() < max_iterations) {
1548 : 693315 : forest.StartOptimizing();
1549 : : do {
1550 [ + + ]: 2842347 : if (!forest.OptimizeStep()) break;
1551 [ + + ]: 2149939 : } while (forest.GetCost() < max_iterations);
1552 : : }
1553 : : // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
1554 : : // minimal.
1555 : 708726 : bool optimal = false;
1556 [ + + ]: 708726 : if (forest.GetCost() < max_iterations) {
1557 : 692408 : forest.StartMinimizing();
1558 : : do {
1559 [ + + ]: 4126416 : if (!forest.MinimizeStep()) {
1560 : : optimal = true;
1561 : : break;
1562 : : }
1563 [ + + ]: 3434549 : } while (forest.GetCost() < max_iterations);
1564 : : }
1565 : 708726 : return {forest.GetLinearization(), optimal, forest.GetCost()};
1566 : 708726 : }
1567 : :
1568 : : /** Improve a given linearization.
1569 : : *
1570 : : * @param[in] depgraph Dependency graph of the cluster being linearized.
1571 : : * @param[in,out] linearization On input, an existing linearization for depgraph. On output, a
1572 : : * potentially better linearization for the same graph.
1573 : : *
1574 : : * Postlinearization guarantees:
1575 : : * - The resulting chunks are connected.
1576 : : * - If the input has a tree shape (either all transactions have at most one child, or all
1577 : : * transactions have at most one parent), the result is optimal.
1578 : : * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
1579 : : * optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
1580 : : * as good as L1. This means that replacing transactions with same-size higher-fee transactions
1581 : : * will not worsen linearizations through a "drop conflicts, append new transactions,
1582 : : * postlinearize" process.
1583 : : */
1584 : : template<typename SetType>
1585 [ - + ]: 708380 : void PostLinearize(const DepGraph<SetType>& depgraph, std::span<DepGraphIndex> linearization)
1586 : : {
1587 : : // This algorithm performs a number of passes (currently 2); the even ones operate from back to
1588 : : // front, the odd ones from front to back. Each results in an equal-or-better linearization
1589 : : // than the one started from.
1590 : : // - One pass in either direction guarantees that the resulting chunks are connected.
1591 : : // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
1592 : : // guarantee this for graphs where each transaction has at most one child; backward passes
1593 : : // guarantee this for graphs where each transaction has at most one parent).
1594 : : // - Starting with a backward pass guarantees the moved-tree property.
1595 : : //
1596 : : // During an odd (forward) pass, the high-level operation is:
1597 : : // - Start with an empty list of groups L=[].
1598 : : // - For every transaction i in the old linearization, from front to back:
1599 : : // - Append a new group C=[i], containing just i, to the back of L.
1600 : : // - While L has at least one group before C, and the group immediately before C has feerate
1601 : : // lower than C:
1602 : : // - If C depends on P:
1603 : : // - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
1604 : : // - Otherwise:
1605 : : // - Swap P with C, continuing with the now-moved C.
1606 : : // - The output linearization is the concatenation of the groups in L.
1607 : : //
1608 : : // During even (backward) passes, i iterates from the back to the front of the existing
1609 : : // linearization, and new groups are prepended instead of appended to the list L. To enable
1610 : : // more code reuse, both passes append groups, but during even passes the meanings of
1611 : : // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
1612 : : // on output.
1613 : : //
1614 : : // In the implementation below, the groups are represented by singly-linked lists (pointing
1615 : : // from the back to the front), which are themselves organized in a singly-linked circular
1616 : : // list (each group pointing to its predecessor, with a special sentinel group at the front
1617 : : // that points back to the last group).
1618 : : //
1619 : : // Information about transaction t is stored in entries[t + 1], while the sentinel is in
1620 : : // entries[0].
1621 : :
1622 : : /** Index of the sentinel in the entries array below. */
1623 : : static constexpr DepGraphIndex SENTINEL{0};
1624 : : /** Indicator that a group has no previous transaction. */
1625 : : static constexpr DepGraphIndex NO_PREV_TX{0};
1626 : :
1627 : :
1628 : : /** Data structure per transaction entry. */
1629 : 6465010 : struct TxEntry
1630 : : {
1631 : : /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
1632 : : * entry of a group. */
1633 : : DepGraphIndex prev_tx;
1634 : :
1635 : : // The fields below are only used for transactions that are the last one in a group
1636 : : // (referred to as tail transactions below).
1637 : :
1638 : : /** Index of the first transaction in this group, possibly itself. */
1639 : : DepGraphIndex first_tx;
1640 : : /** Index of the last transaction in the previous group. The first group (the sentinel)
1641 : : * points back to the last group here, making it a singly-linked circular list. */
1642 : : DepGraphIndex prev_group;
1643 : : /** All transactions in the group. Empty for the sentinel. */
1644 : : SetType group;
1645 : : /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
1646 : : SetType deps;
1647 : : /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
1648 : : FeeFrac feerate;
1649 : : };
1650 : :
1651 : : // As an example, consider the state corresponding to the linearization [1,0,3,2], with
1652 : : // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
1653 : : //
1654 : : // +-----+
1655 : : // 0<-P-- | 0 S | ---\ Legend:
1656 : : // +-----+ |
1657 : : // ^ | - digit in box: entries index
1658 : : // /--------------F---------+ G | (note: one more than tx value)
1659 : : // v \ | | - S: sentinel group
1660 : : // +-----+ +-----+ +-----+ | (empty feerate)
1661 : : // 0<-P-- | 2 | <--P-- | 1 | <--P-- | 4 T | | - T: tail transaction, contains
1662 : : // +-----+ +-----+ +-----+ | fields beyond prev_tv.
1663 : : // ^ | - P: prev_tx reference
1664 : : // G G - F: first_tx reference
1665 : : // | | - G: prev_group reference
1666 : : // +-----+ |
1667 : : // 0<-P-- | 3 T | <--/
1668 : : // +-----+
1669 : : // ^ |
1670 : : // \-F-/
1671 : : //
1672 : : // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
1673 : : // groups [2] and [3,0,1].
1674 : :
1675 : 708380 : std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
1676 : :
1677 : : // Perform two passes over the linearization.
1678 [ + + ]: 2125140 : for (int pass = 0; pass < 2; ++pass) {
1679 [ - + ]: 1416760 : int rev = !(pass & 1);
1680 : : // Construct a sentinel group, identifying the start of the list.
1681 : 1416760 : entries[SENTINEL].prev_group = SENTINEL;
1682 [ - + ]: 1416760 : Assume(entries[SENTINEL].feerate.IsEmpty());
1683 : :
1684 : : // Iterate over all elements in the existing linearization.
1685 [ + + ]: 12902676 : for (DepGraphIndex i = 0; i < linearization.size(); ++i) {
1686 : : // Even passes are from back to front; odd passes from front to back.
1687 [ + + ]: 11485916 : DepGraphIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
1688 : : // Construct a new group containing just idx. In even passes, the meaning of
1689 : : // parent/child and high/low feerate are swapped.
1690 : 11485916 : DepGraphIndex cur_group = idx + 1;
1691 [ + + ]: 11485916 : entries[cur_group].group = SetType::Singleton(idx);
1692 [ + + + + ]: 11485916 : entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
1693 : 11485916 : entries[cur_group].feerate = depgraph.FeeRate(idx);
1694 [ + + ]: 11485916 : if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
1695 : 11485916 : entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
1696 : 11485916 : entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
1697 : : // Insert the new group at the back of the groups linked list.
1698 : 11485916 : entries[cur_group].prev_group = entries[SENTINEL].prev_group;
1699 : 11485916 : entries[SENTINEL].prev_group = cur_group;
1700 : :
1701 : : // Start merge/swap cycle.
1702 : 11485916 : DepGraphIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
1703 : 11485916 : DepGraphIndex prev_group = entries[cur_group].prev_group;
1704 : : // Continue as long as the current group has higher feerate than the previous one.
1705 [ + + ]: 17565985 : while (entries[cur_group].feerate >> entries[prev_group].feerate) {
1706 : : // prev_group/cur_group/next_group refer to (the last transactions of) 3
1707 : : // consecutive entries in groups list.
1708 [ - + ]: 6080069 : Assume(cur_group == entries[next_group].prev_group);
1709 [ - + ]: 6080069 : Assume(prev_group == entries[cur_group].prev_group);
1710 : : // The sentinel has empty feerate, which is neither higher or lower than other
1711 : : // feerates. Thus, the while loop we are in here guarantees that cur_group and
1712 : : // prev_group are not the sentinel.
1713 [ - + ]: 6080069 : Assume(cur_group != SENTINEL);
1714 [ - + ]: 6080069 : Assume(prev_group != SENTINEL);
1715 [ + + ]: 6080069 : if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
1716 : : // There is a dependency between cur_group and prev_group; merge prev_group
1717 : : // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
1718 : : // but become unused.
1719 : 5119816 : entries[cur_group].group |= entries[prev_group].group;
1720 : 5119816 : entries[cur_group].deps |= entries[prev_group].deps;
1721 : 5119816 : entries[cur_group].feerate += entries[prev_group].feerate;
1722 : : // Make the first of the current group point to the tail of the previous group.
1723 : 5119816 : entries[entries[cur_group].first_tx].prev_tx = prev_group;
1724 : : // The first of the previous group becomes the first of the newly-merged group.
1725 : 5119816 : entries[cur_group].first_tx = entries[prev_group].first_tx;
1726 : : // The previous group becomes whatever group was before the former one.
1727 : 5119816 : prev_group = entries[prev_group].prev_group;
1728 : 5119816 : entries[cur_group].prev_group = prev_group;
1729 : : } else {
1730 : : // There is no dependency between cur_group and prev_group; swap them.
1731 : 960253 : DepGraphIndex preprev_group = entries[prev_group].prev_group;
1732 : : // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
1733 : : // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
1734 : 960253 : entries[next_group].prev_group = prev_group;
1735 : 960253 : entries[prev_group].prev_group = cur_group;
1736 : 960253 : entries[cur_group].prev_group = preprev_group;
1737 : : // The current group remains the same, but the groups before/after it have
1738 : : // changed.
1739 : 960253 : next_group = prev_group;
1740 : 960253 : prev_group = preprev_group;
1741 : : }
1742 : : }
1743 : : }
1744 : :
1745 : : // Convert the entries back to linearization (overwriting the existing one).
1746 : 1416760 : DepGraphIndex cur_group = entries[0].prev_group;
1747 : 1416760 : DepGraphIndex done = 0;
1748 [ + + ]: 7782860 : while (cur_group != SENTINEL) {
1749 : 6366100 : DepGraphIndex cur_tx = cur_group;
1750 : : // Traverse the transactions of cur_group (from back to front), and write them in the
1751 : : // same order during odd passes, and reversed (front to back) in even passes.
1752 [ + + ]: 6366100 : if (rev) {
1753 : : do {
1754 [ + + ]: 5742958 : *(linearization.begin() + (done++)) = cur_tx - 1;
1755 [ + + ]: 5742958 : cur_tx = entries[cur_tx].prev_tx;
1756 [ + + ]: 5742958 : } while (cur_tx != NO_PREV_TX);
1757 : : } else {
1758 : : do {
1759 [ + + ]: 5742958 : *(linearization.end() - (++done)) = cur_tx - 1;
1760 [ + + ]: 5742958 : cur_tx = entries[cur_tx].prev_tx;
1761 [ + + ]: 5742958 : } while (cur_tx != NO_PREV_TX);
1762 : : }
1763 : 6366100 : cur_group = entries[cur_group].prev_group;
1764 : : }
1765 [ - + ]: 1416760 : Assume(done == linearization.size());
1766 : : }
1767 : 708380 : }
1768 : :
1769 : : } // namespace cluster_linearize
1770 : :
1771 : : #endif // BITCOIN_CLUSTER_LINEARIZE_H
|
