1 // Copyright (c) The Limenka 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 LIMENKA_CLUSTER_LINEARIZE_H
6 #define LIMENKA_CLUSTER_LINEARIZE_H
7 8 #include <algorithm>
9 #include <numeric>
10 #include <optional>
11 #include <stdint.h>
12 #include <vector>
13 #include <utility>
14 15 #include <random.h>
16 #include <span.h>
17 #include <util/feefrac.h>
18 #include <util/vecdeque.h>
19 20 namespace cluster_linearize {
21 22 /** Data type to represent transaction indices in clusters. */
23 using ClusterIndex = uint32_t;
24 25 /** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
26 * descendants). */
27 template<typename SetType>
28 class DepGraph
29 {
30 /** Information about a single transaction. */
31 struct Entry
32 {
33 /** Fee and size of transaction itself. */
34 FeeFrac feerate;
35 /** All ancestors of the transaction (including itself). */
36 SetType ancestors;
37 /** All descendants of the transaction (including itself). */
38 SetType descendants;
39 40 /** Equality operator (primarily for for testing purposes). */
41 friend bool operator==(const Entry&, const Entry&) noexcept = default;
42 43 /** Construct an empty entry. */
44 Entry() noexcept = default;
45 /** Construct an entry with a given feerate, ancestor set, descendant set. */
46 Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
47 };
48 49 /** Data for each transaction. */
50 std::vector<Entry> entries;
51 52 /** Which positions are used. */
53 SetType m_used;
54 55 public:
56 /** Equality operator (primarily for testing purposes). */
57 friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept
58 {
59 if (a.m_used != b.m_used) return false;
60 // Only compare the used positions within the entries vector.
61 for (auto idx : a.m_used) {
62 if (a.entries[idx] != b.entries[idx]) return false;
63 }
64 return true;
65 }
66 67 // Default constructors.
68 DepGraph() noexcept = default;
69 DepGraph(const DepGraph&) noexcept = default;
70 DepGraph(DepGraph&&) noexcept = default;
71 DepGraph& operator=(const DepGraph&) noexcept = default;
72 DepGraph& operator=(DepGraph&&) noexcept = default;
73 74 /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
75 *
76 * @param depgraph The original DepGraph that is being remapped.
77 *
78 * @param mapping A Span such that mapping[i] gives the position in the new DepGraph
79 * for position i in the old depgraph. Its size must be equal to
80 * depgraph.PositionRange(). The value of mapping[i] is ignored if
81 * position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]).
82 *
83 * @param pos_range The PositionRange() for the new DepGraph. It must equal the largest
84 * value in mapping for any used position in depgraph plus 1, or 0 if
85 * depgraph.TxCount() == 0.
86 *
87 * Complexity: O(N^2) where N=depgraph.TxCount().
88 */
89 DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping, ClusterIndex pos_range) noexcept : entries(pos_range)
90 {
91 Assume(mapping.size() == depgraph.PositionRange());
92 Assume((pos_range == 0) == (depgraph.TxCount() == 0));
93 for (ClusterIndex i : depgraph.Positions()) {
94 auto new_idx = mapping[i];
95 Assume(new_idx < pos_range);
96 // Add transaction.
97 entries[new_idx].ancestors = SetType::Singleton(new_idx);
98 entries[new_idx].descendants = SetType::Singleton(new_idx);
99 m_used.Set(new_idx);
100 // Fill in fee and size.
101 entries[new_idx].feerate = depgraph.entries[i].feerate;
102 }
103 for (ClusterIndex i : depgraph.Positions()) {
104 // Fill in dependencies by mapping direct parents.
105 SetType parents;
106 for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]);
107 AddDependencies(parents, mapping[i]);
108 }
109 // Verify that the provided pos_range was correct (no unused positions at the end).
110 Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1));
111 }
112 113 /** Get the set of transactions positions in use. Complexity: O(1). */
114 const SetType& Positions() const noexcept { return m_used; }
115 /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */
116 ClusterIndex PositionRange() const noexcept { return entries.size(); }
117 /** Get the number of transactions in the graph. Complexity: O(1). */
118 auto TxCount() const noexcept { return m_used.Count(); }
119 /** Get the feerate of a given transaction i. Complexity: O(1). */
120 const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
121 /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
122 FeeFrac& FeeRate(ClusterIndex i) noexcept { return entries[i].feerate; }
123 /** Get the ancestors of a given transaction i. Complexity: O(1). */
124 const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
125 /** Get the descendants of a given transaction i. Complexity: O(1). */
126 const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
127 128 /** Add a new unconnected transaction to this transaction graph (in the first available
129 * position), and return its ClusterIndex.
130 *
131 * Complexity: O(1) (amortized, due to resizing of backing vector).
132 */
133 ClusterIndex AddTransaction(const FeeFrac& feefrac) noexcept
134 {
135 static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size());
136 auto available = ALL_POSITIONS - m_used;
137 Assume(available.Any());
138 ClusterIndex new_idx = available.First();
139 if (new_idx == entries.size()) {
140 entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
141 } else {
142 entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
143 }
144 m_used.Set(new_idx);
145 return new_idx;
146 }
147 148 /** Remove the specified positions from this DepGraph.
149 *
150 * The specified positions will no longer be part of Positions(), and dependencies with them are
151 * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct
152 * dependencies), if a parent is removed while a grandparent remains, the grandparent will
153 * remain an ancestor.
154 *
155 * Complexity: O(N) where N=TxCount().
156 */
157 void RemoveTransactions(const SetType& del) noexcept
158 {
159 m_used -= del;
160 // Remove now-unused trailing entries.
161 while (!entries.empty() && !m_used[entries.size() - 1]) {
162 entries.pop_back();
163 }
164 // Remove the deleted transactions from ancestors/descendants of other transactions. Note
165 // that the deleted positions will retain old feerate and dependency information. This does
166 // not matter as they will be overwritten by AddTransaction if they get used again.
167 for (auto& entry : entries) {
168 entry.ancestors &= m_used;
169 entry.descendants &= m_used;
170 }
171 }
172 173 /** Modify this transaction graph, adding multiple parents to a specified child.
174 *
175 * Complexity: O(N) where N=TxCount().
176 */
177 void AddDependencies(const SetType& parents, ClusterIndex child) noexcept
178 {
179 Assume(m_used[child]);
180 Assume(parents.IsSubsetOf(m_used));
181 // Compute the ancestors of parents that are not already ancestors of child.
182 SetType par_anc;
183 for (auto par : parents - Ancestors(child)) {
184 par_anc |= Ancestors(par);
185 }
186 par_anc -= Ancestors(child);
187 // Bail out if there are no such ancestors.
188 if (par_anc.None()) return;
189 // To each such ancestor, add as descendants the descendants of the child.
190 const auto& chl_des = entries[child].descendants;
191 for (auto anc_of_par : par_anc) {
192 entries[anc_of_par].descendants |= chl_des;
193 }
194 // To each descendant of the child, add those ancestors.
195 for (auto dec_of_chl : Descendants(child)) {
196 entries[dec_of_chl].ancestors |= par_anc;
197 }
198 }
199 200 /** Compute the (reduced) set of parents of node i in this graph.
201 *
202 * This returns the minimal subset of the parents of i whose ancestors together equal all of
203 * i's ancestors (unless i is part of a cycle of dependencies). Note that DepGraph does not
204 * store the set of parents; this information is inferred from the ancestor sets.
205 *
206 * Complexity: O(N) where N=Ancestors(i).Count() (which is bounded by TxCount()).
207 */
208 SetType GetReducedParents(ClusterIndex i) const noexcept
209 {
210 SetType parents = Ancestors(i);
211 parents.Reset(i);
212 for (auto parent : parents) {
213 if (parents[parent]) {
214 parents -= Ancestors(parent);
215 parents.Set(parent);
216 }
217 }
218 return parents;
219 }
220 221 /** Compute the (reduced) set of children of node i in this graph.
222 *
223 * This returns the minimal subset of the children of i whose descendants together equal all of
224 * i's descendants (unless i is part of a cycle of dependencies). Note that DepGraph does not
225 * store the set of children; this information is inferred from the descendant sets.
226 *
227 * Complexity: O(N) where N=Descendants(i).Count() (which is bounded by TxCount()).
228 */
229 SetType GetReducedChildren(ClusterIndex i) const noexcept
230 {
231 SetType children = Descendants(i);
232 children.Reset(i);
233 for (auto child : children) {
234 if (children[child]) {
235 children -= Descendants(child);
236 children.Set(child);
237 }
238 }
239 return children;
240 }
241 242 /** Compute the aggregate feerate of a set of nodes in this graph.
243 *
244 * Complexity: O(N) where N=elems.Count().
245 **/
246 FeeFrac FeeRate(const SetType& elems) const noexcept
247 {
248 FeeFrac ret;
249 for (auto pos : elems) ret += entries[pos].feerate;
250 return ret;
251 }
252 253 /** Find some connected component within the subset "todo" of this graph.
254 *
255 * Specifically, this finds the connected component which contains the first transaction of
256 * todo (if any).
257 *
258 * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
259 * of the other in the entire graph (so not just within `todo`), or transitively there is a
260 * path of transactions connecting them. This does mean that if `todo` contains a transaction
261 * and a grandparent, but misses the parent, they will still be part of the same component.
262 *
263 * Complexity: O(ret.Count()).
264 */
265 SetType FindConnectedComponent(const SetType& todo) const noexcept
266 {
267 if (todo.None()) return todo;
268 auto to_add = SetType::Singleton(todo.First());
269 SetType ret;
270 do {
271 SetType old = ret;
272 for (auto add : to_add) {
273 ret |= Descendants(add);
274 ret |= Ancestors(add);
275 }
276 ret &= todo;
277 to_add = ret - old;
278 } while (to_add.Any());
279 return ret;
280 }
281 282 /** Determine if a subset is connected.
283 *
284 * Complexity: O(subset.Count()).
285 */
286 bool IsConnected(const SetType& subset) const noexcept
287 {
288 return FindConnectedComponent(subset) == subset;
289 }
290 291 /** Determine if this entire graph is connected.
292 *
293 * Complexity: O(TxCount()).
294 */
295 bool IsConnected() const noexcept { return IsConnected(m_used); }
296 297 /** Append the entries of select to list in a topologically valid order.
298 *
299 * Complexity: O(select.Count() * log(select.Count())).
300 */
301 void AppendTopo(std::vector<ClusterIndex>& list, const SetType& select) const noexcept
302 {
303 ClusterIndex old_len = list.size();
304 for (auto i : select) list.push_back(i);
305 std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
306 const auto a_anc_count = entries[a].ancestors.Count();
307 const auto b_anc_count = entries[b].ancestors.Count();
308 if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
309 return a < b;
310 });
311 }
312 };
313 314 /** A set of transactions together with their aggregate feerate. */
315 template<typename SetType>
316 struct SetInfo
317 {
318 /** The transactions in the set. */
319 SetType transactions;
320 /** Their combined fee and size. */
321 FeeFrac feerate;
322 323 /** Construct a SetInfo for the empty set. */
324 SetInfo() noexcept = default;
325 326 /** Construct a SetInfo for a specified set and feerate. */
327 SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
328 329 /** Construct a SetInfo for a given transaction in a depgraph. */
330 explicit SetInfo(const DepGraph<SetType>& depgraph, ClusterIndex pos) noexcept :
331 transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
332 333 /** Construct a SetInfo for a set of transactions in a depgraph. */
334 explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
335 transactions(txn), feerate(depgraph.FeeRate(txn)) {}
336 337 /** Add a transaction to this SetInfo (which must not yet be in it). */
338 void Set(const DepGraph<SetType>& depgraph, ClusterIndex pos) noexcept
339 {
340 Assume(!transactions[pos]);
341 transactions.Set(pos);
342 feerate += depgraph.FeeRate(pos);
343 }
344 345 /** Add the transactions of other to this SetInfo (no overlap allowed). */
346 SetInfo& operator|=(const SetInfo& other) noexcept
347 {
348 Assume(!transactions.Overlaps(other.transactions));
349 transactions |= other.transactions;
350 feerate += other.feerate;
351 return *this;
352 }
353 354 /** Construct a new SetInfo equal to this, with more transactions added (which may overlap
355 * with the existing transactions in the SetInfo). */
356 [[nodiscard]] SetInfo Add(const DepGraph<SetType>& depgraph, const SetType& txn) const noexcept
357 {
358 return {transactions | txn, feerate + depgraph.FeeRate(txn - transactions)};
359 }
360 361 /** Swap two SetInfo objects. */
362 friend void swap(SetInfo& a, SetInfo& b) noexcept
363 {
364 swap(a.transactions, b.transactions);
365 swap(a.feerate, b.feerate);
366 }
367 368 /** Permit equality testing. */
369 friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
370 };
371 372 /** Compute the feerates of the chunks of linearization. */
373 template<typename SetType>
374 std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> linearization) noexcept
375 {
376 std::vector<FeeFrac> ret;
377 for (ClusterIndex i : linearization) {
378 /** The new chunk to be added, initially a singleton. */
379 auto new_chunk = depgraph.FeeRate(i);
380 // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
381 while (!ret.empty() && new_chunk >> ret.back()) {
382 new_chunk += ret.back();
383 ret.pop_back();
384 }
385 // Actually move that new chunk into the chunking.
386 ret.push_back(std::move(new_chunk));
387 }
388 return ret;
389 }
390 391 /** Data structure encapsulating the chunking of a linearization, permitting removal of subsets. */
392 template<typename SetType>
393 class LinearizationChunking
394 {
395 /** The depgraph this linearization is for. */
396 const DepGraph<SetType>& m_depgraph;
397 398 /** The linearization we started from, possibly with removed prefix stripped. */
399 Span<const ClusterIndex> m_linearization;
400 401 /** Chunk sets and their feerates, of what remains of the linearization. */
402 std::vector<SetInfo<SetType>> m_chunks;
403 404 /** How large a prefix of m_chunks corresponds to removed transactions. */
405 ClusterIndex m_chunks_skip{0};
406 407 /** Which transactions remain in the linearization. */
408 SetType m_todo;
409 410 /** Fill the m_chunks variable, and remove the done prefix of m_linearization. */
411 void BuildChunks() noexcept
412 {
413 // Caller must clear m_chunks.
414 Assume(m_chunks.empty());
415 416 // Chop off the initial part of m_linearization that is already done.
417 while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
418 m_linearization = m_linearization.subspan(1);
419 }
420 421 // Iterate over the remaining entries in m_linearization. This is effectively the same
422 // algorithm as ChunkLinearization, but supports skipping parts of the linearization and
423 // keeps track of the sets themselves instead of just their feerates.
424 for (auto idx : m_linearization) {
425 if (!m_todo[idx]) continue;
426 // Start with an initial chunk containing just element idx.
427 SetInfo add(m_depgraph, idx);
428 // Absorb existing final chunks into add while they have lower feerate.
429 while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
430 add |= m_chunks.back();
431 m_chunks.pop_back();
432 }
433 // Remember new chunk.
434 m_chunks.push_back(std::move(add));
435 }
436 }
437 438 public:
439 /** Initialize a LinearizationSubset object for a given length of linearization. */
440 explicit LinearizationChunking(const DepGraph<SetType>& depgraph LIFETIMEBOUND, Span<const ClusterIndex> lin LIFETIMEBOUND) noexcept :
441 m_depgraph(depgraph), m_linearization(lin)
442 {
443 // Mark everything in lin as todo still.
444 for (auto i : m_linearization) m_todo.Set(i);
445 // Compute the initial chunking.
446 m_chunks.reserve(depgraph.TxCount());
447 BuildChunks();
448 }
449 450 /** Determine how many chunks remain in the linearization. */
451 ClusterIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
452 453 /** Access a chunk. Chunk 0 is the highest-feerate prefix of what remains. */
454 const SetInfo<SetType>& GetChunk(ClusterIndex n) const noexcept
455 {
456 Assume(n + m_chunks_skip < m_chunks.size());
457 return m_chunks[n + m_chunks_skip];
458 }
459 460 /** Remove some subset of transactions from the linearization. */
461 void MarkDone(SetType subset) noexcept
462 {
463 Assume(subset.Any());
464 Assume(subset.IsSubsetOf(m_todo));
465 m_todo -= subset;
466 if (GetChunk(0).transactions == subset) {
467 // If the newly done transactions exactly match the first chunk of the remainder of
468 // the linearization, we do not need to rechunk; just remember to skip one
469 // additional chunk.
470 ++m_chunks_skip;
471 // With subset marked done, some prefix of m_linearization will be done now. How long
472 // that prefix is depends on how many done elements were interspersed with subset,
473 // but at least as many transactions as there are in subset.
474 m_linearization = m_linearization.subspan(subset.Count());
475 } else {
476 // Otherwise rechunk what remains of m_linearization.
477 m_chunks.clear();
478 m_chunks_skip = 0;
479 BuildChunks();
480 }
481 }
482 483 /** Find the shortest intersection between subset and the prefixes of remaining chunks
484 * of the linearization that has a feerate not below subset's.
485 *
486 * This is a crucial operation in guaranteeing improvements to linearizations. If subset has
487 * a feerate not below GetChunk(0)'s, then moving IntersectPrefixes(subset) to the front of
488 * (what remains of) the linearization is guaranteed not to make it worse at any point.
489 *
490 * See https://delvinglimenka.org/t/introduction-to-cluster-linearization/1032 for background.
491 */
492 SetInfo<SetType> IntersectPrefixes(const SetInfo<SetType>& subset) const noexcept
493 {
494 Assume(subset.transactions.IsSubsetOf(m_todo));
495 SetInfo<SetType> accumulator;
496 // Iterate over all chunks of the remaining linearization.
497 for (ClusterIndex i = 0; i < NumChunksLeft(); ++i) {
498 // Find what (if any) intersection the chunk has with subset.
499 const SetType to_add = GetChunk(i).transactions & subset.transactions;
500 if (to_add.Any()) {
501 // If adding that to accumulator makes us hit all of subset, we are done as no
502 // shorter intersection with higher/equal feerate exists.
503 accumulator.transactions |= to_add;
504 if (accumulator.transactions == subset.transactions) break;
505 // Otherwise update the accumulator feerate.
506 accumulator.feerate += m_depgraph.FeeRate(to_add);
507 // If that does result in something better, or something with the same feerate but
508 // smaller, return that. Even if a longer, higher-feerate intersection exists, it
509 // does not hurt to return the shorter one (the remainder of the longer intersection
510 // will generally be found in the next call to Intersect, but even if not, it is not
511 // required for the improvement guarantee this function makes).
512 if (!(accumulator.feerate << subset.feerate)) return accumulator;
513 }
514 }
515 return subset;
516 }
517 };
518 519 /** Class encapsulating the state needed to find the best remaining ancestor set.
520 *
521 * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
522 * MarkDone.
523 *
524 * As long as any part of the graph remains, FindCandidateSet() can be called which will return a
525 * SetInfo with the highest-feerate ancestor set that remains (an ancestor set is a single
526 * transaction together with all its remaining ancestors).
527 */
528 template<typename SetType>
529 class AncestorCandidateFinder
530 {
531 /** Internal dependency graph. */
532 const DepGraph<SetType>& m_depgraph;
533 /** Which transaction are left to include. */
534 SetType m_todo;
535 /** Precomputed ancestor-set feerates (only kept up-to-date for indices in m_todo). */
536 std::vector<FeeFrac> m_ancestor_set_feerates;
537 538 public:
539 /** Construct an AncestorCandidateFinder for a given cluster.
540 *
541 * Complexity: O(N^2) where N=depgraph.TxCount().
542 */
543 AncestorCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
544 m_depgraph(depgraph),
545 m_todo{depgraph.Positions()},
546 m_ancestor_set_feerates(depgraph.PositionRange())
547 {
548 // Precompute ancestor-set feerates.
549 for (ClusterIndex i : m_depgraph.Positions()) {
550 /** The remaining ancestors for transaction i. */
551 SetType anc_to_add = m_depgraph.Ancestors(i);
552 FeeFrac anc_feerate;
553 // Reuse accumulated feerate from first ancestor, if usable.
554 Assume(anc_to_add.Any());
555 ClusterIndex first = anc_to_add.First();
556 if (first < i) {
557 anc_feerate = m_ancestor_set_feerates[first];
558 Assume(!anc_feerate.IsEmpty());
559 anc_to_add -= m_depgraph.Ancestors(first);
560 }
561 // Add in other ancestors (which necessarily include i itself).
562 Assume(anc_to_add[i]);
563 anc_feerate += m_depgraph.FeeRate(anc_to_add);
564 // Store the result.
565 m_ancestor_set_feerates[i] = anc_feerate;
566 }
567 }
568 569 /** Remove a set of transactions from the set of to-be-linearized ones.
570 *
571 * The same transaction may not be MarkDone()'d twice.
572 *
573 * Complexity: O(N*M) where N=depgraph.TxCount(), M=select.Count().
574 */
575 void MarkDone(SetType select) noexcept
576 {
577 Assume(select.Any());
578 Assume(select.IsSubsetOf(m_todo));
579 m_todo -= select;
580 for (auto i : select) {
581 auto feerate = m_depgraph.FeeRate(i);
582 for (auto j : m_depgraph.Descendants(i) & m_todo) {
583 m_ancestor_set_feerates[j] -= feerate;
584 }
585 }
586 }
587 588 /** Check whether any unlinearized transactions remain. */
589 bool AllDone() const noexcept
590 {
591 return m_todo.None();
592 }
593 594 /** Count the number of remaining unlinearized transactions. */
595 ClusterIndex NumRemaining() const noexcept
596 {
597 return m_todo.Count();
598 }
599 600 /** Find the best (highest-feerate, smallest among those in case of a tie) ancestor set
601 * among the remaining transactions. Requires !AllDone().
602 *
603 * Complexity: O(N) where N=depgraph.TxCount();
604 */
605 SetInfo<SetType> FindCandidateSet() const noexcept
606 {
607 Assume(!AllDone());
608 std::optional<ClusterIndex> best;
609 for (auto i : m_todo) {
610 if (best.has_value()) {
611 Assume(!m_ancestor_set_feerates[i].IsEmpty());
612 if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue;
613 }
614 best = i;
615 }
616 Assume(best.has_value());
617 return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]};
618 }
619 };
620 621 /** Class encapsulating the state needed to perform search for good candidate sets.
622 *
623 * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
624 * MarkDone().
625 *
626 * As long as any part of the graph remains, FindCandidateSet() can be called to perform a search
627 * over the set of topologically-valid subsets of that remainder, with a limit on how many
628 * combinations are tried.
629 */
630 template<typename SetType>
631 class SearchCandidateFinder
632 {
633 /** Internal RNG. */
634 InsecureRandomContext m_rng;
635 /** m_sorted_to_original[i] is the original position that sorted transaction position i had. */
636 std::vector<ClusterIndex> m_sorted_to_original;
637 /** m_original_to_sorted[i] is the sorted position original transaction position i has. */
638 std::vector<ClusterIndex> m_original_to_sorted;
639 /** Internal dependency graph for the cluster (with transactions in decreasing individual
640 * feerate order). */
641 DepGraph<SetType> m_sorted_depgraph;
642 /** Which transactions are left to do (indices in m_sorted_depgraph's order). */
643 SetType m_todo;
644 645 /** Given a set of transactions with sorted indices, get their original indices. */
646 SetType SortedToOriginal(const SetType& arg) const noexcept
647 {
648 SetType ret;
649 for (auto pos : arg) ret.Set(m_sorted_to_original[pos]);
650 return ret;
651 }
652 653 /** Given a set of transactions with original indices, get their sorted indices. */
654 SetType OriginalToSorted(const SetType& arg) const noexcept
655 {
656 SetType ret;
657 for (auto pos : arg) ret.Set(m_original_to_sorted[pos]);
658 return ret;
659 }
660 661 public:
662 /** Construct a candidate finder for a graph.
663 *
664 * @param[in] depgraph Dependency graph for the to-be-linearized cluster.
665 * @param[in] rng_seed A random seed to control the search order.
666 *
667 * Complexity: O(N^2) where N=depgraph.Count().
668 */
669 SearchCandidateFinder(const DepGraph<SetType>& depgraph, uint64_t rng_seed) noexcept :
670 m_rng(rng_seed),
671 m_sorted_to_original(depgraph.TxCount()),
672 m_original_to_sorted(depgraph.PositionRange())
673 {
674 // Determine reordering mapping, by sorting by decreasing feerate. Unused positions are
675 // not included, as they will never be looked up anyway.
676 ClusterIndex sorted_pos{0};
677 for (auto i : depgraph.Positions()) {
678 m_sorted_to_original[sorted_pos++] = i;
679 }
680 std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) {
681 auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b);
682 if (feerate_cmp == 0) return a < b;
683 return feerate_cmp > 0;
684 });
685 // Compute reverse mapping.
686 for (ClusterIndex i = 0; i < m_sorted_to_original.size(); ++i) {
687 m_original_to_sorted[m_sorted_to_original[i]] = i;
688 }
689 // Compute reordered dependency graph.
690 m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted, m_sorted_to_original.size());
691 m_todo = m_sorted_depgraph.Positions();
692 }
693 694 /** Check whether any unlinearized transactions remain. */
695 bool AllDone() const noexcept
696 {
697 return m_todo.None();
698 }
699 700 /** Find a high-feerate topologically-valid subset of what remains of the cluster.
701 * Requires !AllDone().
702 *
703 * @param[in] max_iterations The maximum number of optimization steps that will be performed.
704 * @param[in] best A set/feerate pair with an already-known good candidate. This may
705 * be empty.
706 * @return A pair of:
707 * - The best (highest feerate, smallest size as tiebreaker)
708 * topologically valid subset (and its feerate) that was
709 * encountered during search. It will be at least as good as the
710 * best passed in (if not empty).
711 * - The number of optimization steps that were performed. This will
712 * be <= max_iterations. If strictly < max_iterations, the
713 * returned subset is optimal.
714 *
715 * Complexity: possibly O(N * min(max_iterations, sqrt(2^N))) where N=depgraph.TxCount().
716 */
717 std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations, SetInfo<SetType> best) noexcept
718 {
719 Assume(!AllDone());
720 721 // Convert the provided best to internal sorted indices.
722 best.transactions = OriginalToSorted(best.transactions);
723 724 /** Type for work queue items. */
725 struct WorkItem
726 {
727 /** Set of transactions definitely included (and its feerate). This must be a subset
728 * of m_todo, and be topologically valid (includes all in-m_todo ancestors of
729 * itself). */
730 SetInfo<SetType> inc;
731 /** Set of undecided transactions. This must be a subset of m_todo, and have no overlap
732 * with inc. The set (inc | und) must be topologically valid. */
733 SetType und;
734 /** (Only when inc is not empty) The best feerate of any superset of inc that is also a
735 * subset of (inc | und), without requiring it to be topologically valid. It forms a
736 * conservative upper bound on how good a set this work item can give rise to.
737 * Transactions whose feerate is below best's are ignored when determining this value,
738 * which means it may technically be an underestimate, but if so, this work item
739 * cannot result in something that beats best anyway. */
740 FeeFrac pot_feerate;
741 742 /** Construct a new work item. */
743 WorkItem(SetInfo<SetType>&& i, SetType&& u, FeeFrac&& p_f) noexcept :
744 inc(std::move(i)), und(std::move(u)), pot_feerate(std::move(p_f))
745 {
746 Assume(pot_feerate.IsEmpty() == inc.feerate.IsEmpty());
747 }
748 749 /** Swap two WorkItems. */
750 void Swap(WorkItem& other) noexcept
751 {
752 swap(inc, other.inc);
753 swap(und, other.und);
754 swap(pot_feerate, other.pot_feerate);
755 }
756 };
757 758 /** The queue of work items. */
759 VecDeque<WorkItem> queue;
760 queue.reserve(std::max<size_t>(256, 2 * m_todo.Count()));
761 762 // Create initial entries per connected component of m_todo. While clusters themselves are
763 // generally connected, this is not necessarily true after some parts have already been
764 // removed from m_todo. Without this, effort can be wasted on searching "inc" sets that
765 // span multiple components.
766 auto to_cover = m_todo;
767 do {
768 auto component = m_sorted_depgraph.FindConnectedComponent(to_cover);
769 to_cover -= component;
770 // If best is not provided, set it to the first component, so that during the work
771 // processing loop below, and during the add_fn/split_fn calls, we do not need to deal
772 // with the best=empty case.
773 if (best.feerate.IsEmpty()) best = SetInfo(m_sorted_depgraph, component);
774 queue.emplace_back(/*inc=*/SetInfo<SetType>{},
775 /*und=*/std::move(component),
776 /*pot_feerate=*/FeeFrac{});
777 } while (to_cover.Any());
778 779 /** Local copy of the iteration limit. */
780 uint64_t iterations_left = max_iterations;
781 782 /** The set of transactions in m_todo which have feerate > best's. */
783 SetType imp = m_todo;
784 while (imp.Any()) {
785 ClusterIndex check = imp.Last();
786 if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
787 imp.Reset(check);
788 }
789 790 /** Internal function to add an item to the queue of elements to explore if there are any
791 * transactions left to split on, possibly improving it before doing so, and to update
792 * best/imp.
793 *
794 * - inc: the "inc" value for the new work item (must be topological).
795 * - und: the "und" value for the new work item ((inc | und) must be topological).
796 */
797 auto add_fn = [&](SetInfo<SetType> inc, SetType und) noexcept {
798 /** SetInfo object with the set whose feerate will become the new work item's
799 * pot_feerate. It starts off equal to inc. */
800 auto pot = inc;
801 if (!inc.feerate.IsEmpty()) {
802 // Add entries to pot. We iterate over all undecided transactions whose feerate is
803 // higher than best. While undecided transactions of lower feerate may improve pot,
804 // the resulting pot feerate cannot possibly exceed best's (and this item will be
805 // skipped in split_fn anyway).
806 for (auto pos : imp & und) {
807 // Determine if adding transaction pos to pot (ignoring topology) would improve
808 // it. If not, we're done updating pot. This relies on the fact that
809 // m_sorted_depgraph, and thus the transactions iterated over, are in decreasing
810 // individual feerate order.
811 if (!(m_sorted_depgraph.FeeRate(pos) >> pot.feerate)) break;
812 pot.Set(m_sorted_depgraph, pos);
813 }
814 815 // The "jump ahead" optimization: whenever pot has a topologically-valid subset,
816 // that subset can be added to inc. Any subset of (pot - inc) has the property that
817 // its feerate exceeds that of any set compatible with this work item (superset of
818 // inc, subset of (inc | und)). Thus, if T is a topological subset of pot, and B is
819 // the best topologically-valid set compatible with this work item, and (T - B) is
820 // non-empty, then (T | B) is better than B and also topological. This is in
821 // contradiction with the assumption that B is best. Thus, (T - B) must be empty,
822 // or T must be a subset of B.
823 //
824 // See https://delvinglimenka.org/t/how-to-linearize-your-cluster/303 section 2.4.
825 const auto init_inc = inc.transactions;
826 for (auto pos : pot.transactions - inc.transactions) {
827 // If the transaction's ancestors are a subset of pot, we can add it together
828 // with its ancestors to inc. Just update the transactions here; the feerate
829 // update happens below.
830 auto anc_todo = m_sorted_depgraph.Ancestors(pos) & m_todo;
831 if (anc_todo.IsSubsetOf(pot.transactions)) inc.transactions |= anc_todo;
832 }
833 // Finally update und and inc's feerate to account for the added transactions.
834 und -= inc.transactions;
835 inc.feerate += m_sorted_depgraph.FeeRate(inc.transactions - init_inc);
836 837 // If inc's feerate is better than best's, remember it as our new best.
838 if (inc.feerate > best.feerate) {
839 best = inc;
840 // See if we can remove any entries from imp now.
841 while (imp.Any()) {
842 ClusterIndex check = imp.Last();
843 if (m_sorted_depgraph.FeeRate(check) >> best.feerate) break;
844 imp.Reset(check);
845 }
846 }
847 848 // If no potential transactions exist beyond the already included ones, no
849 // improvement is possible anymore.
850 if (pot.feerate.size == inc.feerate.size) return;
851 // At this point und must be non-empty. If it were empty then pot would equal inc.
852 Assume(und.Any());
853 } else {
854 Assume(inc.transactions.None());
855 // If inc is empty, we just make sure there are undecided transactions left to
856 // split on.
857 if (und.None()) return;
858 }
859 860 // Actually construct a new work item on the queue. Due to the switch to DFS when queue
861 // space runs out (see below), we know that no reallocation of the queue should ever
862 // occur.
863 Assume(queue.size() < queue.capacity());
864 queue.emplace_back(/*inc=*/std::move(inc),
865 /*und=*/std::move(und),
866 /*pot_feerate=*/std::move(pot.feerate));
867 };
868 869 /** Internal process function. It takes an existing work item, and splits it in two: one
870 * with a particular transaction (and its ancestors) included, and one with that
871 * transaction (and its descendants) excluded. */
872 auto split_fn = [&](WorkItem&& elem) noexcept {
873 // Any queue element must have undecided transactions left, otherwise there is nothing
874 // to explore anymore.
875 Assume(elem.und.Any());
876 // The included and undecided set are all subsets of m_todo.
877 Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
878 // Included transactions cannot be undecided.
879 Assume(!elem.inc.transactions.Overlaps(elem.und));
880 // If pot is empty, then so is inc.
881 Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
882 883 const ClusterIndex first = elem.und.First();
884 if (!elem.inc.feerate.IsEmpty()) {
885 // If no undecided transactions remain with feerate higher than best, this entry
886 // cannot be improved beyond best.
887 if (!elem.und.Overlaps(imp)) return;
888 // We can ignore any queue item whose potential feerate isn't better than the best
889 // seen so far.
890 if (elem.pot_feerate <= best.feerate) return;
891 } else {
892 // In case inc is empty use a simpler alternative check.
893 if (m_sorted_depgraph.FeeRate(first) <= best.feerate) return;
894 }
895 896 // Decide which transaction to split on. Splitting is how new work items are added, and
897 // how progress is made. One split transaction is chosen among the queue item's
898 // undecided ones, and:
899 // - A work item is (potentially) added with that transaction plus its remaining
900 // descendants excluded (removed from the und set).
901 // - A work item is (potentially) added with that transaction plus its remaining
902 // ancestors included (added to the inc set).
903 //
904 // To decide what to split on, consider the undecided ancestors of the highest
905 // individual feerate undecided transaction. Pick the one which reduces the search space
906 // most. Let I(t) be the size of the undecided set after including t, and E(t) the size
907 // of the undecided set after excluding t. Then choose the split transaction t such
908 // that 2^I(t) + 2^E(t) is minimal, tie-breaking by highest individual feerate for t.
909 ClusterIndex split = 0;
910 const auto select = elem.und & m_sorted_depgraph.Ancestors(first);
911 Assume(select.Any());
912 std::optional<std::pair<ClusterIndex, ClusterIndex>> split_counts;
913 for (auto t : select) {
914 // Call max = max(I(t), E(t)) and min = min(I(t), E(t)). Let counts = {max,min}.
915 // Sorting by the tuple counts is equivalent to sorting by 2^I(t) + 2^E(t). This
916 // expression is equal to 2^max + 2^min = 2^max * (1 + 1/2^(max - min)). The second
917 // factor (1 + 1/2^(max - min)) there is in (1,2]. Thus increasing max will always
918 // increase it, even when min decreases. Because of this, we can first sort by max.
919 std::pair<ClusterIndex, ClusterIndex> counts{
920 (elem.und - m_sorted_depgraph.Ancestors(t)).Count(),
921 (elem.und - m_sorted_depgraph.Descendants(t)).Count()};
922 if (counts.first < counts.second) std::swap(counts.first, counts.second);
923 // Remember the t with the lowest counts.
924 if (!split_counts.has_value() || counts < *split_counts) {
925 split = t;
926 split_counts = counts;
927 }
928 }
929 // Since there was at least one transaction in select, we must always find one.
930 Assume(split_counts.has_value());
931 932 // Add a work item corresponding to exclusion of the split transaction.
933 const auto& desc = m_sorted_depgraph.Descendants(split);
934 add_fn(/*inc=*/elem.inc,
935 /*und=*/elem.und - desc);
936 937 // Add a work item corresponding to inclusion of the split transaction.
938 const auto anc = m_sorted_depgraph.Ancestors(split) & m_todo;
939 add_fn(/*inc=*/elem.inc.Add(m_sorted_depgraph, anc),
940 /*und=*/elem.und - anc);
941 942 // Account for the performed split.
943 --iterations_left;
944 };
945 946 // Work processing loop.
947 //
948 // New work items are always added at the back of the queue, but items to process use a
949 // hybrid approach where they can be taken from the front or the back.
950 //
951 // Depth-first search (DFS) corresponds to always taking from the back of the queue. This
952 // is very memory-efficient (linear in the number of transactions). Breadth-first search
953 // (BFS) corresponds to always taking from the front, which potentially uses more memory
954 // (up to exponential in the transaction count), but seems to work better in practice.
955 //
956 // The approach here combines the two: use BFS (plus random swapping) until the queue grows
957 // too large, at which point we temporarily switch to DFS until the size shrinks again.
958 while (!queue.empty()) {
959 // Randomly swap the first two items to randomize the search order.
960 if (queue.size() > 1 && m_rng.randbool()) {
961 queue[0].Swap(queue[1]);
962 }
963 964 // Processing the first queue item, and then using DFS for everything it gives rise to,
965 // may increase the queue size by the number of undecided elements in there, minus 1
966 // for the first queue item being removed. Thus, only when that pushes the queue over
967 // its capacity can we not process from the front (BFS), and should we use DFS.
968 while (queue.size() - 1 + queue.front().und.Count() > queue.capacity()) {
969 if (!iterations_left) break;
970 auto elem = queue.back();
971 queue.pop_back();
972 split_fn(std::move(elem));
973 }
974 975 // Process one entry from the front of the queue (BFS exploration)
976 if (!iterations_left) break;
977 auto elem = queue.front();
978 queue.pop_front();
979 split_fn(std::move(elem));
980 }
981 982 // Return the found best set (converted to the original transaction indices), and the
983 // number of iterations performed.
984 best.transactions = SortedToOriginal(best.transactions);
985 return {std::move(best), max_iterations - iterations_left};
986 }
987 988 /** Remove a subset of transactions from the cluster being linearized.
989 *
990 * Complexity: O(N) where N=done.Count().
991 */
992 void MarkDone(const SetType& done) noexcept
993 {
994 const auto done_sorted = OriginalToSorted(done);
995 Assume(done_sorted.Any());
996 Assume(done_sorted.IsSubsetOf(m_todo));
997 m_todo -= done_sorted;
998 }
999 };
1000 1001 /** Find or improve a linearization for a cluster.
1002 *
1003 * @param[in] depgraph Dependency graph of the cluster to be linearized.
1004 * @param[in] max_iterations Upper bound on the number of optimization steps that will be done.
1005 * @param[in] rng_seed A random number seed to control search order. This prevents peers
1006 * from predicting exactly which clusters would be hard for us to
1007 * linearize.
1008 * @param[in] old_linearization An existing linearization for the cluster (which must be
1009 * topologically valid), or empty.
1010 * @return A pair of:
1011 * - The resulting linearization. It is guaranteed to be at least as
1012 * good (in the feerate diagram sense) as old_linearization.
1013 * - A boolean indicating whether the result is guaranteed to be
1014 * optimal.
1015 *
1016 * Complexity: possibly O(N * min(max_iterations + N, sqrt(2^N))) where N=depgraph.TxCount().
1017 */
1018 template<typename SetType>
1019 std::pair<std::vector<ClusterIndex>, bool> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, Span<const ClusterIndex> old_linearization = {}) noexcept
1020 {
1021 Assume(old_linearization.empty() || old_linearization.size() == depgraph.TxCount());
1022 if (depgraph.TxCount() == 0) return {{}, true};
1023 1024 uint64_t iterations_left = max_iterations;
1025 std::vector<ClusterIndex> linearization;
1026 1027 AncestorCandidateFinder anc_finder(depgraph);
1028 std::optional<SearchCandidateFinder<SetType>> src_finder;
1029 linearization.reserve(depgraph.TxCount());
1030 bool optimal = true;
1031 1032 // Treat the initialization of SearchCandidateFinder as taking N^2/64 (rounded up) iterations
1033 // (largely due to the cost of constructing the internal sorted-by-feerate DepGraph inside
1034 // SearchCandidateFinder), a rough approximation based on benchmark. If we don't have that
1035 // many, don't start it.
1036 uint64_t start_iterations = (uint64_t{depgraph.TxCount()} * depgraph.TxCount() + 63) / 64;
1037 if (iterations_left > start_iterations) {
1038 iterations_left -= start_iterations;
1039 src_finder.emplace(depgraph, rng_seed);
1040 }
1041 1042 /** Chunking of what remains of the old linearization. */
1043 LinearizationChunking old_chunking(depgraph, old_linearization);
1044 1045 while (true) {
1046 // Find the highest-feerate prefix of the remainder of old_linearization.
1047 SetInfo<SetType> best_prefix;
1048 if (old_chunking.NumChunksLeft()) best_prefix = old_chunking.GetChunk(0);
1049 1050 // Then initialize best to be either the best remaining ancestor set, or the first chunk.
1051 auto best = anc_finder.FindCandidateSet();
1052 if (!best_prefix.feerate.IsEmpty() && best_prefix.feerate >= best.feerate) best = best_prefix;
1053 1054 uint64_t iterations_done_now = 0;
1055 uint64_t max_iterations_now = 0;
1056 if (src_finder) {
1057 // Treat the invocation of SearchCandidateFinder::FindCandidateSet() as costing N/4
1058 // up-front (rounded up) iterations (largely due to the cost of connected-component
1059 // splitting), a rough approximation based on benchmarks.
1060 uint64_t base_iterations = (anc_finder.NumRemaining() + 3) / 4;
1061 if (iterations_left > base_iterations) {
1062 // Invoke bounded search to update best, with up to half of our remaining
1063 // iterations as limit.
1064 iterations_left -= base_iterations;
1065 max_iterations_now = (iterations_left + 1) / 2;
1066 std::tie(best, iterations_done_now) = src_finder->FindCandidateSet(max_iterations_now, best);
1067 iterations_left -= iterations_done_now;
1068 }
1069 }
1070 1071 if (iterations_done_now == max_iterations_now) {
1072 optimal = false;
1073 // If the search result is not (guaranteed to be) optimal, run intersections to make
1074 // sure we don't pick something that makes us unable to reach further diagram points
1075 // of the old linearization.
1076 if (old_chunking.NumChunksLeft() > 0) {
1077 best = old_chunking.IntersectPrefixes(best);
1078 }
1079 }
1080 1081 // Add to output in topological order.
1082 depgraph.AppendTopo(linearization, best.transactions);
1083 1084 // Update state to reflect best is no longer to be linearized.
1085 anc_finder.MarkDone(best.transactions);
1086 if (anc_finder.AllDone()) break;
1087 if (src_finder) src_finder->MarkDone(best.transactions);
1088 if (old_chunking.NumChunksLeft() > 0) {
1089 old_chunking.MarkDone(best.transactions);
1090 }
1091 }
1092 1093 return {std::move(linearization), optimal};
1094 }
1095 1096 /** Improve a given linearization.
1097 *
1098 * @param[in] depgraph Dependency graph of the cluster being linearized.
1099 * @param[in,out] linearization On input, an existing linearization for depgraph. On output, a
1100 * potentially better linearization for the same graph.
1101 *
1102 * Postlinearization guarantees:
1103 * - The resulting chunks are connected.
1104 * - If the input has a tree shape (either all transactions have at most one child, or all
1105 * transactions have at most one parent), the result is optimal.
1106 * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
1107 * optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
1108 * as good as L1. This means that replacing transactions with same-size higher-fee transactions
1109 * will not worsen linearizations through a "drop conflicts, append new transactions,
1110 * postlinearize" process.
1111 */
1112 template<typename SetType>
1113 void PostLinearize(const DepGraph<SetType>& depgraph, Span<ClusterIndex> linearization)
1114 {
1115 // This algorithm performs a number of passes (currently 2); the even ones operate from back to
1116 // front, the odd ones from front to back. Each results in an equal-or-better linearization
1117 // than the one started from.
1118 // - One pass in either direction guarantees that the resulting chunks are connected.
1119 // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
1120 // guarantee this for graphs where each transaction has at most one child; backward passes
1121 // guarantee this for graphs where each transaction has at most one parent).
1122 // - Starting with a backward pass guarantees the moved-tree property.
1123 //
1124 // During an odd (forward) pass, the high-level operation is:
1125 // - Start with an empty list of groups L=[].
1126 // - For every transaction i in the old linearization, from front to back:
1127 // - Append a new group C=[i], containing just i, to the back of L.
1128 // - While L has at least one group before C, and the group immediately before C has feerate
1129 // lower than C:
1130 // - If C depends on P:
1131 // - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
1132 // - Otherwise:
1133 // - Swap P with C, continuing with the now-moved C.
1134 // - The output linearization is the concatenation of the groups in L.
1135 //
1136 // During even (backward) passes, i iterates from the back to the front of the existing
1137 // linearization, and new groups are prepended instead of appended to the list L. To enable
1138 // more code reuse, both passes append groups, but during even passes the meanings of
1139 // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
1140 // on output.
1141 //
1142 // In the implementation below, the groups are represented by singly-linked lists (pointing
1143 // from the back to the front), which are themselves organized in a singly-linked circular
1144 // list (each group pointing to its predecessor, with a special sentinel group at the front
1145 // that points back to the last group).
1146 //
1147 // Information about transaction t is stored in entries[t + 1], while the sentinel is in
1148 // entries[0].
1149 1150 /** Index of the sentinel in the entries array below. */
1151 static constexpr ClusterIndex SENTINEL{0};
1152 /** Indicator that a group has no previous transaction. */
1153 static constexpr ClusterIndex NO_PREV_TX{0};
1154 1155 1156 /** Data structure per transaction entry. */
1157 struct TxEntry
1158 {
1159 /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
1160 * entry of a group. */
1161 ClusterIndex prev_tx;
1162 1163 // The fields below are only used for transactions that are the last one in a group
1164 // (referred to as tail transactions below).
1165 1166 /** Index of the first transaction in this group, possibly itself. */
1167 ClusterIndex first_tx;
1168 /** Index of the last transaction in the previous group. The first group (the sentinel)
1169 * points back to the last group here, making it a singly-linked circular list. */
1170 ClusterIndex prev_group;
1171 /** All transactions in the group. Empty for the sentinel. */
1172 SetType group;
1173 /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
1174 SetType deps;
1175 /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
1176 FeeFrac feerate;
1177 };
1178 1179 // As an example, consider the state corresponding to the linearization [1,0,3,2], with
1180 // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
1181 //
1182 // +-----+
1183 // 0<-P-- | 0 S | ---\ Legend:
1184 // +-----+ |
1185 // ^ | - digit in box: entries index
1186 // /--------------F---------+ G | (note: one more than tx value)
1187 // v \ | | - S: sentinel group
1188 // +-----+ +-----+ +-----+ | (empty feerate)
1189 // 0<-P-- | 2 | <--P-- | 1 | <--P-- | 4 T | | - T: tail transaction, contains
1190 // +-----+ +-----+ +-----+ | fields beyond prev_tv.
1191 // ^ | - P: prev_tx reference
1192 // G G - F: first_tx reference
1193 // | | - G: prev_group reference
1194 // +-----+ |
1195 // 0<-P-- | 3 T | <--/
1196 // +-----+
1197 // ^ |
1198 // \-F-/
1199 //
1200 // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
1201 // groups [2] and [3,0,1].
1202 1203 std::vector<TxEntry> entries(depgraph.PositionRange() + 1);
1204 1205 // Perform two passes over the linearization.
1206 for (int pass = 0; pass < 2; ++pass) {
1207 int rev = !(pass & 1);
1208 // Construct a sentinel group, identifying the start of the list.
1209 entries[SENTINEL].prev_group = SENTINEL;
1210 Assume(entries[SENTINEL].feerate.IsEmpty());
1211 1212 // Iterate over all elements in the existing linearization.
1213 for (ClusterIndex i = 0; i < linearization.size(); ++i) {
1214 // Even passes are from back to front; odd passes from front to back.
1215 ClusterIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
1216 // Construct a new group containing just idx. In even passes, the meaning of
1217 // parent/child and high/low feerate are swapped.
1218 ClusterIndex cur_group = idx + 1;
1219 entries[cur_group].group = SetType::Singleton(idx);
1220 entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
1221 entries[cur_group].feerate = depgraph.FeeRate(idx);
1222 if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
1223 entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
1224 entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
1225 // Insert the new group at the back of the groups linked list.
1226 entries[cur_group].prev_group = entries[SENTINEL].prev_group;
1227 entries[SENTINEL].prev_group = cur_group;
1228 1229 // Start merge/swap cycle.
1230 ClusterIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
1231 ClusterIndex prev_group = entries[cur_group].prev_group;
1232 // Continue as long as the current group has higher feerate than the previous one.
1233 while (entries[cur_group].feerate >> entries[prev_group].feerate) {
1234 // prev_group/cur_group/next_group refer to (the last transactions of) 3
1235 // consecutive entries in groups list.
1236 Assume(cur_group == entries[next_group].prev_group);
1237 Assume(prev_group == entries[cur_group].prev_group);
1238 // The sentinel has empty feerate, which is neither higher or lower than other
1239 // feerates. Thus, the while loop we are in here guarantees that cur_group and
1240 // prev_group are not the sentinel.
1241 Assume(cur_group != SENTINEL);
1242 Assume(prev_group != SENTINEL);
1243 if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
1244 // There is a dependency between cur_group and prev_group; merge prev_group
1245 // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
1246 // but become unused.
1247 entries[cur_group].group |= entries[prev_group].group;
1248 entries[cur_group].deps |= entries[prev_group].deps;
1249 entries[cur_group].feerate += entries[prev_group].feerate;
1250 // Make the first of the current group point to the tail of the previous group.
1251 entries[entries[cur_group].first_tx].prev_tx = prev_group;
1252 // The first of the previous group becomes the first of the newly-merged group.
1253 entries[cur_group].first_tx = entries[prev_group].first_tx;
1254 // The previous group becomes whatever group was before the former one.
1255 prev_group = entries[prev_group].prev_group;
1256 entries[cur_group].prev_group = prev_group;
1257 } else {
1258 // There is no dependency between cur_group and prev_group; swap them.
1259 ClusterIndex preprev_group = entries[prev_group].prev_group;
1260 // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
1261 // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
1262 entries[next_group].prev_group = prev_group;
1263 entries[prev_group].prev_group = cur_group;
1264 entries[cur_group].prev_group = preprev_group;
1265 // The current group remains the same, but the groups before/after it have
1266 // changed.
1267 next_group = prev_group;
1268 prev_group = preprev_group;
1269 }
1270 }
1271 }
1272 1273 // Convert the entries back to linearization (overwriting the existing one).
1274 ClusterIndex cur_group = entries[0].prev_group;
1275 ClusterIndex done = 0;
1276 while (cur_group != SENTINEL) {
1277 ClusterIndex cur_tx = cur_group;
1278 // Traverse the transactions of cur_group (from back to front), and write them in the
1279 // same order during odd passes, and reversed (front to back) in even passes.
1280 if (rev) {
1281 do {
1282 *(linearization.begin() + (done++)) = cur_tx - 1;
1283 cur_tx = entries[cur_tx].prev_tx;
1284 } while (cur_tx != NO_PREV_TX);
1285 } else {
1286 do {
1287 *(linearization.end() - (++done)) = cur_tx - 1;
1288 cur_tx = entries[cur_tx].prev_tx;
1289 } while (cur_tx != NO_PREV_TX);
1290 }
1291 cur_group = entries[cur_group].prev_group;
1292 }
1293 Assume(done == linearization.size());
1294 }
1295 }
1296 1297 /** Merge two linearizations for the same cluster into one that is as good as both.
1298 *
1299 * Complexity: O(N^2) where N=depgraph.TxCount(); O(N) if both inputs are identical.
1300 */
1301 template<typename SetType>
1302 std::vector<ClusterIndex> MergeLinearizations(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> lin1, Span<const ClusterIndex> lin2)
1303 {
1304 Assume(lin1.size() == depgraph.TxCount());
1305 Assume(lin2.size() == depgraph.TxCount());
1306 1307 /** Chunkings of what remains of both input linearizations. */
1308 LinearizationChunking chunking1(depgraph, lin1), chunking2(depgraph, lin2);
1309 /** Output linearization. */
1310 std::vector<ClusterIndex> ret;
1311 if (depgraph.TxCount() == 0) return ret;
1312 ret.reserve(depgraph.TxCount());
1313 1314 while (true) {
1315 // As long as we are not done, both linearizations must have chunks left.
1316 Assume(chunking1.NumChunksLeft() > 0);
1317 Assume(chunking2.NumChunksLeft() > 0);
1318 // Find the set to output by taking the best remaining chunk, and then intersecting it with
1319 // prefixes of remaining chunks of the other linearization.
1320 SetInfo<SetType> best;
1321 const auto& lin1_firstchunk = chunking1.GetChunk(0);
1322 const auto& lin2_firstchunk = chunking2.GetChunk(0);
1323 if (lin2_firstchunk.feerate >> lin1_firstchunk.feerate) {
1324 best = chunking1.IntersectPrefixes(lin2_firstchunk);
1325 } else {
1326 best = chunking2.IntersectPrefixes(lin1_firstchunk);
1327 }
1328 // Append the result to the output and mark it as done.
1329 depgraph.AppendTopo(ret, best.transactions);
1330 chunking1.MarkDone(best.transactions);
1331 if (chunking1.NumChunksLeft() == 0) break;
1332 chunking2.MarkDone(best.transactions);
1333 }
1334 1335 Assume(ret.size() == depgraph.TxCount());
1336 return ret;
1337 }
1338 1339 } // namespace cluster_linearize
1340 1341 #endif // LIMENKA_CLUSTER_LINEARIZE_H
1342