Мне интересно, как эффективные низкоуровневые алгоритмы могут быть в .net. Я бы хотел, чтобы мы решили записать больше нашего кода на С#, а не на С++ в будущем, но один камень преткновения - это проверка границ в .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. В С++ я сравнивал времена 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, оптимизированная сборка, параметры по умолчанию). Однако мне пришло в голову, что в С# могут быть три проверки границ. Один явный (i < length
в функции static void SumProduct(double[] X, double[] Y)
в начале этого вопроса) и два неявных (X[i]
и Y[i]
). Поэтому я протестировал третью С++-функцию с тремя ограничениями проверки
for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i];
Это произошло на 35% медленнее первого, чего стоит заботиться. Я сделал еще несколько исследований в этом вопросе, Почему добавление дополнительного цикла проверки делает большую разницу на некоторых машинах и небольшая разница в других?. Интересно, что, по-видимому, стоимость проверки границ значительно различается на разных машинах.