Branch data Line data Source code
1 : : // Copyright (c) The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_CLUSTER_LINEARIZE_H
6 : : #define BITCOIN_CLUSTER_LINEARIZE_H
7 : :
8 : : #include <algorithm>
9 : : #include <numeric>
10 : : #include <optional>
11 : : #include <stdint.h>
12 : : #include <vector>
13 : : #include <utility>
14 : :
15 : : #include <random.h>
16 : : #include <span.h>
17 : : #include <util/feefrac.h>
18 : : #include <util/vecdeque.h>
19 : :
20 : : namespace cluster_linearize {
21 : :
22 : : /** Data type to represent cluster input.
23 : : *
24 : : * cluster[i].first is tx_i's fee and size.
25 : : * cluster[i].second[j] is true iff tx_i spends one or more of tx_j's outputs.
26 : : */
27 : : template<typename SetType>
28 : : using Cluster = std::vector<std::pair<FeeFrac, SetType>>;
29 : :
30 : : /** Data type to represent transaction indices in clusters. */
31 : : using ClusterIndex = uint32_t;
32 : :
33 : : /** Data structure that holds a transaction graph's preprocessed data (fee, size, ancestors,
34 : : * descendants). */
35 : : template<typename SetType>
36 [ + - ]: 54 : class DepGraph
37 : : {
38 : : /** Information about a single transaction. */
39 : : struct Entry
40 : : {
41 : : /** Fee and size of transaction itself. */
42 : 45 : FeeFrac feerate;
43 : : /** All ancestors of the transaction (including itself). */
44 : 45 : SetType ancestors;
45 : : /** All descendants of the transaction (including itself). */
46 : 45 : SetType descendants;
47 : :
48 : : /** Equality operator (primarily for for testing purposes). */
49 [ + - + - : 90 : friend bool operator==(const Entry&, const Entry&) noexcept = default;
- + ]
50 : :
51 : : /** Construct an empty entry. */
52 : 15 : Entry() noexcept = default;
53 : : /** Construct an entry with a given feerate, ancestor set, descendant set. */
54 : 90 : Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {}
55 : : };
56 : :
57 : : /** Data for each transaction, in the same order as the Cluster it was constructed from. */
58 : 6 : std::vector<Entry> entries;
59 : :
60 : : public:
61 : : /** Equality operator (primarily for testing purposes). */
62 [ + - - + : 18 : friend bool operator==(const DepGraph&, const DepGraph&) noexcept = default;
- + ]
63 : :
64 : : // Default constructors.
65 : 24 : DepGraph() noexcept = default;
66 : : DepGraph(const DepGraph&) noexcept = default;
67 : : DepGraph(DepGraph&&) noexcept = default;
68 : : DepGraph& operator=(const DepGraph&) noexcept = default;
69 : 24 : DepGraph& operator=(DepGraph&&) noexcept = default;
70 : :
71 : : /** Construct a DepGraph object for ntx transactions, with no dependencies.
72 : : *
73 : : * Complexity: O(N) where N=ntx.
74 : : **/
75 : : explicit DepGraph(ClusterIndex ntx) noexcept
76 : : {
77 : : Assume(ntx <= SetType::Size());
78 : : entries.resize(ntx);
79 : : for (ClusterIndex i = 0; i < ntx; ++i) {
80 : : entries[i].ancestors = SetType::Singleton(i);
81 : : entries[i].descendants = SetType::Singleton(i);
82 : : }
83 : : }
84 : :
85 : : /** Construct a DepGraph object given a cluster.
86 : : *
87 : : * Complexity: O(N^2) where N=cluster.size().
88 : : */
89 : 6 : explicit DepGraph(const Cluster<SetType>& cluster) noexcept : entries(cluster.size())
90 : : {
91 [ + + ]: 21 : for (ClusterIndex i = 0; i < cluster.size(); ++i) {
92 : : // Fill in fee and size.
93 : 15 : entries[i].feerate = cluster[i].first;
94 : : // Fill in direct parents as ancestors.
95 : 15 : entries[i].ancestors = cluster[i].second;
96 : : // Make sure transactions are ancestors of themselves.
97 : 15 : entries[i].ancestors.Set(i);
98 : : }
99 : :
100 : : // Propagate ancestor information.
101 [ + + ]: 21 : for (ClusterIndex i = 0; i < entries.size(); ++i) {
102 : : // At this point, entries[a].ancestors[b] is true iff b is an ancestor of a and there
103 : : // is a path from a to b through the subgraph consisting of {a, b} union
104 : : // {0, 1, ..., (i-1)}.
105 : 15 : SetType to_merge = entries[i].ancestors;
106 [ + + ]: 70 : for (ClusterIndex j = 0; j < entries.size(); ++j) {
107 [ + + ]: 55 : if (entries[j].ancestors[i]) {
108 : 27 : entries[j].ancestors |= to_merge;
109 : : }
110 : : }
111 : : }
112 : :
113 : : // Fill in descendant information by transposing the ancestor information.
114 [ + + ]: 21 : for (ClusterIndex i = 0; i < entries.size(); ++i) {
115 [ + - + + ]: 58 : for (auto j : entries[i].ancestors) {
116 : 28 : entries[j].descendants.Set(i);
117 : : }
118 : : }
119 : 6 : }
120 : :
121 : : /** Get the number of transactions in the graph. Complexity: O(1). */
122 [ + - + - : 217 : auto TxCount() const noexcept { return entries.size(); }
+ + + + +
+ + + - +
+ + + + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
123 : : /** Get the feerate of a given transaction i. Complexity: O(1). */
124 [ + - + + : 75 : const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; }
+ - ]
125 : : /** Get the mutable feerate of a given transaction i. Complexity: O(1). */
126 : 45 : FeeFrac& FeeRate(ClusterIndex i) noexcept { return entries[i].feerate; }
127 : : /** Get the ancestors of a given transaction i. Complexity: O(1). */
128 [ + + + + : 369 : const SetType& Ancestors(ClusterIndex i) const noexcept { return entries[i].ancestors; }
+ + + - -
+ + - - +
- + - + ]
[ # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
129 : : /** Get the descendants of a given transaction i. Complexity: O(1). */
130 [ + - + + : 233 : const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; }
+ + + - -
+ ][ # # #
# # # # #
# # # # #
# # # ]
131 : :
132 : : /** Add a new unconnected transaction to this transaction graph (at the end), and return its
133 : : * ClusterIndex.
134 : : *
135 : : * Complexity: O(1) (amortized, due to resizing of backing vector).
136 : : */
137 : 90 : ClusterIndex AddTransaction(const FeeFrac& feefrac) noexcept
138 : : {
139 : 90 : Assume(TxCount() < SetType::Size());
140 : 90 : ClusterIndex new_idx = TxCount();
141 : 90 : entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx));
142 : 90 : return new_idx;
143 : : }
144 : :
145 : : /** Modify this transaction graph, adding a dependency between a specified parent and child.
146 : : *
147 : : * Complexity: O(N) where N=TxCount().
148 : : **/
149 : 114 : void AddDependency(ClusterIndex parent, ClusterIndex child) noexcept
150 : : {
151 : : // Bail out if dependency is already implied.
152 [ + + ]: 114 : if (entries[child].ancestors[parent]) return;
153 : : // To each ancestor of the parent, add as descendants the descendants of the child.
154 [ + - ]: 63 : const auto& chl_des = entries[child].descendants;
155 [ + - + + ]: 207 : for (auto anc_of_par : Ancestors(parent)) {
156 : 81 : entries[anc_of_par].descendants |= chl_des;
157 : : }
158 : : // To each descendant of the child, add as ancestors the ancestors of the parent.
159 [ + - ]: 63 : const auto& par_anc = entries[parent].ancestors;
160 [ + - + + ]: 189 : for (auto dec_of_chl : Descendants(child)) {
161 : 63 : entries[dec_of_chl].ancestors |= par_anc;
162 : : }
163 : : }
164 : :
165 : : /** Compute the aggregate feerate of a set of nodes in this graph.
166 : : *
167 : : * Complexity: O(N) where N=elems.Count().
168 : : **/
169 [ # # ]: 0 : FeeFrac FeeRate(const SetType& elems) const noexcept
170 : : {
171 : 0 : FeeFrac ret;
172 [ # # # # ]: 0 : for (auto pos : elems) ret += entries[pos].feerate;
173 : 0 : return ret;
174 : : }
175 : :
176 : : /** Find some connected component within the subset "todo" of this graph.
177 : : *
178 : : * Specifically, this finds the connected component which contains the first transaction of
179 : : * todo (if any).
180 : : *
181 : : * Two transactions are considered connected if they are both in `todo`, and one is an ancestor
182 : : * of the other in the entire graph (so not just within `todo`), or transitively there is a
183 : : * path of transactions connecting them. This does mean that if `todo` contains a transaction
184 : : * and a grandparent, but misses the parent, they will still be part of the same component.
185 : : *
186 : : * Complexity: O(ret.Count()).
187 : : */
188 [ # # ]: 0 : SetType FindConnectedComponent(const SetType& todo) const noexcept
189 : : {
190 [ # # ]: 0 : if (todo.None()) return todo;
191 : 0 : auto to_add = SetType::Singleton(todo.First());
192 : 0 : SetType ret;
193 : : do {
194 : 0 : SetType old = ret;
195 [ # # # # ]: 0 : for (auto add : to_add) {
196 : 0 : ret |= Descendants(add);
197 : 0 : ret |= Ancestors(add);
198 : : }
199 [ # # ]: 0 : ret &= todo;
200 : 0 : to_add = ret - old;
201 [ # # ]: 0 : } while (to_add.Any());
202 : 0 : return ret;
203 : : }
204 : :
205 : : /** Determine if a subset is connected.
206 : : *
207 : : * Complexity: O(subset.Count()).
208 : : */
209 : 0 : bool IsConnected(const SetType& subset) const noexcept
210 : : {
211 [ # # ]: 0 : return FindConnectedComponent(subset) == subset;
212 : : }
213 : :
214 : : /** Determine if this entire graph is connected.
215 : : *
216 : : * Complexity: O(TxCount()).
217 : : */
218 : 0 : bool IsConnected() const noexcept { return IsConnected(SetType::Fill(TxCount())); }
219 : :
220 : : /** Append the entries of select to list in a topologically valid order.
221 : : *
222 : : * Complexity: O(select.Count() * log(select.Count())).
223 : : */
224 [ # # ]: 0 : void AppendTopo(std::vector<ClusterIndex>& list, const SetType& select) const noexcept
225 : : {
226 : 0 : ClusterIndex old_len = list.size();
227 [ # # # # ]: 0 : for (auto i : select) list.push_back(i);
228 : 0 : std::sort(list.begin() + old_len, list.end(), [&](ClusterIndex a, ClusterIndex b) noexcept {
229 [ # # ]: 0 : const auto a_anc_count = entries[a].ancestors.Count();
230 : 0 : const auto b_anc_count = entries[b].ancestors.Count();
231 [ # # ]: 0 : if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count;
232 : 0 : return a < b;
233 : : });
234 : 0 : }
235 : : };
236 : :
237 : : /** A set of transactions together with their aggregate feerate. */
238 : : template<typename SetType>
239 : : struct SetInfo
240 : : {
241 : : /** The transactions in the set. */
242 : 0 : SetType transactions;
243 : : /** Their combined fee and size. */
244 : 0 : FeeFrac feerate;
245 : :
246 : : /** Construct a SetInfo for the empty set. */
247 [ # # ]: 0 : SetInfo() noexcept = default;
248 : :
249 : : /** Construct a SetInfo for a specified set and feerate. */
250 : 0 : SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {}
251 : :
252 : : /** Construct a SetInfo for a given transaction in a depgraph. */
253 : 0 : explicit SetInfo(const DepGraph<SetType>& depgraph, ClusterIndex pos) noexcept :
254 : 0 : transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {}
255 : :
256 : : /** Construct a SetInfo for a set of transactions in a depgraph. */
257 : 0 : explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept :
258 : 0 : transactions(txn), feerate(depgraph.FeeRate(txn)) {}
259 : :
260 : : /** Add the transactions of other to this SetInfo (no overlap allowed). */
261 : 0 : SetInfo& operator|=(const SetInfo& other) noexcept
262 : : {
263 : 0 : Assume(!transactions.Overlaps(other.transactions));
264 : 0 : transactions |= other.transactions;
265 : 0 : feerate += other.feerate;
266 : 0 : return *this;
267 : : }
268 : :
269 : : /** Construct a new SetInfo equal to this, with more transactions added (which may overlap
270 : : * with the existing transactions in the SetInfo). */
271 : 0 : [[nodiscard]] SetInfo Add(const DepGraph<SetType>& depgraph, const SetType& txn) const noexcept
272 : : {
273 : 0 : return {transactions | txn, feerate + depgraph.FeeRate(txn - transactions)};
274 : : }
275 : :
276 : : /** Swap two SetInfo objects. */
277 : 0 : friend void swap(SetInfo& a, SetInfo& b) noexcept
278 : : {
279 : 0 : swap(a.transactions, b.transactions);
280 : 0 : swap(a.feerate, b.feerate);
281 : : }
282 : :
283 : : /** Permit equality testing. */
284 [ # # # # : 0 : friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default;
# # # # #
# # # ]
285 : : };
286 : :
287 : : /** Compute the feerates of the chunks of linearization. */
288 : : template<typename SetType>
289 : 0 : std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> linearization) noexcept
290 : : {
291 : 0 : std::vector<FeeFrac> ret;
292 [ # # ]: 0 : for (ClusterIndex i : linearization) {
293 : : /** The new chunk to be added, initially a singleton. */
294 : 0 : auto new_chunk = depgraph.FeeRate(i);
295 : : // As long as the new chunk has a higher feerate than the last chunk so far, absorb it.
296 [ # # # # ]: 0 : while (!ret.empty() && new_chunk >> ret.back()) {
297 : 0 : new_chunk += ret.back();
298 : 0 : ret.pop_back();
299 : : }
300 : : // Actually move that new chunk into the chunking.
301 : 0 : ret.push_back(std::move(new_chunk));
302 : : }
303 : 0 : return ret;
304 : : }
305 : :
306 : : /** Data structure encapsulating the chunking of a linearization, permitting removal of subsets. */
307 : : template<typename SetType>
308 : 0 : class LinearizationChunking
309 : : {
310 : : /** The depgraph this linearization is for. */
311 : : const DepGraph<SetType>& m_depgraph;
312 : :
313 : : /** The linearization we started from, possibly with removed prefix stripped. */
314 : : Span<const ClusterIndex> m_linearization;
315 : :
316 : : /** Chunk sets and their feerates, of what remains of the linearization. */
317 : : std::vector<SetInfo<SetType>> m_chunks;
318 : :
319 : : /** How large a prefix of m_chunks corresponds to removed transactions. */
320 : : ClusterIndex m_chunks_skip{0};
321 : :
322 : : /** Which transactions remain in the linearization. */
323 : : SetType m_todo;
324 : :
325 : : /** Fill the m_chunks variable, and remove the done prefix of m_linearization. */
326 : 0 : void BuildChunks() noexcept
327 : : {
328 : : // Caller must clear m_chunks.
329 : 0 : Assume(m_chunks.empty());
330 : :
331 : : // Chop off the initial part of m_linearization that is already done.
332 [ # # # # ]: 0 : while (!m_linearization.empty() && !m_todo[m_linearization.front()]) {
333 : 0 : m_linearization = m_linearization.subspan(1);
334 : : }
335 : :
336 : : // Iterate over the remaining entries in m_linearization. This is effectively the same
337 : : // algorithm as ChunkLinearization, but supports skipping parts of the linearization and
338 : : // keeps track of the sets themselves instead of just their feerates.
339 [ # # ]: 0 : for (auto idx : m_linearization) {
340 [ # # ]: 0 : if (!m_todo[idx]) continue;
341 : : // Start with an initial chunk containing just element idx.
342 : 0 : SetInfo add(m_depgraph, idx);
343 : : // Absorb existing final chunks into add while they have lower feerate.
344 [ # # # # ]: 0 : while (!m_chunks.empty() && add.feerate >> m_chunks.back().feerate) {
345 : 0 : add |= m_chunks.back();
346 : 0 : m_chunks.pop_back();
347 : : }
348 : : // Remember new chunk.
349 : 0 : m_chunks.push_back(std::move(add));
350 : : }
351 : 0 : }
352 : :
353 : : public:
354 : : /** Initialize a LinearizationSubset object for a given length of linearization. */
355 : 0 : explicit LinearizationChunking(const DepGraph<SetType>& depgraph LIFETIMEBOUND, Span<const ClusterIndex> lin LIFETIMEBOUND) noexcept :
356 : 0 : m_depgraph(depgraph), m_linearization(lin)
357 : : {
358 : : // Mark everything in lin as todo still.
359 [ # # ]: 0 : for (auto i : m_linearization) m_todo.Set(i);
360 : : // Compute the initial chunking.
361 : 0 : m_chunks.reserve(depgraph.TxCount());
362 : 0 : BuildChunks();
363 : 0 : }
364 : :
365 : : /** Determine how many chunks remain in the linearization. */
366 [ # # # # : 0 : ClusterIndex NumChunksLeft() const noexcept { return m_chunks.size() - m_chunks_skip; }
# # # # #
# # # # #
# # ]
367 : :
368 : : /** Access a chunk. Chunk 0 is the highest-feerate prefix of what remains. */
369 : 0 : const SetInfo<SetType>& GetChunk(ClusterIndex n) const noexcept
370 : : {
371 [ # # ]: 0 : Assume(n + m_chunks_skip < m_chunks.size());
372 [ # # # # : 0 : return m_chunks[n + m_chunks_skip];
# # # # ]
373 : : }
374 : :
375 : : /** Remove some subset of transactions from the linearization. */
376 [ # # ]: 0 : void MarkDone(SetType subset) noexcept
377 : : {
378 : 0 : Assume(subset.Any());
379 [ # # ]: 0 : Assume(subset.IsSubsetOf(m_todo));
380 [ # # ]: 0 : m_todo -= subset;
381 [ # # ]: 0 : if (GetChunk(0).transactions == subset) {
382 : : // If the newly done transactions exactly match the first chunk of the remainder of
383 : : // the linearization, we do not need to rechunk; just remember to skip one
384 : : // additional chunk.
385 : 0 : ++m_chunks_skip;
386 : : // With subset marked done, some prefix of m_linearization will be done now. How long
387 : : // that prefix is depends on how many done elements were interspersed with subset,
388 : : // but at least as many transactions as there are in subset.
389 : 0 : m_linearization = m_linearization.subspan(subset.Count());
390 : : } else {
391 : : // Otherwise rechunk what remains of m_linearization.
392 [ # # ]: 0 : m_chunks.clear();
393 : 0 : m_chunks_skip = 0;
394 : 0 : BuildChunks();
395 : : }
396 : 0 : }
397 : :
398 : : /** Find the shortest intersection between subset and the prefixes of remaining chunks
399 : : * of the linearization that has a feerate not below subset's.
400 : : *
401 : : * This is a crucial operation in guaranteeing improvements to linearizations. If subset has
402 : : * a feerate not below GetChunk(0)'s, then moving IntersectPrefixes(subset) to the front of
403 : : * (what remains of) the linearization is guaranteed not to make it worse at any point.
404 : : *
405 : : * See https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032 for background.
406 : : */
407 : 0 : SetInfo<SetType> IntersectPrefixes(const SetInfo<SetType>& subset) const noexcept
408 : : {
409 : 0 : Assume(subset.transactions.IsSubsetOf(m_todo));
410 : 0 : SetInfo<SetType> accumulator;
411 : : // Iterate over all chunks of the remaining linearization.
412 [ # # ]: 0 : for (ClusterIndex i = 0; i < NumChunksLeft(); ++i) {
413 : : // Find what (if any) intersection the chunk has with subset.
414 [ # # ]: 0 : const SetType to_add = GetChunk(i).transactions & subset.transactions;
415 [ # # ]: 0 : if (to_add.Any()) {
416 : : // If adding that to accumulator makes us hit all of subset, we are done as no
417 : : // shorter intersection with higher/equal feerate exists.
418 : 0 : accumulator.transactions |= to_add;
419 [ # # ]: 0 : if (accumulator.transactions == subset.transactions) break;
420 : : // Otherwise update the accumulator feerate.
421 [ # # ]: 0 : accumulator.feerate += m_depgraph.FeeRate(to_add);
422 : : // If that does result in something better, or something with the same feerate but
423 : : // smaller, return that. Even if a longer, higher-feerate intersection exists, it
424 : : // does not hurt to return the shorter one (the remainder of the longer intersection
425 : : // will generally be found in the next call to Intersect, but even if not, it is not
426 : : // required for the improvement guarantee this function makes).
427 [ # # ]: 0 : if (!(accumulator.feerate << subset.feerate)) return accumulator;
428 : : }
429 : : }
430 : 0 : return subset;
431 : : }
432 : : };
433 : :
434 : : /** Class encapsulating the state needed to find the best remaining ancestor set.
435 : : *
436 : : * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
437 : : * MarkDone.
438 : : *
439 : : * As long as any part of the graph remains, FindCandidateSet() can be called which will return a
440 : : * SetInfo with the highest-feerate ancestor set that remains (an ancestor set is a single
441 : : * transaction together with all its remaining ancestors).
442 : : */
443 : : template<typename SetType>
444 : 0 : class AncestorCandidateFinder
445 : : {
446 : : /** Internal dependency graph. */
447 : : const DepGraph<SetType>& m_depgraph;
448 : : /** Which transaction are left to include. */
449 : : SetType m_todo;
450 : : /** Precomputed ancestor-set feerates (only kept up-to-date for indices in m_todo). */
451 : : std::vector<FeeFrac> m_ancestor_set_feerates;
452 : :
453 : : public:
454 : : /** Construct an AncestorCandidateFinder for a given cluster.
455 : : *
456 : : * Complexity: O(N^2) where N=depgraph.TxCount().
457 : : */
458 : 0 : AncestorCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept :
459 : 0 : m_depgraph(depgraph),
460 : 0 : m_todo{SetType::Fill(depgraph.TxCount())},
461 : 0 : m_ancestor_set_feerates(depgraph.TxCount())
462 : : {
463 : : // Precompute ancestor-set feerates.
464 [ # # ]: 0 : for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
465 : : /** The remaining ancestors for transaction i. */
466 [ # # ]: 0 : SetType anc_to_add = m_depgraph.Ancestors(i);
467 [ # # ]: 0 : FeeFrac anc_feerate;
468 : : // Reuse accumulated feerate from first ancestor, if usable.
469 [ # # ]: 0 : Assume(anc_to_add.Any());
470 : 0 : ClusterIndex first = anc_to_add.First();
471 [ # # ]: 0 : if (first < i) {
472 : 0 : anc_feerate = m_ancestor_set_feerates[first];
473 : 0 : Assume(!anc_feerate.IsEmpty());
474 : 0 : anc_to_add -= m_depgraph.Ancestors(first);
475 : : }
476 : : // Add in other ancestors (which necessarily include i itself).
477 : 0 : Assume(anc_to_add[i]);
478 : 0 : anc_feerate += m_depgraph.FeeRate(anc_to_add);
479 : : // Store the result.
480 : 0 : m_ancestor_set_feerates[i] = anc_feerate;
481 : : }
482 : 0 : }
483 : :
484 : : /** Remove a set of transactions from the set of to-be-linearized ones.
485 : : *
486 : : * The same transaction may not be MarkDone()'d twice.
487 : : *
488 : : * Complexity: O(N*M) where N=depgraph.TxCount(), M=select.Count().
489 : : */
490 [ # # ]: 0 : void MarkDone(SetType select) noexcept
491 : : {
492 : 0 : Assume(select.Any());
493 [ # # ]: 0 : Assume(select.IsSubsetOf(m_todo));
494 [ # # ]: 0 : m_todo -= select;
495 [ # # # # ]: 0 : for (auto i : select) {
496 [ # # ]: 0 : auto feerate = m_depgraph.FeeRate(i);
497 [ # # # # ]: 0 : for (auto j : m_depgraph.Descendants(i) & m_todo) {
498 : 0 : m_ancestor_set_feerates[j] -= feerate;
499 : : }
500 : : }
501 : 0 : }
502 : :
503 : : /** Check whether any unlinearized transactions remain. */
504 : 0 : bool AllDone() const noexcept
505 : : {
506 [ # # # # : 0 : return m_todo.None();
# # # # ]
507 : : }
508 : :
509 : : /** Find the best (highest-feerate, smallest among those in case of a tie) ancestor set
510 : : * among the remaining transactions. Requires !AllDone().
511 : : *
512 : : * Complexity: O(N) where N=depgraph.TxCount();
513 : : */
514 [ # # ]: 0 : SetInfo<SetType> FindCandidateSet() const noexcept
515 : : {
516 : 0 : Assume(!AllDone());
517 : 0 : std::optional<ClusterIndex> best;
518 [ # # # # : 0 : for (auto i : m_todo) {
# # ]
519 [ # # ]: 0 : if (best.has_value()) {
520 [ # # ]: 0 : Assume(!m_ancestor_set_feerates[i].IsEmpty());
521 [ # # ]: 0 : if (!(m_ancestor_set_feerates[i] > m_ancestor_set_feerates[*best])) continue;
522 : : }
523 : 0 : best = i;
524 : : }
525 : 0 : Assume(best.has_value());
526 : 0 : return {m_depgraph.Ancestors(*best) & m_todo, m_ancestor_set_feerates[*best]};
527 : : }
528 : : };
529 : :
530 : : /** Class encapsulating the state needed to perform search for good candidate sets.
531 : : *
532 : : * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling
533 : : * MarkDone().
534 : : *
535 : : * As long as any part of the graph remains, FindCandidateSet() can be called to perform a search
536 : : * over the set of topologically-valid subsets of that remainder, with a limit on how many
537 : : * combinations are tried.
538 : : */
539 : : template<typename SetType>
540 : : class SearchCandidateFinder
541 : : {
542 : : /** Internal RNG. */
543 : : InsecureRandomContext m_rng;
544 : : /** Internal dependency graph for the cluster. */
545 : : const DepGraph<SetType>& m_depgraph;
546 : : /** Which transactions are left to do (sorted indices). */
547 : : SetType m_todo;
548 : :
549 : : public:
550 : : /** Construct a candidate finder for a graph.
551 : : *
552 : : * @param[in] depgraph Dependency graph for the to-be-linearized cluster.
553 : : * @param[in] rng_seed A random seed to control the search order.
554 : : *
555 : : * Complexity: O(1).
556 : : */
557 : 0 : SearchCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND, uint64_t rng_seed) noexcept :
558 : 0 : m_rng(rng_seed),
559 : 0 : m_depgraph(depgraph),
560 : 0 : m_todo(SetType::Fill(depgraph.TxCount())) {}
561 : :
562 : : /** Check whether any unlinearized transactions remain. */
563 : 0 : bool AllDone() const noexcept
564 : : {
565 [ # # # # ]: 0 : return m_todo.None();
566 : : }
567 : :
568 : : /** Find a high-feerate topologically-valid subset of what remains of the cluster.
569 : : * Requires !AllDone().
570 : : *
571 : : * @param[in] max_iterations The maximum number of optimization steps that will be performed.
572 : : * @param[in] best A set/feerate pair with an already-known good candidate. This may
573 : : * be empty.
574 : : * @return A pair of:
575 : : * - The best (highest feerate, smallest size as tiebreaker)
576 : : * topologically valid subset (and its feerate) that was
577 : : * encountered during search. It will be at least as good as the
578 : : * best passed in (if not empty).
579 : : * - The number of optimization steps that were performed. This will
580 : : * be <= max_iterations. If strictly < max_iterations, the
581 : : * returned subset is optimal.
582 : : *
583 : : * Complexity: O(N * min(max_iterations, 2^N)) where N=depgraph.TxCount().
584 : : */
585 [ # # ]: 0 : std::pair<SetInfo<SetType>, uint64_t> FindCandidateSet(uint64_t max_iterations, SetInfo<SetType> best) noexcept
586 : : {
587 : 0 : Assume(!AllDone());
588 : :
589 : : /** Type for work queue items. */
590 : : struct WorkItem
591 : : {
592 : : /** Set of transactions definitely included (and its feerate). This must be a subset
593 : : * of m_todo, and be topologically valid (includes all in-m_todo ancestors of
594 : : * itself). */
595 : : SetInfo<SetType> inc;
596 : : /** Set of undecided transactions. This must be a subset of m_todo, and have no overlap
597 : : * with inc. The set (inc | und) must be topologically valid. */
598 : : SetType und;
599 : :
600 : : /** Construct a new work item. */
601 : 0 : WorkItem(SetInfo<SetType>&& i, SetType&& u) noexcept :
602 : 0 : inc(std::move(i)), und(std::move(u)) {}
603 : :
604 : : /** Swap two WorkItems. */
605 : 0 : void Swap(WorkItem& other) noexcept
606 : : {
607 : 0 : swap(inc, other.inc);
608 : 0 : swap(und, other.und);
609 : 0 : }
610 : : };
611 : :
612 : : /** The queue of work items. */
613 : 0 : VecDeque<WorkItem> queue;
614 [ # # # # : 0 : queue.reserve(std::max<size_t>(256, 2 * m_todo.Count()));
# # ]
615 : :
616 : : // Create an initial entry with m_todo as undecided. Also use it as best if not provided,
617 : : // so that during the work processing loop below, and during the add_fn/split_fn calls, we
618 : : // do not need to deal with the best=empty case.
619 [ # # ]: 0 : if (best.feerate.IsEmpty()) best = SetInfo(m_depgraph, m_todo);
620 : 0 : queue.emplace_back(SetInfo<SetType>{}, SetType{m_todo});
621 : :
622 : : /** Local copy of the iteration limit. */
623 : 0 : uint64_t iterations_left = max_iterations;
624 : :
625 : : /** Internal function to add an item to the queue of elements to explore if there are any
626 : : * transactions left to split on, and to update best.
627 : : *
628 : : * - inc: the "inc" value for the new work item (must be topological).
629 : : * - und: the "und" value for the new work item ((inc | und) must be topological).
630 : : */
631 [ # # ]: 0 : auto add_fn = [&](SetInfo<SetType> inc, SetType und) noexcept {
632 [ # # ]: 0 : if (!inc.feerate.IsEmpty()) {
633 : : // If inc's feerate is better than best's, remember it as our new best.
634 [ # # ]: 0 : if (inc.feerate > best.feerate) {
635 : 0 : best = inc;
636 : : }
637 : : } else {
638 : 0 : Assume(inc.transactions.None());
639 : : }
640 : :
641 : : // Make sure there are undecided transactions left to split on.
642 [ # # ]: 0 : if (und.None()) return;
643 : :
644 : : // Actually construct a new work item on the queue. Due to the switch to DFS when queue
645 : : // space runs out (see below), we know that no reallocation of the queue should ever
646 : : // occur.
647 : 0 : Assume(queue.size() < queue.capacity());
648 : 0 : queue.emplace_back(std::move(inc), std::move(und));
649 : : };
650 : :
651 : : /** Internal process function. It takes an existing work item, and splits it in two: one
652 : : * with a particular transaction (and its ancestors) included, and one with that
653 : : * transaction (and its descendants) excluded. */
654 : 0 : auto split_fn = [&](WorkItem&& elem) noexcept {
655 : : // Any queue element must have undecided transactions left, otherwise there is nothing
656 : : // to explore anymore.
657 [ # # ]: 0 : Assume(elem.und.Any());
658 : : // The included and undecided set are all subsets of m_todo.
659 [ # # # # ]: 0 : Assume(elem.inc.transactions.IsSubsetOf(m_todo) && elem.und.IsSubsetOf(m_todo));
660 : : // Included transactions cannot be undecided.
661 [ # # ]: 0 : Assume(!elem.inc.transactions.Overlaps(elem.und));
662 : :
663 : : // Pick the first undecided transaction as the one to split on.
664 [ # # ]: 0 : const ClusterIndex split = elem.und.First();
665 : :
666 : : // Add a work item corresponding to exclusion of the split transaction.
667 : 0 : const auto& desc = m_depgraph.Descendants(split);
668 : 0 : add_fn(/*inc=*/elem.inc,
669 : 0 : /*und=*/elem.und - desc);
670 : :
671 : : // Add a work item corresponding to inclusion of the split transaction.
672 : 0 : const auto anc = m_depgraph.Ancestors(split) & m_todo;
673 : 0 : add_fn(/*inc=*/elem.inc.Add(m_depgraph, anc),
674 : 0 : /*und=*/elem.und - anc);
675 : :
676 : : // Account for the performed split.
677 : 0 : --iterations_left;
678 : : };
679 : :
680 : : // Work processing loop.
681 : : //
682 : : // New work items are always added at the back of the queue, but items to process use a
683 : : // hybrid approach where they can be taken from the front or the back.
684 : : //
685 : : // Depth-first search (DFS) corresponds to always taking from the back of the queue. This
686 : : // is very memory-efficient (linear in the number of transactions). Breadth-first search
687 : : // (BFS) corresponds to always taking from the front, which potentially uses more memory
688 : : // (up to exponential in the transaction count), but seems to work better in practice.
689 : : //
690 : : // The approach here combines the two: use BFS (plus random swapping) until the queue grows
691 : : // too large, at which point we temporarily switch to DFS until the size shrinks again.
692 [ # # ]: 0 : while (!queue.empty()) {
693 : : // Randomly swap the first two items to randomize the search order.
694 [ # # # # ]: 0 : if (queue.size() > 1 && m_rng.randbool()) {
695 : 0 : queue[0].Swap(queue[1]);
696 : : }
697 : :
698 : : // Processing the first queue item, and then using DFS for everything it gives rise to,
699 : : // may increase the queue size by the number of undecided elements in there, minus 1
700 : : // for the first queue item being removed. Thus, only when that pushes the queue over
701 : : // its capacity can we not process from the front (BFS), and should we use DFS.
702 [ # # ]: 0 : while (queue.size() - 1 + queue.front().und.Count() > queue.capacity()) {
703 [ # # ]: 0 : if (!iterations_left) break;
704 : 0 : auto elem = queue.back();
705 : 0 : queue.pop_back();
706 : 0 : split_fn(std::move(elem));
707 : : }
708 : :
709 : : // Process one entry from the front of the queue (BFS exploration)
710 [ # # ]: 0 : if (!iterations_left) break;
711 [ # # ]: 0 : auto elem = queue.front();
712 : 0 : queue.pop_front();
713 : 0 : split_fn(std::move(elem));
714 : : }
715 : :
716 : : // Return the found best set and the number of iterations performed.
717 : 0 : return {std::move(best), max_iterations - iterations_left};
718 : 0 : }
719 : :
720 : : /** Remove a subset of transactions from the cluster being linearized.
721 : : *
722 : : * Complexity: O(N) where N=done.Count().
723 : : */
724 : 0 : void MarkDone(const SetType& done) noexcept
725 : : {
726 : 0 : Assume(done.Any());
727 : 0 : Assume(done.IsSubsetOf(m_todo));
728 : 0 : m_todo -= done;
729 : 0 : }
730 : : };
731 : :
732 : : /** Find or improve a linearization for a cluster.
733 : : *
734 : : * @param[in] depgraph Dependency graph of the cluster to be linearized.
735 : : * @param[in] max_iterations Upper bound on the number of optimization steps that will be done.
736 : : * @param[in] rng_seed A random number seed to control search order. This prevents peers
737 : : * from predicting exactly which clusters would be hard for us to
738 : : * linearize.
739 : : * @param[in] old_linearization An existing linearization for the cluster (which must be
740 : : * topologically valid), or empty.
741 : : * @return A pair of:
742 : : * - The resulting linearization. It is guaranteed to be at least as
743 : : * good (in the feerate diagram sense) as old_linearization.
744 : : * - A boolean indicating whether the result is guaranteed to be
745 : : * optimal.
746 : : *
747 : : * Complexity: O(N * min(max_iterations + N, 2^N)) where N=depgraph.TxCount().
748 : : */
749 : : template<typename SetType>
750 [ # # ]: 0 : std::pair<std::vector<ClusterIndex>, bool> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, Span<const ClusterIndex> old_linearization = {}) noexcept
751 : : {
752 [ # # # # : 0 : Assume(old_linearization.empty() || old_linearization.size() == depgraph.TxCount());
# # ]
753 [ # # ]: 0 : if (depgraph.TxCount() == 0) return {{}, true};
754 : :
755 : 0 : uint64_t iterations_left = max_iterations;
756 : 0 : std::vector<ClusterIndex> linearization;
757 : :
758 : 0 : AncestorCandidateFinder anc_finder(depgraph);
759 : 0 : SearchCandidateFinder src_finder(depgraph, rng_seed);
760 : 0 : linearization.reserve(depgraph.TxCount());
761 : 0 : bool optimal = true;
762 : :
763 : : /** Chunking of what remains of the old linearization. */
764 : 0 : LinearizationChunking old_chunking(depgraph, old_linearization);
765 : :
766 : : while (true) {
767 : : // Find the highest-feerate prefix of the remainder of old_linearization.
768 [ # # ]: 0 : SetInfo<SetType> best_prefix;
769 [ # # ]: 0 : if (old_chunking.NumChunksLeft()) best_prefix = old_chunking.GetChunk(0);
770 : :
771 : : // Then initialize best to be either the best remaining ancestor set, or the first chunk.
772 [ # # ]: 0 : auto best = anc_finder.FindCandidateSet();
773 [ # # # # ]: 0 : if (!best_prefix.feerate.IsEmpty() && best_prefix.feerate >= best.feerate) best = best_prefix;
774 : :
775 : : // Invoke bounded search to update best, with up to half of our remaining iterations as
776 : : // limit.
777 : 0 : uint64_t max_iterations_now = (iterations_left + 1) / 2;
778 : 0 : uint64_t iterations_done_now = 0;
779 [ # # ]: 0 : std::tie(best, iterations_done_now) = src_finder.FindCandidateSet(max_iterations_now, best);
780 : 0 : iterations_left -= iterations_done_now;
781 : :
782 [ # # ]: 0 : if (iterations_done_now == max_iterations_now) {
783 [ # # ]: 0 : optimal = false;
784 : : // If the search result is not (guaranteed to be) optimal, run intersections to make
785 : : // sure we don't pick something that makes us unable to reach further diagram points
786 : : // of the old linearization.
787 [ # # ]: 0 : if (old_chunking.NumChunksLeft() > 0) {
788 : 0 : best = old_chunking.IntersectPrefixes(best);
789 : : }
790 : : }
791 : :
792 : : // Add to output in topological order.
793 : 0 : depgraph.AppendTopo(linearization, best.transactions);
794 : :
795 : : // Update state to reflect best is no longer to be linearized.
796 [ # # ]: 0 : anc_finder.MarkDone(best.transactions);
797 [ # # ]: 0 : if (anc_finder.AllDone()) break;
798 [ # # ]: 0 : src_finder.MarkDone(best.transactions);
799 [ # # ]: 0 : if (old_chunking.NumChunksLeft() > 0) {
800 : 0 : old_chunking.MarkDone(best.transactions);
801 : : }
802 : : }
803 : :
804 : 0 : return {std::move(linearization), optimal};
805 : 0 : }
806 : :
807 : : /** Improve a given linearization.
808 : : *
809 : : * @param[in] depgraph Dependency graph of the cluster being linearized.
810 : : * @param[in,out] linearization On input, an existing linearization for depgraph. On output, a
811 : : * potentially better linearization for the same graph.
812 : : *
813 : : * Postlinearization guarantees:
814 : : * - The resulting chunks are connected.
815 : : * - If the input has a tree shape (either all transactions have at most one child, or all
816 : : * transactions have at most one parent), the result is optimal.
817 : : * - Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end,
818 : : * optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least
819 : : * as good as L1. This means that replacing transactions with same-size higher-fee transactions
820 : : * will not worsen linearizations through a "drop conflicts, append new transactions,
821 : : * postlinearize" process.
822 : : */
823 : : template<typename SetType>
824 : 0 : void PostLinearize(const DepGraph<SetType>& depgraph, Span<ClusterIndex> linearization)
825 : : {
826 : : // This algorithm performs a number of passes (currently 2); the even ones operate from back to
827 : : // front, the odd ones from front to back. Each results in an equal-or-better linearization
828 : : // than the one started from.
829 : : // - One pass in either direction guarantees that the resulting chunks are connected.
830 : : // - Each direction corresponds to one shape of tree being linearized optimally (forward passes
831 : : // guarantee this for graphs where each transaction has at most one child; backward passes
832 : : // guarantee this for graphs where each transaction has at most one parent).
833 : : // - Starting with a backward pass guarantees the moved-tree property.
834 : : //
835 : : // During an odd (forward) pass, the high-level operation is:
836 : : // - Start with an empty list of groups L=[].
837 : : // - For every transaction i in the old linearization, from front to back:
838 : : // - Append a new group C=[i], containing just i, to the back of L.
839 : : // - While L has at least one group before C, and the group immediately before C has feerate
840 : : // lower than C:
841 : : // - If C depends on P:
842 : : // - Merge P into C, making C the concatenation of P+C, continuing with the combined C.
843 : : // - Otherwise:
844 : : // - Swap P with C, continuing with the now-moved C.
845 : : // - The output linearization is the concatenation of the groups in L.
846 : : //
847 : : // During even (backward) passes, i iterates from the back to the front of the existing
848 : : // linearization, and new groups are prepended instead of appended to the list L. To enable
849 : : // more code reuse, both passes append groups, but during even passes the meanings of
850 : : // parent/child, and of high/low feerate are reversed, and the final concatenation is reversed
851 : : // on output.
852 : : //
853 : : // In the implementation below, the groups are represented by singly-linked lists (pointing
854 : : // from the back to the front), which are themselves organized in a singly-linked circular
855 : : // list (each group pointing to its predecessor, with a special sentinel group at the front
856 : : // that points back to the last group).
857 : : //
858 : : // Information about transaction t is stored in entries[t + 1], while the sentinel is in
859 : : // entries[0].
860 : :
861 : : /** Index of the sentinel in the entries array below. */
862 : : static constexpr ClusterIndex SENTINEL{0};
863 : : /** Indicator that a group has no previous transaction. */
864 : : static constexpr ClusterIndex NO_PREV_TX{0};
865 : :
866 : :
867 : : /** Data structure per transaction entry. */
868 : 0 : struct TxEntry
869 : : {
870 : : /** The index of the previous transaction in this group; NO_PREV_TX if this is the first
871 : : * entry of a group. */
872 : : ClusterIndex prev_tx;
873 : :
874 : : // The fields below are only used for transactions that are the last one in a group
875 : : // (referred to as tail transactions below).
876 : :
877 : : /** Index of the first transaction in this group, possibly itself. */
878 : : ClusterIndex first_tx;
879 : : /** Index of the last transaction in the previous group. The first group (the sentinel)
880 : : * points back to the last group here, making it a singly-linked circular list. */
881 : : ClusterIndex prev_group;
882 : : /** All transactions in the group. Empty for the sentinel. */
883 : : SetType group;
884 : : /** All dependencies of the group (descendants in even passes; ancestors in odd ones). */
885 : : SetType deps;
886 : : /** The combined fee/size of transactions in the group. Fee is negated in even passes. */
887 : : FeeFrac feerate;
888 : : };
889 : :
890 : : // As an example, consider the state corresponding to the linearization [1,0,3,2], with
891 : : // groups [1,0,3] and [2], in an odd pass. The linked lists would be:
892 : : //
893 : : // +-----+
894 : : // 0<-P-- | 0 S | ---\ Legend:
895 : : // +-----+ |
896 : : // ^ | - digit in box: entries index
897 : : // /--------------F---------+ G | (note: one more than tx value)
898 : : // v \ | | - S: sentinel group
899 : : // +-----+ +-----+ +-----+ | (empty feerate)
900 : : // 0<-P-- | 2 | <--P-- | 1 | <--P-- | 4 T | | - T: tail transaction, contains
901 : : // +-----+ +-----+ +-----+ | fields beyond prev_tv.
902 : : // ^ | - P: prev_tx reference
903 : : // G G - F: first_tx reference
904 : : // | | - G: prev_group reference
905 : : // +-----+ |
906 : : // 0<-P-- | 3 T | <--/
907 : : // +-----+
908 : : // ^ |
909 : : // \-F-/
910 : : //
911 : : // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with
912 : : // groups [2] and [3,0,1].
913 : :
914 : 0 : std::vector<TxEntry> entries(linearization.size() + 1);
915 : :
916 : : // Perform two passes over the linearization.
917 [ # # ]: 0 : for (int pass = 0; pass < 2; ++pass) {
918 : 0 : int rev = !(pass & 1);
919 : : // Construct a sentinel group, identifying the start of the list.
920 : 0 : entries[SENTINEL].prev_group = SENTINEL;
921 : 0 : Assume(entries[SENTINEL].feerate.IsEmpty());
922 : :
923 : : // Iterate over all elements in the existing linearization.
924 [ # # ]: 0 : for (ClusterIndex i = 0; i < linearization.size(); ++i) {
925 : : // Even passes are from back to front; odd passes from front to back.
926 [ # # ]: 0 : ClusterIndex idx = linearization[rev ? linearization.size() - 1 - i : i];
927 : : // Construct a new group containing just idx. In even passes, the meaning of
928 : : // parent/child and high/low feerate are swapped.
929 [ # # ]: 0 : ClusterIndex cur_group = idx + 1;
930 [ # # ]: 0 : entries[cur_group].group = SetType::Singleton(idx);
931 [ # # # # ]: 0 : entries[cur_group].deps = rev ? depgraph.Descendants(idx): depgraph.Ancestors(idx);
932 : 0 : entries[cur_group].feerate = depgraph.FeeRate(idx);
933 [ # # ]: 0 : if (rev) entries[cur_group].feerate.fee = -entries[cur_group].feerate.fee;
934 : 0 : entries[cur_group].prev_tx = NO_PREV_TX; // No previous transaction in group.
935 : 0 : entries[cur_group].first_tx = cur_group; // Transaction itself is first of group.
936 : : // Insert the new group at the back of the groups linked list.
937 : 0 : entries[cur_group].prev_group = entries[SENTINEL].prev_group;
938 : 0 : entries[SENTINEL].prev_group = cur_group;
939 : :
940 : : // Start merge/swap cycle.
941 : 0 : ClusterIndex next_group = SENTINEL; // We inserted at the end, so next group is sentinel.
942 : 0 : ClusterIndex prev_group = entries[cur_group].prev_group;
943 : : // Continue as long as the current group has higher feerate than the previous one.
944 [ # # ]: 0 : while (entries[cur_group].feerate >> entries[prev_group].feerate) {
945 : : // prev_group/cur_group/next_group refer to (the last transactions of) 3
946 : : // consecutive entries in groups list.
947 [ # # ]: 0 : Assume(cur_group == entries[next_group].prev_group);
948 : 0 : Assume(prev_group == entries[cur_group].prev_group);
949 : : // The sentinel has empty feerate, which is neither higher or lower than other
950 : : // feerates. Thus, the while loop we are in here guarantees that cur_group and
951 : : // prev_group are not the sentinel.
952 : 0 : Assume(cur_group != SENTINEL);
953 : 0 : Assume(prev_group != SENTINEL);
954 [ # # ]: 0 : if (entries[cur_group].deps.Overlaps(entries[prev_group].group)) {
955 : : // There is a dependency between cur_group and prev_group; merge prev_group
956 : : // into cur_group. The group/deps/feerate fields of prev_group remain unchanged
957 : : // but become unused.
958 : 0 : entries[cur_group].group |= entries[prev_group].group;
959 : 0 : entries[cur_group].deps |= entries[prev_group].deps;
960 : 0 : entries[cur_group].feerate += entries[prev_group].feerate;
961 : : // Make the first of the current group point to the tail of the previous group.
962 : 0 : entries[entries[cur_group].first_tx].prev_tx = prev_group;
963 : : // The first of the previous group becomes the first of the newly-merged group.
964 : 0 : entries[cur_group].first_tx = entries[prev_group].first_tx;
965 : : // The previous group becomes whatever group was before the former one.
966 : 0 : prev_group = entries[prev_group].prev_group;
967 : 0 : entries[cur_group].prev_group = prev_group;
968 : : } else {
969 : : // There is no dependency between cur_group and prev_group; swap them.
970 : 0 : ClusterIndex preprev_group = entries[prev_group].prev_group;
971 : : // If PP, P, C, N were the old preprev, prev, cur, next groups, then the new
972 : : // layout becomes [PP, C, P, N]. Update prev_groups to reflect that order.
973 : 0 : entries[next_group].prev_group = prev_group;
974 : 0 : entries[prev_group].prev_group = cur_group;
975 : 0 : entries[cur_group].prev_group = preprev_group;
976 : : // The current group remains the same, but the groups before/after it have
977 : : // changed.
978 : 0 : next_group = prev_group;
979 : 0 : prev_group = preprev_group;
980 : : }
981 : : }
982 : : }
983 : :
984 : : // Convert the entries back to linearization (overwriting the existing one).
985 : 0 : ClusterIndex cur_group = entries[0].prev_group;
986 : 0 : ClusterIndex done = 0;
987 [ # # ]: 0 : while (cur_group != SENTINEL) {
988 : 0 : ClusterIndex cur_tx = cur_group;
989 : : // Traverse the transactions of cur_group (from back to front), and write them in the
990 : : // same order during odd passes, and reversed (front to back) in even passes.
991 [ # # ]: 0 : if (rev) {
992 : : do {
993 [ # # ]: 0 : *(linearization.begin() + (done++)) = cur_tx - 1;
994 [ # # ]: 0 : cur_tx = entries[cur_tx].prev_tx;
995 [ # # ]: 0 : } while (cur_tx != NO_PREV_TX);
996 : : } else {
997 : : do {
998 [ # # ]: 0 : *(linearization.end() - (++done)) = cur_tx - 1;
999 [ # # ]: 0 : cur_tx = entries[cur_tx].prev_tx;
1000 [ # # ]: 0 : } while (cur_tx != NO_PREV_TX);
1001 : : }
1002 : 0 : cur_group = entries[cur_group].prev_group;
1003 : : }
1004 : 0 : Assume(done == linearization.size());
1005 : : }
1006 : 0 : }
1007 : :
1008 : : /** Merge two linearizations for the same cluster into one that is as good as both.
1009 : : *
1010 : : * Complexity: O(N^2) where N=depgraph.TxCount(); O(N) if both inputs are identical.
1011 : : */
1012 : : template<typename SetType>
1013 : 0 : std::vector<ClusterIndex> MergeLinearizations(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> lin1, Span<const ClusterIndex> lin2)
1014 : : {
1015 : 0 : Assume(lin1.size() == depgraph.TxCount());
1016 : 0 : Assume(lin2.size() == depgraph.TxCount());
1017 : :
1018 : : /** Chunkings of what remains of both input linearizations. */
1019 : 0 : LinearizationChunking chunking1(depgraph, lin1), chunking2(depgraph, lin2);
1020 : : /** Output linearization. */
1021 [ # # ]: 0 : std::vector<ClusterIndex> ret;
1022 [ # # ]: 0 : if (depgraph.TxCount() == 0) return ret;
1023 [ # # ]: 0 : ret.reserve(depgraph.TxCount());
1024 : :
1025 : 0 : while (true) {
1026 : : // As long as we are not done, both linearizations must have chunks left.
1027 : 0 : Assume(chunking1.NumChunksLeft() > 0);
1028 [ # # ]: 0 : Assume(chunking2.NumChunksLeft() > 0);
1029 : : // Find the set to output by taking the best remaining chunk, and then intersecting it with
1030 : : // prefixes of remaining chunks of the other linearization.
1031 [ # # ]: 0 : SetInfo<SetType> best;
1032 : 0 : const auto& lin1_firstchunk = chunking1.GetChunk(0);
1033 : 0 : const auto& lin2_firstchunk = chunking2.GetChunk(0);
1034 [ # # ]: 0 : if (lin2_firstchunk.feerate >> lin1_firstchunk.feerate) {
1035 : 0 : best = chunking1.IntersectPrefixes(lin2_firstchunk);
1036 : : } else {
1037 : 0 : best = chunking2.IntersectPrefixes(lin1_firstchunk);
1038 : : }
1039 : : // Append the result to the output and mark it as done.
1040 : 0 : depgraph.AppendTopo(ret, best.transactions);
1041 [ # # ]: 0 : chunking1.MarkDone(best.transactions);
1042 [ # # ]: 0 : if (chunking1.NumChunksLeft() == 0) break;
1043 : 0 : chunking2.MarkDone(best.transactions);
1044 : : }
1045 : :
1046 : 0 : Assume(ret.size() == depgraph.TxCount());
1047 : 0 : return ret;
1048 : 0 : }
1049 : :
1050 : : } // namespace cluster_linearize
1051 : :
1052 : : #endif // BITCOIN_CLUSTER_LINEARIZE_H
|
