Сравнение производительности массивов в .NET, часть 1

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/arrays-access-performance/.

---

Платформа .NET поддерживает два способа задания многомерных массивов: прямоугольные (rectangular) и изломанные (jagged). Второй способ по сути представляет собой массив массивов. Это обстоятельство создаёт у многих программистов иллюзию того, что jagged-массивы должны работать медленнее, т.к. обращение к их элементам реализуется через многократные переходы по ссылкам в управляемой куче. Но на самом деле jagged-массивы могут работают быстрее (если речь идёт непосредственно о работе с массивами, а не о их инициализации), ведь они представляют собой комбинацию одномерных (single) массивов, работа с которыми в CLR весьма оптимизирована (за счёт IL-команд newarr, ldelem, ldelema, ldlen, stelem). Другим подходом к представлению многомерных данных является использование одномерного массива с ручным преобразованием координат (в массиве размерности N*M для обращения к элементу [i,j] будем писать [i*M+j]). Если производительности не хватает, то можно использовать неуправляемый код, но этот случай мы сейчас рассматривать не будем, остановимся на трёх вышеозначенных способах. Для замеров времени используется BenchmarkDotNet. Рассмотрим C# код, который замеряет время работы каждого варианта (полный вариант кода: MultidimensionalArrayProgram.cs, тестировать следует в Release mode without debugging). Данные результаты получены в сборке под x64 для процессора Intel Core i7-3632QM CPU 2.20GHz и параметров N=M=100, IterationCount=100000. Исследование вопроса о влиянии используемой архитектуры и параметров запуска на результат бенчмарка можно найти во второй части статьи.

private const int N = 100, M = 100, IterationCount = 100000;
private int[] single;
private int[][] jagged;
private int[,] rectangular;

public void Run()
{
    var competition = new BenchmarkCompetition();

    competition.AddTask("Single",
        () => single = new int[N * M],
        () => SingleRun(single));

    competition.AddTask("Jagged",
        () =>
        {
            jagged = new int[N][];
            for (int i = 0; i < N; i++)
                jagged[i] = new int[M];
        },
        () => JaggedRun(jagged));

    competition.AddTask("Rectangular",
        () => rectangular = new int[N, M],
        () => RectangularRun(rectangular));

    competition.Run();
}

private int SingleRun(int[] a)
{
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                sum += a[i * M + j];
    return sum;
}

private int JaggedRun(int[][] a)
{
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                sum += a[i][j];
    return sum;
}

private int RectangularRun(int[,] a)
{
    int sum = 0;
    for (int iteration = 0; iteration < IterationCount; iteration++)
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                sum += a[i, j];
    return sum;
}

Этот пример на моём ноутбуке даёт следующие результаты (запускать следует в Release mode):

Single:      542ms
Jagged:      346ms
Rectangular: 755ms

Как можно видеть, доступ к элементам jagged-массива всегда осуществляется заметно быстрее, чем доступ к элементам rectangular-массива. Работа с single-массивом будет происходить быстрее, чем с rectangular, но чуть медленнее, чем с jagged. Мне думается, что single работает чуть медленнее jagged в большей степени из-за следующей причины:

• На расчёт индекса i*M+j требуется время, не дающее оптимизации в сравнении с лишним вызовом ldelem.ref.

Чтобы лучше разобраться рассмотрим IL-код каждого из методов в release режиме (для упрощения чтения из каждого метода был убран цикл итераций по iteration).

---

single.il

.method private hidebysig instance 
    int32 SingleAccessTest(int32[] a) cil managed
{
    .maxstack 4
    .locals init (
        [0] int32 sum,
        [1] int32 i,
        [2] int32 j)
    L_0000: ldc.i4.0     // Stack = [0]
    L_0001: stloc.0      // sum = 0, Stack = []
    L_0002: ldc.i4.0     // Stack = [0]
    L_0003: stloc.1      // i = 0, Stack = []
    L_0004: br.s L_0022  // GoTo L_0022
CY1 L_0006: ldc.i4.0     // Stack = [0]
    L_0007: stloc.2      // j = 0, Stack = []
    L_0008: br.s L_0019  // GoTo L_0019
CY2 L_000a: ldloc.0      // Stack = [sum]
    L_000b: ldarg.1      // Stack = [sum, a]
    L_000c: ldloc.1      // Stack = [sum, a, i]
    L_000d: ldc.i4.s 100 // Stack = [sum, a, i, 100]
    L_000f: mul          // Stack = [sum, a, i * 100]
    L_0010: ldloc.2      // Stack = [sum, a, i * 100, j]
    L_0011: add          // Stack = [sum, a, i * 100 + j]
    L_0012: ldelem.i4    // Stack = [sum, a[i * 100 + j]]
    L_0013: add          // Stack = [sum + a[i * 100 + j]]
    L_0014: stloc.0      // sum = sum + a[i * 100 + j], Stack = []
    L_0015: ldloc.2      // Stack = [j]
    L_0016: ldc.i4.1     // Stack = [j, 1]
    L_0017: add          // Stack = [j + 1]
    L_0018: stloc.2      // j = j + 1, Stack = []
CY2 L_0019: ldloc.2      // Stack = [j]
    L_001a: ldc.i4.s 100 // Stack = [j, 100]
    L_001c: blt.s L_000a // GoTo L_000a (if j < 100), Stack = []
    L_001e: ldloc.1      // Stack = [i]
    L_001f: ldc.i4.1     // Stack = [i, 1]
    L_0020: add          // Stack = [i + 1]
    L_0021: stloc.1      // i = i + 1, Stack = []
CY1 L_0022: ldloc.1      // Stack = [i]
    L_0023: ldc.i4.s 100 // Stack = [i, 100]
    L_0025: blt.s L_0006 // GoTo L_0006 (if i < 100), Stack = []
    L_0027: ldloc.0      // Stack = [sum]
    L_0028: ret          // return sum, Stack = []
}

---

jagged.il

.method private hidebysig instance 
    int32 JaggedAccessTest(int32[][] a) cil managed
{
    .maxstack 3
    .locals init (
        [0] int32 sum,
        [1] int32 i,
        [2] int32 j)
    L_0000: ldc.i4.0     // Stack = [0]
    L_0001: stloc.0      // sum = 0, Stack = []
    L_0002: ldc.i4.0     // Stack = [0]
    L_0003: stloc.1      // i = 0, Stack = []
    L_0004: br.s L_001f  // GoTo L_001f
CY1 L_0006: ldc.i4.0     // Stack = [0]
    L_0007: stloc.2      // j = 0, Stack = []
    L_0008: br.s L_0016  // Stack = []
CY2 L_000a: ldloc.0      // Stack = [sum]
    L_000b: ldarg.1      // Stack = [sum, a]
    L_000c: ldloc.1      // Stack = [sum, a, i]
    L_000d: ldelem.ref   // Stack = [sum, a[i]]
    L_000e: ldloc.2      // Stack = [sum, a[i], j]
    L_000f: ldelem.i4    // Stack = [sum, a[i][j]]
    L_0010: add          // Stack = [sum + a[i][j]]
    L_0011: stloc.0      // sum = sum + a[i][j], Stack = []
    L_0012: ldloc.2      // Stack = [j]
    L_0013: ldc.i4.1     // Stack = [j + 1]
    L_0014: add          // Stack = [j + 1]
    L_0015: stloc.2      // j = j + 1, Stack = []
CY2 L_0016: ldloc.2      // Stack = [j]
    L_0017: ldc.i4.s 100 // Stack = [j, 100]
    L_0019: blt.s L_000a // GoTo L_000a (if j < 100)
    L_001b: ldloc.1      // Stack = [i]
    L_001c: ldc.i4.1     // Stack = [i, 1]
    L_001d: add          // Stack = [i + 1]
    L_001e: stloc.1      // i = i + 1, Stack = []
CY1 L_001f: ldloc.1      // Stack = [i]
    L_0020: ldc.i4.s 100 // Stack = [i, 100]
    L_0022: blt.s L_0006 // GoTo L_0006 (if i < 100)
    L_0024: ldloc.0      // Stack = [sum]
    L_0025: ret          // return sum, Stack = []
}

---

rectangular.il

.method private hidebysig instance 
    int32 RectangularAccessTest(int32[0...,0...] a) cil managed
{
    .maxstack 4
    .locals init (
        [0] int32 sum,
        [1] int32 i,
        [2] int32 j)
    L_0000: ldc.i4.0     // Stack = [0]
    L_0001: stloc.0      // sum = 0, Stack = []
    L_0002: ldc.i4.0     // Stack = [0]
    L_0003: stloc.1      // i = 0, Stack = []
    L_0004: br.s L_0022  // GoTo L_0022
CY1 L_0006: ldc.i4.0     // Stack = [0]
    L_0007: stloc.2      // j = 0, Stack = []
    L_0008: br.s L_0019  // GoTo L_0019
CY2 L_000a: ldloc.0      // Stack = [sum]
    L_000b: ldarg.1      // Stack = [sum, a]
    L_000c: ldloc.1      // Stack = [sum, a, i]
    L_000d: ldloc.2      // Stack = [sum, a, i, j]
    L_000e: call instance int32 int32[0...,0...]::Get(int32, int32)
                         // Stack = [sum, a[i, j]]
    L_0013: add          // Stack = [sum + a[i, j]]
    L_0014: stloc.0      // sum = sum + a[i, j], Stack = []
    L_0015: ldloc.2      // Stack = [j]
    L_0016: ldc.i4.1     // Stack = [j, 1]
    L_0017: add          // Stack = [j + 1]
    L_0018: stloc.2      // j = j +1, Stack = []
CY2 L_0019: ldloc.2      // Stack = [j]
    L_001a: ldc.i4.s 100 // Stack = [j, 100]
    L_001c: blt.s L_000a // GoTo L_000a (if j < 100), Stack = []
    L_001e: ldloc.1      // Stack = [i]
    L_001f: ldc.i4.1     // Stack = [i, 1]
    L_0020: add          // Stack = [i + 1]
    L_0021: stloc.1      // i = i + 1, Stack = []
CY1 L_0022: ldloc.1      // Stack = [i]
    L_0023: ldc.i4.s 100 // Stack = [i, 100]
    L_0025: blt.s L_0006 // GoTo L_0006 (if i < 100), Stack = []
    L_0027: ldloc.0      // Stack = [sum]
    L_0028: ret          // return sum, Stack = []
}