Оправдает ли порядок дел в инструкции switch на производительность?

Ответ 1

Вы смотрите на неоптимизированный код, поэтому изучение его для производительности не очень значимо. Если вы посмотрите на оптимизированный код для своих примеров, вы обнаружите, что он не делает сравнения вообще! Оптимизатор замечает, что переменная switch sc всегда имеет значение 1, поэтому она удаляет недоступную case 2.

Оптимизатор также видит, что переменная a не используется после ее назначения, поэтому она также удаляет код в case 1, оставляя main() пустой функцией. И он удаляет функцию prolog/epilog, которая управляет rbp, поскольку этот регистр не используется.

Таким образом, оптимизированный код будет таким же для любой версии вашей функции main():

main:
    xor eax, eax
    ret

Короче говоря, для кода в вопросе не имеет значения, в каком порядке вы помещаете операторы case, потому что ни один из этого кода не будет создан вообще.

Будет ли порядок заказа case в более реальном примере, где код действительно генерируется и используется? Возможно нет. Обратите внимание, что даже в вашем неоптимизированном сгенерированном коде обе версии проверяют два значения case в числовом порядке, сначала проверяя на 1, а затем на 2, независимо от порядка в исходном коде. Очевидно, что компилятор выполняет некоторую сортировку даже в неоптимизированном коде.

Обязательно обратите внимание на комментарии Гленна и Лундина: порядок разделов case не является единственным изменением между вашими двумя примерами, и реальный код тоже отличается. В одном из них значения case соответствуют значениям, установленным в a, но не так в другом.

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

Ответ 2

Оптимизация компилятора операторов switch сложна. Конечно, вам нужно включить оптимизацию (например, попытайтесь скомпилировать свой код с помощью gcc -O2 -fverbose-asm -S с помощью GCC и загляните внутрь сгенерированного файла ассемблера .s). Кстати, на обоих ваших примерах мой GCC 7 на Debian/Sid/x86-64 дает просто:

        .type   main, @function
main:
.LFB0:
        .cfi_startproc
# rsp.c:13: }
        xorl    %eax, %eax      #
        ret
        .cfi_endproc

^{(поэтому в этом сгенерированном коде нет следов switch)}

Если вам нужно понять, как оптимизировать компилятор switch, есть некоторые статьи по этому вопросу, такие как this one.

Если у меня больше номеров коммутаторов, то порядок действий влияет на производительность?

Не вообще, если вы используете какой-то оптимизирующий компилятор и попросите его оптимизировать. См. Также .

Если это так важно для вас (но это не должно быть, оставьте микро-оптимизации вашему компилятору!), вам нужно ориентироваться, профилировать и, возможно, изучать сгенерированный код ассемблера. BTW, пропуски кеша и распределение регистров могут иметь значение гораздо больше, чем порядка case -s, поэтому я думаю, вы не должны беспокоиться вообще. Имейте в виду приблизительные оценки времени последних компьютеров. Поместите case в самый читаемый порядок (для следующего разработчика, работающего над тем же исходным кодом). Читайте также о threaded code. Если у вас есть объективные (связанные с исполнением) причины, чтобы переупорядочить case -s (что очень маловероятно и должно произойти не более одного раза в вашей жизни), напишите хороший комментарий, объясняющий эти причины.

Если вы заботитесь о производительности, обязательно benchmark и и выберите хороший компилятор и используйте его с соответствующими параметрами оптимизации. Возможно, экспериментируйте несколько различных настроек оптимизации (и, возможно, нескольких компиляторов). Вы можете добавить -march=native (кроме -O2 или -O3). Вы можете подумать о компиляции и привязке к -flto -O2, чтобы включить оптимизацию времени соединения и т.д. Вы также можете захотеть профили на основе.

BTW, многие компиляторы огромны бесплатные программы (в частности GCC и Clang). Если вам небезразлична производительность, вы можете исправить компилятор, расширить его, добавив некоторый дополнительный пропуск оптимизации ( форсировать исходный код, добавив некоторые плагин для GCC или некоторые расширения

Ответ 3

Производительность будет зависеть в основном от количества пропусков веток для данного набора данных, а не от общего числа случаев. И это, в свою очередь, сильно зависит от фактических данных и того, как компилятор решил реализовать коммутатор (таблица рассылки, условные условные обозначения, дерево условных выражений - не уверены, можете ли вы даже управлять этим с C).

Ответ 4

В случаях, когда большинство меток case являются последовательными, компиляторы часто обрабатывают операторы switch, чтобы использовать таблицы перехода, а не сравнения. Точные средства, с помощью которых компиляторы решают, какую форму вычисляемого перехода использовать (если таковые имеются) будут различаться между различными реализациями. Иногда добавление дополнительных случаев в оператор switch может повысить производительность за счет упрощения кода, сгенерированного компилятором (например, если код использует случаи 4-11, а случаи 0-3 обрабатываются по умолчанию, добавление явного case 0:; case 1:; case 2:; case 3:; до default: может в результате компилятор сравнивает операнд с 12 и, если он меньше, использует таблицу перехода из 12 элементов. Опускание этих случаев может заставить компилятор вычесть 4 перед сравнением разницы с 8, а затем использовать таблицу из 8 элементов.

Одна из трудностей в оптимизации оптимизации операторов switch заключается в том, что компиляторы обычно знают лучше, чем программисты, о том, как производительность разных подходов будет отличаться при задании определенных входных данных, но программисты могут лучше знать, чем компиляторы, какое распределение входных данных будет получать программа. Учитывая что-то вроде:

if (x==0)
  y++;
else switch(x)
{
  ...
}

"умный" компилятор может распознать, что изменение кода:

switch(x)
{
  case 0:
    y++;
    break;
  ...
}

может устранить сравнение во всех случаях, когда x отличное от нуля, за счет стоимости вычисленного скачка, когда x равно нулю. Если x не больше нуля, это будет хорошей торговлей. Если x равно нулю 99,9% времени, однако, это может быть плохой сделкой. Различные составители компилятора различаются по степени которые они попытаются оптимизировать конструкции, подобные прежним, в последние.

Ответ 5

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

В этом примере показано, что даже если вы измените порядок дел в инструкции switch в вашем примере, GCC и большинство других компиляторов будут переупорядочивать их, если оптимизация включена. Я использовал функции extern, чтобы убедиться, что значения известны только во время выполнения, но я мог бы также использовать rand, например.

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

Ответ 6

Оператор switch обычно скомпилируется с помощью таблиц переходов не с помощью простых сопоставлений.

Таким образом, нет потери в производительности, если вы переставляете case-statements.

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

Когда различия чисел между случаем number велики от одного случая к другому, например, в case 10: и case 200000:, компилятор, несомненно, не генерирует таблицы перехода, так как он должен заполнять около 200 тыс. записей почти всеми указатель на случай default:, и в этом случае он будет использовать comparaisons.

Ответ 7

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

В первом примере случай 1 приводит к a = 1, а случай 2 приводит к a = 2. Компилятор может оптимизировать это, чтобы установить a = sc для этих двух случаев, который является одним утверждением.

В вашем втором примере случай 1 приводит к a = 2, а случай 2 приводит к a = 1. Компилятор больше не может использовать этот ярлык, поэтому он должен явно установить a = 1 или = 2 для обоих случаев. Конечно, для этого требуется больше кода.

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

Вы можете проверить эту оптимизацию, используя код

int main()
{
    int a, sc = 1;

    switch (sc)
    {
        case 1:
        case 2:
            a = sc;
            break;
    }
}

который также должен давать точно такой же ассемблер.

Кстати, ваш тестовый код предполагает, что sc действительно читается. Большинство современных оптимизирующих компиляторов могут определить, что sc не меняется между присваиванием и оператором switch и заменяет чтение sc постоянным значением 1. Дальнейшая оптимизация затем удалит избыточные ветки (switch), и даже назначение может быть оптимизировано, потому что оно фактически не меняется. И с точки зрения переменной a компилятор также может обнаружить, что a не читается в другом месте и поэтому полностью удаляет эту переменную из кода.

Если вы действительно хотите, чтобы sc был прочитан, и он должен быть установлен, вам нужно объявить их как volatile. К счастью, компилятор, похоже, реализовал его так, как вы ожидали, но вы абсолютно не можете этого ожидать, когда включена оптимизация.