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