¿Es “IF” caro?

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

El módulo es “Data Structures and Algorithms” y nos dijo algo como:

La statement if es la más cara [algo]. [algo] registra [algo].

Sí, tengo un recuerdo horrible y realmente lo siento, 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 son caros. Para entender por qué, debes entender cómo funcionan las tuberías .

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

Sin embargo, para las instrucciones de bifurcación , la próxima instrucción que se ejecutará no es la siguiente ubicación después de la instrucción actual. Las twigs son gotos: le dicen al procesador dónde está la próxima instrucción. Las twigs pueden ser condicional o incondicional, y la ubicación del objective puede ser fija o calculada.

Condicional vs. incondicional es fácil de entender: una twig condicional solo se toma si se cumple una determinada condición (por ejemplo, si un número es igual a otro); si no se toma la twig, el control pasa a la siguiente instrucción después de la twig como es normal. Para twigs incondicionales, la twig siempre se toma. Las twigs condicionales aparecen en las sentencias if y las pruebas de control de for y while loops. Las twigs incondicionales aparecen en bucles infinitos, llamadas a función, declaraciones de función, declaraciones break y continue , la infame sentencia goto y muchas más (estas listas no son exhaustivas).

El objective de la sucursal es otro tema importante. La mayoría de las sucursales tienen un objective de sucursal fijo: van a una ubicación específica en el código que se fija en el momento de la comstackción. Esto incluye sentencias if , bucles de todo tipo, llamadas a funciones regulares y muchas más. Las twigs calculadas calculan el objective de la twig en tiempo de ejecución. Esto incluye instrucciones de switch (a veces), regresar de una función, llamadas a funciones virtuales y llamadas a punteros a funciones.

Entonces, ¿qué significa todo esto para el rendimiento? Cuando el procesador ve una instrucción de bifurcación aparecer en su canalización, necesita averiguar cómo continuar para completar su canalización. Para descubrir qué instrucciones vienen después de la twig en el flujo del progtwig, necesita saber dos cosas: (1) si se tomará la twig y (2) el objective de la twig. Entender esto se llama predicción de ramificación , y es un problema desafiante. Si el procesador adivina correctamente, el progtwig continúa a toda velocidad. Si, en cambio, el procesador adivina incorrectamente , simplemente pasó algún tiempo computando lo incorrecto. Ahora debe vaciar su tubería y volver a cargarla con las instrucciones de la ruta de ejecución correcta. En pocas palabras: un gran golpe de rendimiento.

Por lo tanto, la razón por la cual 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 twigs a menudo puede ser superior al código que se ramifica, incluso si se necesitan varias instrucciones más. Hay algunos trucos geniales que puedes hacer para calcular cosas como abs() , min() y max() sin ramificar.

“Caro” es un término muy relativo, especialmente con relación a una afirmación ” if “, ya que también debe incluir en la cuenta el costo de la condición. Eso puede variar desde unas pocas instrucciones de CPU cortas 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 una progtwigción integrada, probablemente no debería preocuparse por el costo de ” if ” en absoluto. Para la mayoría de los progtwigdores, nunca va a ser el factor determinante en el rendimiento de su aplicación.

Las twigs, especialmente en los microprocesadores de architecture RISC, son algunas de las instrucciones más caras. Esto se debe a que en muchas architectures, el comstackdor predice qué ruta de ejecución se tomará con más 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 suceda la twig. Si la sucursal va en dirección opuesta, tiene que volver a la memoria principal y buscar las nuevas instrucciones, eso es bastante caro. En muchas architectures RISC, todas las instrucciones son de un ciclo, excepto para la bifurcación (que suele ser de 2 ciclos). No estamos hablando de un costo importante aquí, así que no te preocupes por eso. Además, el comstackdor optimizará mejor que usted el 99% del tiempo 🙂 Una de las cosas realmente asombrosas de la architecture EPIC (Itanium es un ejemplo) es que almacena en caché (y comienza a procesar) las instrucciones de ambos lados de la twig, luego descarta el conjunto que no necesita una vez que se conoce el resultado de la twig. Esto ahorra el acceso de memoria adicional de una architecture típica en el caso de que se ramifique a lo largo de la ruta imprevista.

Consulte el artículo Mejor rendimiento a través de la eliminación de sucursales en el rendimiento de la célula. Otra diversión es esta publicación sobre selecciones sin sucursales 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 recordar que aunque las afirmaciones “si” se consideran costosas operaciones de bajo nivel, intentan utilizar técnicas de progtwigción sin ramificación en un entorno de nivel superior. , como un lenguaje de scripting o una capa de lógica de negocios (independientemente del idioma), puede ser ridículamente inapropiado.

La gran mayoría de las veces, los progtwigs deben escribirse primero para mayor claridad y optimizados para el rendimiento en segundo lugar. Hay numerosos dominios problemáticos donde el rendimiento es primordial, pero el hecho es que la mayoría de los desarrolladores no están escribiendo módulos para utilizarlos 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 “funcione”, lo último que debe tener en cuenta es si puede guardar en la sobrecarga de una statement condicional en su código.

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

  • algunas instrucciones de prueba
  • salte a algún lugar en el código si la prueba tiene éxito, proceda de otra manera.

Costos asociados con eso:

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

Reson por qué los saltos son caros:

  • puede saltar al código arbirary que se encuentra 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 tienen predición de twig. Intentan adivinar si tendrán éxito o no y ejecutan el código por adelantado en la tubería, así que acelere las cosas. Si la predicción falla, todo cómputo hecho por tubería tiene que ser invalidado. Eso también es una operación costosa

Así que para resumir:

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

¿Tal vez la ramificación mata la captación previa de instrucciones de la CPU?

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

Lo veo como un largo tren de mercancías. Puede transportar una gran cantidad de carga rápida en línea recta, pero no rinde mucho.

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

Más en Wikipedia

if en sí mismo no es lento. La lentitud es siempre relativa. Apuesto por mi vida a que nunca has sentido el “overhead” de una statement de si. Si vas a hacer un código de alto rendimiento, puedes evitar las twigs de todos modos. Lo que hace que if lento es que el procesador está precargando el código después de if basado en alguna heurística y otras cosas. También impedirá que las tuberías ejecuten código directamente después de la instrucción de bifurcación en el código de la máquina, ya que el procesador aún no sabe qué camino tomará (en un procesador segmentado, múltiples instrucciones se entrelazan y se ejecutan). El código ejecutado podría tener que ejecutarse en reversa (si se tomó la otra twig, se llama branch misprediction noop branch misprediction ), o noop se llenará en esos lugares para que esto no suceda.

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

A lo único que me imagino que esto podría estar refiriéndose es al hecho de que una statement if generalmente puede dar como resultado una twig. Dependiendo de las características específicas de la architecture del procesador, las sucursales pueden causar paradas de tuberías u otras situaciones que no sean ó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 bifurcación que intentan minimizar los efectos negativos de la bifurcación. Otro ejemplo sería cómo la architecture ARM (y probablemente otros) 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 ramificación – las instrucciones simplemente se ejecutan como NOP si no se cumplen las condiciones.

Todo lo dicho: haz que tu lógica sea correcta antes de preocuparte por esto. El código incorrecto es tan desoptimizado como puede obtener.

Como lo señalaron muchos, las twigs condicionales pueden ser muy lentas en una computadora moderna.

Una vez dicho esto, hay muchas twigs condicionales que no viven en las sentencias if, no siempre se puede decir qué se producirá el comstackdor, y preocuparse por cuánto tiempo tomarán las declaraciones básicas es prácticamente siempre lo incorrecto. que hacer. (Si puede ver lo que el comstackdor generará de manera confiable, es posible que no tenga un buen comstackdor de optimización).

Las CPU están profundamente segmentadas. 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 anterior, o si la suposición es incorrecta, tendrá que sufrir un locking de línea mientras se descarga y cargar las instrucciones correctas. Dependiendo de la CPU esto puede ser tan alto como 10-20 instrucciones por valor de pérdida.

Las CPU modernas intentan evitar esto haciendo una buena predicción de bifurcación y ejecutando múltiples rutas al mismo tiempo, y solo manteniendo la real. Esto ayuda mucho, pero solo puede ir 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 caro.

La CPU moderna asume, en la primera visita de un enunciado if, que se debe tomar el “si-cuerpo” (o dicho de otra manera: también supone que un bucle-cuerpo debe tomarse varias veces) (*). Luego de una segunda visita y más visitas, (la CPU) puede buscar en la Tabla de historial de twigs y ver cómo fue la condición la última vez (¿era cierto? ¿Era falsa?). Si fue falsa la última vez, la ejecución especulativa procederá al “else” del if, o más allá del loop.

(*) La regla es en realidad ” twig adelante no tomada, twig hacia atrás tomada “. En un enunciado if, solo hay un salto [hacia adelante] (hacia el punto posterior al if-body ) si la condición se evalúa como falsa (recuerde: de todos modos, la CPU asume que no tomará una bifurcación / salto), sino en un bucle , tal vez haya una twig hacia adelante a la posición después del bucle (no se debe tomar), y una twig hacia atrás sobre la repetición (que se 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 grave como muchos suponen ( http://phresnel.org/blog/ )

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

Tuve esta discusión con un amigo mío una vez. Estaba usando un algoritmo de círculo muy ingenuo, pero afirmó que era más rápido que el mío (el tipo que solo calcula 1/8 del círculo) porque el mío lo usaba. 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 incorporado sqrt?

Algunas CPU (como X86) proporcionan predicción de bifurcación al nivel de progtwigción para evitar dicha latencia de predicción de bifurcación.

Algunos comstackdores exponen (como GCC) estos como una extensión a lenguajes de progtwigción de nivel superior (como C / C ++).

Refiera las macros likely () / unlikely () 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 los registros de la 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 tus palabras faltantes.

    Intereting Posts