Цикл начинается с 0 быстрее, чем цикл начинается с 1?

Ответ 1

Обновление

Мне кажется, что это результат неудачной попытки оптимизации с помощью дрожания, а не компилятора. Короче говоря, если дрожание может определить нижнюю границу, это константа, она будет делать что-то другое, что оказывается на самом деле медленнее. Основа для моих выводов требует некоторого доказательства, так что несите меня. Или прочитайте что-нибудь еще, если вам это неинтересно!

Я сделал это после тестирования четырех разных способов установки нижней границы цикла:

• Жесткий код на каждом уровне, как в вопросе colinfang
• Используйте локальную переменную, назначаемую динамически с помощью аргумента командной строки
• Используйте локальную переменную, но присвойте ей постоянное значение
• Используйте локальную переменную и назначьте ей постоянное значение, но сначала передайте значение через туповатую функцию идентификации колбасы. Это смущает дрожание, чтобы предотвратить его "оптимизацию" константы.

Скомпилированный промежуточный язык для всех четырех версий цикла цикла почти идентичен. Единственное различие заключается в том, что в версии 1 нижняя граница загружается командой ldc.i4.#, где # равно 0, 1, 2 или 3. Это означает постоянную нагрузки. (Смотрите ldc.i4 opcode). Во всех остальных версиях нижняя граница загружается с помощью ldloc. Это справедливо даже в случае 3, когда компилятор мог предположить, что lowerBound действительно является константой.

Результирующая производительность не является постоянной. Версия 1 (явная константа) медленнее, чем версия 2 (аргумент времени выполнения) вдоль аналогичных строк, найденных OP. Что очень интересно, так это то, что версия 3 более также медленнее, сопоставимо с версией 1. Таким образом, хотя IL рассматривает нижнюю границу как переменную, дрожание, похоже, выяснило, что значение никогда изменения и заменяет константу, как в версии 1, с соответствующим снижением производительности. В версии 4 джиттер не может вывести то, что я знаю, - что Confuser на самом деле является функцией идентификации, и поэтому он оставляет переменную как переменную. Полученная производительность такая же, как версия аргумента командной строки (2).

Моя теория о причине разницы в производительности: джиттер знает и использует тонкие детали реальной архитектуры процессора. Когда он решает использовать константу, отличную от 0, она должна фактически выполнить выборку этого литерального значения из некоторого хранилища, которое не находится в кэше L2. Когда он извлекает часто используемую локальную переменную, он вместо этого считывает свое значение из кеша L2, что безумно быстро. Обычно не имеет смысла занять место в драгоценном кеше с чем-то немым, как известное целочисленное значение буква. В этом случае мы больше заботимся о времени чтения, чем о хранении, поэтому оно оказывает нежелательное влияние на производительность.

Вот полный код для версии 2 (командная строка arg):

class Program {
    static void Main(string[] args) {
        List<double> testResults = new List<double>();
        Stopwatch sw = new Stopwatch();
        int upperBound = int.Parse(args[0]) + 1;
        int tests = int.Parse(args[1]);
        int lowerBound = int.Parse(args[2]);   // THIS LINE CHANGES
        int sum = 0;

        for (int iTest = 0; iTest < tests; iTest++) {
            sum = 0;
            GC.Collect();
            sw.Reset();
            sw.Start();
            for (int lvl1 = lowerBound; lvl1 < upperBound; lvl1++)
                for (int lvl2 = lowerBound; lvl2 < upperBound; lvl2++)
                    for (int lvl3 = lowerBound; lvl3 < upperBound; lvl3++)
                        for (int lvl4 = lowerBound; lvl4 < upperBound; lvl4++)
                            for (int lvl5 = lowerBound; lvl5 < upperBound; lvl5++)
                                sum++;
            sw.Stop();
            testResults.Add(sw.Elapsed.TotalMilliseconds);
        }

        double avg = testResults.Average();
        double stdev = testResults.StdDev();
        string fmt = "{0,13} {1,13} {2,13} {3,13}"; string bar = new string('-', 13);
        Console.WriteLine();
        Console.WriteLine(fmt, "Iterations", "Average (ms)", "Std Dev (ms)", "Per It. (ns)");
        Console.WriteLine(fmt, bar, bar, bar, bar);
        Console.WriteLine(fmt, sum, avg.ToString("F3"), stdev.ToString("F3"),
                          ((avg * 1000000) / (double)sum).ToString("F3"));
    }
}

public static class Ext {
    public static double StdDev(this IEnumerable<double> vals) {
        double result = 0;
        int cnt = vals.Count();
        if (cnt > 1) {
            double avg = vals.Average();
            double sum = vals.Sum(d => Math.Pow(d - avg, 2));
            result = Math.Sqrt((sum) / (cnt - 1));
        }
        return result;
    }
}

Для версии 1: то же, что и выше, кроме удаления объявления lowerBound и заменить все экземпляры lowerBound литералами 0, 1, 2 или 3 (скомпилировано и выполнено отдельно).

Для версии 3: то же, что и выше, кроме замены объявления lowerBound с помощью

        int lowerBound = 0; // or 1, 2, or 3

Для версии 4: то же, что и выше, кроме замены объявления lowerBound с помощью

        int lowerBound = Ext.Confuser<int>(0); // or 1, 2, or 3

Где Confuser:

public static T Confuser<T>(T d) {
    decimal d1 = (decimal)Convert.ChangeType(d, typeof(decimal));
    List<decimal> L = new List<decimal>() { d1, d1 };
    decimal d2 = L.Average();
    if (d1 - d2 < 0.1m) {
        return (T)Convert.ChangeType(d2, typeof(T));
    } else {
        // This will never actually happen :)
        return (T)Convert.ChangeType(0, typeof(T));
    }
}

Результаты (50 итераций каждого теста в 5 партиях по 10):

1: Lower bound hard-coded in all loops: 
 Program    Iterations  Average (ms)  Std Dev (ms)  Per It. (ns)
-------- ------------- ------------- ------------- -------------
 Looper0     345025251       267.813         1.776         0.776
 Looper1     312500000       344.596         0.597         1.103
 Looper2     282475249       311.951         0.803         1.104
 Looper3     254803968       282.710         2.042         1.109

2: Lower bound supplied at command line: 
 Program    Iterations  Average (ms)  Std Dev (ms)  Per It. (ns)
-------- ------------- ------------- ------------- -------------
  Looper     345025251       269.317         0.853         0.781
  Looper     312500000       244.946         1.434         0.784
  Looper     282475249       222.029         0.919         0.786
  Looper     254803968       201.238         1.158         0.790

3: Lower bound hard-coded but copied to local variable: 
 Program    Iterations  Average (ms)  Std Dev (ms)  Per It. (ns)
-------- ------------- ------------- ------------- -------------
LooperX0     345025251       267.496         1.055         0.775
LooperX1     312500000       345.614         1.633         1.106
LooperX2     282475249       311.868         0.441         1.104
LooperX3     254803968       281.983         0.681         1.107

4: Lower bound hard-coded but ground through Confuser: 
 Program    Iterations  Average (ms)  Std Dev (ms)  Per It. (ns)
-------- ------------- ------------- ------------- -------------
LooperZ0     345025251       266.203         0.489         0.772
LooperZ1     312500000       241.689         0.571         0.774
LooperZ2     282475249       219.533         1.205         0.777
LooperZ3     254803968       198.308         0.416         0.778

Это массивный массив. Во всех практических целях вы проверяете, сколько времени требуется вашей операционной системе для извлечения значений каждого элемента из памяти, а не для сравнения: j, k и т.д. Меньше arrayLength, чтобы увеличить счетчики и увеличивайте свою сумму. Задержка для получения этих значений имеет мало общего с временем выполнения или джиттером как таковым, и многое зависит от того, что еще происходит в вашей системе в целом, а также при сжатии и организации кучи.

Кроме того, поскольку ваш массив занимает столько места и часто обращается к нему, вполне возможно, что сбор мусора работает во время некоторых ваших итераций теста, что полностью завышает кажущееся время процессора.

Попробуйте выполнить свой тест без поиска массива - просто добавьте 1 (sum++), а затем посмотрите, что произойдет. Чтобы быть еще более тщательным, вызовите GC.Collect() непосредственно перед каждым тестом, чтобы избежать сбора во время цикла.

Ответ 2

Я думаю, что версия 0 быстрее, потому что компилятор генерирует специальный код без проверки диапазона в этом случае. См. http://msdn.microsoft.com/library/ms973858.aspx (раздел Исправление диапазона проверки пробелов)

Ответ 3

Просто идея:

Возможно, в циклах есть оптимизаторы с перестановкой битов, поэтому при начале с неравномерным счетчиком это займет больше времени.

Я также не знаю, может ли ваш процессор быть индикатором для разных результатов

Ответ 4

Сверху моей головы, возможно, есть оптимизация компилятора для длины 0 → . Проверьте настройки сборки (отладка и отладка).

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