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

1574

Es if( a < 901 )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.

snoopy
fuente
153
No veo ninguna razón por la cual esta pregunta deba cerrarse (y especialmente no eliminarse, como muestran actualmente los votos) dada su importancia histórica, la calidad de la respuesta y el hecho de que las otras preguntas principales en el desempeño permanecen abiertas. A lo sumo debe estar bloqueado. Además, incluso si la pregunta en sí misma está mal informada / ingenua, el hecho de que apareció en un libro significa que la información errónea original existe en fuentes "creíbles" en algún lugar, y esta pregunta es, por lo tanto, constructiva, ya que ayuda a aclarar eso.
Jason C
32
Nunca nos dijiste a qué libro te refieres.
Jonathon Reinhart
160
Escribir <es dos veces más rápido que escribir <=.
Deqing
66
Era cierto en el 8086.
Joshua
77
El número de votos positivos muestra claramente que hay cientos de personas que optimizan demasiado.
m93a

Respuestas:

1704

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

  • A testo cmpinstrucción, que estableceEFLAGS
  • Y una Jccinstrucción (salto) , según el tipo de comparación (y el diseño del código):
    • jne - Salta si no es igual -> ZF = 0
    • jz - Saltar si cero (igual) -> ZF = 1
    • jg - Salta si es mayor -> ZF = 0 and SF = OF
    • (etc ...)

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

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

Compila a:

    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
    }

Compila a:

    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 jguna jgeinstrucción versus una . Los dos tomarán la misma cantidad de tiempo.


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

Latencia : el número 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 : la cantidad de ciclos de reloj necesarios para esperar antes de que los puertos de emisión puedan volver a aceptar la misma instrucción. Para muchas instrucciones, el rendimiento de una instrucción puede ser significativamente menor que su latencia

Los valores para Jccson:

      Latency   Throughput
Jcc     N/A        0.5

con la siguiente nota al pie sobre Jcc:

7) La selección de instrucciones de salto condicional debe basarse en la recomendación de la sección Sección 3.4.1, “Optimización de predicción de rama”, para mejorar la previsibilidad de las ramas. Cuando las ramas se predicen con éxito, la latencia de jcces efectivamente cero.

Por lo tanto, nada en los documentos de Intel trata una Jccinstrucción de manera diferente a las demás.

Si se piensa en la circuitería real utilizada para implementar las instrucciones, se puede suponer que habría puertas AND / OR simples en los diferentes bits EFLAGSpara determinar si se cumplen las condiciones. Entonces, no hay razón para que una instrucción que prueba dos bits tome más o menos tiempo que una que prueba solo uno (Ignorando el retraso de propagación de la puerta, que es mucho menor que el período del reloj).


Editar: Punto flotante

Esto también es válido para el punto flotante x87: (Más o menos el mismo código que el anterior, pero con en doublelugar 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
Jonathon Reinhart
fuente
239
@Dyppl en realidad jgy jnleson la misma instrucción, 7F:-)
Jonathon Reinhart
17
Sin mencionar que el optimizador puede modificar el código si de hecho una opción es más rápida que la otra.
Elazar Leibovich
3
el hecho de que algo dé como resultado la misma cantidad de instrucciones no significa necesariamente que el tiempo total de ejecución de todas esas instrucciones sea el mismo. En realidad, más instrucciones podrían ejecutarse más rápido. Las instrucciones por ciclo no son un número fijo, varían según las instrucciones.
jontejj
22
@jontejj Soy muy consciente de eso. ¿Incluso leíste mi respuesta? No dije nada sobre el mismo número de instrucciones, dije que están compiladas esencialmente con las mismas instrucciones , excepto que una instrucción de salto está mirando una bandera, y la otra instrucción de salto está mirando dos banderas. Creo que he aportado pruebas más que adecuadas para demostrar que son semánticamente idénticas.
Jonathon Reinhart
2
@jontejj Haces un muy buen punto. Para obtener tanta visibilidad como esta respuesta, probablemente debería darle un poco de limpieza. Gracias por la respuesta.
Jonathon Reinhart
593

Históricamente (estamos hablando de la década de 1980 y principios de 1990), hubo algunas arquitecturas en las que esto era cierto. El problema raíz es que la comparación de enteros se implementa inherentemente a través de sustracciones de enteros. 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, cuando A < Bla resta tiene que pedir prestado un bit alto para que la resta sea correcta, al igual que llevas y pides prestado al sumar y restar a mano. Este bit "prestado" generalmente se denominaba bit de acarreo y sería comprobable mediante una instrucción de bifurcación. Un segundo bit llamado bit cero se establecería si la resta fuera idénticamente cero, lo que implicaba igualdad.

Por lo general, había al menos dos instrucciones de bifurcación condicionales, una para bifurcar en el bit de acarreo y otra en el bit cero.

Ahora, para llegar al meollo del asunto, 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, la implementación de una rama para A < Bse 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, necesitamos hacer una verificación adicional de la bandera de cero para detectar el caso de la 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, el uso de una comparación "menor que" podría ahorrar una instrucción de máquina . Esto fue relevante en la era de la velocidad del procesador por debajo de los megahercios y las relaciones de velocidad de CPU a memoria 1: 1, pero hoy en día es casi totalmente irrelevante.

Lucas
fuente
10
Además, arquitecturas como x86 implementan instrucciones como jge, que prueban tanto el cero como las banderas de signo / acarreo.
greyfade
3
Incluso si es cierto para una arquitectura dada. ¿Cuáles son las probabilidades de que ninguno de los escritores del compilador se haya dado cuenta, y agregó una optimización para reemplazar lo más lento por lo más rápido?
Jon Hanna
8
Esto es cierto en el 8080. Tiene instrucciones para saltar en cero y saltar en menos, pero ninguna que pueda probar ambas simultáneamente.
44
Este es también el caso de la familia de procesadores 6502 y 65816, que también se extiende al Motorola 68HC11 / 12.
Lucas
31
Incluso en el 8080 una <=prueba puede ser implementado en una instrucción con el canje de los operandos y pruebas para not <(a equivalentes >=) Esta es la deseada <=con operandos intercambiadas: cmp B,A; bcs addr. Esa es la razón por la que Intel omitió esta prueba, la consideraron redundante y no podía permitirse instrucciones redundantes en esos momentos :-)
Gunther Piez
92

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 compilador que haga exactamente lo mismo. Solo un compilador horriblemente roto generaría un código inferior para uno de estos.

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

David Schwartz
fuente
66
+1 estoy de acuerdo. Ni <tampoco <=tienen velocidad hasta que el compilador decida qué velocidad tendrán. Esta es una optimización muy simple para los compiladores cuando considera que generalmente ya realizan una optimización de código muerto, optimización de llamada de cola, elevación de bucle (y desenrollado, en ocasiones), paralelización automática de varios bucles, etc. ¿ Por qué perder el tiempo reflexionando sobre optimizaciones prematuras? ? Obtenga un prototipo en funcionamiento, perfílelo para determinar dónde se encuentran las optimizaciones más significativas, realice esas optimizaciones en orden de importancia y vuelva a perfilar en el camino para medir el progreso ...
autista
Todavía hay algunos casos extremos en los que una comparación que tiene un valor constante podría ser más lenta en <=, por ejemplo, cuando la transformación de (a < C)a (a <= C-1)(para alguna constante C) hace Cque sea más difícil codificar en el conjunto de instrucciones. Por ejemplo, un conjunto de instrucciones puede ser capaz de representar constantes con signo de -127 a 128 en una forma compacta en las comparaciones, pero las constantes fuera de ese rango tienen que cargarse utilizando una codificación más larga y más lenta u otra instrucción por completo. Por lo tanto, una comparación como (a < -127)puede no tener una transformación directa.
BeeOnRope
@BeeOnRope El problema no era si realizar operaciones que diferían debido a tener diferentes constantes en ellas podría afectar el rendimiento, sino si expresar la misma operación usando diferentes constantes podría afectar el rendimiento. Así que no estamos comparando a > 127a a > 128porque no tiene otra opción existe, se utiliza el que necesita. Estamos comparando a > 127a a >= 128, que no puede requerir codificación diferente o diferentes instrucciones, ya que tienen la misma tabla de verdad. Cualquier codificación de uno es igualmente una codificación del otro.
David Schwartz
Estaba respondiendo de manera general a su afirmación de que "si hubiera alguna plataforma donde [<= era más lenta], el compilador siempre debería convertir <=a <constantes". Hasta donde yo sé, esa transformación implica cambiar la constante. Por ejemplo, a <= 42se compila como a < 43porque <es más rápido. En algunos casos extremos, tal transformación no sería fructífera porque la nueva constante puede requerir instrucciones más o más lentas. Por supuesto a > 127, y a >= 128son equivalentes y un compilador debe codificar ambas formas en la (misma) manera más rápida, pero eso no es inconsistente con lo que he dicho.
BeeOnRope
67

Veo que ninguno es más rápido. El compilador 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 ifes de GCC en la plataforma x86_64 en Linux.

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

Noté que si no es una constante, 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
Adrian Cornish
fuente
99
Tenga en cuenta que esto es específico de x86.
Michael Petrotta
10
Creo que deberías usar eso if(a <=900)para demostrar que genera exactamente lo mismo :)
Lipis
2
@AdrianCornish Lo siento ... lo edité ... es más o menos lo mismo ... pero si cambias el segundo if a <= 900, entonces el código asm será exactamente el mismo :) Es más o menos lo mismo ahora ... pero tú saber .. para el TOC :)
Lipis
3
@Boann Eso podría reducirse a if (verdadero) y eliminarse por completo.
Qsario
55
Nadie ha señalado que esta optimización solo se aplica a comparaciones constantes . Puedo garantizar que no se hará así para comparar dos variables.
Jonathon Reinhart
51

Para el código de coma flotante, la comparación <= puede ser más lenta (según 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 se 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, coloca el bit "comparado menos que" en su lugar y luego regresa. Se necesitan 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_strictantes, pero ahora hay dos partes de interés: "era menor que" y "era igual a". Esto requiere una instrucción adicional (cror - registro de condición a nivel de bit O) para combinar estos dos bits en uno. Entonces compare_looserequiere cinco instrucciones, mientras quecompare_strict requiere cuatro.

Puede pensar que el compilador 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 <= NaN2y NaN1 > NaN2necesitan ambos evaluar a falso.

pez ridículo
fuente
Afortunadamente no funciona así en x86 (x87). fucomipestablece ZF y CF.
Jonathon Reinhart
3
@JonathonReinhart: Creo que estás malinterpretando lo que está haciendo el PowerPC: el registro de condición cr es el equivalente a banderas como ZFy CFen el x86. (Aunque el CR es más flexible). De lo que habla el afiche es de mover el resultado a un GPR: que toma dos instrucciones en PowerPC, pero x86 tiene una instrucción de movimiento condicional.
Dietrich Epp
@DietrichEpp Lo que quise agregar después de mi declaración fue: Lo que luego puede saltar inmediatamente en función del valor de EFLAGS. Perdón por no ser claro.
Jonathon Reinhart
1
@JonathonReinhart: Sí, y también puedes saltar inmediatamente en función del valor de la CR. La respuesta no está hablando de saltar, que es de donde provienen las instrucciones adicionales.
Dietrich Epp
34

Tal vez el autor de ese libro sin nombre ha leído que se a > 0ejecuta más rápido a >= 1y cree que es cierto universalmente.

Pero es porque a 0está involucrado (porque CMPpuede, dependiendo de la arquitectura, reemplazado, por ejemplo, por OR) y no por el <.

glglgl
fuente
1
Por supuesto, en una "depuración" de construcción, pero tendrían que pasar un mal compilador para (a >= 1)ir más despacio que (a > 0), ya que el primero puede ser trivialmente transformaron a este último por el optimizador ..
BeeOnRope
2
@BeeOnRope A veces me sorprende las cosas complicadas que un optimizador puede optimizar y las cosas fáciles que no puede hacer.
glglgl
1
De hecho, y siempre vale la pena verificar la salida de asm para las muy pocas funciones en las que sería importante. Dicho esto, la transformación anterior es muy básica y se ha realizado incluso en compiladores simples durante décadas.
BeeOnRope
32

Por lo menos, si esto fuera cierto, un compilador 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 los compiladores menos ingenuos, no notaría una diferencia .

Eliot Ball
fuente
¡Por qué! (A> b) es una versión optimizada de a <= b. ¿No es! (A> b) 2 operaciones en una?
Abhishek Singh
66
@AbhishekSingh NOTestá hecho por otra instrucción ( jevs. jne)
Pavel Gatnar
15

Tienen la misma velocidad. Tal vez en alguna arquitectura especial lo que él / ella dijo es correcto, pero en la familia x86 al menos sé que son lo mismo. Porque para hacer esto, la CPU hará una sustracción (a - b) y luego verificará las banderas del registro de banderas. Dos bits de ese registro se llaman ZF (indicador cero) y SF (indicador de signo), y se realiza en un ciclo, porque lo hará con una operación de máscara.

Masoud
fuente
14

Esto dependería mucho de la arquitectura subyacente con la que se compila el C. Algunos procesadores y arquitecturas pueden tener instrucciones explícitas para igual o menor que, que se ejecutan en diferentes números de ciclos.

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

Telgin
fuente
1
SI hubo una diferencia en los ciclos. 1) no sería detectable. 2) Cualquier compilador que valga la pena ya estaría haciendo la transformación de la forma lenta a la forma más rápida sin cambiar el significado del código. Entonces la instrucción resultante plantada sería idéntica.
Martin York
Totalmente de acuerdo, sería una diferencia bastante trivial y tonta en cualquier caso. Ciertamente, nada que mencionar en un libro que debería ser independiente de la plataforma.
Telgin
@lttlrck: lo entiendo. Me tomó un tiempo (tonto). No, no son detectables porque están sucediendo muchas otras cosas que hacen que su medición sea imposible. El procesador se detiene / errores de caché / señales / intercambio de procesos. Por lo tanto, en una situación normal del sistema operativo, las cosas en el nivel de ciclo único no pueden medirse físicamente. Si puede eliminar toda esa interferencia de sus mediciones (ejecútelo en un chip con memoria integrada y sin sistema operativo), entonces todavía tiene que preocuparse por la granularidad de sus temporizadores, pero en teoría, si lo ejecuta el tiempo suficiente, podría ver algo.
Martin York
12

TL; respuesta DR

Para la mayoría de las combinaciones de arquitectura, compilador y lenguaje, no será más rápido.

Respuesta completa

Otras respuestas se han concentrado en la arquitectura x86 , y no conozco la arquitectura ARM (que parece ser su ensamblador de ejemplo) lo suficientemente bien como para comentar específicamente sobre 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 lo es ser una optimización .

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

Probablemente hay algunas arquitecturas donde esto es una optimización, pero sé de al menos una arquitectura donde lo contrario puede ser cierto. La venerable arquitectura Transputer solo tenía instrucciones de código de máquina para igual y mayor o igual que , por lo que todas las comparaciones tuvieron que construirse a partir de estas primitivas.

Incluso entonces, en casi todos los casos, el compilador podría ordenar las instrucciones de evaluación de tal manera que, en la práctica, ninguna comparación tuviera ninguna ventaja sobre ninguna otra. Sin embargo, en el peor de los casos, es posible que deba agregar una instrucción inversa (REV) para intercambiar los dos primeros elementos en la pila de operandos . Esta fue una instrucción de un solo byte que tardó un solo ciclo en ejecutarse, por lo que tenía la sobrecarga más pequeña posible.

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

Mark Booth
fuente
6

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

shinkou
fuente
1
¿Cuál es la mala práctica? ¿Incrementando o decrementando un contador? ¿Cómo se almacena la notación de índice entonces?
jcolebrand
55
Él quiere decir que si estás haciendo una comparación de 2 tipos de variables. Por supuesto, es trivial si está configurando el valor para un bucle o algo así. Pero si tiene x <= y, yy es desconocido, sería más lento 'optimizarlo' para x <y + 1
JustinDanielson
@JustinDanielson estuvo de acuerdo. Sin mencionar feo, confuso, etc.
Jonathon Reinhart
4

Se podría decir que la línea es correcta en la mayoría de los lenguajes de secuencias de comandos, 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 efecto en C ++, y cualquier cosa que se haga con un lenguaje de script probablemente no esté tan preocupado por la optimización.

Ecksters
fuente
Estoy un poco en desacuerdo. En la programación competitiva, los lenguajes de secuencias de comandos a menudo ofrecen la solución más rápida a un problema, pero se deben aplicar las técnicas correctas (léase: optimización) para obtener una solución correcta.
Tyler Crompton
3

Cuando escribí esta respuesta, sólo estaba mirando a la pregunta del título sobre vs. <<= en general, no el ejemplo específico de una constante a < 901vs a <= 900. Muchos compiladores siempre reducen la magnitud de las constantes al convertir entre <y<= , por ejemplo, porque el operando inmediato x86 tiene una codificación más corta de 1 byte para -128..127.

Para ARM y especialmente AArch64, poder codificar como inmediato depende de poder rotar un campo estrecho en cualquier posición de una palabra. Entonces cmp w0, #0x00f000sería codificable, mientras que cmp w0, #0x00effffpodría no serlo. Por lo tanto, la regla de hacer más pequeño para la comparación frente a una constante de tiempo de compilación no siempre se aplica a AArch64.


<vs. <= en general, incluso para condiciones variables de tiempo de ejecución

En lenguaje ensamblador en la mayoría de las máquinas, una comparación <=tiene el mismo costo que una comparación para< . Esto se aplica ya sea que se bifurque en él, lo booleanice para crear un entero 0/1 o lo use como predicado para una operación de selección sin ramificación (como x86 CMOV). Las otras respuestas solo han abordado esta parte de la pregunta.

Pero esta pregunta es sobre los operadores de C ++, la entrada al optimizador. Normalmente ambos son igualmente eficientes; el consejo del libro suena totalmente falso porque los compiladores siempre pueden transformar la comparación que implementan en asm. Pero hay al menos una excepción en la que el uso <=puede crear accidentalmente algo que el compilador no puede optimizar.

Como condición de bucle, hay casos en los que <=es cualitativamente diferente de <, cuando impide que el compilador pruebe que un bucle no es infinito. Esto puede hacer una gran diferencia, deshabilitando la auto-vectorización.

El desbordamiento sin signo está bien definido como envoltura de base 2, a diferencia del desbordamiento con signo (UB). Los contadores de bucles firmados generalmente están a salvo de esto con compiladores que se optimizan en función de que el UB de desbordamiento firmado no suceda: ++i <= sizesiempre se convertirá en falso. ( Lo que todo programador de C debe saber sobre el comportamiento indefinido )

void foo(unsigned size) {
    unsigned upper_bound = size - 1;  // or any calculation that could produce UINT_MAX
    for(unsigned i=0 ; i <= upper_bound ; i++)
        ...

Los compiladores solo pueden optimizar de manera que preserven el comportamiento (definido y legalmente observable) de la fuente C ++ para todos los valores de entrada posibles , excepto los que conducen a un comportamiento indefinido.

(Un simple i <= size también crearía el problema, pero pensé que calcular un límite superior era un ejemplo más realista de introducir accidentalmente la posibilidad de un bucle infinito para una entrada que no le interesa pero que el compilador debe considerar).

En este caso, size=0conduce a upper_bound=UINT_MAX, y i <= UINT_MAXsiempre es cierto. Por lo tanto, este bucle es infinito size=0y el compilador debe respetarlo aunque usted, como programador, probablemente nunca tenga la intención de pasar size = 0. Si el compilador puede incorporar esta función a una persona que llama, donde puede demostrar que size = 0 es imposible, entonces es genial, puede optimizar como podría i < size.

Asm like if(!size) skip the loop; do{...}while(--size);es una forma normalmente eficiente de optimizar un for( i<size )bucle, si el valor real de ino es necesario dentro del bucle ( ¿Por qué los bucles siempre se compilan en el estilo "do ... while" (salto de cola)? ).

Pero eso sí {} mientras que no puede ser infinito: si se ingresa con size==0, obtenemos 2 ^ n iteraciones. ( Iterar sobre todos los enteros sin signo en un bucle for C hace posible expresar un bucle sobre todos los enteros sin signo, incluido cero, pero no es fácil sin un indicador de acarreo de la forma en que está en asm).

Dado que el contador de bucle es una posibilidad, los compiladores modernos a menudo simplemente "se dan por vencidos" y no optimizan tan agresivamente.

Ejemplo: suma de enteros de 1 a n

El uso de las i <= nderrotas sin signo de reconocimiento de idioma clang que optimiza los sum(1 .. n)bucles con una forma cerrada basada en la n * (n+1) / 2fórmula de Gauss .

unsigned sum_1_to_n_finite(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i < n+1 ; ++i)
        total += i;
    return total;
}

Asistente x86-64 de clang7.0 y gcc8.2 en el explorador del compilador Godbolt

 # clang7.0 -O3 closed-form
    cmp     edi, -1       # n passed in EDI: x86-64 System V calling convention
    je      .LBB1_1       # if (n == UINT_MAX) return 0;  // C++ loop runs 0 times
          # else fall through into the closed-form calc
    mov     ecx, edi         # zero-extend n into RCX
    lea     eax, [rdi - 1]   # n-1
    imul    rax, rcx         # n * (n-1)             # 64-bit
    shr     rax              # n * (n-1) / 2
    add     eax, edi         # n + (stuff / 2) = n * (n+1) / 2   # truncated to 32-bit
    ret          # computed without possible overflow of the product before right shifting
.LBB1_1:
    xor     eax, eax
    ret

Pero para la versión ingenua, solo obtenemos un bobo tonto de clang.

unsigned sum_1_to_n_naive(unsigned n) {
    unsigned total = 0;
    for (unsigned i = 0 ; i<=n ; ++i)
        total += i;
    return total;
}
# clang7.0 -O3
sum_1_to_n(unsigned int):
    xor     ecx, ecx           # i = 0
    xor     eax, eax           # retval = 0
.LBB0_1:                       # do {
    add     eax, ecx             # retval += i
    add     ecx, 1               # ++1
    cmp     ecx, edi
    jbe     .LBB0_1            # } while( i<n );
    ret

GCC no usa una forma cerrada de ninguna manera, por lo que la elección de la condición del bucle realmente no lo perjudica ; se auto-vectoriza con la suma de enteros SIMD, ejecutando 4 ivalores en paralelo en los elementos de un registro XMM.

# "naive" inner loop
.L3:
    add     eax, 1       # do {
    paddd   xmm0, xmm1    # vect_total_4.6, vect_vec_iv_.5
    paddd   xmm1, xmm2    # vect_vec_iv_.5, tmp114
    cmp     edx, eax      # bnd.1, ivtmp.14     # bound and induction-variable tmp, I think.
    ja      .L3 #,       # }while( n > i )

 "finite" inner loop
  # before the loop:
  # xmm0 = 0 = totals
  # xmm1 = {0,1,2,3} = i
  # xmm2 = set1_epi32(4)
 .L13:                # do {
    add     eax, 1       # i++
    paddd   xmm0, xmm1    # total[0..3] += i[0..3]
    paddd   xmm1, xmm2    # i[0..3] += 4
    cmp     eax, edx
    jne     .L13      # }while( i != upper_limit );

     then horizontal sum xmm0
     and peeled cleanup for the last n%3 iterations, or something.

También tiene un bucle escalar simple que creo que usa para ncasos muy pequeños y / o para el caso de bucle infinito.

Por cierto, ambos bucles desperdician una instrucción (y una uop en las CPU de la familia Sandybridge) en la sobrecarga del bucle. sub eax,1/ en jnzlugar de add eax,1/ cmp / jcc sería más eficiente. 1 uop en lugar de 2 (después de la macro fusión de sub / jcc o cmp / jcc). El código después de ambos bucles escribe EAX incondicionalmente, por lo que no está utilizando el valor final del contador de bucles.

Peter Cordes
fuente
Buen ejemplo artificial. ¿Qué pasa con su otro comentario sobre un posible efecto en la ejecución fuera de orden debido al uso de EFLAGS? ¿Es puramente teórico o puede suceder que un JB conduzca a una tubería mejor que un JBE?
rustyx
@rustyx: ¿comenté eso en algún lugar con otra respuesta? Los compiladores no van a emitir código que cause bloqueos parciales, y ciertamente no para una C <o <=. Pero claro, test ecx,ecx/ bt eax, 3/ jbesaltará si ZF está configurado (ecx == 0), o si CF está configurado (bit 3 de EAX == 1), causando un bloqueo parcial de bandera en la mayoría de las CPU porque las banderas que lee no todas provienen de la última instrucción para escribir cualquier bandera. En la familia Sandybridge, en realidad no se detiene, solo necesita insertar una fusión. cmp/ testescribe todas las banderas, pero btdeja ZF sin modificar. felixcloutier.com/x86/bt
Peter Cordes
2

Solo si las personas que crearon las computadoras son malas con la lógica booleana. Que no deberían ser.

Cada comparación ( >= <= > <) se puede hacer a la misma velocidad.

Lo que cada comparación es, es solo una resta (la diferencia) y ver si es positiva / negativa.
(Si msbse establece, el número es negativo)

¿Cómo verificar a >= b? Sub a-b >= 0Check si a-bes positivo.
¿Cómo verificar a <= b? Sub 0 <= b-aCheck si b-aes positivo.
¿Cómo verificar a < b? Sub a-b < 0Check si a-bes negativo.
¿Cómo verificar a > b? Sub 0 > b-aCheck si b-aes negativo.

En pocas palabras, la computadora puede hacer esto debajo del capó para la operación dada:

a >= b== msb(a-b)==0
a <= b== msb(b-a)==0
a > b== msb(b-a)==1
a < b==msb(a-b)==1

y por supuesto el equipo no sería realmente necesita hacer la ==0o ==1tampoco.
porque ==0podría simplemente invertir el msbdel circuito.

De todos modos, ciertamente no se habrían a >= bcalculado como a>b || a==bjajaja

Charco
fuente