"ЕСЛИ" дорого?

Question

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

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

Оператор if самый дорогой [что-то]. [что-то] регистрируется [Что-то].

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

Answer 1

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

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

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

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

Answer 2

ЦП глубоко конвейерны. Любая инструкция ветвления (если / для / while / switch / и т. Д.) Означает, что ЦП действительно не знает, какую инструкцию загрузить и выполнить дальше.

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

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

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

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