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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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