Es & # 8220; IF & # 8221; ¿costoso?

https://stackoverflow.com/questions/315306

10-07-2019
|

Pregunta

No puedo, por mi vida, recordar exactamente lo que dijo nuestro maestro ese día y espero que probablemente lo sepas.

El módulo es "Estructuras de datos y algoritmos" y nos dijo algo como:

La declaración if es la más cara [alguna cosa]. [algo] se registra [algo].

Sí, tengo un recuerdo horrible y lo siento mucho, pero he estado buscando en Google durante horas y no ha aparecido nada. ¿Alguna idea?

Solución

En el nivel más bajo (en el hardware), sí, si s son caros. Para entender por qué, debe comprender cómo tuberías .

La instrucción actual que se ejecutará se almacena en algo típicamente llamado puntero de instrucción (IP) o contador de programa (PC); estos términos son sinónimos, pero se usan términos diferentes con arquitecturas diferentes. Para la mayoría de las instrucciones, la PC de la siguiente instrucción es solo la PC actual más la longitud de la instrucción actual. Para la mayoría de las arquitecturas RISC, las instrucciones tienen una longitud constante, por lo que la PC puede incrementarse en una cantidad constante. Para arquitecturas CISC como x86, las instrucciones pueden ser de longitud variable, por lo que la lógica que decodifica la instrucción tiene que determinar cuánto dura la instrucción actual para encontrar la ubicación de la siguiente instrucción.

Para las instrucciones branch , sin embargo, la siguiente instrucción a ejecutar no es la siguiente ubicación después de la instrucción actual. Las ramas son gotos: le dicen al procesador dónde está la próxima instrucción. Las ramas pueden ser condicionales o incondicionales, y la ubicación de destino puede ser fija o calculada.

Condicional vs. incondicional es fácil de entender: una rama condicional solo se toma si se cumple una determinada condición (como si un número es igual a otro); Si no se toma la rama, el control pasa a la siguiente instrucción después de la rama como de costumbre. Para ramas incondicionales, la rama siempre se toma. Las ramas condicionales se muestran en las declaraciones if y en las pruebas de control de for y while . Las ramas incondicionales se muestran en bucles infinitos, llamadas de función, retornos de función, declaraciones break y continue , la infame declaración goto y muchas más (estas las listas están lejos de ser exhaustivas).

El objetivo de la rama es otro tema importante. La mayoría de las sucursales tienen un objetivo de sucursal fijo: van a una ubicación específica en el código que se fija en el momento de la compilación. Esto incluye sentencias if , bucles de todo tipo, llamadas a funciones regulares y muchos más. Las ramas Computed calculan el objetivo de la rama en tiempo de ejecución. Esto incluye declaraciones switch (a veces), que regresan de una función, llamadas a funciones virtuales y llamadas a punteros de función.

Entonces, ¿qué significa todo esto para el rendimiento? Cuando el procesador ve aparecer una instrucción de bifurcación en su tubería, necesita descubrir cómo continuar llenando su tubería. Para descubrir qué instrucciones vienen después de la rama en la secuencia del programa, necesita saber dos cosas: (1) si se tomará la rama y (2) el objetivo de la rama. Resolver esto se llama predicción de rama , y es un problema difícil. Si el procesador adivina correctamente, el programa continúa a toda velocidad. Si, en cambio, el procesador adivina incorrectamente , solo pasó algún tiempo calculando lo incorrecto. Ahora tiene que vaciar su canalización y volver a cargarlo con instrucciones de la ruta de ejecución correcta. En pocas palabras: un gran éxito de rendimiento.

Por lo tanto, la razón por la cual las declaraciones son caras se debe a predicciones erróneas de las sucursales . Esto es solo en el nivel más bajo. Si está escribiendo código de alto nivel, no necesita preocuparse por estos detalles en absoluto. Solo debe preocuparse por esto si está escribiendo código extremadamente crítico para el rendimiento en C o ensamblado. Si ese es el caso, escribir código sin bifurcación a menudo puede ser superior al código que bifurca, incluso si se necesitan varias instrucciones más. Hay algunos trucos geniales que puedes hacer para calcular cosas como abs () , min () y



	
					
			
			


	
			


	
			
						 Otros consejos
			
			
	
		
	
	
			 " Caro " es un término muy relativo, especialmente con relación a un "  if  " declaración ya que también debe tener en cuenta el costo de la condición. Eso podría variar desde unas pocas instrucciones breves de la CPU hasta probar el resultado de una función que llama a una base de datos remota. 

 No me preocuparía por eso. A menos que esté haciendo programación incrustada, probablemente no debería preocuparse por el costo de "  if  " en absoluto. Para la mayoría de los programadores,  nunca  será el factor determinante en el rendimiento de su aplicación. 
	


	
		
	
	
			 Las ramas, especialmente en los microprocesadores de arquitectura RISC, son algunas de las instrucciones más caras. Esto se debe a que en muchas arquitecturas, el compilador predice qué ruta de ejecución se tomará con mayor probabilidad y coloca esas instrucciones a continuación en el ejecutable, por lo que ya estarán en la memoria caché de la CPU cuando ocurra la rama. Si la rama se va para otro lado, tiene que volver a la memoria principal y buscar las nuevas instrucciones, eso es bastante costoso. En muchas arquitecturas RISC, todas las instrucciones son de un ciclo, excepto la rama (que suele ser de 2 ciclos). No estamos hablando de un costo importante aquí, así que no te preocupes por eso. Además, el compilador se optimizará mejor que usted el 99% del tiempo :) Una de las cosas realmente asombrosas de la arquitectura EPIC (Itanium es un ejemplo) es que almacena en caché (y comienza a procesar) instrucciones de ambos lados de la rama, luego descarta el conjunto que no necesita una vez que se conoce el resultado de la rama. Esto ahorra el acceso adicional a la memoria de una arquitectura típica en caso de que se bifurque a lo largo de la ruta imprevista. 
	


	
		
	
	
			 Consulte el artículo  Mejor rendimiento a través de la eliminación de ramas  sobre el rendimiento de la célula . Otra divertida es  esta publicación sobre selecciones sin ramificación  en el Blog de detección de colisiones en tiempo real. 

 Además de las excelentes respuestas ya publicadas en respuesta a esta pregunta, me gustaría poner un recordatorio de que aunque "si" las declaraciones se consideran costosas operaciones de bajo nivel, tratar de utilizar técnicas de programación sin sucursales en un entorno de nivel superior, como un lenguaje de secuencias de comandos o una capa de lógica de negocios (independientemente del lenguaje), puede ser ridículamente inapropiado. 

 La gran mayoría de las veces, los programas deben escribirse para mayor claridad primero y optimizados para el rendimiento en segundo lugar. Existen numerosos dominios problemáticos donde el rendimiento es primordial, pero el hecho simple es que la mayoría de los desarrolladores no están escribiendo módulos para su uso en el núcleo de un motor de renderizado o una simulación de dinámica de fluidos de alto rendimiento que se ejecuta durante semanas. Cuando la máxima prioridad es que su solución "simplemente funcione" lo último que debe pensar es si puede ahorrar o no en la sobrecarga de una declaración condicional en su código. 
	


	
		
	
	
			 En el nivel más bajo posible,  if  consiste en (después de calcular todos los requisitos previos específicos de la aplicación para  if  en particular): 


 algunas instrucciones de prueba 
 salte a algún lugar en el código si la prueba tiene éxito, de lo contrario, avance. 


 Costos asociados con eso: 


 una comparación de bajo nivel - generalmente 1 operación de CPU, super barata 
 salto potencial, que puede ser costoso 


 Reson por qué los saltos son caros: 


 puede saltar al código de arbirary que vive en cualquier lugar de la memoria, si resulta que la CPU no lo almacena en caché; tenemos un problema, porque necesitamos acceder a la memoria principal, que es más lenta 
 CPU modernas hacen predición de ramificación. Intentan adivinar si tendrá éxito o no y ejecutan el código por delante en la tubería, así que aceleren las cosas. Si la predicción falla, todos los cálculos realizados por tubería deben ser invalidados. Esa también es una operación costosa 


 Entonces, para resumir: 


 Si puede ser costoso, si realmente te importa el rendimiento. 
 Deberías preocuparte  si y solo si  estás escribiendo raytracer en tiempo real o simulación biológica o algo similar. No hay razón para preocuparse por eso en la mayoría del mundo real. 
	


	
		
	
	
			  if  en sí mismo es  no  lento. La lentitud siempre es relativa, apuesto por mi vida a que nunca has sentido la `` sobrecarga '' de una declaración if. Si va a crear un código de alto rendimiento, es posible que desee evitar las ramas de todos modos. Lo que hace que  if  sea lento es que el procesador está precargando el código después del  if  basado en alguna heurística y demás. También evitará que las tuberías ejecuten código directamente después de la instrucción de bifurcación  if  en el código de la máquina, ya que el procesador aún no sabe qué ruta se tomará (en un procesador interconectado, se intercalan varias instrucciones y ejecutado). El código ejecutado podría tener que ejecutarse en reversa (si se tomó la otra rama. Se llama  branch misprediction ), o  noop  se debe llenar en esos lugares para que esto no no suceda. 

 Si  if  es malo, entonces  switch  también es malo, y  & amp; & amp; ,  ||  también. No te preocupes por eso. 
	


	
		
	
	
			 ¿Quizás la ramificación mata la captación previa de instrucciones de la CPU? 
	


	
		
	
	
			 Los procesadores modernos tienen canales de ejecución largos, lo que significa que se ejecutan varias instrucciones en varias etapas al mismo tiempo. Es posible que no siempre conozcan el resultado de una instrucción cuando la siguiente comience a ejecutarse. Cuando se topan con un salto condicional (si) a veces tienen que esperar hasta que la tubería esté vacía antes de que puedan saber en qué dirección debe ir el puntero de instrucción. 

 Pienso en ello como un largo tren de carga. Puede transportar una gran cantidad de carga rápidamente en línea recta, pero se dobla mal. 

 Pentium 4 (Prescott) tenía una tubería largamente famosa de 31 etapas. 

 Más sobre  Wikipedia  
	


	
		
	
	
			 La única cosa a la que me imagino que esto podría estar refiriéndose es el hecho de que una declaración  if  generalmente puede resultar en una rama. Dependiendo de los detalles de la arquitectura del procesador, las ramas pueden causar paradas de tubería u otras situaciones menos que óptimas. 

 Sin embargo, esto es extremadamente específico de la situación: la mayoría de los procesadores modernos tienen capacidades de predicción de ramificación que intentan minimizar los efectos negativos de la ramificación. Otro ejemplo sería cómo la arquitectura ARM (y probablemente otras) puede manejar la lógica condicional: el ARM tiene ejecución condicional de nivel de instrucción, por lo que la lógica condicional simple no genera ramificaciones; las instrucciones simplemente se ejecutan como NOP si no se cumplen las condiciones. 

 Todo lo dicho: acerta tu lógica antes de preocuparte por estas cosas. El código incorrecto es tan poco optimizado como puede obtener. 
	


	
		
	
	
			 Como señalan muchos, las ramas condicionales pueden ser muy lentas en una computadora moderna. 

 Dicho esto, hay una gran cantidad de ramas condicionales que no viven en las declaraciones if, no siempre se puede saber qué inventará el compilador, y preocuparse por cuánto tiempo tomarán las declaraciones básicas es casi siempre Lo incorrecto que hacer. (Si puede saber qué generará el compilador de manera confiable, es posible que no tenga un buen compilador de optimización). 
	


	
		
	
	
			 Las CPU están profundamente canalizadas. Cualquier instrucción de bifurcación (if / for / while / switch / etc) significa que la CPU realmente no sabe qué instrucción cargar y ejecutar a continuación. 

 La CPU se detiene mientras espera saber qué hacer o la CPU adivina. En el caso de una CPU más antigua, o si la suposición es incorrecta, tendrá que sufrir un bloqueo de la tubería mientras se carga y carga la instrucción correcta. Dependiendo de la CPU, esto puede ser tan alto como 10-20 instrucciones de bloqueo. 

 Las CPU modernas intentan evitar esto haciendo una buena predicción de rama y ejecutando múltiples rutas al mismo tiempo, y solo manteniendo la actual. Esto ayuda mucho, pero solo puede llegar tan lejos. 

 Buena suerte en la clase. 

 Además, si tiene que preocuparse por esto en la vida real, probablemente esté haciendo diseño de sistema operativo, gráficos en tiempo real, computación científica o algo similar relacionado con la CPU. Perfil antes de preocuparse. 
	


	
		
	
	
			 También tenga en cuenta que dentro de un bucle  no  es necesariamente muy costoso. 

 La CPU moderna asume en la primera visita de una instrucción if, que el "cuerpo if" debe tomarse (o dicho de otra manera: también supone que se tomará un cuerpo de bucle varias veces) (*). En una segunda y más visitas, (la CPU) puede ver la  Tabla de historial de sucursales  y ver cómo fue la última vez (¿fue cierto? ¿Fue falso?). Si fue falsa la última vez, entonces la ejecución especulativa procederá al '' else '' del if, o más allá del ciclo. 

 (*) La regla es en realidad "  rama hacia adelante no tomada, rama hacia atrás tomada  " ;. En una declaración if, hay  solo  un salto [hacia adelante] (al punto  después del if-body ) si la condición se evalúa como falsa (recuerde: la CPU de todos modos supone no tomar una rama / salto), pero en un bucle, tal vez haya una rama hacia adelante a la posición después del bucle (no se tomará), y una rama hacia atrás al repetirse (se tomará). 

 Esta es también una de las razones por las cuales una llamada a una función virtual o una función-puntero-llamada no es tan grave como muchos suponen ( http://phresnel.org/blog/ ) 
	


	
		
	
	
			 Escriba sus programas de la manera más clara, simple y limpia que obviamente no sea ineficiente. Eso hace el mejor uso del recurso más caro, usted. Ya sea escribiendo o depurando posteriormente (requiere comprensión) el programa. Si el rendimiento no es suficiente,  medir  dónde están los cuellos de botella y vea cómo mitigarlos. Solo en ocasiones extremadamente raras tendrá que preocuparse por las instrucciones individuales (fuente) al hacerlo. El rendimiento consiste en seleccionar los algoritmos y las estructuras de datos correctos en la primera línea, una programación cuidadosa y obtener una máquina lo suficientemente rápida. Use un buen compilador, se sorprendería al ver el tipo de reestructuración de código que hace un compilador moderno. La reestructuración del código para el rendimiento es una especie de medida de último recurso, el código se vuelve más complejo (por lo tanto, más problemático), más difícil de modificar y, por lo tanto, más costoso. 
	


	
		
	
	
			 Una vez tuve esta discusión con un amigo mío. Estaba usando un algoritmo de círculo muy ingenuo, pero afirmó que era más rápido que el mío (del tipo que solo calcula 1/8 del círculo) porque el mío lo usaba si. Al final, la instrucción if fue reemplazada por sqrt y de alguna manera eso fue más rápido. ¿Quizás porque la FPU tiene sqrt incorporado? 
	


	
		
	
	
			 Algunas CPU (como X86) proporcionan predicción de rama a nivel de programación para evitar dicha latencia de predicción de rama. 

 Algunos compiladores los exponen (como GCC) como una extensión a lenguajes de programación de nivel superior (como C / C ++). 

 Consulte  macros probables () / improbables () en el kernel de Linux - cómo ¿funcionan? ¿Cuál es su beneficio? . 
	


	
		
	
	
			 ¿El más caro en términos de uso de ALU? Utiliza registros de CPU para almacenar los valores que se van a comparar y toma tiempo para buscar y comparar los valores cada vez que se ejecuta la instrucción if. 

 Por lo tanto, una optimización de eso es hacer una comparación y almacenar el resultado como una variable antes de ejecutar el ciclo. 

 Solo trato de interpretar las palabras que faltan. 
	

			
		
			


	
		
			Licenciado bajo: CC-BY-SA con atribución
			No afiliado a StackOverflow