Я пытаюсь придумать, как написать наиболее оптимальное if ... else if ... else ...
утверждение в C++
.
Предположим, что у нас есть 3 возможных условия, основанных на некотором значении переменной n
: n = 0
, 0 < n < 100
и n = 100
. Предположим, что n = 0
произойдет в 1%
случаях, 0 < n < 100
– 90%
и n = 100
– 9%
. Обратите внимание, что if ... else if ... else ...
будет выполняться много раз, и значение n
каждый раз будет разным.
Моим первым предположением было расположить условия в порядке убывания (наиболее частые — первые, наименее частые — последние), как показано ниже. Однако первое условие будет иметь 3 логических выражения. А поскольку первое условие будет выполняться всегда (в случаях 100%
) и оно состоит из 3 логических выражений (>
, <
и &&
), эти 3 выражения будут выполняться в случаях 100%
. (Возможно, компилятор проведет некоторую оптимизацию и каким-то образом сократит число выражений до 2.) Второе условие будет выполняться в 10%
случаях, а третье условие — в 1%
случаях.
Итак, учитывая, что будет 1 000
итераций, будет оценено 3 100
логических выражений (3 000 + 100
).
if ((n > 0) && (n < 100)) { // 3 boolean expressions will be executed in 100% cases.
...
} else if (n == 100) { // 1 additional boolean expression – in 10% cases.
...
} else { // n = 0 // No additional boolean expressions – in 1% cases.
...
}
Если изменить порядок условий (чтобы исключить условие с помощью 3 логических выражений), будет оценено 1 910
логических выражений (1 000 + 910
).
if (n == 100) { // 1 boolean expression will be executed in 100% cases.
...
} else if (n == 0) { // 1 additional boolean expression – in 91% cases.
...
} else { // 0 < n < 100 // No additional boolean expressions – in 90% cases.
...
}
Я правильно понимаю? Если нет, то как правильно оптимизировать код с помощью if ... else if ... else ...
для скорости?
Обновление: На основании комментариев сделал тест. Первый вариант дает меньше строк скомпилированного кода, чем второй. Не знаю языка ассемблера, поэтому не уверен, лучше ли в этом случае меньше строк.
Прежде всего, при проведении тестов не забывайте всегда выполнять сборку с включенной оптимизацией. Во-вторых, сравните сгенерированный код друг с другом, что легко сделать, например. проводник компилятора.
Обычно последнее предложение else
выполняется быстрее, поскольку не требуется дополнительная инструкция перехода. Итак if (n == 100) ... else if (n == 0) ... else ... ;
Но сравнивать конечно надо.
Из-за операций короткого замыкания (часть стандарта, т.е. независимая от компилятора), цифры, которые вы даете, неверны. Более того, количество потерянных при этом циклов будет очень небольшим по сравнению с тем, что происходит внутри { ... }
, удачи в тестировании. По той же причине мне не кажется, что все, чему вы надеетесь научиться с помощью этого, можно применять как общее правило. В более реалистичном if (someFunctionWithSideEffect(n) == 0) ...
будет доминировать то, что происходит в функции, а не то, как вы упорядочиваете if
.
Оставьте производительность оптимизатору. Потому что преждевременная оптимизация — источник зла. Вместо этого я бы предпочел сосредоточиться на читабельности программы.
ИМХО, излишне узкий и глубокий анализ. Все гораздо проще. switch (n) { case 0: ...; break; case 100: ...; break; default: ...; break; }
Пишите код максимально логично и понятно. Если после того, как вы написали код, возникла проблема с производительностью и профилирование показывает, что порядок операторов имеет значение, вы можете попробовать его оптимизировать.
@3CxEZiVIQ Я согласен, что здесь может быть уместен оператор переключения, поскольку он дает компилятору возможность использовать таблицу переходов (которую я никогда не видел созданной для вложенных операторов if). В более общем случае вложенных операторов if, которые должны быть очень быстрыми и проверять заданное значение, тогда лучше всего организовать тесты в дереве, которое разбивается как можно ближе к 50:50 на каждом уровне. получать. В противном случае возвращайте наиболее частое значение по кратчайшему пути через (ассемблерный) код. Сегодняшние оптимизирующие компиляторы очень хороши, поэтому почти никогда не имеют смысла.
Если в вашем коде есть if
, то на производительность влияют предсказания ветвей. Чем больше вложенных ваших if, тем больше вероятность того, что предсказание ветвей не удастся, и это будет стоить вам производительности. Тем не менее, если производительность является проблемой (скорее всего, это не в данном случае), вам следует использовать профилировщики, чтобы сначала найти худшие узкие места в вашем коде (или дизайне) и исправить их.
Преобразуйте три условия в int
со значением 0, 1 или 2 (по одному значению для каждого из трех условий), затем используйте переключатель/регистр.
Вы не учитываете тот факт, что &&
(и ||
) вызывает короткое замыкание. Таким образом, if ((n > 0) && (n < 100)) {stuff();} else if (n == 0) ...
эквивалентно if (n > 0) { if (n < 100) {stuff();} } else if (n == 0) ...
и никогда не проверяет n < 100
, является ли n > 0
ложным.
Один из ваших счетчиков отключен. Ты говоришь:
if ((n > 0) && (n < 100)) { // 3 boolean expressions will be executed in 100% cases.
Но (1) &&
не является логическим выражением, а неявным if
, поскольку оно сокращает выражение, и (2) из-за короткого замыкания вторая половина n < 100
будет выполнена только в 99% случаев. В 100% случаев будут обследованы только n > 0
.
Кроме того, вы слишком много внимания уделяете тому, как часто оцениваются условия. Это второстепенная проблема, поскольку, прежде всего, обратите внимание, что неизбежна проверка двух условий перед тем, как можно будет войти в наиболее часто встречающуюся ветвь.
Имея это в виду, теперь вы можете начать задаваться вопросом, можно ли избежать проверки одного из двух условий с более высокой вероятностью. Условия: n > 0
(ложно в 1% случаев) и n < 100
(ложно в 10% случаев). Теперь, если вы сначала проверите n > 0
, вы сможете избежать проверки другого в 1% случаев, но если вы сначала проверите n < 100
, то вы сможете избежать второй проверки в 10% случаев. Итак, вот что вам следует сделать:
if (n == 100) { // get 10% of the cases out of the way
...
} else if (n == 0) { // unavoidable second check after first check failed
...
} else { // most frequent case needs both checks
...
}
(Предполагается, что [0 ... 100] — единственные значения, которые n
может принимать.)
Спасибо за дополнительные пояснения! Ваш ответ имеет смысл.
Однако у большинства процессоров есть практически бесплатный тест на нулевое или ненулевое значение, что может склонить чашу весов в пользу проведения этого теста в первую очередь. Только профилирование реального кода может сказать вам, какая версия самая быстрая (и делать это стоит только в крайнем случае). Имейте в виду, что современные компиляторы умны, и если они могут реализовать оператор if как условные ходы (без штрафа за ветвление), то они это сделают. Кодирование, облегчающее просмотр компилятором, иногда необходимо в коде, который должен быть быстрым.
Пожалуйста, поделитесь тестами производительности, показывающими разницу между различными порядками.