если заявление считается полезным
Краткое описание
оператор в форме if (a > max) max = a - это самый быстрый способ определения максимума набора чисел. Однако сама инфраструктура цикла занимает большую часть процессорного времени, поэтому такая оптимизация в конце концов сомнительна.
Подробнее
Ответ от luisperezphd интересен тем, что он предоставляет числа, однако я считаю, что метод некорректен: компилятор, скорее всего, переместит сравнение из цикла, поэтому ответ не измеряет то, что он хочет измерить. Это объясняет незначительную разницу во времени между контуром управления и контурами измерения.
Чтобы избежать этой оптимизации цикла, я добавил операцию, которая зависит от переменной цикла, в пустой цикл управления, а также во все измерительные циклы. Я моделирую общий случай нахождения максимума в списке чисел и использовал три набора данных:
- лучший случай: первое число является максимальным, все числа после него меньше
- худший случай: каждое число больше предыдущего, поэтому максимум меняет каждую итерацию
- средний регистр: набор случайных чисел
См. Ниже код.
Результат был довольно неожиданным для меня. На моем ноутбуке Core i5 2520M я получил следующее за 1 миллиард итераций (пустой контроль занял около 2,6 с во всех случаях):
max = Math.Max(max, a): 2,0 с в лучшем случае / 1,3 с в худшем случае / 2,0 с в среднем max = Math.Max(a, max): наилучший случай - 1,6 с / наихудший случай - 2,0 с / средний случай - 1,5 с * max = max > a ? max : a: лучший случай 1,2 с / наихудший случай 1,2 с / средний случай 1,2 с if (a > max) max = a: 0,2 с, наилучший случай / 0,9 с, наихудший случай / 0,3 с, средний случай
Таким образом, несмотря на длинные конвейеры ЦП и вытекающие из этого штрафы за ветвление, старый добрый оператор if является явным победителем для всех смоделированных наборов данных; в лучшем случае это в 10 раз быстрее, чем Math.Max, а в худшем - еще более чем на 30%.
Еще одним сюрпризом является то, что порядок аргументов Math.Max имеет значение. Предположительно это происходит из-за того, что логика предсказания ветвлений ЦП работает по-разному для этих двух случаев и неправильное предсказание ветвей более или менее в зависимости от порядка аргументов.
Однако большая часть времени ЦП расходуется на инфраструктуру контуров, поэтому в конечном итоге такая оптимизация в лучшем случае сомнительна. Это обеспечивает измеримое, но незначительное сокращение общего времени выполнения.
ОБНОВЛЕНО luisperezphd
Я не смог бы уместить это в качестве комментария, и было более разумно написать его здесь, а не как часть моего ответа, чтобы он был в контексте.
Ваша теория имеет смысл, но я не смог воспроизвести результаты. Сначала по какой-то причине, используя ваш код, мой цикл управления занимал больше времени, чем циклы, содержащие работу.
По этой причине я сделал числа здесь относительно самого низкого времени вместо контрольного цикла. Секунды в результатах показывают, сколько времени прошло, чем самое быстрое время. Например, в результатах, приведенных ниже, самое быстрое время было для лучшего случая Math.Max (a, max), поэтому каждый второй результат показывает, сколько времени они заняли.
Ниже приведены результаты, которые я получил:
max = Math.Max(max, a): лучший случай 0,012 с / наихудший случай 0,007 с / средний случай 0,028 с max = Math.Max(a, max): 0,000 в лучшем случае / 0,021 в худшем случае / 0,019 с в среднем max = max > a ? max : a: 0,022 с в лучшем случае / 0,02 с в худшем случае / 0,01 с в среднем if (a > max) max = a: лучший случай 0,015 с / наихудший случай 0,024 с / средний случай 0,019 с
Во второй раз, когда я запустил его, я получил:
max = Math.Max(max, a): 0,024 с в лучшем случае / 0,010 с в худшем случае / 0,009 с в среднем max = Math.Max(a, max): лучший случай 0,001 с / наихудший случай 0,000 с / средний случай 0,018 с max = max > a ? max : a: 0,011 с в лучшем случае / 0,005 с в худшем случае / 0,018 с в среднем if (a > max) max = a: лучший случай 0,000 с / наихудший случай 0,005 с / средний случай 0,039 с
В этих тестах достаточно объема, чтобы аномалии могли быть уничтожены. Тем не менее, несмотря на это, результаты довольно разные. Возможно, большое выделение памяти для массива как-то связано с этим. Или, возможно, разница настолько мала, что все, что происходит на компьютере в то время, является истинной причиной изменения.
Обратите внимание, что самое быстрое время, представленное в приведенных выше результатах 0,000, составляет около 8 секунд. Поэтому, если учесть, что самый длинный пробег составлял 8,039, разница во времени составляет около половины процента (0,5%) - слишком мало, чтобы иметь значение.
Компьютер
Код был запущен в Windows 8.1, i7 4810MQ 2,8 ГГц и скомпилирован в .NET 4.0.
Модификации кода
Я немного изменил ваш код для вывода результатов в формате, показанном выше. Я также добавил дополнительный код для ожидания через 1 секунду после начала учета любого дополнительного времени загрузки .NET может потребоваться при запуске сборки.
Также я выполнил все тесты дважды, чтобы учесть любые оптимизации процессора. Наконец, я изменил int для i на unit, чтобы я мог выполнить цикл 4 миллиарда раз вместо 1 миллиарда, чтобы получить больший промежуток времени.
Вероятно, это все излишне, но все для того, чтобы как можно больше убедиться, что на тесты не влияет ни один из этих факторов.
Вы можете найти код по адресу: http://pastebin.com/84qi2cbD
код
using System;
using System.Diagnostics;
namespace ProfileMathMax
{
class Program
{
static double controlTotalSeconds;
const int InnerLoopCount = 100000;
const int OuterLoopCount = 1000000000 / InnerLoopCount;
static int[] values = new int[InnerLoopCount];
static int total = 0;
static void ProfileBase()
{
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
int maxValue;
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
// baseline
total += values[i];
}
}
stopwatch.Stop();
controlTotalSeconds = stopwatch.Elapsed.TotalSeconds;
Console.WriteLine("Control - Empty Loop - " + controlTotalSeconds + " seconds");
}
static void ProfileMathMax()
{
int maxValue;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = Math.Max(values[i], maxValue);
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("Math.Max(a, max) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileMathMaxReverse()
{
int maxValue;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = Math.Max(maxValue, values[i]);
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("Math.Max(max, a) - " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileInline()
{
int maxValue = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
maxValue = maxValue > values[i] ? values[i] : maxValue;
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("max = max > a ? a : max: " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void ProfileIf()
{
int maxValue = 0;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int j = 0; j < OuterLoopCount; j++)
{
maxValue = 0;
for (int i = 0; i < InnerLoopCount; i++)
{
if (values[i] > maxValue)
maxValue = values[i];
total += values[i];
}
}
stopwatch.Stop();
Console.WriteLine("if (a > max) max = a: " + stopwatch.Elapsed.TotalSeconds + " seconds");
Console.WriteLine("Relative: " + (stopwatch.Elapsed.TotalSeconds - controlTotalSeconds) + " seconds");
}
static void Main(string[] args)
{
Random rnd = new Random();
for (int i = 0; i < InnerLoopCount; i++)
{
//values[i] = i; // worst case: every new number biggest than the previous
//values[i] = i == 0 ? 1 : 0; // best case: first number is the maximum
values[i] = rnd.Next(int.MaxValue); // average case: random numbers
}
ProfileBase();
Console.WriteLine();
ProfileMathMax();
Console.WriteLine();
ProfileMathMaxReverse();
Console.WriteLine();
ProfileInline();
Console.WriteLine();
ProfileIf();
Console.ReadLine();
}
}
}