Блог Юдакова Дмитрия: Стоит ли отдельно сохранять длину массива в .NET

Свежая версия этой статьи находится здесь: https://habr.com/ru/post/434060/
Очень часто замечаю, что люди пишут вот так:

var length = array.Length;
for (int i = 0; i < length; i++) {
    //do smth
}

Пишут они это в надежде ускорить цикл, думая что создавая локальную переменную избавляют CLR от необходимости вызывать каждый раз геттер для Array.Length. В моём главном рабочем проекте подобный код встречается более 150 раз. Я решил раз и навсегда для себя понять стоит так делать или можно сэкономить своё время и написать без временной переменной.
Для начала рассмотрим два метода на C#:

public int WithoutVariable() {
    int sum = 0;
    for (int i = 0; i < array.Length; i++) {
        sum += array[i];
    }
    return sum;
}

public int WithVariable() {
    int sum = 0;
    int length = array.Length;
    for (int i = 0; i < length; i++) {
        sum += array[i];
    }
    return sum;
}

И давайте посмотрим на код, который получается после JIT компиляции в релизе на .NET Framework 4.7.2:

WithoutVariable()
int sum = 0;
    xor  edi,edi
int i = 0;
    xor  esi,esi
int[] localRefToArray = this.array;
    mov  edx,dword ptr [ecx+4]
int arrayLength = localRefToArray.Length;
    mov  ecx,dword ptr [edx+4]
if (arrayLength == 0) return sum;
    test ecx,ecx
    jle  056e2d2b
int anotherArrayLength = localRefToArray.Length;
    mov  eax,dword ptr [edx+4] 
if (i >= anotherArrayLength)
  throw new OutOfRangeException();
  loop:
    cmp  esi,eax
    jae  056e2d31
sum += localRefToArray[i];
    add  edi,dword ptr [edx+esi*4+8]
i++;
    inc  esi
if (i < arrayLength) goto loop
    cmp  ecx,esi
    jg   056e2d1e
return sum;
    mov  eax,edi

WithVariable()
int sum = 0;
    xor  esi,esi
int[] localRefToArray = this.array;
    mov  edx,dword ptr [ecx+4]
int arrayLength = localRefToArray.Length;
    mov  edi,dword ptr [edx+4]
int i = 0;
    xor  eax,eax
if (arrayLength == 0) return sum;
    test edi,edi
    jle  05902d2b
int anotherArrayLength = localRefToArray.Length;
    mov  ecx,dword ptr [edx+4]
if (i >= anotherArrayLength)
  throw new OutOfRangeException();
  loop:
    cmp  eax,ecx
    jae  05902d31
sum += localRefToArray[i];
    add  esi,dword ptr [edx+eax*4+8]
i++;
    inc  eax
if (i < arrayLength) goto loop
    cmp  eax,edi
    jl   05902d1e
return sum;
    mov  eax,esi

Несложно заметить, что количество ассемблерных инструкций абсолютно одинаково - 15 штук. Причём логика этих инструкций тоже абсолютно совпадает. Есть только небольшое различие в порядке инициализации переменных. Можно заметить, что в обоих случаях длина массива заносится в регистры два раза перед циклом: чтобы проверить на 0 и во временную переменную для проверки в условии цикла.

Получается, что оба вышеприведённых метода компилируются в один и тот же код, но первый пишется быстрее и явный выигрыш в скорости выполнения отсутствует.

Приведённый выше ассемблерный код навёл меня на некоторые мысли и я решил проверить ещё несколько методов:

public int WithoutVariable() {
    int sum = 0;
    for(int i = 0; i < array.Length; i++) {
        sum += array[i] + array.Length;
    }
    return sum;
}

public int WithVariable() {
    int sum = 0;
    int length = array.Length;
    for(int i = 0; i < length; i++) {
        sum += array[i] + length;
    }
    return sum;
}

Теперь суммируется текущий элемент и длина массива, только в первом случае длина массива каждый раз запрашивается, а во втором сохраняется один раз в локальную переменную. Посмотрим на ассемблерный код этих методов:

WithoutVariable()
int sum = 0;
    xor  edi,edi
int i = 0; 
    xor  esi,esi
int[] localRefToArray = this.array; 
    mov  edx,dword ptr [ecx+4]
int arrayLength = localRefToArray.Length; 
    mov  ebx,dword ptr [edx+4]
if (arrayLength == 0) return sum;
    test ebx,ebx
    jle  05562d32
int anotherArrayLength = localRefToArray.Length;
    mov  ecx,dword ptr [edx+4]
if (i >= anotherArrayLength)
  throw new OutOfRangeException(); 
  loop:
    cmp  esi,ecx 
    jae  05562d39
int t = array[i]; 
    mov  eax,dword ptr [edx+esi*4+8]
t += sum;
    add  eax,edi
t+= arrayLength;
    add  eax,ebx
sum = t; 
    mov  edi,eax
i++;
    inc  esi
if (i < arrayLength) goto loop
    cmp  ebx,esi
    jg   05562d1f
return sum;
    mov  eax,edi

WithVariable()
int sum = 0;
    xor  esi,esi
int[] localRefToArray = this.array;  
    mov  edx,dword ptr [ecx+4]
int arrayLength = localRefToArray.Length;  
    mov  ebx,dword ptr [edx+4]
int i = 0;  
    xor  ecx,ecx
if (arrayLength == 0) goto 04b12d32 (return sum;) 
    test  ebx,ebx
    jle   04b12d32
int anotherArrayLength = localRefToArray.Length;
    mov   edi,dword ptr [edx+4]
if (i >= anotherArrayLength)
 throw new OutOfRangeException();
 loop:
    cmp  ecx,edi
    jae  04b12d39
int t = array[i]; 
    mov  eax,dword ptr [edx+ecx*4+8]
t += sum; 
    add  eax,esi
t+= arrayLength; 
    add  eax,ebx
sum = t; 
    mov  esi,eax
i++; 
    inc  ecx
if (i < arrayLength) goto loop 
    cmp  ecx,ebx
    jl   04b12d1f
return sum;
    mov  eax,esi

Количество инструкций у этих двух методов и сами инструкции абсолютно одинаковые, опять различие есть только в порядке инициализации переменных. Причём можно заметить, что в расчёте sum учитывается только тот array.Length, который был взят самым первым. Очевидно что вот это:

int anotherArrayLength = localRefToArray.Length;
    mov     edi,dword ptr [edx+4]
if (i >=anotherArrayLength) throw new OutOfRangeException();
    cmp     ecx,edi
    jae     04b12d39

во всех четырёх методах - просто заинлайниная проверка на выход на пределы массива перед первой итерацией цикла. Больше таких проверок нет, т.к. JIT видит, что в теле цикла нет изменений длины массива, и цикл заканчивается на последнем элементе, значит нет смысла каждый элемент массива проверять на выход за пределы.

Можно сделать уже первый вывод о том, что заводить дополнительную переменную чтобы пытаться ускорить выполнение цикла - пустая трата времени, т.к. компилятор всё сделает за нас. Заводить переменную с длиной цикла имеет смысл только чтобы увеличить читабельность кода.

Совершенно другая ситуация с ForEach. Возьмём три метода:

public int ForEachWithoutLength() {
    int sum = 0;
    foreach (int i in array) {
        sum += i;
    }
    return sum;
}

public int ForEachWithLengthWithoutLocalVariable() {
    int sum = 0;
    foreach (int i in array) {
        sum += i + array.Length;
    }
    return sum;
}

public int ForEachWithLengthWithLocalVariable() {
    int sum = 0;
    int length = array.Length;
    foreach (int i in array) {
        sum += i + length;
    }
    return sum;
}

И посмотрим на их код после JIT :

ForEachWithoutLength()
int sum = 0;
 04c22d2d 33f6            xor     esi,esi
int[] localRefToArray = this.array; 
 04c22d2f 8b4904          mov     ecx,dword ptr [ecx+4]
int i = 0;
 04c22d32 33d2            xor     edx,edx
int arrayLength = localRefToArray.Length; 
 04c22d34 8b7904          mov     edi,dword ptr [ecx+4]
if (arrayLength == 0) goto 04c22d46 (return sum;)
 04c22d37 85ff            test    edi,edi
 04c22d39 7e0b            jle     04c22d46
int t = array[i]; 
 04c22d3b 8b449108        mov     eax,dword ptr [ecx+edx*4+8]
sum+=i;
 04c22d3f 03f0            add     esi,eax
i++;
 04c22d41 42              inc     edx
if (i < arrayLength) goto 04c22d3b
 04c22d42 3bfa            cmp     edi,edx
 04c22d44 7ff5            jg      04c22d3b
return sum;
 04c22d46 8bc6            mov     eax,esi
 
 
ForEachWithLengthWithoutLocalVariable()
int sum = 0;
 05a32d2d 33f6            xor     esi,esi
int[] localRefToArray = this.array;  
 05a32d2f 8b4904          mov     ecx,dword ptr [ecx+4]
int i = 0; 
 05a32d32 33d2            xor     edx,edx
int arrayLength = localRefToArray.Length;  
 05a32d34 8b7904          mov     edi,dword ptr [ecx+4]
if (arrayLength == 0) goto 04c22d46 (return sum;) 
 05a32d37 85ff            test    edi,edi
 05a32d39 7e0e            jle     05a32d49
int t = array[i];  
 05a32d3b 8b449108        mov     eax,dword ptr [ecx+edx*4+8]
sum+=i; 
 05a32d3f 03f0            add     esi,eax
sum+=localRefToArray.Length;
 05a32d41 037104          add     esi,dword ptr [ecx+4]
i++;
 05a32d44 42              inc     edx
if (i < arrayLength) goto 05a32d3b 
 05a32d45 3bfa            cmp     edi,edx
 05a32d47 7ff2            jg      05a32d3b
return sum;
 05a32d49 8bc6            mov     eax,esi
 
 
ForEachWithLengthWithLocalVariable()
int sum = 0;
 04cb2d2e 33f6            xor     esi,esi
int[] localRefToArray = this.array;   
 04cb2d30 8b5104          mov     edx,dword ptr [ecx+4]
int length = localRefToArray.Length;   
 04cb2d33 8b5a04          mov     ebx,dword ptr [edx+4]
int i = 0;  
 04cb2d36 33c9            xor     ecx,ecx
int arrayLength = localRefToArray.Length;   
 04cb2d38 8b7a04          mov     edi,dword ptr [edx+4]
if (arrayLength == 0) goto 04c22d46 (return sum;) 
 04cb2d3b 85ff            test    edi,edi
 04cb2d3d 7e0d            jle     04cb2d4c
int t = array[i];   
 04cb2d3f 8b448a08        mov     eax,dword ptr [edx+ecx*4+8]
sum+=i;  
 04cb2d43 03f0            add     esi,eax
sum+=length ; 
 04cb2d45 03f3            add     esi,ebx
i++; 
 04cb2d47 41              inc     ecx
if (i < arrayLength) goto 04cb2d3f  
 04cb2d48 3bf9            cmp     edi,ecx
 04cb2d4a 7ff3            jg      04cb2d3f
return sum;
 04cb2d4c 8bc6            mov     eax,esi

Первое что бросается в глаза это то, что получилось меньше ассемблерных инструкций, по сравнению с циклом for (foreach - 12, for - 15).

В самом деле, если написать бенчмарк for vs foreach на 1 000 000 элементов, то получится такая картина:

для sum+=array[i];

Method	ItemsCount	Mean	Error	StdDev	Median	Ratio	RatioSD
ForEach	1000000	1.401 ms	0.2691 ms	0.7935 ms	1.694 ms	1.00	0.00
For	1000000	1.586 ms	0.3204 ms	0.9447 ms	1.740 ms	1.23	0.65

и для sum+=array[i] + array.Length;

Method	ItemsCount	Mean	Error	StdDev	Median	Ratio	RatioSD
ForEach	1000000	1.703 ms	0.3010 ms	0.8874 ms	1.726 ms	1.00	0.00
For	1000000	1.715 ms	0.2859 ms	0.8430 ms	1.956 ms	1.13	0.56

ForEach для массивов отрабатывает быстрее чем For. Почему так происходит? Чтобы это понять нужно сравнивать код после JIT.

Посмотрим на ForEachWithoutLength. В нём длина массива запрашивается только один раз и не происходит никаких проверок на выход первого элемента за пределы массива. Так происходит потому что цикл ForEach во-первых запрещает изменение коллекции внутри цикла, а во-вторых точно не будет выходить за пределы коллекции. Из-за этого JIT может себе позволить вообще убрать проверки на выход за пределы массива.

Теперь посмотрим внимательно на метод ForEachWithLengthWithoutLocalVariable. В его коде есть только один странный момент в том, что sum+=length происходит не с сохранённой ранее локальной переменной arrayLength, а с новой, которую программа спрашивает каждый раз из памяти. Получается, что обращений к памяти за длиной массива будет N + 1, где N - длина массива.

Осталось рассмотреть метод ForEachWithLengthWithLocalVariable. Его код ничем не отличается от ForEachWithLengthWithoutLocalVariable, кроме работы с длинной массива. Компилятор опять сгенерировал локальную переменную arrayLength, с помощью которой проверяет что массив не пустой, но при этом компилятор честно сохранил нашу явную локальную переменную length и сложение в теле цикла происходит уже с ней. Получается, что этот метод всего дважды обращается к памяти для определения длины массива. Эту разницу очень сложно заметить в реальной жизни и ею можно смело пренебречь.

Ассемблерный код рассмотренных методов получился такой простой потому что сами методы простые. Будь в методе больше параметров, там была бы уже работа со стеком, переменные хранились бы не только в регистрах и возможно было бы больше проверок, но основная логика осталась бы такая же: введение локальной переменной с длиной массива может иметь смысл только для повышения читабельности кода. Кроме того, оказалось, что Foreach по массиву часто выполняется быстрее чем For.

Посмотреть на ассемблерный код для тех же самых методов, но для List<T> можно здесь:
https://yadi.sk/d/csSSLKC4CqAF2g

Блог Юдакова Дмитрия

четверг, 13 декабря 2018 г.

Стоит ли отдельно сохранять длину массива в .NET

Комментариев нет:

Отправить комментарий

Небольшой обзор SIMD в .NET

Сообщить о нарушении

Ярлыки

четверг, 13 декабря 2018 г.

Стоит ли отдельно сохранять длину массива в .NET

Комментариев нет:

Отправить комментарий

Небольшой обзор SIMD в .NET

четверг, 13 декабря 2018 г.