Попробуй ускорить мой код?

Question

Я написал некоторый код для тестирования воздействия try-catch, но увидел некоторые неожиданные результаты.

static void Main(string[] args)
{
    Thread.CurrentThread.Priority = ThreadPriority.Highest;
    Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;

    long start = 0, stop = 0, elapsed = 0;
    double avg = 0.0;

    long temp = Fibo(1);

    for (int i = 1; i < 100000000; i++)
    {
        start = Stopwatch.GetTimestamp();
        temp = Fibo(100);
        stop = Stopwatch.GetTimestamp();

        elapsed = stop - start;
        avg = avg + ((double)elapsed - avg) / i;
    }

    Console.WriteLine("Elapsed: " + avg);
    Console.ReadKey();
}

static long Fibo(int n)
{
    long n1 = 0, n2 = 1, fibo = 0;
    n++;

    for (int i = 1; i < n; i++)
    {
        n1 = n2;
        n2 = fibo;
        fibo = n1 + n2;
    }

    return fibo;
}

На моем компьютере это постоянно выводит значение около 0,96 ..

Когда я оборачиваю цикл for внутри Fibo () блоком try-catch, подобным этому:

static long Fibo(int n)
{
    long n1 = 0, n2 = 1, fibo = 0;
    n++;

    try
    {
        for (int i = 1; i < n; i++)
        {
            n1 = n2;
            n2 = fibo;
            fibo = n1 + n2;
        }
    }
    catch {}

    return fibo;
}

Теперь он последовательно выводит 0,69 ... - на самом деле он работает быстрее! Но почему?

Примечание: я скомпилировал это с использованием конфигурации Release и непосредственно запустил файл EXE (вне Visual Studio).

РЕДАКТИРОВАТЬ: Jon Skeet's превосходный анализ показывает, что try-catch каким-то образом заставляет CLR x86 использовать регистры ЦП более благоприятным образом в этом конкретном случае (и я думаю, мы еще не поняли почему). Я подтвердил вывод Джона о том, что x64 CLR не имеет этой разницы и что она была быстрее, чем x86 CLR. Я также проверил использование int типов внутри метода Fibo вместо long типов, и затем x86 CLR был таким же быстрым, как x64 CLR.

---

ОБНОВЛЕНИЕ: Похоже, эта проблема была исправлена ​​Roslyn. Та же машина, та же версия CLR - проблема остается такой же, как описано выше при компиляции с VS 2013, но проблема исчезает при компиляции с VS 2015.

Answer 1

Один из инженеров Roslyn , который специализируется на понимании оптимизации использования стека, взглянул на это и сообщил мне, что, похоже, существует проблема во взаимодействии между способом, которым компилятор C # генерирует локальную переменнуюсохраняет и то, как компилятор JIT регистрирует планирование в соответствующем коде x86.Результатом является неоптимальная генерация кода на загрузках и хранилищах локальных компьютеров.

По какой-то непонятной для всех нас причине проблемный путь генерации кода избегается, когда JITter знает, что блок находится в защищенной от пробобласть, край.

Это довольно странно.Мы свяжемся с командой JITter и посмотрим, сможем ли мы ввести ошибку, чтобы они могли это исправить.

Кроме того, мы работаем над улучшением для Roslyn алгоритмов компиляторов C # и VB для определения, когда локальные объекты можно сделать «эфемерными», то есть просто помещать их в стек, а не выделятьконкретное место в стеке на время активации.Мы полагаем, что JITter сможет лучше справляться с распределением регистров, и вообще, если мы дадим ему подсказки о том, когда местные жители могут быть «мертвыми» раньше.

Спасибо, что обратили на это наше внимание, иизвиняюсь за странное поведение.

Answer 2

Ну, то, как вы рассчитываете время, кажется мне довольно неприятным.Было бы гораздо разумнее просто рассчитать время всего цикла:

var stopwatch = Stopwatch.StartNew();
for (int i = 1; i < 100000000; i++)
{
    Fibo(100);
}
stopwatch.Stop();
Console.WriteLine("Elapsed time: {0}", stopwatch.Elapsed);

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

Сделавэто изменение, посмотрите, является ли версия «без улова» все еще более медленной, чем версия с «уловом».

РЕДАКТИРОВАТЬ: Хорошо, я попробовал это сам - и я вижу тот же результат.Очень странно.Я задавался вопросом, отключает ли try / catch какую-то плохую вставку, но использование [MethodImpl(MethodImplOptions.NoInlining)] вместо этого не помогло ...

В принципе, я подозреваю, что вам нужно взглянуть на оптимизированный JITted-код в cordbg...

РЕДАКТИРОВАТЬ: еще несколько битов информации:

• Размещение try / catch вокруг только строки n++; по-прежнему улучшает производительность, но не столько, сколько еевокруг всего блока
• Если вы ловите определенное исключение (ArgumentException в моих тестах), оно все еще быстро
• Если вы печатаете исключение в блоке захвата, оно все еще быстро
• Если вы перебрасываете исключение в блоке catch, он снова замедляется
• Если вы используете блок finally вместо блока catch, он снова замедляется
• Если вы также используете блок finally как блок захвата, это быстро

Странно ...

РЕДАКТИРОВАТЬ: Хорошо, у нас есть разборка ...

Это с использованием C #2 компилятор и .NET 2 (32-битная) CLR, разборка с mdbg (так как у меня нетмоя машина).Я все еще вижу те же эффекты производительности, даже под отладчиком.В быстрой версии используется блок try вокруг всего, что находится между объявлениями переменных и оператором return, с помощью только обработчика catch{}.Очевидно, что медленная версия такая же, за исключением без try / catch.Код вызова (т. Е. Main) одинаков в обоих случаях и имеет одинаковое представление сборки (поэтому это не проблема с включением).

Разобранный код для быстрой версии:

 [0000] push        ebp
 [0001] mov         ebp,esp
 [0003] push        edi
 [0004] push        esi
 [0005] push        ebx
 [0006] sub         esp,1Ch
 [0009] xor         eax,eax
 [000b] mov         dword ptr [ebp-20h],eax
 [000e] mov         dword ptr [ebp-1Ch],eax
 [0011] mov         dword ptr [ebp-18h],eax
 [0014] mov         dword ptr [ebp-14h],eax
 [0017] xor         eax,eax
 [0019] mov         dword ptr [ebp-18h],eax
*[001c] mov         esi,1
 [0021] xor         edi,edi
 [0023] mov         dword ptr [ebp-28h],1
 [002a] mov         dword ptr [ebp-24h],0
 [0031] inc         ecx
 [0032] mov         ebx,2
 [0037] cmp         ecx,2
 [003a] jle         00000024
 [003c] mov         eax,esi
 [003e] mov         edx,edi
 [0040] mov         esi,dword ptr [ebp-28h]
 [0043] mov         edi,dword ptr [ebp-24h]
 [0046] add         eax,dword ptr [ebp-28h]
 [0049] adc         edx,dword ptr [ebp-24h]
 [004c] mov         dword ptr [ebp-28h],eax
 [004f] mov         dword ptr [ebp-24h],edx
 [0052] inc         ebx
 [0053] cmp         ebx,ecx
 [0055] jl          FFFFFFE7
 [0057] jmp         00000007
 [0059] call        64571ACB
 [005e] mov         eax,dword ptr [ebp-28h]
 [0061] mov         edx,dword ptr [ebp-24h]
 [0064] lea         esp,[ebp-0Ch]
 [0067] pop         ebx
 [0068] pop         esi
 [0069] pop         edi
 [006a] pop         ebp
 [006b] ret

Разобранный код для медленной версии:

 [0000] push        ebp
 [0001] mov         ebp,esp
 [0003] push        esi
 [0004] sub         esp,18h
*[0007] mov         dword ptr [ebp-14h],1
 [000e] mov         dword ptr [ebp-10h],0
 [0015] mov         dword ptr [ebp-1Ch],1
 [001c] mov         dword ptr [ebp-18h],0
 [0023] inc         ecx
 [0024] mov         esi,2
 [0029] cmp         ecx,2
 [002c] jle         00000031
 [002e] mov         eax,dword ptr [ebp-14h]
 [0031] mov         edx,dword ptr [ebp-10h]
 [0034] mov         dword ptr [ebp-0Ch],eax
 [0037] mov         dword ptr [ebp-8],edx
 [003a] mov         eax,dword ptr [ebp-1Ch]
 [003d] mov         edx,dword ptr [ebp-18h]
 [0040] mov         dword ptr [ebp-14h],eax
 [0043] mov         dword ptr [ebp-10h],edx
 [0046] mov         eax,dword ptr [ebp-0Ch]
 [0049] mov         edx,dword ptr [ebp-8]
 [004c] add         eax,dword ptr [ebp-1Ch]
 [004f] adc         edx,dword ptr [ebp-18h]
 [0052] mov         dword ptr [ebp-1Ch],eax
 [0055] mov         dword ptr [ebp-18h],edx
 [0058] inc         esi
 [0059] cmp         esi,ecx
 [005b] jl          FFFFFFD3
 [005d] mov         eax,dword ptr [ebp-1Ch]
 [0060] mov         edx,dword ptr [ebp-18h]
 [0063] lea         esp,[ebp-4]
 [0066] pop         esi
 [0067] pop         ebp
 [0068] ret

В каждом случае * показывает, где отладчик вошел в простое «вступление».

РЕДАКТИРОВАТЬ: Хорошо, я сейчаспросмотрел код и думаю, что вижу, как работает каждая версия ... и я считаю, что более медленная версия медленнее, потому что она использует меньше регистров и больше места в стеке.Для малых значений n это возможно быстрее, но когда цикл занимает большую часть времени, он медленнее.

Возможно, блок try / catch заставляет сохранить больше регистрови восстановлен, поэтому JIT использует их и для цикла ... что в целом повышает производительность.Неясно, является ли разумным решение для JIT не использовать столько же регистров в "нормальном" коде.

РЕДАКТИРОВАТЬ: Только что попробовал это на моей машине x64.X64 CLR на намного быстрее (примерно в 3-4 раза быстрее), чем x86 CLR для этого кода, а под x64 блок try / catch не имеет заметного различия.

Answer 3

Разборки Джона показывают, что разница между двумя версиями заключается в том, что быстрая версия использует пару регистров (esi,edi) для хранения одной из локальных переменных, где медленная версия не делает.

JIT-компилятор делает различные предположения относительно использования регистров для кода, который содержит блок try-catch, по сравнению с кодом, который этого не делает.Это заставляет его делать разные варианты выделения регистров.В этом случае это благоприятствует коду с блоком try-catch.Разный код может привести к противоположному эффекту, поэтому я бы не стал считать это универсальной техникой ускорения.

В конце концов, очень трудно сказать, какой код будет работать быстрее всего.Нечто подобное распределению регистров и факторам, влияющим на него, является настолько низкоуровневой реализацией, что я не понимаю, как какой-либо конкретный метод может надежно создавать более быстрый код.

Например, рассмотрим следующие два метода.Они были адаптированы на примере из реальной жизни:

interface IIndexed { int this[int index] { get; set; } }
struct StructArray : IIndexed { 
    public int[] Array;
    public int this[int index] {
        get { return Array[index]; }
        set { Array[index] = value; }
    }
}

static int Generic<T>(int length, T a, T b) where T : IIndexed {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}
static int Specialized(int length, StructArray a, StructArray b) {
    int sum = 0;
    for (int i = 0; i < length; i++)
        sum += a[i] * b[i];
    return sum;
}

Один является обобщенной версией другого.Замена универсального типа на StructArray сделает методы идентичными.Поскольку StructArray является типом значения, он получает свою собственную скомпилированную версию универсального метода.Тем не менее, фактическое время работы значительно больше, чем у специализированного метода, но только для x86.Для x64 тайминги в значительной степени идентичны.В других случаях я наблюдал различия и для x64.

Answer 4

Это похоже на случай, когда сошло плохо.На ядре x86 у джиттера есть регистры ebx, edx, esi и edi, доступные для общего хранения локальных переменных.Регистр ecx становится доступным в статическом методе, он не должен хранить this .Регистр eax часто необходим для расчетов.Но это 32-битные регистры, для переменных типа long он должен использовать пару регистров.Это edx: eax для вычислений и edi: ebx для хранения.

Что выделяется в разборке для медленной версии, ни edi, ни ebx не используются.

Когда дрожание можетНе найдено достаточно регистров для хранения локальных переменных, поэтому он должен сгенерировать код для загрузки и сохранения их из стекового фрейма.Это замедляет код, предотвращает оптимизацию процессора под названием «переименование регистра», трюк по оптимизации внутреннего ядра процессора, который использует несколько копий регистра и позволяет выполнять суперскалярное выполнение.Это позволяет одновременно выполнять несколько инструкций, даже если они используют один и тот же регистр.Отсутствие достаточного количества регистров является распространенной проблемой в ядрах x86, которые решаются в x64 с 8 дополнительными регистрами (от r9 до r15).

Джиттер приложит все усилия, чтобы применить другую оптимизацию генерации кода, он попытается встроитьваш метод Фибо ().Другими словами, не вызывайте метод, а сгенерируйте код для встроенного метода в методе Main ().Довольно важная оптимизация, которая, например, делает свойства класса C # бесплатными, давая им характеристику поля.Это позволяет избежать накладных расходов, связанных с вызовом метода и настройкой его стека, и экономит пару наносекунд.

Существует несколько правил, которые точно определяют, когда метод может быть встроен.Они не совсем задокументированы, но были упомянуты в блогах.Одно из правил заключается в том, что этого не произойдет, если тело метода слишком большое.Это сводит на нет выигрыш от встраивания, он генерирует слишком много кода, который также не помещается в кэш инструкций L1.Другое строгое правило, которое здесь применяется, заключается в том, что метод не будет встроенным, если он содержит инструкцию try / catch.Основой этого является деталь реализации исключений, они привязаны к встроенной поддержке Windows SEH (обработка исключений структуры), которая основана на кадрах стека.

Одно поведение алгоритма распределения регистровв джиттер можно заключить, играя с этим кодом.Похоже, известно, когда джиттер пытается встроить метод.Кажется, в одном из правил используется только пара регистров edx: eax для встроенного кода, имеющего локальные переменные типа long.Но не edi: ebx.Без сомнения, поскольку это было бы слишком пагубно для генерации кода для вызывающего метода, и edi, и ebx являются важными регистрами хранения.

Таким образом, вы получаете быструю версию, потому что джиттер заранее знает, что тело метода содержит try/ ловить заявления.Он знает, что он никогда не может быть встроен, поэтому с готовностью использует edi: ebx для хранения длинной переменной.Вы получили медленную версию, потому что джиттер не знал заранее, что вставка не будет работать.Он обнаружил только после генерации кода для тела метода.

Недостатком является то, что он не вернулся и повторно сгенерировал код дляметод.И это понятно, учитывая временные ограничения, с которыми он должен работать.

Это замедление не происходит на x64, потому что для одного у него есть еще 8 регистров.Для другого, потому что он может хранить long только в одном регистре (например, rax).И замедление не происходит, когда вы используете int вместо long, потому что джиттер обладает гораздо большей гибкостью при выборе регистров.

Answer 5

Я бы поставил это в качестве комментария, так как я действительно не уверен, что это, вероятно, так, но, насколько я помню, это не означает, что оператор try / исключением предполагает изменение способа сбора мусораМеханизм утилизации компилятора работает в том смысле, что он рекурсивно очищает выделение памяти объекта из стека.В этом случае может не быть объекта, который нужно очистить, или цикл for может представлять собой замыкание, которое механизм сбора мусора признает достаточным для обеспечения применения другого метода сбора.Возможно, нет, но я подумал, что стоит упомянуть, потому что я не видел, чтобы это обсуждалось где-либо еще.