Tablice danych: wydajność

W C# istnieje wiele typów tablic. W poście chciałbym skupić się na ich wydajności. Rozważę następujące przypadki:

– tablica wielowymiarowa,

– tablica tablic tzw. jagged.

– tablica unsafe.

Tablice wielowymiarowe w c# są najwolniejsze ponieważ CLR nie wykonuje wszystkich optymalizacji. Zacznijmy jednak od testu:

internal class Program
{
    private static void DoSomething(int arg)
    {
    }
    private static void MultiDimensionalArrayTest(int xCount, int yCount)
    {
        int[,] array = new int[xCount, yCount];

        var stopWatch = Stopwatch.StartNew();

        for (int i = 0; i < xCount; i++)
            for (int j = 0; j < yCount; j++)
                DoSomething(array[i, j]);

        stopWatch.Stop();
        Console.WriteLine("MultiArray:{0}", stopWatch.ElapsedMilliseconds);
    }
    private static void JaggedArrayTest(int xCount, int yCount)
    {
        int[][] array = new int[xCount][];
        for (int i = 0; i < array.Length; i++)
            array[i] = new int[yCount];

        var stopWatch = Stopwatch.StartNew();

        for (int i = 0; i < xCount; i++)
            for (int j = 0; j < yCount; j++)
                DoSomething(array[i][j]);

        stopWatch.Stop();
        Console.WriteLine("JaggedArray:{0}", stopWatch.ElapsedMilliseconds);
    }
    private unsafe static void UnsafeArrayTest(int xCount, int yCount)
    {
        int[,] array = new int[xCount, yCount];

        fixed (int* pointer = array)
        {
            var stopWatch = Stopwatch.StartNew();

            for (int i = 0; i < yCount; i++)
            {
                int baseIndex = i * xCount;
                for (int j = 0; j < xCount; j++)
                    DoSomething(pointer[baseIndex + j]);
            }

            stopWatch.Stop();

            Console.WriteLine("Unsafe:{0}", stopWatch.ElapsedMilliseconds);
        }
    }
    private static void Main(string[] args)
    {
        const int xCount = 13000;
        const int yCount = 13000;

        UnsafeArrayTest(xCount, yCount);
        JaggedArrayTest(xCount, yCount);
        MultiDimensionalArrayTest(xCount, yCount);
    }
}

Otrzymany wynik w trybie release to:

Unsafe: 555,

Jagged: 363

MultiArray:787

Najwolniejsza jest oczywiście zwykła wielowymiarowa tablica. CLR przede wszystkim w każdej iteracji musi sprawdzać czy indeks nie wykracza poza rozmiar tzn. wykonuje następujący kod:

if(0 >= a.GetLowerBound(0)) && ((i) <= a.GetUpperBound(0))

W przypadku jednowymiarowych tablic kod zostanie w większości przypadków wykonany raz, przed pętlą:

(0 >= a.GetLowerBound(0)) && ((elementsCount – 1)
<= a.GetUpperBound(0)).

Ponadto tablice wielowymiarowe zachowują się podobnie do tych, które nie zaczynają się od indeksu zero (tak w C# można również takie tablice tworzyć). Z tego względu, w każdej iteracji CLR ma o jedną rzecz więcej do roboty a mianowicie obliczenie prawidłowego indeksu dostępowego.

Dostęp do tablic jagged jest najszybszy ponieważ jest to zwykła jednowymiarowa tablica. Niestety alokacja takich tablic jest zdecydowanie wolniejsza ponieważ tworzonych jest wiele obiektów, które muszą potem zostać zebrane przez GC. W przypadku tablicy wielowymiarowej tworzony jest wyłącznie jeden obiekt – dla jagged tworzone są one dla każdego wymiaru.

W przypadkach gdy tablica jest tworzona tylko raz a za to często należy uzyskiwać dostęp do elementów, jagged jest najlepszym rozwiązaniem. Dostęp przez wskaźnik jest za to kompromisem – szybsza inicjalizacja niż jagged ale trochę wolniejszy dostęp. Wydajnościowo takie podejście jest umiejscowione pomiędzy tymi dwoma rozwiązaniami. Niestety unsafe jest trudniejszy w implementacji, łatwo popełnić błąd i czytać elementy, które znajdują się poza tablicą – zamiast tablicy może okazać się, że czytamy pamięć przechowującą np. hasło.