.NET遍歷二維陣列-先行/先列哪個更快？

上週在.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 = 0; i < Size; i++)
            {
                for (int j = 0; j < Size; j++)
                {
                    _array[i, j] = rnd.Next();
                }
            }
        }

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

        [Benchmark]
        public int ColumnFirst()
        {
            // 先遍歷一整列
            int sum = 0;
            for (int j = 0; j < Size; j++)
            {
                for (int i = 0; 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兩者差別幾乎可以忽略不計，當然這不在本文的討論範圍中。

.NET效能優化交流群

相信大家在開發中經常會遇到一些效能問題，苦於沒有有效的工具去發現效能瓶頸，或者是發現瓶頸以後不知道該如何優化。之前一直有讀者朋友詢問有沒有技術交流群，但是由於各種原因一直都沒建立，現在很高興的在這裡宣佈，我建立了一個專門交流.NET效能優化經驗的群組，主題包括但不限於：

如何找到.NET效能瓶頸，如使用APM、dotnet tools等工具
.NET框架底層原理的實現，如垃圾回收器、JIT等等
如何編寫高效能的.NET程式碼，哪些地方存在效能陷阱

希望能有更多志同道合朋友加入，分享一些工作中遇到的.NET效能問題和寶貴的效能分析優化經驗。目前一群已滿，現在開放二群。
如果提示已經達到200人，可以加我微信，我拉你進群: ls1075
另外也建立了QQ群，群號: 687779078，歡迎大家加入。