为何堆分配cost数组的Levenshtein距离实现性能优于栈分配版本？

原实现（堆分配） #

// Fastenshtein/StaticLevenshtein.cs
public static int Distance(string value1, string value2)
{
    if (value2.Length == 0) { return value1.Length; }

    // *** 注意："costs" 是堆分配的 ***
    int[] costs = new int[value2.Length];
    
    for (int i = 0; i < costs.Length;) { costs[i] = ++i; }

    for (int i = 0; i < value1.Length; i++)
    {
        int cost = i;
        int previousCost = i;
        char value1Char = value1[i];

        for (int j = 0; j < value2.Length; j++)
        {
            int currentCost = cost;
            cost = costs[j];

            if (value1Char != value2[j])
            {
                if (previousCost < currentCost) { currentCost = previousCost; }
                if (cost < currentCost) { currentCost = cost; }
                ++currentCost;
            }

            costs[j] = currentCost;
            previousCost = currentCost;
        }
    }

    return costs[costs.Length - 1];
}

修改后的栈分配版本 #

// 栈分配的 "costs"
public static int Distance_StackAlloc(string value1, string value2)
{
    if (value2.Length == 0) { return value1.Length; }

    // *** 注意："costs" 现在是栈分配的 ***
    Span<int> costs = stackalloc int[value2.Length];

    // ... 剩余代码与原实现一致
}

性能测试结果 #

测试场景：从英文单词库随机选取1000个单词，计算每个单词与"foofaraw"的Levenshtein距离并求和，使用BenchmarkDotNet测试：

补充统计数据：

原因分析 #

从测试数据里能直接看到核心差异：栈分配版本的分支预测错误数比堆分配版高了50%左右，这就是性能反超的关键。

为什么栈分配会搞砸分支预测？

• 托管堆上的int[]是标准连续内存结构，JIT编译器对这种结构的访问模式非常熟悉，能生成让CPU分支预测器容易命中的机器码——循环里的数组读写模式稳定，预测器能大概率猜中分支走向。
• 而栈分配的Span<int>虽然也是连续内存，但JIT对栈内存的优化逻辑不同。栈内存布局更灵活，JIT没法像对待托管数组那样，给循环内的内存访问做针对性优化。CPU分支预测器面对栈内存的访问模式，更容易猜错，一旦猜错就得清空指令流水线、重新加载，这开销远大于缓存缺失带来的影响。

另外，虽然栈分配版的缓存缺失数大幅降低，但这点收益完全扛不住分支预测错误的损失。再加上.NET对小对象的堆分配优化极强，测试里的总分配内存才60多KB，根本不会触发GC，堆分配的开销几乎可以忽略。所以栈分配省下来的GC开销，完全抵不上分支预测错误多出来的时间。

内容的提问来源于stack exchange，提问作者chase.stone