代码之家 › 专栏 › 技术社区 › user626528

阵列写入对性能的影响远大于预期

performance .net c#

user626528 · 技术社区 · 7 年前

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

它给出了以下结果:

Data init, count: 100,000 x 10,000, 4.6133365 secs Perf test 0 (False): 5.8289565 secs Perf test 0 (True): 5.8485172 secs Perf test 1 (False): 32.3222312 secs Perf test 1 (True): 217.0089923 secs

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

增加了UPD额外测试;性能0按预期显示结果,性能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");
    }
}

1 回复 | 直到 7 年前

Alex Multifabrika 7 年前

在对代码进行了一段时间的测试之后,我的最佳猜测是,正如在评论中所说的,您在当前的解决方案中遇到了很多缓存未命中的情况。台词:

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

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

在经历了反汇编之后,您可以清楚地看到,您还引入了一系列新指令,这可能会进一步增加前面提到的问题。

总的来说,我建议你重新编写完整的算法,因为有更好的地方可以提高性能,而不是在这一个小任务中挑拣拣。这就是我建议的优化(这也提高了可读性):

颠倒你的方向 i 和 j 环这将删除 allEmpty 完全可变。
铸造 ch 到 int 具有 var ch = (int) val[j]; -因为你总是用它作为索引。
想想为什么这可能是个问题。你引入了一个新的指令,任何指令都是有代价的。如果这真的是你代码的主要“热点”,你可以开始考虑更好的解决方案(记住:“过早优化是万恶之源”)。
由于这是一个顾名思义的“测试环境”,这有什么重要意义吗?把它拿走。

编辑: 为什么我建议反转为循环?通过对代码的重新排列:

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

我来自这样的运行时:

要创建这样的运行时:

你还觉得不值得一试吗?我在这里保存了几个数量级,几乎消除了 if (需要澄清的是,设置中禁用了所有优化)。如果有特殊原因不这样做,您应该告诉我们更多关于此代码将在其中使用的上下文。

编辑2 :获取深入的答案。我对为什么会出现这个问题的最好解释是,您交叉引用了缓存线。在这些行中:

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

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

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

这是最贴切的解释,解释了为什么me代码运行得那么快,它还支持这样一种假设,即您的代码存在严重的缓存问题。