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

StackOverflow https://stackoverflow.com/questions/1827406

Вопрос

Рассмотреть:

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

Это было полезно?

Решение

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

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top