Избегайте веток на управляемых языках - PullRequest
Новая
       58

Избегайте веток на управляемых языках

6 голосов
/ 08 ноября 2011

В C при компиляции на машину x86 я обычно заменял бы ветви логическим выражением, когда скорость является наиболее важным аспектом, даже если условия сложные, например, вместо 

char isSomething() {
    if (complexExpression01) {
        if (complexExpression02) {
            if(!complexExpression03) {
                return 1;
            }
        }
    }
    return 0;
}

Я напишу: 

char isSomething() {
    return complexExpression01 &&
           complexExpression02 &&
           !complexExpression03 ;
}

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

Есть ли основания действовать таким же образом при работе с управляемым кодом, таким как C #? Являются ли «переходы» дорогостоящими в управляемом коде, как в неуправляемом коде (по крайней мере, в x86)?

Ответы [ 4 ]

4 голосов
/ 08 ноября 2011

General

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

csc.exe /optimize+
cl.exe /O2
g++ -O2

и соответствующие режимы оптимизации по умолчанию.

Общая мантра: профиль, профиль, профиль (и не оптимизируйте микро, пока ваш профилировщик не скажет вам).Вы всегда можете посмотреть на сгенерированный код 2 , чтобы увидеть, есть ли возможности для улучшения.

Подумайте об этом так, например, код C #:

C # /.NET

Каждый из ваших complexExpressions является де-факто вызовом функции (call, calli, код операции callvirt 3 ), который требует, чтобы его аргументы были помещены в стек,Возвращаемое значение будет оставлено в стеке вместо параметров на выходе.

Теперь, CLR - это виртуальная машина, основанная на стеке (т. Е. Без регистра), это равнозначно анонимная временная переменная в стеке.Единственное различие заключается в количестве идентификаторов, используемых в коде.

Теперь то, что движок JIT делает с этим, другое дело: движок JIT должен будет переводить эти вызовы в собственную сборку и может выполнять оптимизацию путем настройкираспределение регистров, порядок команд, прогноз ветвлений и тому подобное 1

1 (хотя на практике для этого примера это не будет разрешеносделать более интересные оптимизации, потому что complex function calls может иметь побочные эффекты, а спецификации C # очень четко указывают на порядок оценки и так называемую последовательность). Обратите внимание , однако, что движку JIT разрешено встроенных вызовов функций, чтобы уменьшить накладные расходы на вызовы.

Не только когда они не виртуальные, но (IIRC)также, когда тип среды выполнения может быть известен статически во время компиляции для определенных внутренних компонентов .NET Framework.Мне нужно было бы найти ссылку на это, но на самом деле я думаю, что в .NET Framework 4.0 есть атрибуты, которые явно предотвращают встраивание функций платформы;это позволяет Microsoft исправлять код библиотеки в пакетах обновления / обновления, даже если пользовательские сборки были заранее скомпилированы (ngen.exe) в собственные образы.

C / C ++

В C / C ++ модель памяти намного более слабая (т. Е. По крайней мере до C ++ 11), и код обычно компилируется до собственных инструкций ввремя компиляции напрямую.Добавим, что компиляторы C / C ++ обычно выполняют агрессивное встраивание, код даже в таких компиляторах обычно будет одинаковым, если только вы не компилируете без включенной оптимизации

2 Я использую

  • ildasm или monodis для просмотра сгенерированного кода IL
  • mono -aot=full,static или mkbundle для создания собственных объектных модулей и objdump -CdS для просмотра аннотированной собственной сборкиинструкции для этого.

Обратите внимание, что это просто любопытство, потому что редко бывает, что я нахожу интересные узкие места таким образом.Однако см. J в сообщениях Skeet в блоге об оптимизации производительности Noda.NET для хороших примеров неожиданностей, которые могут скрываться в сгенерированном коде IL для общих классов.

3 Редактировать не точно для операторов встроенных функций компилятора, хотя даже они просто оставят свой результат в стеке.

2 голосов
/ 08 ноября 2011

Это зависит от реализации CLR и компилятора управляемого языка.В случае C # следующий тестовый пример подтверждает, что нет разницы в инструкциях для вложенных операторов if и комбинированных операторов if: 

            // case 1
            if (value1 < value2)
00000089  mov         eax,dword ptr [ebp-0Ch] 
0000008c  cmp         eax,dword ptr [ebp-10h] 
0000008f  jge         000000A6 
            {
                if (value2 < value3)
00000091  mov         eax,dword ptr [ebp-10h] 
00000094  cmp         eax,dword ptr [ebp-14h] 
00000097  jge         000000A6 
                {
                    result1 = true;
00000099  mov         eax,1 
0000009e  and         eax,0FFh 
000000a3  mov         dword ptr [ebp-4],eax 
                }
            }

            // case 2
            if (value1 < value2 && value2 < value3)
000000a6  mov         eax,dword ptr [ebp-0Ch] 
000000a9  cmp         eax,dword ptr [ebp-10h] 
000000ac  jge         000000C3 
000000ae  mov         eax,dword ptr [ebp-10h] 
000000b1  cmp         eax,dword ptr [ebp-14h] 
000000b4  jge         000000C3 
            {
                result2 = true;
000000b6  mov         eax,1 
000000bb  and         eax,0FFh 
000000c0  mov         dword ptr [ebp-8],eax 
            }
1 голос
/ 08 ноября 2011

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

0 голосов
/ 08 ноября 2011

Единственный способ узнать это измерить.

Истина и ложь представлены как 1 и 0 в CLR, поэтому меня не удивит, если использование логических выражений имеет какое-то преимущество. Посмотрим: 

static void BenchBranch() {
    Stopwatch sw = new Stopwatch();

    const int NMAX = 1000000000;
    bool a = true;
    bool b = false;
    bool c = true;

    sw.Restart();
    int sum = 0;
    for (int i = 0; i < NMAX; i++) {
        if (a)
            if (b)
                if (c)
                    sum++;
        a = !a;
        b = a ^ b;
        c = b;
    }
    sw.Stop();
    Console.WriteLine("1: {0:F3} ms ({1})", sw.Elapsed.TotalMilliseconds, sum);

    sw.Restart();
    sum = 0;
    for (int i = 0; i < NMAX; i++) {
        if (a && b && c) 
            sum++;
        a = !a;
        b = a ^ b;
        c = b;
    }
    sw.Stop();
    Console.WriteLine("2: {0:F3} ms ({1})", sw.Elapsed.TotalMilliseconds, sum);

    sw.Restart();
    sum = 0;
    for (int i = 0; i < NMAX; i++) {
        sum += (a && b && c) ? 1 : 0;
        a = !a;
        b = a ^ b;
        c = b;
    }
    sw.Stop();
    Console.WriteLine("3: {0:F3} ms ({1})", sw.Elapsed.TotalMilliseconds, sum);
}

Результат: 

1:  2713.396 ms (250000000)
2:  2477.912 ms (250000000)
3:  2324.916 ms (250000000)

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

В конце концов, стоит ли такая микрооптимизация, как это, зависит от того, насколько критичен для кода код.

...