Проверка границ массива в.net 4 и выше
Меня интересует, насколько эффективными могут быть низкоуровневые алгоритмы в.net. Я хотел бы дать нам возможность в будущем писать больше нашего кода на C#, а не на C++, но одним камнем преткновения является проверка границ в.net, которая возникает при циклическом и произвольном доступе к массивам.
Мотивирующим примером является функция, которая вычисляет сумму произведений соответствующих элементов в двух массивах (это скалярное произведение двух векторов).
static void SumProduct(double[] X, double[] Y)
{
double sum = 0;
int length = X.Length;
if (length != Y.Length)
throw new ArgumentException("X and Y must be same size");
for (int i = 0; i < length; i++) // Check X.Length instead? See below
sum += X[i] * Y[i];
}
Из того, что я могу сказать, и не знаю достаточно IL или x86 для проверки, компилятор не будет оптимизировать проверку границ X а также Y, Я ошибаюсь и / или есть ли способ написать свой код, чтобы компилятор помог мне?
Более подробная информация
Существует множество аргументов за и против использования определенных языков, и не в последнюю очередь, что лучше сконцентрироваться на алгоритмических затратах "большой О", а не на константе пропорциональности, и языки более высокого уровня помогут вам сделать это. Что касается проверки границ в.net, то лучшая статья, которую я нашел, это " Устранение проверки массивов в CLR на MSDN" (также упоминается в ответе о переполнении стека о важности включения оптимизации).
Это относится к 2009 году, поэтому мне интересно, изменились ли вещи с тех пор. Кроме того, статья раскрывает некоторые реальные тонкости, которые могли бы поразить меня, поэтому по одной только этой причине я хотел бы получить совет специалиста.
Например, кажется, что в моем коде выше мне лучше написать i< X.Length скорее, чем i < length, Кроме того, я также наивно предполагал, что для алгоритма с одним массивом foreach Цикл лучше объявит ваше намерение компилятору и даст ему лучший шанс оптимизировать проверку границ.
Согласно статье MSDN, SumForBAD, ниже, который, как я думал, был обязательно оптимизирован, не будет. В то время как SumFor было бы просто оптимизировано, и SumForEach также будет оптимизирован, но не тривиально (и не может быть оптимизирован вообще, если массив был передан в функцию как IEnumerable<int>)?
static double SumForBAD(double[] X)
{
double sum = 0;
int length = X.Length; // better to use i < X.length in loop
for (int i = 0; i < length; i++)
sum += X[i];
return sum;
}
static double SumFor(double[] X)
{
double sum = 0;
for (int i = 0; i < X.Length; i++)
sum += X[i];
return sum;
}
static double SumForEach(double[] X)
{
double sum = 0;
foreach (int element in X)
sum += element;
return sum;
}
Я провел некоторое расследование, основываясь на ответе doug65536. В C++ я сравнил времена SumProduct, который делает одну проверку границ
for(int i=0; i<n; ++i) sum += v1[i]*v2[i];
против другой версии, которая делает две проверки границ
for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i];
Я обнаружил, что вторая версия была медленнее, но только примерно на 3,5% (Visual Studio 2010, оптимизированная сборка, параметры по умолчанию). Однако мне пришло в голову, что в C# может быть три проверки границ. Одно явное (i < length в функции static void SumProduct(double[] X, double[] Y) в начале этого вопроса) и два неявных (X[i] а также Y[i]). Итак, я протестировал третью функцию C++ с тремя проверками границ
for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];
Это произошло на 35% медленнее, чем первое, о котором стоит позаботиться. Я провел еще несколько исследований в этом вопросе: почему добавление дополнительной проверки в цикле имеет большое значение на некоторых машинах и небольшое различие на других?, Интересно, что кажется, что стоимость проверки границ значительно различается на разных машинах.
4 ответа
Проверка границ не имеет значения, потому что:
Проверка границ состоит из
cmp/jaeпара команд, которая объединена в одну микрооперацию на современных архитектурах ЦП (термин "макрооперация слияния"). Сравнение и ветка очень высоко оптимизированы.Проверка границ - это прямая ветвь, которая, согласно статическим прогнозам, не будет принята, что также уменьшит стоимость. Ветка никогда не будет взята. (Если оно когда-либо предпринято, исключение все равно будет выброшено, поэтому стоимость неверного прогноза становится совершенно неактуальной)
Как только возникает какая-либо задержка памяти, умозрительное выполнение поставит в очередь многие итерации цикла, поэтому затраты на декодирование дополнительной пары команд почти исчезают.
Доступ к памяти, вероятно, станет вашим узким местом, поэтому эффект микрооптимизации, такой как удаление проверок границ, исчезнет.
64-битный
64-битный джиттер хорошо справляется с устранением проверок границ (по крайней мере, в простых сценариях). я добавил return sum; в конце вашего метода, а затем скомпилировали программу, используя Visual Studio 2010 в режиме выпуска. В разборке ниже (которую я аннотировал переводом C#) обратите внимание, что:
- Там нет границ проверки для
Xдаже если ваш код сравниваетсяiпротивlengthвместоX.Length, Это улучшение по сравнению с поведением, описанным в статье. - Перед основным циклом есть одна проверка, чтобы убедиться, что
Y.Length >= X.Length, - Основной цикл (смещение от 00000032 до 00000052) не содержит проверок границ.
разборка
; Register assignments:
; rcx := i
; rdx := X
; r8 := Y
; r9 := X.Length ("length" in your code, "XLength" below)
; r10 := Y.Length ("YLength" below)
; r11 := X.Length - 1 ("XLengthMinus1" below)
; xmm1 := sum
; (Prologue)
00000000 push rbx
00000001 push rdi
00000002 sub rsp,28h
; (Store arguments X and Y in rdx and r8)
00000006 mov r8,rdx ; Y
00000009 mov rdx,rcx ; X
; int XLength = X.Length;
0000000c mov r9,qword ptr [rdx+8]
; int XLengthMinus1 = XLength - 1;
00000010 movsxd rax,r9d
00000013 lea r11,[rax-1]
; int YLength = Y.Length;
00000017 mov r10,qword ptr [r8+8]
; if (XLength != YLength)
; throw new ArgumentException("X and Y must be same size");
0000001b cmp r9d,r10d
0000001e jne 0000000000000060
; double sum = 0;
00000020 xorpd xmm1,xmm1
; if (XLength > 0)
; {
00000024 test r9d,r9d
00000027 jle 0000000000000054
; int i = 0;
00000029 xor ecx,ecx
0000002b xor eax,eax
; if (XLengthMinus1 >= YLength)
; throw new IndexOutOfRangeException();
0000002d cmp r11,r10
00000030 jae 0000000000000096
; do
; {
; sum += X[i] * Y[i];
00000032 movsd xmm0,mmword ptr [rdx+rax+10h]
00000038 mulsd xmm0,mmword ptr [r8+rax+10h]
0000003f addsd xmm0,xmm1
00000043 movapd xmm1,xmm0
; i++;
00000047 inc ecx
00000049 add rax,8
; }
; while (i < XLength);
0000004f cmp ecx,r9d
00000052 jl 0000000000000032
; }
; return sum;
00000054 movapd xmm0,xmm1
; (Epilogue)
00000058 add rsp,28h
0000005c pop rdi
0000005d pop rbx
0000005e ret
00000060 ...
00000096 ...
32-битный
К сожалению, 32-битный джиттер не такой умный. При разборке ниже обратите внимание, что:
- Там нет границ проверки для
Xдаже если ваш код сравниваетсяiпротивlengthвместоX.Length, Опять же, это улучшение по сравнению с поведением, описанным в статье. - Основной цикл (смещение от 00000018 до 0000002a) содержит проверку границ для
Y,
разборка
; Register assignments:
; eax := i
; ecx := X
; edx := Y
; esi := X.Length ("length" in your code, "XLength" below)
; (Prologue)
00000000 push ebp
00000001 mov ebp,esp
00000003 push esi
; double sum = 0;
00000004 fldz
; int XLength = X.Length;
00000006 mov esi,dword ptr [ecx+4]
; if (XLength != Y.Length)
; throw new ArgumentException("X and Y must be same size");
00000009 cmp dword ptr [edx+4],esi
0000000c je 00000012
0000000e fstp st(0)
00000010 jmp 0000002F
; int i = 0;
00000012 xor eax,eax
; if (XLength > 0)
; {
00000014 test esi,esi
00000016 jle 0000002C
; do
; {
; double temp = X[i];
00000018 fld qword ptr [ecx+eax*8+8]
; if (i >= Y.Length)
; throw new IndexOutOfRangeException();
0000001c cmp eax,dword ptr [edx+4]
0000001f jae 0000005A
; sum += temp * Y[i];
00000021 fmul qword ptr [edx+eax*8+8]
00000025 faddp st(1),st
; i++;
00000027 inc eax
; while (i < XLength);
00000028 cmp eax,esi
0000002a jl 00000018
; }
; return sum;
0000002c pop esi
0000002d pop ebp
0000002e ret
0000002f ...
0000005a ...
Подводя итоги
Джиттер улучшился с 2009 года, и 64-битный джиттер может генерировать более эффективный код, чем 32-битный джиттер.
Однако при необходимости вы всегда можете полностью обойти проверку границ массива, используя небезопасный код и указатели (как указывает svick). Этот метод используется некоторым критичным к производительности кодом в библиотеке базовых классов.
Один из способов убедиться, что проверка границ не выполняется, - это использовать указатели, что можно сделать в C# в небезопасном режиме (для этого необходимо установить флаг в свойствах проекта):
private static unsafe double SumProductPointer(double[] X, double[] Y)
{
double sum = 0;
int length = X.Length;
if (length != Y.Length)
throw new ArgumentException("X and Y must be same size");
fixed (double* xp = X, yp = Y)
{
for (int i = 0; i < length; i++)
sum += xp[i] * yp[i];
}
return sum;
}
Я попытался измерить ваш оригинальный метод, ваш метод с X.Length изменить и мой код с помощью указателей, скомпилированных как x86 и x64 в.Net 4.5. В частности, я попытался вычислить метод для векторов длиной 10 000 и запустил метод 10 000 раз.
Результаты в значительной степени соответствуют ответу Майкла Лю: между этими тремя методами нет ощутимой разницы, что означает, что проверка границ либо не выполнена, либо ее влияние на производительность незначительно. Между x86 и x64 была ощутимая разница: x64 был примерно на 34 % медленнее.
Полный код, который я использовал:
static void Main()
{
var random = new Random(42);
double[] x = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray();
double[] y = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray();
// make sure JIT doesn't affect the results
SumProduct(x, y);
SumProductLength(x, y);
SumProductPointer(x, y);
var stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < 10000; i++)
{
SumProduct(x, y);
}
Console.WriteLine(stopwatch.ElapsedMilliseconds);
stopwatch.Restart();
for (int i = 0; i < 10000; i++)
{
SumProductLength(x, y);
}
Console.WriteLine(stopwatch.ElapsedMilliseconds);
stopwatch.Restart();
for (int i = 0; i < 10000; i++)
{
SumProductPointer(x, y);
}
Console.WriteLine(stopwatch.ElapsedMilliseconds);
}
private static double SumProduct(double[] X, double[] Y)
{
double sum = 0;
int length = X.Length;
if (length != Y.Length)
throw new ArgumentException("X and Y must be same size");
for (int i = 0; i < length; i++)
sum += X[i] * Y[i];
return sum;
}
private static double SumProductLength(double[] X, double[] Y)
{
double sum = 0;
if (X.Length != Y.Length)
throw new ArgumentException("X and Y must be same size");
for (int i = 0; i < X.Length; i++)
sum += X[i] * Y[i];
return sum;
}
private static unsafe double SumProductPointer(double[] X, double[] Y)
{
double sum = 0;
int length = X.Length;
if (length != Y.Length)
throw new ArgumentException("X and Y must be same size");
fixed (double* xp = X, yp = Y)
{
for (int i = 0; i < length; i++)
sum += xp[i] * yp[i];
}
return sum;
}
Прежде всего, я хотел бы поблагодарить всех, кто выступил в этом посте, от оригинального ОП до парней, которые предоставили чрезвычайно подробные и проницательные объяснения. Мне действительно очень понравилось читать существующие ответы. Поскольку уже существует множество теорий о том, как и почему циклы работают так, как они работают, я хотел бы предложить некоторые эмпирические (по определению авторитетные) измерения:
Выводы:
- Цикл Foreach работает быстрее, чем цикл For.
- Локальная переменная быстрее массива
.Lengthимущество. - GC-пиннинг с использованием
unsafe fixedне быстрее, чем обычно для цикла.
Код бенчмаркинга:
using System;
using System.Diagnostics;
using System.Runtime;
namespace demo
{
class MainClass
{
static bool ByForArrayLength (byte[] data)
{
for (int i = 0; i < data.Length; i++)
if (data [i] != 0)
return false;
return true;
}
static bool ByForLocalLength (byte[] data)
{
int len = data.Length;
for (int i = 0; i < len; i++)
if (data [i] != 0)
return false;
return true;
}
static unsafe bool ByForUnsafe (byte[] data)
{
fixed (byte* datap = data)
{
int len = data.Length;
for (int i = 0; i < len; i++)
if (datap [i] != 0)
return false;
return true;
}
}
static bool ByForeach (byte[] data)
{
foreach (byte b in data)
if (b != 0)
return false;
return true;
}
static void Measure (Action work, string description)
{
GCSettings.LatencyMode = GCLatencyMode.LowLatency;
var watch = Stopwatch.StartNew ();
work.Invoke ();
Console.WriteLine ("{0,-40}: {1} ms", description, watch.Elapsed.TotalMilliseconds);
}
public static void Main (string[] args)
{
byte[] data = new byte[256 * 1024 * 1024];
Measure (() => ByForArrayLength (data), "For with .Length property");
Measure (() => ByForLocalLength (data), "For with local variable");
Measure (() => ByForUnsafe (data), "For with local variable and GC-pinning");
Measure (() => ByForeach (data), "Foreach loop");
}
}
}
Результаты: (использует Mono runtime)
$ mcs Program.cs -optimize -unsafe
For with .Length property : 440,9208 ms
For with local variable : 333,2252 ms
For with local variable and GC-pinning : 330,2205 ms
Foreach loop : 280,5205 ms