SFP 算法在链式 cluster 上的复杂度分析

English

背景

Bitcoin Core 的 Linearize() 函数使用 Spanning Forest（SFP）算法对 cluster 进行线性化。 SFP 算法由以下几个阶段组成：

SpanningForestState forest(depgraph, rng_seed);
forest.MakeTopological();
forest.StartOptimizing();
while (forest.OptimizeStep()) {}
forest.StartMinimizing();
while (forest.MinimizeStep()) {}

本文分析 SFP 在链式 cluster（tx_0 → tx_1 → … → tx_{N-1}）上，针对两种极端费率分布的各阶段复杂度：

各阶段分析

1. SpanningForestState（构造函数）

对每个 tx 调用 GetReducedParents() 并建立 dep 条目。链式图每个 tx 至多一个直接父节点，构造 N-1 条 dep。

两种情况完全相同：O(N)。

2. MakeTopological()

初始状态：N 个各自为一个 chunk 的 tx，所有 dep 均为 inactive。

算法逻辑：从队列中取出一个 chunk，尝试两个方向的合并：

递增费率（fee_i = i+1）

每个 tx_i 的子 tx_{i+1} 费率更高，触发 DownWard merge；父 tx_{i-1} 费率更低，触发 UpWard merge。两个方向都会引发全链级联合并：

{tx_0:1} + {tx_1:2} → {0,1 : 1.5}
{0,1:1.5} + {tx_2:3} → {0,1,2 : 2}
...
最终合并为一个 N-tx 大 chunk

每次第 k 步合并，Activate() 内的 UpdateChunk() 遍历当前 chunk 的 k 个 tx（每个 tx 有 1 条 dep），总迭代次数：

\[\sum_{k=1}^{N-1} k = \frac{N(N-1)}{2} = O(N^2)\]

复杂度：O(N²)（但每次迭代仅为 bitset 运算，常数极小）

递减费率（fee_i = N-i）

tx_i 的父费率更高（正确顺序），子费率更低（正确顺序），两个方向的合并条件均不满足，无任何合并触发。

复杂度：O(N)（N 次出队，每次直接放弃）

3. StartOptimizing() + OptimizeStep()

OptimizeStep 在每个 chunk 的 active dep 中寻找满足 top_setinfo.feerate > chunk.feerate 的候选，若找到则调用 Improve()（Deactivate + 两次 MergeSequence）拆分并重组。

递增费率

MakeTopological 后状态为 1 个大 chunk，N-1 条 active dep。

对 dep_i（parent=tx_i，child=tx_{i+1}），其 top_setinfo = {tx_0,…,tx_i}，feerate = (i+2)/2。

比较：(i+2)/2 vs (N+1)/2，即 i+2 vs N+1。对所有 i ≤ N-2 均有 i+2 ≤ N < N+1，严格不等式成立，无任何 dep 满足条件。OptimizeStep 扫描 N-1 条 dep 后立即返回。

复杂度：O(N)（单次扫描，无改进）

递减费率

MakeTopological 后状态为 N 个独立 chunk，所有 dep inactive。OptimizeStep 的内层循环对每个 inactive dep 直接 continue，无实质工作。

复杂度：O(N)（N 次出队，内层循环空转）

4. StartMinimizing() + MinimizeStep()

MinimizeStep 在每个 chunk 的 active dep 中寻找 top_setinfo.feerate == chunk.feerate 的候选，尝试将 chunk 拆分为更小的等费率块。

递增费率

1 个大 chunk，N-1 条 active dep。对 dep_i：top feerate = (i+2)/2，chunk feerate = (N+1)/2，两者永不相等（前者 < 后者的严格不等式）。have_any = false，chunk 被判定为 minimal。

复杂度：O(N)（单次扫描，立即确认 minimal）

递减费率

N 个独立 chunk，所有 dep inactive，内层循环空转。N 次 MinimizeStep 后队列清空。

复杂度：O(N)

汇总

阶段 递增费率（worst case） 递减费率（best case）
Constructor O(N) O(N)
MakeTopological O(N²)（级联合并全链） O(N)（无合并）
OptimizeStep O(N)（无改进，单次扫描） O(N)（无 active dep）
MinimizeStep O(N)（严格不等式，单次扫描） O(N)（无 active dep）
总计 O(N²) O(N)

两种情况结果均为最优线性化：

为什么 benchmark 在 N≤63 时看不出 O(N²)？

实测数据（优化前，递增费率链）

N 总指令数 指令数/tx
9 13,855 1,539
16 27,053 1,691
32 58,665 1,833
48 95,629 1,992
63 133,221 2,115

数据呈缓慢增长，看起来是 O(N^1.1) 而非 O(N²)。

建模分析

将总指令数拆分为 O(N²) 项（MakeTopological 级联）和 O(N) 项（构造函数、GetLinearization、函数调用等固定开销）：

\[\text{total}(N) = C \cdot \frac{N^2}{2} + D \cdot N\]

代入 N=9 和 N=63 的实测值联立求解：

\[C \approx 21 \text{ ins/merge-iter}, \quad D \approx 1443 \text{ ins/tx}\]

各 N 值的贡献比：

N O(N²) 贡献 O(N) 贡献 O(N²) 占比
9 862 12,987 6%
63 41,622 90,909 31%
200（估算） 420,000 288,600 59%

结论

MakeTopological 级联合并的 O(N²) 确实存在，但每次迭代仅约 21 条指令（纯 bitset 运算，BitSet<64> 全部为单条 64-bit 硬件指令）。而每个 tx 的 O(N) 基础开销（构造函数、GetReducedParents、GetLinearization 中的拓扑排序等）约 1443 条指令，远大于 O(N²) 的系数。

在 N≤63 的测试范围内，O(N) 基础开销占主导（6%~31%），导致整体看起来近似线性。O(N²) 开始明显主导的临界点约在 N ≈ 150，届时两项贡献相当。

TryLinearizeChain 优化的效果

算法描述与 benchmark 数据详见链式 Cluster 的 O(N) 快速路径优化。