Дорого ли стоит “ЕСЛИ”?

https://stackoverflow.com/questions/315306

10-07-2019
|

Вопрос

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

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

Тот Самый if утверждение - это самое дорогое [что-то].[что-то] регистрируется [что-то].

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

Решение

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

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

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

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

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

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

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



	
					
			
			


	
			


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

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


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


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

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

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


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


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


Расходы, связанные с этим:


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


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


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


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


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

    	


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

 Если  if  является злом, то  switch  также является злым, и  & amp; & amp; ,  ||  тоже. Не беспокойся об этом. 
	


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


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

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

 Pentium 4 (Prescott) имел знаменитый длинный конвейер из 31 ступени. 

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


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

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

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


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

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


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

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

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

Удачи в занятиях.

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


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

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

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

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


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


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


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

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

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


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

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

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

			
		
			


	
		
			Лицензировано под: CC-BY-SA с атрибуция
			Не связан с StackOverflow