Es <más rápido que <=?

Estoy leyendo un libro donde el autor dice que if( a < 901 ) es más rápido que if( a <= 900 ) .

No exactamente como en este ejemplo simple, pero hay ligeros cambios de rendimiento en el código complejo de bucle. Supongo que esto tiene que ver con el código de máquina generado en caso de que sea cierto.

No, no será más rápido en la mayoría de las architectures. No especificó, pero en x86, todas las comparaciones integrales se implementarán típicamente en dos instrucciones de máquina:

  • Una instrucción de test o cmp , que establece EFLAGS
  • Y una Jcc (salto) , según el tipo de comparación (y el diseño del código):
    • jne – Saltar si no es igual -> ZF = 0
    • jz – Salta si es cero (igual) -> ZF = 1
    • jg – Salta si es mayor -> ZF = 0 and SF = OF
    • (etc …)

Ejemplo (Editado por brevedad) Comstackdo con $ gcc -m32 -S -masm=intel test.c

  if (a < b) { // Do something 1 } 

Comstack para:

  mov eax, DWORD PTR [esp+24] ; a cmp eax, DWORD PTR [esp+28] ; b jge .L2 ; jump if a is >= b ; Do something 1 .L2: 

Y

  if (a < = b) { // Do something 2 } 

Comstack para:

  mov eax, DWORD PTR [esp+24] ; a cmp eax, DWORD PTR [esp+28] ; b jg .L5 ; jump if a is > b ; Do something 2 .L5: 

Entonces la única diferencia entre los dos es una instrucción jg versus una instrucción jge . Los dos tomarán la misma cantidad de tiempo.


Me gustaría comentar el comentario de que nada indica que las diferentes instrucciones de salto tomen la misma cantidad de tiempo. Este es un poco difícil de responder, pero esto es lo que puedo dar: en Intel Instruction Set Reference , todos están agrupados bajo una instrucción común, Jcc (Saltar si se cumple la condición). La misma agrupación se realiza en conjunto en el Manual de referencia de optimización , en el Apéndice C. Latencia y rendimiento.

Latencia : la cantidad de ciclos de reloj necesarios para que el núcleo de ejecución complete la ejecución de todos los μops que forman una instrucción.

Rendimiento : el número de ciclos de reloj requeridos para esperar antes de que los puertos de emisión sean libres de aceptar la misma instrucción nuevamente. Para muchas instrucciones, el rendimiento de una instrucción puede ser significativamente menor que su latencia

Los valores para Jcc son:

  Latency Throughput Jcc N/A 0.5 

con la siguiente nota al pie en Jcc :

7) La selección de instrucciones de salto condicional se debe basar en la recomendación de la sección Sección 3.4.1, "Optimización de predicción de bifurcación", para mejorar la predictibilidad de las bifurcaciones. Cuando las twigs se predicen con éxito, la latencia de jcc es efectivamente cero.

Por lo tanto, nada en los documentos de Intel trata alguna vez una instrucción Jcc diferente a las demás.

Si uno piensa en los circuitos reales utilizados para implementar las instrucciones, se puede suponer que habría puertas Y / O simples en los diferentes bits en EFLAGS , para determinar si se cumplen las condiciones. Entonces, no hay razón para que una instrucción que prueba dos bits deba tomar más o menos tiempo que una prueba solo una (ignorando el retardo de propagación de la puerta, que es mucho menor que el período del reloj).


Editar: punto flotante

Esto también es cierto para el punto flotante x87: (Casi el mismo código que el anterior, pero con el double lugar de int ).

  fld QWORD PTR [esp+32] fld QWORD PTR [esp+40] fucomip st, st(1) ; Compare ST(0) and ST(1), and set CF, PF, ZF in EFLAGS fstp st(0) seta al ; Set al if above (CF=0 and ZF=0). test al, al je .L2 ; Do something 1 .L2: fld QWORD PTR [esp+32] fld QWORD PTR [esp+40] fucomip st, st(1) ; (same thing as above) fstp st(0) setae al ; Set al if above or equal (CF=0). test al, al je .L5 ; Do something 2 .L5: leave ret 

Históricamente (estamos hablando de la década de 1980 y principios de la década de 1990), había algunas architectures en las que esto era cierto. La raíz del problema es que la comparación entera se implementa inherentemente a través de restas enteras. Esto da lugar a los siguientes casos.

 Comparison Subtraction ---------- ----------- A < B --> A - B < 0 A = B --> A - B = 0 A > B --> A - B > 0 

Ahora bien, cuando A < B la resta tiene que pedir prestado un bit alto para que la resta sea correcta, igual que llevas y pides al agregar y restar con la mano. Este bit "prestado" generalmente se denominaba bit de acarreo y podría ser comprobado por una instrucción de bifurcación. Se establecería un segundo bit llamado bit cero si la resta fuera idénticamente cero, lo que implicaba igualdad.

Habitualmente había al menos dos instrucciones de bifurcación condicional, una para bifurcar en el bit de acarreo y otra en el bit cero.

Ahora, para llegar al meollo de la cuestión, expandamos la tabla anterior para incluir los resultados de acarreo y cero bits.

 Comparison Subtraction Carry Bit Zero Bit ---------- ----------- --------- -------- A < B --> A - B < 0 0 0 A = B --> A - B = 0 1 1 A > B --> A - B > 0 1 0 

Por lo tanto, implementar una twig para A < B se puede hacer en una instrucción, porque el bit de acarreo es claro solo en este caso, es decir,

 ;; Implementation of "if (A < B) goto address;" cmp A, B ;; compare A to B bcz address ;; Branch if Carry is Zero to the new address 

Pero, si queremos hacer una comparación menor o igual, tenemos que hacer una verificación adicional de la bandera cero para capturar el caso de igualdad.

 ;; Implementation of "if (A < = B) goto address;" cmp A, B ;; compare A to B bcz address ;; branch if A < B bzs address ;; also, Branch if the Zero bit is Set 

Entonces, en algunas máquinas, usar una comparación "menor que" podría salvar una instrucción de máquina . Esto fue relevante en la era de la velocidad del procesador sub-megahertz y las relaciones de velocidad de la CPU a la memoria de 1: 1, pero hoy es casi totalmente irrelevante.

Suponiendo que estamos hablando de tipos enteros internos, no hay forma posible de que uno sea más rápido que el otro. Obviamente son semánticamente idénticos. Ambos le piden al comstackdor que haga exactamente lo mismo. Solo un comstackdor horriblemente roto generaría un código inferior para uno de estos.

Si hubiera alguna plataforma donde < fuera más rápido que < = para tipos enteros simples, el comstackdor siempre debería convertir < = a < para las constantes. Cualquier comstackdor que no fuera solo sería un comstackdor incorrecto (para esa plataforma).

Veo que ninguno es más rápido. El comstackdor genera el mismo código de máquina en cada condición con un valor diferente.

 if(a < 901) cmpl $900, -4(%rbp) jg .L2 if(a <=901) cmpl $901, -4(%rbp) jg .L3 

Mi ejemplo es de GCC en la plataforma x86_64 en Linux.

Los escritores de comstackción son personas bastante inteligentes, y piensan en estas cosas y en muchas otras que la mayoría de nosotros damos por sentadas.

Noté que si no es una constante, entonces se genera el mismo código de máquina en cualquier caso.

 int b; if(a < b) cmpl -4(%rbp), %eax jge .L2 if(a <=b) cmpl -4(%rbp), %eax jg .L3 

Para el código de coma flotante, la comparación < = puede de hecho ser más lenta (con una instrucción) incluso en arquitecturas modernas. Aquí está la primera función:

 int compare_strict(double a, double b) { return a < b; } 

En PowerPC, primero realiza una comparación de punto flotante (que actualiza cr , el registro de condición), luego mueve el registro de condición a un GPR, desplaza el bit "comparado menos que" a su lugar, y luego regresa. Toma cuatro instrucciones.

Ahora considere esta función en su lugar:

 int compare_loose(double a, double b) { return a < = b; } 

Esto requiere el mismo trabajo que compare_strict anterior, pero ahora hay dos bits de interés: "era menor que" y "era igual a". Esto requiere una instrucción adicional ( cror condición de cror O) para combinar estos dos bits en uno. Entonces compare_loose requiere cinco instrucciones, mientras que compare_strict requiere cuatro.

Podría pensar que el comstackdor podría optimizar la segunda función de esta manera:

 int compare_loose(double a, double b) { return ! (a > b); } 

Sin embargo, esto manejará incorrectamente los NaN. NaN1 < = NaN2 y NaN1 > NaN2 necesitan ambos evaluar a falso.

Tal vez el autor de ese libro sin nombre haya leído que a > 0 corre más rápido que a >= 1 y piensa que eso es verdad universalmente.

Pero es porque un 0 está involucrado (porque CMP puede, según la architecture, reemplazarse, por ejemplo, con OR ) y no a causa de < .

Por lo menos, si esto fuera cierto, un comstackdor podría optimizar trivialmente a < = b to! (A> b), por lo que incluso si la comparación en sí fuera más lenta, con todos menos el comstackdor más ingenuo, no notaría la diferencia .

Ellos tienen la misma velocidad. Tal vez en alguna architecture especial, lo que él dijo es correcto, pero en la familia x86, al menos, sé que son lo mismo. Porque para hacer esto, la CPU hará una resta (a – b) y luego comprobará los indicadores del registro de banderas. Dos bits de ese registro se llaman ZF (bandera cero) y SF (bandera de señal), y se realiza en un ciclo, porque lo hará con una operación de máscara.

Esto dependería en gran medida de la architecture subyacente a la que se comstack el C. Algunos procesadores y architectures pueden tener instrucciones explícitas para igual a, o menor que e igual a, que se ejecutan en diferentes números de ciclos.

Sin embargo, eso sería bastante inusual, ya que el comstackdor podría evitarlo, haciéndolo irrelevante.

Otras respuestas se han concentrado en la architecture x86 , y no sé la architecture ARM (que su ensamblador de ejemplo parece ser) lo suficientemente buena como para comentar específicamente el código generado, pero este es un ejemplo de una micro-optimización que es muy arquitectónica específico, y es tan probable que sea una anti-optimización como una optimización .

Como tal, sugeriría que este tipo de micro-optimización es un ejemplo de progtwigción de culto de carga en lugar de la mejor práctica de ingeniería de software.

Probablemente haya algunas architectures donde se trata de una optimización, pero conozco al menos una architecture en la que puede ser todo lo contrario. La venerable architecture de Transputer solo tenía instrucciones de código de máquina para igual o mayor que o igual a , por lo que todas las comparaciones tuvieron que construirse a partir de estas primitivas.

Incluso entonces, en casi todos los casos, el comstackdor podía ordenar las instrucciones de evaluación de tal manera que, en la práctica, ninguna comparación tenía ninguna ventaja sobre ninguna otra. En el peor de los casos, podría necesitar agregar una instrucción inversa (REV) para intercambiar los dos elementos principales en la stack de operandos . Esta fue una instrucción de un solo byte que tomó un solo ciclo para ejecutarse, por lo que tuvo la menor sobrecarga posible.

Si una micro-optimización como esta es una optimización o una anti-optimización depende de la architecture específica que esté usando, por lo que generalmente es una mala idea adquirir el hábito de usar micro-optimizaciones específicas de la architecture, de lo contrario, podría instintivamente use uno cuando no sea apropiado, y parece que esto es exactamente lo que defiende el libro que está leyendo.

No debería ser capaz de notar la diferencia, incluso si hay alguna. Además, en la práctica, tendrás que hacer un a + 1 o a - 1 adicional para hacer que la condición se mantenga a menos que uses algunas constantes mágicas, lo cual es una práctica muy mala por todos los medios.

Se podría decir que la línea es correcta en la mayoría de los lenguajes de scripting, ya que el carácter adicional resulta en un procesamiento de código ligeramente más lento. Sin embargo, como señaló la respuesta principal, no debería tener ningún efecto en C ++, y cualquier cosa que se haga con un lenguaje de scripting probablemente no esté tan preocupado por la optimización.

En realidad, tendrán exactamente la misma velocidad, porque en el nivel de ensamblaje ambos toman una línea. Como:

  • jl ax,dx (salta si AX es menor que DX)
  • jle ax,dx (salta si AX es menor o igual a DX)

Entonces, no, ninguno es más rápido. Pero si quieres ser realmente técnico, creo que si lo compruebas en un nivel de stream de electrones, sería un poco más rápido, pero no cerca de la velocidad que notarías.