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

Я написал некоторый код для проверки влияния 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).

EDIT: Отличный анализ Jon Skeet показывает, что попытка try-catch каким-то образом заставляет среду CLR x86 более выгодно использовать регистры процессора в этом конкретном случае (и Я думаю, нам еще предстоит понять, почему). Я подтвердил, что Джон обнаружил, что x64 CLR не имеет этой разницы и что он был быстрее, чем CLR x86. Я также тестировал с использованием типов int внутри метода Fibo вместо типов long, а затем CLR x86 был столь же быстрым, как и x64 CLR.

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

Ответы

Ответ 1

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

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

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

Кроме того, мы работаем над усовершенствованиями для Roslyn для алгоритмов компиляторов С# и VB для определения того, когда локальные жители могут быть сделаны "эфемерными", то есть просто толкаются и выталкиваются в стек, вместо того, чтобы выделять определенное место на стек на время активации. Мы считаем, что JITTER сможет лучше выполнять распределение регистров, а еще больше, если мы дадим ему более четкие подсказки о том, когда локальные жители могут быть "мертвы" раньше.

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

Ответ 2

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

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

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

Сделав это изменение, посмотрите, будет ли версия "не-catch" еще медленнее, чем версия "catch".

EDIT: Хорошо, я сам пробовал - и я вижу тот же результат. Очень странно. Я задавался вопросом, отключает ли try/catch какую-то плохую инкрустацию, но использование [MethodImpl(MethodImplOptions.NoInlining)] вместо этого не помогло...

В принципе, вам нужно будет посмотреть оптимизированный JIT-код под cordbg, я подозреваю...

EDIT: Еще несколько бит информации:

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

Weird...

EDIT: Хорошо, у нас есть разборка...

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

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

 [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

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

EDIT: Хорошо, теперь я просмотрел код, и я думаю, что вижу, как работает каждая версия... и я считаю, что медленная версия работает медленнее, потому что она использует меньше регистров и больше пространства стека. При небольших значениях n, возможно, быстрее - но когда цикл занимает основную часть времени, он медленнее.

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

EDIT: просто попробовал это на моей машине x64. X64 CLR намного быстрее (примерно в 3-4 раза быстрее), чем CLR x86 в этом коде, а в x64 блок try/catch не создает заметной разницы.

Ответ 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.

Ответ 4

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

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

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

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

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

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

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

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

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

Ответ 5

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