Насколько порядок меток регистра влияет на эффективность операторов switch?

Question

Рассмотрим:

if (condition1)
{
    // Code block 1
}
else
{
    // Code block 2
}

Если я знаю, что condition1 будет true большую часть времени, тогда я должен закодировать логику как написано, вместо:

if (!condition1)
{
    // Code block 2
}
else
{
    // Code block 1
}

, поскольку я избегу штрафа jump за второй блок кода (примечание: у меня ограниченные знания ассемблера). Относится ли эта идея к switch операторам и case меткам?

switch (myCaseValue)
{
    case Case1:
        // Code block 1
        break;

    case Case2:
        // Code block 2
        break;

    // etc.
}

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

Answer 1

Некоторые факты для современного оборудования, такие как x86 или x86_64:

• Безоговорочно занятая ветка почти не требует дополнительных затрат, кроме декодирования. Если вы хотите число, это примерно четверть такта.
• Условный переход, который был правильно спрогнозирован, почти не требует дополнительных затрат.
• Условная ветвь, которая не была правильно спрогнозирована, имеет штраф, равный длине конвейеров процессора, это около 12-20 часов, в зависимости от аппаратного обеспечения.
• Механизмы прогнозирования очень сложны. Циклы с небольшим числом итераций (на Core 2, например, до 64) могут быть точно предсказаны. Небольшие повторяющиеся шаблоны, такие как «взят, взят, не взят, взят», могут быть предсказаны, если они не слишком длинные (IIRC 6 на Core2).

Подробнее о прогнозировании ветвей вы можете прочитать в руководстве Agner Fogs превосходное .

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

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

Answer 2

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

Как обычно, см. Википедию: Ветвь Предсказатель

Answer 3

Это зависит. Компилятор будет использовать набор внутренних зависимых от реализации критериев, чтобы решить, реализовывать ли switch как последовательность тестов, похожих на if, или как таблицу переходов. Это может зависеть, например, от того, насколько «компактен» ваш набор меток case. Если ваши значения меток case образуют "плотный" набор, компилятор, скорее всего, будет использовать таблицу переходов, и в этом случае порядок меток case не будет иметь значения. Если он решит пойти с тем, что напоминает последовательность тестов if-else, порядок может иметь значение.

Имейте в виду, однако, что тело switch является одним большим оператором, а метки case обеспечивают несколько точек входа в этот оператор. По этой причине способность компиляторов (так же как и ваша) переставлять case «подблоки» внутри этого оператора может быть ограничена.

Answer 4

Я думаю, что даже ваша первоначальная предпосылка - что вы можете оптимизировать оператор if путем перестановки условного выражения, вполне может быть ошибочной. В неоптимизированной сборке вы можете обнаружить, что выполнение того, о чем вы говорите, имеет определенную ценность - возможно. В общем случае вам придется прыгать хотя бы один раз в любом случае, так что нет никакой пользы (в общем случае) в том, чтобы расположить условные выражения в любом случае. Но это для неоптимизированных сборок, так кого волнует эта оптимизация?

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

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

Если вы действительно заинтересованы в том, чтобы получить максимальную отдачу от этого условия, вы можете использовать что-то вроде Оптимизация профиля профиля MSVC (PGO или 'pogo'), которая использует результаты профилирования работает, чтобы оптимизировать, как создаются условия. Я не знаю, имеет ли GCC аналогичные возможности.

Answer 5

Ярлыки на корпусах должны быть заказаны наиболее эффективным способом для удобства чтения.

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

Answer 6

Я не уверен насчет компилятора C #, но я знаю, что в ассемблере оператор switch может фактически быть запрограммирован как переход к определенной строке, а не как выражение выражения, как оператор if. Поскольку в выборке у вас есть все константы, он просто обрабатывает наблюдения как номера строк, и вы переходите непосредственно к номеру строки (значению регистра), переданному без какой-либо оценки. Это делает порядок регистров не очень важным.

Answer 7

Полагаю, вы знаете, что это будет иметь значение, только если это горячая точка. Лучший способ определить, является ли это горячей точкой, - это запустить код, проверить счетчик программы и посмотреть, присутствует ли он там более 10% времени. Если это горячая точка, посмотрите, сколько времени потрачено на выполнение if или switch. Обычно это незначительно, если ваши Block 1 и / или Block 2 не делают почти ничего . Вы можете использовать профилировщик для этого. Я просто делаю паузу несколько раз.

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

Answer 8

Как уже говорили другие, это зависит от многих вещей, включая количество случаев, то, как выполняется оптимизация и архитектура, на которой вы работаете. Интересный обзор см. http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf

Answer 9

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

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