Порядок условий в `if ... else if ... else ...` в C++

Я пытаюсь придумать, как написать наиболее оптимальное if ... else if ... else ... утверждение в C++.

Предположим, что у нас есть 3 возможных условия, основанных на некотором значении переменной n: n = 0, 0 < n < 100 и n = 100. Предположим, что n = 0 произойдет в 1% случаях, 0 < n < 10090% и n = 1009%. Обратите внимание, что 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 ... для скорости?

Обновление: На основании комментариев сделал тест. Первый вариант дает меньше строк скомпилированного кода, чем второй. Не знаю языка ассемблера, поэтому не уверен, лучше ли в этом случае меньше строк.

Пожалуйста, поделитесь тестами производительности, показывающими разницу между различными порядками.

cigien 15.06.2024 08:55

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

Some programmer dude 15.06.2024 08:58

Обычно последнее предложение else выполняется быстрее, поскольку не требуется дополнительная инструкция перехода. Итак if (n == 100) ... else if (n == 0) ... else ... ; Но сравнивать конечно надо.

dimich 15.06.2024 09:14

Из-за операций короткого замыкания (часть стандарта, т.е. независимая от компилятора), цифры, которые вы даете, неверны. Более того, количество потерянных при этом циклов будет очень небольшим по сравнению с тем, что происходит внутри { ... }, удачи в тестировании. По той же причине мне не кажется, что все, чему вы надеетесь научиться с помощью этого, можно применять как общее правило. В более реалистичном if (someFunctionWithSideEffect(n) == 0) ... будет доминировать то, что происходит в функции, а не то, как вы упорядочиваете if.

Atmo 15.06.2024 09:24

Оставьте производительность оптимизатору. Потому что преждевременная оптимизация — источник зла. Вместо этого я бы предпочел сосредоточиться на читабельности программы.

Red.Wave 15.06.2024 09:32

ИМХО, излишне узкий и глубокий анализ. Все гораздо проще. switch (n) { case 0: ...; break; case 100: ...; break; default: ...; break; }

3CxEZiVlQ 15.06.2024 09:38

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

Alan Birtles 15.06.2024 09:55

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

Martin Brown 15.06.2024 09:57

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

Pepijn Kramer 15.06.2024 10:06

Преобразуйте три условия в int со значением 0, 1 или 2 (по одному значению для каждого из трех условий), затем используйте переключатель/регистр.

Eljay 15.06.2024 14:08

Вы не учитываете тот факт, что &&||) вызывает короткое замыкание. Таким образом, 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 ложным.

Peter 15.06.2024 14:38
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
6
11
136
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Один из ваших счетчиков отключен. Ты говоришь:

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 может принимать.)

Спасибо за дополнительные пояснения! Ваш ответ имеет смысл.

ENIAC 15.06.2024 09:42

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

Martin Brown 15.06.2024 22:24

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