«ЕСЛИ» дорого?

101

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

Модуль называется «Структуры данных и алгоритмы», и он рассказал нам что-то вроде:

ifУтверждение является самым дорогим [что - то]. [что-то] регистрирует [что-то].

Да, у меня ужасная память, и мне действительно очень жаль, но я гуглил часами, но ничего не вышло. Любые идеи?

пек
источник
29
Есть ли у учителя вариант?
Майкл Майерс
7
Почему бы тебе не написать своему учителю по электронной почте? Маловероятно, что кто-то на SO знает, что сказал ваш учитель, если только он не был там в то время (или ваш учитель сам не читает SO).
Билл Карвин
11
И, конечно же, ссылка на обязательный ответ железной дороги
bobobobo
Операторы if или особенно выражения «?:» В языках с фигурными скобками, на которые влияет C, могут быть реализованы с помощью специальных инструкций условного выполнения, например, на процессорах x86 и arm. Это инструкции, которые либо выполняют, либо не выполняют какую-либо операцию на основе предыдущего теста. Использование этих отличных инструкций полностью избавляет от необходимости использовать инструкции условного перехода / перехода / перехода. Значительное улучшение производительности в некоторых ситуациях за счет того, что выполнение программы становится полностью предсказуемой, поскольку она просто работает без перескоков (возможно, непредсказуемых) к разным точкам кода.
Сесил Уорд,
Хорошему компилятору иногда может потребоваться небольшой толчок в правильном направлении, чтобы он использовал условные инструкции вместо тупости и использования условных переходов, реорганизуя код и, возможно, используя умную арифметику в выражении или? : выражение. Не играйте с этим, если вы действительно не знаете свой asm и не прочитали, например, руководства по оптимизации Agner Fog. Компиляторы иногда делают это правильно независимо от того, операторы if или? : выражения используются.
Сесил Уорд

Ответы:

189

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

Текущая команда, которая должна быть выполнена, хранится в том, что обычно называется указателем команд (IP) или счетчиком программ (ПК); эти термины синонимичны, но для разных архитектур используются разные термины. Для большинства инструкций ПК следующей инструкции - это просто текущий ПК плюс длина текущей инструкции. Для большинства архитектур RISC все инструкции имеют постоянную длину, поэтому ПК можно увеличивать на постоянную величину. Для архитектур CISC, таких как x86, инструкции могут иметь переменную длину, поэтому логика, которая декодирует инструкцию, должна определять, как долго текущая инструкция должна найти местоположение следующей инструкции.

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

Условное и безусловное легко понять - условная ветвь берется только в том случае, если выполняется определенное условие (например, равно ли одно число другому); если ветвление не выполнено, управление переходит к следующей инструкции после ветвления, как обычно. Для безусловных переходов всегда берется ветвь. Условные переходы появляются в ifоператорах и контрольных тестахfor и whileпетель. Безусловные переходы проявляются в бесконечных циклах, вызовах функций, возвратах функций breakи continueоператорах, печально известном gotoутверждении и многом другом (эти списки далеко не исчерпывающие).

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

Что все это значит для производительности? Когда процессор видит, что в его конвейере появляется инструкция ветвления, ему необходимо выяснить, как продолжить заполнение своего конвейера. Чтобы выяснить, какие инструкции идут после ветки в потоке программы, ему необходимо знать две вещи: (1) будет ли ветвь взята и (2) цель ветки. Это называется предсказанием ветвления , и это сложная задача. Если процессор угадает правильно, программа продолжает работу на полной скорости. Если вместо того, чтобы процессор угадывает неправильно , он просто провел некоторое время вычисления неправильных вещей. Теперь он должен очистить свой конвейер и перезагрузить его инструкциями из правильного пути выполнения. Итог: большая производительность.

Таким образом, причина, по которой операторы if являются дорогостоящими, связана с неверными предсказаниями ветвлений . Это только на самом низком уровне. Если вы пишете код высокого уровня, вам совсем не нужно беспокоиться об этих деталях. Об этом следует заботиться только в том случае, если вы пишете крайне критичный для производительности код на C или ассемблере. В этом случае написание кода без ветвлений часто может быть лучше, чем код с ветвлениями, даже если требуется еще несколько инструкций. Есть некоторые интересные битовые-вертел трюки , которые вы можете сделать , чтобы вычислить такие вещи, как abs(), min()и max()без ветвления.

Адам Розенфилд
источник
20
Это не просто неверные предсказания веток. Ветви также препятствуют переупорядочению инструкций на уровне компилятора, а также в некоторой степени на уровне ЦП (конечно, для ЦП, вышедшего из строя). Хотя хороший подробный ответ.
jalf
5
Если языки высокого уровня в конечном итоге переводятся на языки низкого уровня, и вы пишете код, ориентированный на производительность, вы все равно ничего не выиграете, написав код, который избегает операторов if? Разве эта концепция не переносится на языки более высокого уровня?
c ..
19

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

Я бы не стал об этом беспокоиться. Если вы не занимаетесь встроенным программированием, вам, вероятно, вообще не стоит беспокоиться о стоимости " if". Для большинства программистов это никогда не будет определяющим фактором производительности вашего приложения.

Джоэл Кохорн
источник
2
Определенно относительный ... cmp / cond jmp все еще быстрее, чем mul на многих процессорах.
Brian Knoblauch
4
Да, я согласен с тем, что меня это не беспокоит. Я не пытаюсь здесь ничего оптимизировать. Я просто пытаюсь узнать и научиться. ;)
pek
15

Ответвления, особенно в микропроцессорах с архитектурой RISC, являются одними из самых дорогих инструкций. Это связано с тем, что на многих архитектурах компилятор предсказывает, какой путь выполнения будет выбран наиболее вероятным, и помещает эти инструкции следующими в исполняемый файл, поэтому они уже будут в кеше ЦП, когда произойдет ветвление. Если ветвь идет другим путем, она должна вернуться в основную память и получить новые инструкции - это довольно дорого. На многих архитектурах RISC все инструкции представляют собой один цикл, за исключением перехода (который часто составляет 2 цикла). Мы не говорим здесь о крупных расходах, поэтому не беспокойтесь об этом. Кроме того, компилятор оптимизирует лучше, чем вы, в 99% случаев: ) Одна из действительно замечательных особенностей архитектуры EPIC (например, Itanium) заключается в том, что она кэширует (и начинает обработку) инструкции с обеих сторон ветки, а затем отбрасывает набор, который ему не нужен, как только результат ветки известный. Это экономит дополнительный доступ к памяти типичной архитектуры в случае ее разветвления по непредсказуемому пути.

Rmeador
источник
13

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

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

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

Параппа
источник
На самом деле! Можно также добавить, что при кодировании на языке, который поддерживает вызовы (в основном, на любом другом языке, кроме ассемблера или C без stdlib), вмешательство конвейера со стороны обычных методов программирования подавит любые вопросы об условном ветвлении.
Росс Паттерсон
10

ifсам по себе не медленный. Медлительность всегда относительно. Бьюсь об заклад, вы никогда не испытывали «накладных расходов», связанных с оператором if. Если вы собираетесь создать высокопроизводительный код, вы все равно можете избегать ветвлений. Что делает ifмедленным, так это то, что процессор предварительно загружает код после, ifосновываясь на какой-то эвристике и так далее. Это также остановит конвейеры от выполнения кода непосредственно после ifинструкции ветвления в машинном коде, поскольку процессор еще не знает, какой путь будет выбран (в конвейерном процессоре несколько инструкций чередуются и выполняются). Выполняемый код может быть выполнен в обратном порядке (если была взята другая ветвь. Она вызывается branch misprediction), или noopзаполниться в этих местах, чтобы этого не произошло.

Если ifесть зло, то switchзло тоже, и &&, ||тоже. Не беспокойся об этом.

Йоханнес Шауб - litb
источник
7

На самом низком возможном уровне ifсостоит из (после вычисления всех конкретных предпосылок для конкретного приложения if):

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

Затраты, связанные с этим:

  • низкоуровневое сравнение - обычно 1 процессор, супер дешево
  • потенциальный скачок - что может быть дорого

Резон, почему прыжки дорогие:

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

Итак, подведем итоги:

  • Если вы действительно очень заботитесь о производительности.
  • Вы должны заботиться об этом тогда и только тогда, когда пишете трассировщик лучей в реальном времени, или биологическое моделирование, или что-то подобное. Нет причин беспокоиться об этом в большей части реального мира.
Марчин
источник
Перейдите на следующий уровень: как насчет вложенных и / или составных операторов if? Расходы могут быстро стать заметными, если кто-то напишет много таких операторов if. А поскольку большинству разработчиков операторы if кажутся такой фундаментальной операцией, избегание запутанного условного ветвления часто сводится к стилистической задаче. Стилистические соображения по-прежнему важны, но часто в пылу срыва они могут быть первой проблемой, которую следует игнорировать.
jaydel
7

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

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

Pentium 4 (Prescott) имел длинную цепочку из 31 ступени.

Подробнее в Википедии

Guge
источник
6

Может, ветвление убивает предварительную выборку инструкций CPU?

activout.se
источник
После моего ... "исследования" я узнал о таблицах переходов и ветвлениях для операторов switch, но ничего об операторах if. Не могли бы вы немного подробнее рассказать об этом?
pek
IIRC, ЦП обычно выполняет предварительную выборку инструкций по единственному вероятному пути выполнения, но оператор if, вызывающий переход от прогнозируемого пути выполнения, делает недействительными предварительно выбранные инструкции, и предварительное тестирование необходимо будет перезапустить.
activout.se
Любой достойный процессор должен иметь возможности предсказания ветвления, которые будут пытаться угадать, будет ли ветвление выполнено или нет, и инструкцию предварительной выборки на основе предсказания (что, как правило, неплохо). У GCC даже есть расширения C, которые позволяют программисту предоставлять подсказки для предсказателей ветвления.
mipadi
2
Более того, ЦП обычно заранее ожидает начала выполнения предстоящих инструкций (а не только их предварительной выборки), а компилятор пытается переупорядочить инструкции, и это становится опасным для разных ветвей, поэтому вы действительно можете убить планирование инструкций с помощью слишком большого количества ветвей. Что вредит производительности.
jalf
6

Также обратите внимание, что внутри цикла нет обязательно очень дорого.

Современный ЦП предполагает, что при первом обращении к if-заявлению должно быть взято "if-body" (или, наоборот, предполагается, что тело цикла будет взято несколько раз) (*). При втором и последующих посещениях он (ЦП) может, возможно, заглянуть в таблицу истории ветвей и увидеть, какое условие было в последний раз (было ли оно истинным? Было ли оно ложным?). Если в прошлый раз оно было ложным, то спекулятивное выполнение перейдет к "else" if или вне цикла.

(*) Правило на самом деле « прямая ветвь не выполняется , обратная ветвь выполняется ». В операторе if существует только переход [вперед] (к точке после тела if), если условие оценивается как ложное (помните: ЦП в любом случае предполагает, что не выполняет переход / переход), но в цикле , может быть прямая ветвь к позиции после цикла (не должна выполняться) и обратная ветвь при повторении (которая должна выполняться).

Это также одна из причин, почему вызов виртуальной функции или вызов указателя на функцию не настолько хуже, как многие предполагают ( http://phresnel.org/blog/ )

Себастьян Мах
источник
5

Как отмечают многие, условные переходы на современном компьютере могут выполняться очень медленно.

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

Дэвид Торнли
источник
4

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

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

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

Майкл Берр
источник
Я слышал, что условные инструкции ARM запрещают ILP, поэтому они, возможно, просто пытаются решить проблему.
JD
3

ЦП имеют глубокий конвейер. Любая инструкция ветвления (if / for / while / switch / etc) означает, что ЦП на самом деле не знает, какую инструкцию загрузить и запустить следующей.

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

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

Удачи в классе.

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

tfinniga
источник
2

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

фонбранд
источник
1

Некоторые процессоры (например, X86) обеспечивают прогнозирование ветвлений на уровне программирования, чтобы избежать такой задержки прогнозирования ветвлений.

Некоторые компиляторы предоставляют (например, GCC) их как расширение для языков программирования более высокого уровня (например, C / C ++).

Обратитесь к макросам вероятно () / маловероятно () в ядре Linux - как они работают? В чем их выгода? .

Арунпрасад Раджкумар
источник
0

Однажды у меня был этот спор с моим другом. Он использовал очень наивный алгоритм круга, но утверждал, что его быстрее, чем мой (тот, который вычисляет только 1/8 круга), потому что мой использовал if. В конце концов, оператор if был заменен на sqrt, и почему-то это было быстрее. Возможно, потому, что в FPU встроен sqrt?

Демур Румед
источник
-1

Самый дорогой с точки зрения использования ALU? Он использует регистры ЦП для хранения сравниваемых значений и требует времени на выборку и сравнение значений при каждом запуске оператора if.

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

Просто пытаюсь интерпретировать ваши пропущенные слова.


источник