¿Es "SI" caro?

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

El módulo es "Estructuras de datos y algoritmos" y nos dijo algo en la línea de:

La ifdeclaración es el [algo] más caro. [algo] registra [algo].

Sí, tengo una memoria horrible y realmente lo siento mucho, pero he estado buscando en Google durante horas y no ha surgido nada. ¿Algunas ideas?

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

La instrucción actual que se va a ejecutar se almacena en algo que normalmente se denomina puntero de instrucción (IP) o contador de programa (PC); estos términos son sinónimos, pero se utilizan 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 se puede incrementar 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 tiempo es la instrucción actual para encontrar la ubicación de la siguiente instrucción.

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

Condicional versus 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 las ramas incondicionales, la rama siempre se toma. Las ramas condicionales aparecen en ifdeclaraciones y las pruebas de control de fory whilebucles. Las ramas incondicionales aparecen en ciclos infinitos, llamadas a funciones, retornos de funciones breaky continuedeclaraciones, la gotodeclaración infame y muchas más (estas listas están lejos de ser exhaustivas).

El objetivo de la sucursal es otro tema importante. La mayoría de las sucursales tienen un destino 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 ifdeclaraciones, bucles de todo tipo, llamadas a funciones regulares y muchos más. Las ramas calculadas calculan el destino de la rama en tiempo de ejecución. Esto incluye switchdeclaraciones (a veces), retorno de una función, llamadas de función virtual y llamadas de puntero de función.

Entonces, ¿qué significa todo esto para el rendimiento? Cuando el procesador ve aparecer una instrucción de bifurcación en su canalización, necesita averiguar cómo continuar llenando su canalización. Para averiguar 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 destino de la rama. Descubrir esto se llama predicción de rama y es un problema desafiante. Si el procesador adivina correctamente, el programa continúa a toda velocidad. Si, en cambio, el procesador adivina incorrectamente , simplemente pasó un tiempo calculando lo incorrecto. Ahora tiene que vaciar su tubería y volver a cargarla 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 que las declaraciones son caras se debe a errores de predicción 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 debería 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 ramificaciones a menudo puede ser superior al código que se ramifica, incluso si se necesitan varias instrucciones más. Hay algunos trucos de bits haciendo girar los que puede hacer para calcular cosas tales como abs(), min()y max()sin ramificación.

"Caro" es un término muy relativo, especialmente en relación con una ifdeclaración " ", ya que también debe tener en cuenta el costo de la afecció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.

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

Las ramificaciones, especialmente en 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 el caché de la CPU cuando ocurra la rama. Si la rama va en sentido contrario, tiene que volver a la memoria principal y buscar las nuevas instrucciones; eso es bastante caro. 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 se preocupe. Además, el compilador optimizará mejor que tú 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 el resultado de la rama es conocido. Esto ahorra el acceso a memoria adicional de una arquitectura típica en caso de que se bifurque a lo largo de la ruta imprevista.

Consulte el artículo Mejor rendimiento mediante la eliminación de ramificaciones sobre el rendimiento celular. Otra divertida es esta publicación sobre selecciones sin ramas en el Blog de detección de colisiones en tiempo real.

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

La gran mayoría de las veces, los programas deben escribirse primero para mayor claridad y luego optimizados para el rendimiento. Existen numerosos dominios problemáticos en los que 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 o no ahorrar en la sobrecarga de una declaración condicional en su código.

ifen sí mismo no es lento. La lentitud siempre es relativa. Apuesto por mi vida a que nunca has sentido la "sobrecarga" de una afirmación si. Si va a crear un código de alto rendimiento, es posible que desee evitar las ramas de todos modos. Lo que lo hace iflento es que el procesador está precargando el código posterior al ifbasado en alguna heurística y otras cosas. También impedirá que las canalizaciones ejecuten código directamente después de la ifinstrucción de bifurcación en el código de máquina, ya que el procesador aún no sabe qué ruta se tomará (en un procesador canalizado, se intercalan y ejecutan varias instrucciones). El código ejecutado podría tener que ejecutarse a la inversa (si se tomó la otra rama, se llama branch misprediction), o se noopdebe completar en esos lugares para que esto no suceda.

Si ifes malo, entonces switches malo también, y &&, ||también. No se preocupe por eso.

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

• alguna instrucción de prueba
• salte a algún lugar en el código si la prueba tiene éxito, continúe hacia adelante de lo contrario.

Costos asociados con eso:

• una comparación de bajo nivel: generalmente una operación de 1 CPU, súper barata
• salto potencial, que puede ser caro

Reson por qué los saltos son caros:

• puede saltar al código arbitrario 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
• las CPU modernas hacen la predición de bifurcaciones. Intentan adivinar si tendrá éxito o no y ejecutan el código por adelantado, así que acelere las cosas. Si la predicción falla, todos los cálculos realizados con anticipación por la tubería deben invalidarse. Eso también es una operación cara

Así que para resumir:

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

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

Pienso en ello como un largo tren de mercancías. Puede transportar una gran cantidad de carga rápidamente en línea recta, pero tiene malas curvas.

Pentium 4 (Prescott) tenía un pipeline famoso de 31 etapas.

Más en Wikipedia

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

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

La CPU moderna asume en la primera visita de una instrucción if, que el "if-body" debe tomarse (o dicho de otra manera: también asume que un loop-body debe tomarse varias veces) (*). En la segunda y posterior visita, (la CPU) tal vez pueda mirar en la Tabla de historial de sucursales y ver cómo fue la condición la última vez (¿era verdadera? ¿Era falsa?). Si fue falso 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 instrucción if, solo hay un salto [hacia adelante] (hasta el punto después del cuerpo if) si la condición se evalúa como falsa (recuerde: la CPU de todos modos asume que no tomará una bifurcación / salto), pero en un bucle , puede haber una rama hacia adelante a la posición después del bucle (no se debe tomar) y una rama hacia atrás al repetir (se debe tomar).

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

Como muchos señalaron, 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é se le ocurrirá al compilador, y preocuparse por cuánto tiempo tomarán las declaraciones básicas es prácticamente 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).

Lo único a lo que puedo imaginar que esto podría estar refiriéndose es al hecho de que una ifdeclaración generalmente puede resultar en una rama. Dependiendo de las características específicas de la arquitectura del procesador, las ramas pueden provocar bloqueos en la 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 ramificaciones 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 a 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.

Dicho todo esto, obtenga su lógica correcta antes de preocuparse por estas cosas. El código incorrecto es lo menos optimizado posible.

Las CPU están profundamente canalizadas. Cualquier instrucción de bifurcación (if / for / while / switch / etc) significa que la CPU no sabe realmente 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 carga la instrucción correcta. Dependiendo de la CPU, esto puede ser tan alto como 10-20 instrucciones por valor de bloqueo.

Las CPU modernas intentan evitar esto haciendo una buena predicción de ramas y ejecutando múltiples rutas al mismo tiempo, y solo manteniendo la real. Esto ayuda mucho, pero solo puede llegar hasta cierto punto.

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.

Escriba sus programas de la manera más clara, simple y limpia que no sea obviamente ineficiente. Eso hace el mejor uso del recurso más caro, usted. Ya sea escribiendo o depurando posteriormente (requiere comprensión) del programa. Si el rendimiento no es suficiente, midadónde están los cuellos de botella y ver cómo mitigarlos. Solo en ocasiones extremadamente raras tendrá que preocuparse por las instrucciones individuales (fuente) al hacerlo. El rendimiento se trata de seleccionar los algoritmos y estructuras de datos correctos en la primera línea, una programación cuidadosa y obtener una máquina lo suficientemente rápida. Utilice 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 defectuoso), más difícil de modificar y, por lo tanto, más caro.

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

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

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

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

¿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 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 que se ejecute el ciclo.

Solo intento interpretar las palabras que faltan.