Replace cluster linearization algorithm with SFL#32545
Conversation
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32545. ReviewsSee the guideline for information on the review process.
If your review is incorrectly listed, please copy-paste ConflictsReviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first. |
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
3b7477b to
b920e76
Compare
1c6bb72 to
df589da
Compare
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
7d5e4dc to
23072f2
Compare
9ee20ca to
ba7464a
Compare
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
55931c3 to
47bdf8f
Compare
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
|
I have made a number of changes here since my last comment:
I won't make substantial changes like these anymore unless requested by review. |
brunoerg
left a comment
There was a problem hiding this comment.
I ran an incremental mutation test for this PR, specifically for src/cluster_linearize.h (which generated 222 mutants), considering unit (cluster_linearize_tests), functional (mempool_packages), and fuzzing.
For fuzzing, existing targets were run with qa-assets inputs. For the clusterlin_sfl target, I created a simple corpus from a few hours of executions (not very reliable).
Overall, the tests are excellent, achieving a mutation rate of over 98% (excluding equivalent mutants and some useless ones). I've commented out some unkilled mutants here; feel free to ignore them or add tests to eliminate them if it makes sense.
Happy to run it again if any relevant changes are made.
instagibbs
left a comment
There was a problem hiding this comment.
reviewed through 26661a6c655ad148d3ecf200c64b89c439b6d44a
sorry all I have is ticky-tacky, will go one more pass over before finishing
instagibbs
left a comment
There was a problem hiding this comment.
ACK edc6481
Much more straightforward than the in-master linearization approach, even ignoring its clear performance benefits.
marcofleon
left a comment
There was a problem hiding this comment.
ACK edc6481
This implementation was easier for me to review/understand than the current one on master, which I spent some time with when reviewing #30605. We'll see if I still feel that way after looking at the optimizations.
I ran the clusterlin_sfl and clusterlin_linearize fuzz targets for a while and no issues came up. Here's the coverage: sfl and linearize.
I also verified that the test vectors in the python repo are the same ones in the unit test. Both tests pass and arrive at optimal linearizations for the chosen mempool clusters.
Left a couple non-blocking comments that can be addressed in the follow up, if desired.
This also adds a per-cost variant of each.
|
Addressing review comments: diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 817d7d52cd3..7b74d433722 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -951,7 +951,12 @@ public:
{
// Add transactions one by one, in order of existing linearization.
for (DepGraphIndex tx : old_linearization) {
- auto chunk_rep = m_tx_data[tx].chunk_rep;
+ // Since this function must be called after construction, each new transaction added
+ // is in its own singleton chunk still.
+ auto chunk_rep = tx;
+ // Verify that it is indeed in its own chunk.
+ Assume(m_tx_data[tx].chunk_rep == chunk_rep);
+ // Merge the chunk upwards, as long as merging succeeds.
while (true) {
chunk_rep = MergeStep<false>(chunk_rep);
if (chunk_rep == TxIdx(-1)) break;
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index 5244fb840cd..ccf1be68768 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -320,7 +320,7 @@ std::vector<DepGraphIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanR
{
std::vector<DepGraphIndex> linearization;
TestBitSet todo = depgraph.Positions();
- // In every iteration one topologically-valid transaction is appended to linearization.
+ // In every iteration one transaction is appended to linearization.
while (todo.Any()) {
// Compute the set of transactions to select from.
TestBitSet potential_next; |
|
🚧 At least one of the CI tasks failed. HintsTry to run the tests locally, according to the documentation. However, a CI failure may still
Leave a comment here, if you need help tracking down a confusing failure. |
This adds a data structure representing the optimization state for the spanning-forest linearization algorithm (SFL), plus a fuzz test for its correctness. This is preparation for switching over Linearize() to use this algorithm. See https://delvingbitcoin.org/t/spanning-forest-cluster-linearization/1419 for a description of the algorithm.
Rather than using an ad-hoc no-dependency copy of the graph when a potentially non-topological linearization is needed in the clusterlin fuzz test, add this directly as a feature in ReadLinearization(). This is preparation for a later commit where another use for such a function is added.
This replaces the existing LIMO linearization algorithm (which internally uses ancestor set finding and candidate set finding) with the much more performant spanning-forest linearization algorithm. This removes the old candidate-set search algorithm, and several of its tests, benchmarks, and needed utility code. The worst case time per cost is similar to the previous algorithm, so ACCEPTABLE_ITERS is unchanged.
This introduces a queue of chunks that still need processing, in both MakeTopological() and OptimizationStep(). This is simultaneously: * A preparation for introducing randomization, by allowing permuting the queue. * An improvement to the fairness of suboptimal solutions, by distributing the work more fairly over chunks. * An optimization, by avoiding retrying chunks over and over again which are already known to be optimal.
This introduces a local RNG inside the SFL state, which is used to randomize various decisions inside the algorithm, in order to make it hard to create pathological clusters which predictably have bad performance. The decisions being randomized are: * When deciding what chunk to attempt to split, the queue order is randomized. * When deciding which dependency to split on, a uniformly random one is chosen among those with higher top feerate than bottom feerate within the chosen chunk. * When deciding which chunks to merge, a uniformly random one among those with the higher feerate difference is picked. * When merging two chunks, a uniformly random dependency between them is now activated. * When making the state topological, the queue of chunks to process is randomized.
This places equal-feerate chunks (with no dependencies between them) in random order in the linearization output, hiding information about DepGraph insertion order from the output. Likewise, it randomizes the order of transactions within chunks for the same reason.
This ended up never being used in txgraph.
With MergeLinearizations() gone and the LIMO-based Linearize() replaced by SFL, we do not need a class (LinearizationChunking) that can maintain an incrementally-improving chunk set anymore. Replace it with a function (ChunkLinearizationInfo) that just computes the chunks as SetInfos once, and returns them as a vector. This simplifies several call sites too.
|
Oops, sorry, I had to revert this last change because the property I claimed (each new transaction traversed in diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index 7b74d433722..d65e61d4458 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -395,7 +395,7 @@ struct SetInfo
return *this;
}
- /** Remove the transactions of other from this SetInfo (must be subset). */
+ /** Remove the transactions of other from this SetInfo (which must be a subset). */
SetInfo& operator-=(const SetInfo& other) noexcept
{
Assume(other.transactions.IsSubsetOf(transactions));
@@ -951,11 +951,7 @@ public:
{
// Add transactions one by one, in order of existing linearization.
for (DepGraphIndex tx : old_linearization) {
- // Since this function must be called after construction, each new transaction added
- // is in its own singleton chunk still.
- auto chunk_rep = tx;
- // Verify that it is indeed in its own chunk.
- Assume(m_tx_data[tx].chunk_rep == chunk_rep);
+ auto chunk_rep = m_tx_data[tx].chunk_rep;
// Merge the chunk upwards, as long as merging succeeds.
while (true) {
chunk_rep = MergeStep<false>(chunk_rep); |
|
reACK 75bdb92 Comment cleanups only
|
|
reACK 75bdb92
Yeah I was thinking |
Part of cluster mempool: #30289.
This replaces the cluster linearization algorithm introduced in #30126 and #30286 (a combination of LIMO with candidate-set search), with a completely different algorithm: spanning-forest linearization, which appears to have much better performance for hard clusters. See this post for a comparison between various linearization algorithms, and this post for benchmarks comparing them. Replaying historical mempool data on it shows that it can effectively linearize every observed cluster up to 64 transactions optimally within tens of microseconds, though pathological examples can be created which take longer.
The algorithm is effectively a very specialized version of the simplex algorithm to the problem of finding high-feerate topological subsets of clusters, but modified to find all consecutive such subsets concurrently rather than just the first one. See the post above for how it is related.
It represents the cluster as partitioned into a set of chunks, each with a spanning tree of its internal dependencies connecting the transactions. Randomized improvements are made by selecting dependencies to add and remove to these spanning trees, merging and splitting chunks, until no more improvements are possible, or a computation budget is reached. Like simplex, it does not necessarily make progress in every step, and thus has no upper bound on its runtime to find optimal, but randomization makes long runtimes very unlikely, and additionally makes it hard to adversarially construct clusters in which the algorithm reliably makes bad choices.