.NET遍历二维数组-先行/先列哪个更快？

2023-02-13 16:14:57

上周在.NET性能优化群里面有一个很有意思的讨论，讨论的问题如下所示：

请教大佬：2D数组，用C#先遍历行再遍历列，或者先遍历列再遍历行，两种方式在性能上有区别吗？
据我所知，Julia或者python的 pandas，一般建议先遍历列，再遍历行

在群里面引发了很多大佬的讨论，总的来说观点分为以下三种：

应该不会有什么差别
先遍历列会比先遍历行更快
先遍历行会比先遍历列更快

看了群里面激烈的讨论，刚好今天有时间，我们就来看看真实情况是怎么样的？实践出真知，我们编写一个Benchmark一测便知。

测试

在下面的代码中，我们创建了一个 ArrayBenchmark 类，它包含了两个方法：RowFirst 和 ColumnFirst。这两个方法分别代表了先行后列和先列后行两种遍历方式。每次测试时，数组的大小将使用参数（Size）设置。在 Main 方法中，我们调用 BenchmarkRunner.Run 方法来运行测试。

using System;
using System.Diagnostics;
using BenchmarkDotNet.Attributes;

namespace TwoDimensionalArrayBenchmark
{
    public class ArrayBenchmark
    {
        private int[,] _array;

        [Params(1000, 2000, 4000, 8000, 16000)]
        public int Size { get; set; }

        [GlobalSetup]
        public void Setup()
        {
            _array = new int[Size, Size];
            var rnd = new Random();
            for (int i = ; i < Size; i++)
            {
                for (int j = ; j < Size; j++)
                {
                    _array[i, j] = rnd.Next();
                }
            }
        }

        [Benchmark]
        public int RowFirst()
        {
            // 先遍历一整行
            int sum = ;
            for (int i = ; i < Size; i++)
            {
                for (int j = ; j < Size; j++)
                {
                    sum += _array[i, j];
                }
            }
            return sum;
        }

        [Benchmark]
        public int ColumnFirst()
        {
            // 先遍历一整列
            int sum = ;
            for (int j = ; j < Size; j++)
            {
                for (int i = ; i < Size; i++)
                {
                    sum += _array[i, j];
                }
            }
            return sum;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var summary = BenchmarkDotNet.Running.BenchmarkRunner.Run<ArrayBenchmark>();
            Console.ReadKey();
        }
    }
}

得出的结果如下所示，从结果中我们可以看到，在.NET7.0中先遍历行远远快于先遍历列，随着数据量的增大有着近10倍的差距：

关于为什么先行后列的性能比先列后行高，猜测主要有以下两个原因：

CPU 缓存层次结构：当遍历二维数组时，先行后列方式更适合利用 CPU 的缓存层次结构。每次访问二维数组中的一行数据时，这一整行的数据都可以从 L1/L2/L3 缓存中读取，这样就可以大大提高数据读取的效率。
内存布局：二维数组的内存布局可能是按行存储的，也就是说一整行的数据在内存中是连续的。因此，先行后列的方式更容易利用内存的连续性，使数据读取更加顺畅。

我们可以通过简单的代码来验证一下.NET中二维数组的存储格式，使用Unsafe.AsPointer可以获取引用对象的指针，然后将其强转为long类型即可获得它的地址。

下面使用的是先行后列的遍历方式：

由于一个int类型占用4字节的空间，所以我们可以发现在使用先行后列的方式时刚好就是顺序顺序递增的。

也就是说C#在逻辑上虽然是二维数组，实际上存储是按每一行连续存储的，如下图所示：

CPU的缓存也是按照这个顺序进行缓存的，所以当我们先行后列遍历的时候整行数据都可能在CPU缓存中，可以大化的利用好CPU缓存。

如果按照先列后行的遍历，那么对缓存就很不友好，需要多次从内存中读取数据。

总结

这就是本文的全部了，目前看来在C# .NET中遍历二维数组是先行快于先列，不过这也不是的事情，因为在编译器和即时编译器中，是可以自动的去做一些优化，让程序更快的访问数据。比如在群里大佬们比较了在VC中的差异，结果是发现DEBUG模式确实行快于列，但是Release两者差别几乎可以忽略不计，当然这不在本文的讨论范围中。