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


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

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


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


1326


источник


Ответы:


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

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

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

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

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


914



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

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: Еще несколько бит информации:

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

Weird ...

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

Это использует компилятор C # 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 не создает заметной разницы.


693



Разборки Джона показывают, что разница между двумя версиями заключается в том, что в быстрой версии используется пара регистров ( 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.


109



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

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

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

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

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

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

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

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

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


63



I'd have put this in as a comment as I'm really not certain that this is likely to be the case, but as I recall it doesn't a try/except statement involve a modification to the way the garbage disposal mechanism of the compiler works, in that it clears up object memory allocations in a recursive way off the stack. There may not be an object to be cleared up in this case or the for loop may constitute a closure that the garbage collection mechanism recognises sufficient to enforce a different collection method. Probably not, but I thought it worth a mention as I hadn't seen it discussed anywhere else.


18