c# - 数组写入的性能影响比预期的要大得多

Question

我在调试应用程序时偶然发现了这种效果 - 请参阅下面的重现代码。

它给了我以下结果:

数据初始化，计数:100,000 x 10,000，4.6133365 秒 性能测试 0(错误):5.8289565 秒 性能测试 0(真):5.8485172 秒 性能测试 1(错误):32.3222312 秒 性能测试 1(真):217.0089923 秒

据我所知，数组存储操作通常不会产生如此剧烈的性能影响(32 对 217 秒)。我想知道是否有人了解这里有什么影响？

添加了 UPD 额外测试； Perf 0 显示了预期的结果，Perf 1 - 显示了性能异常。

class Program
{
    static void Main(string[] args)
    {
        var data = InitData();

        TestPerf0(data, false);
        TestPerf0(data, true);

        TestPerf1(data, false);
        TestPerf1(data, true);

        if (Debugger.IsAttached)
            Console.ReadKey();
    }

    private static string[] InitData()
    {
        var watch = Stopwatch.StartNew();

        var data = new string[100_000];
        var maxString = 10_000;

        for (int i = 0; i < data.Length; i++)
        {
            data[i] = new string('-', maxString);
        }

        watch.Stop();
        Console.WriteLine($"Data init, count: {data.Length:n0} x {maxString:n0}, {watch.Elapsed.TotalSeconds} secs");

        return data;
    }

    private static void TestPerf1(string[] vals, bool testStore)
    {
        var watch = Stopwatch.StartNew();

        var counters = new int[char.MaxValue];
        int tmp = 0;

        for (var j = 0; ; j++)
        {
            var allEmpty = true;

            for (var i = 0; i < vals.Length; i++)
            {
                var val = vals[i];

                if (j < val.Length)
                {
                    allEmpty = false;

                    var ch = val[j];
                    var count = counters[ch];
                    tmp ^= count;

                    if (testStore)
                        counters[ch] = count + 1;
                }
            }

            if (allEmpty)
                break;
        }

        // prevent the compiler from optimizing away our computations
        tmp.GetHashCode();

        watch.Stop();
        Console.WriteLine($"Perf test 1 ({testStore}): {watch.Elapsed.TotalSeconds} secs");
    }

    private static void TestPerf0(string[] vals, bool testStore)
    {
        var watch = Stopwatch.StartNew();

        var counters = new int[65536];
        int tmp = 0;

        for (var i = 0; i < 1_000_000_000; i++)
        {
            var j = i % counters.Length;
            var count = counters[j];
            tmp ^= count;

            if (testStore)
                counters[j] = count + 1;
        }

        // prevent the compiler from optimizing away our computations
        tmp.GetHashCode();

        watch.Stop();
        Console.WriteLine($"Perf test 0 ({testStore}): {watch.Elapsed.TotalSeconds} secs");
    }
}

Answer 1

在测试您的代码一段时间后，我的最佳猜测是，如评论中所述，您当前的解决方案遇到了很多缓存未命中的情况。线路:

if (testStore)
    counters[ch] = count + 1;

可能会强制编译器将新的缓存行完全加载到内存中并替换当前内容。在这种情况下，分支预测也可能存在一些问题。这高度依赖于硬件，我不知道用任何解释语言测试它的真正好的解决方案(在硬件设置和众所周知的编译语言中也很难)。

在反汇编之后，你可以清楚地看到你还引入了一大堆新的指令，这可能会进一步增加前面提到的问题。

总的来说，我建议您重新编写完整的算法，因为有更好的地方可以提高性能，而不是选择这个小任务。这将是我建议的优化(这也提高了可读性):

1. 反转你的i 和j 循环。这将完全删除 allEmpty 变量。
2. 使用 var ch = (int) val[j]; 将 ch 转换为 int - 因为您总是将它用作索引。
3. 想想为什么这可能是个问题。您引入了一条新指令，而任何指令都是有代价的。如果这确实是您代码的主要“热点”，您可以开始考虑更好的解决方案(记住:“过早优化是万恶之源”)。
4. 顾名思义，这是一个“测试设置”，这重要吗？只需将其删除即可。

---

编辑:为什么我建议反转为循环？通过这个小小的代码重新排列:

foreach (var val in vals)
{
    foreach (int ch in val)
    {
        var count = counters[ch];
        tmp ^= count;
        if (testStore)
        {
            counters[ch] = count + 1;
        }
    }
}

我来自这样的运行时:

像这样的运行时:

你还觉得不值得一试吗？我在这里节省了一些数量级，几乎消除了 if 的影响(要清楚 - 所有优化都在设置中禁用)。如果有特殊原因不这样做，您应该告诉我们更多有关使用此代码的上下文。

---

EDIT2:对于深入的回答。我对为什么会出现此问题的最好解释是因为您交叉引用了缓存行。在行中:

for (var i = 0; i < vals.Length; i++)
{
    var val = vals[i];

您加载了一个非常庞大的数据集。这远远大于缓存行本身。因此，很可能需要在每次迭代时将其从内存中加载到新的缓存行中(替换旧内容)。如果我没记错的话，这也称为“缓存抖动”。感谢@mjwills 在他的评论中指出这一点。

另一方面，在我建议的解决方案中，只要内部循环不超出其边界，缓存行的内容就可以保持事件状态(如果使用这种内存访问方向，这种情况会少很多)。

这是为什么我的代码运行得那么快的最接近的解释，它也支持您的代码存在严重缓存问题的假设。