¿Cuál es más rápido: while (1) o while (2)?

Esta fue una pregunta de entrevista realizada por un gerente superior.

¿Cual es mas rápido?

while(1) {
    // Some code
}

o

while(2) {
    //Some code
}

Dije que ambos tienen la misma velocidad de ejecución, ya que la expresión en el interior whilefinalmente debería evaluar a trueo false. En este caso, ambos evalúan truey no hay instrucciones condicionales adicionales dentro de la whilecondición. Entonces, ambos tendrán la misma velocidad de ejecución y prefiero while (1).

Pero el entrevistador dijo con confianza: "Revise sus conceptos básicos. while(1)Es más rápido que while(2)". (No estaba probando mi confianza)

¿Es esto cierto?

Ver también: ¿"for (;;)" es más rápido que "while (TRUE)"? Si no, ¿por qué la gente lo usa?

Ambos bucles son infinitos, pero podemos ver cuál toma más instrucciones / recursos por iteración.

Usando gcc, compilé los dos siguientes programas para ensamblar en diferentes niveles de optimización:

int main(void) {
    while(1) {}
    return 0;
}

int main(void) {
    while(2) {}
    return 0;
}

Incluso sin optimizaciones (-O0 ), el ensamblado generado fue idéntico para ambos programas . Por lo tanto, no hay diferencia de velocidad entre los dos bucles.

Como referencia, aquí está el ensamblaje generado (usando gcc main.c -S -masm=intelcon un indicador de optimización):

Con -O0 :

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    push    rbp
    .seh_pushreg    rbp
    mov rbp, rsp
    .seh_setframe   rbp, 0
    sub rsp, 32
    .seh_stackalloc 32
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Con -O1 :

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .text
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Con -O2y-O3 (misma salida):

    .file   "main.c"
    .intel_syntax noprefix
    .def    __main; .scl    2;  .type   32; .endef
    .section    .text.startup,"x"
    .p2align 4,,15
    .globl  main
    .def    main;   .scl    2;  .type   32; .endef
    .seh_proc   main
main:
    sub rsp, 40
    .seh_stackalloc 40
    .seh_endprologue
    call    __main
.L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

De hecho, el ensamblaje generado para el bucle es idéntico para cada nivel de optimización:

 .L2:
    jmp .L2
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Los bits importantes son:

.L2:
    jmp .L2

No puedo leer muy bien el ensamblaje, pero obviamente este es un ciclo incondicional. La jmpinstrucción restablece incondicionalmente el programa a.L2 etiqueta sin siquiera comparar un valor con verdadero, y por supuesto lo vuelve a hacer de inmediato hasta que el programa finalice de alguna manera. Esto corresponde directamente al código C / C ++:

L2:
    goto L2;

Editar:

Curiosamente, incluso sin optimizaciones , los siguientes bucles produjeron exactamente el mismo resultado (incondicional jmp) en el ensamblaje:

while(42) {}

while(1==1) {}

while(2==2) {}

while(4<7) {}

while(3==3 && 4==4) {}

while(8-9 < 0) {}

while(4.3 * 3e4 >= 2 << 6) {}

while(-0.1 + 02) {}

E incluso para mi asombro:

#include<math.h>

while(sqrt(7)) {}

while(hypot(3,4)) {}

Las cosas se ponen un poco más interesantes con las funciones definidas por el usuario:

int x(void) {
    return 1;
}

while(x()) {}

#include<math.h>

double x(void) {
    return sqrt(7);
}

while(x()) {}

En -O0, estos dos ejemplos realmente llamanx y realizan una comparación para cada iteración.

Primer ejemplo (devolviendo 1):

.L4:
    call    x
    testl   %eax, %eax
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Segundo ejemplo (regresando sqrt(7)):

.L4:
    call    x
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jp  .L4
    xorpd   %xmm1, %xmm1
    ucomisd %xmm1, %xmm0
    jne .L4
    movl    $0, %eax
    addq    $32, %rsp
    popq    %rbp
    ret
    .seh_endproc
    .ident  "GCC: (tdm64-2) 4.8.1"

Sin embargo, en -O1y arriba, ambos producen el mismo ensamblaje que los ejemplos anteriores (un jmpregreso incondicional a la etiqueta anterior).

TL; DR

Bajo GCC, los diferentes bucles se compilan en un ensamblaje idéntico. El compilador evalúa los valores constantes y no se molesta en realizar ninguna comparación real.

La moraleja de la historia es:

• Existe una capa de traducción entre el código fuente de C ++ y las instrucciones de la CPU, y esta capa tiene implicaciones importantes para el rendimiento.
• Por lo tanto, el rendimiento no puede evaluarse solo mirando el código fuente.
• El compilador debe ser lo suficientemente inteligente como para optimizar estos casos triviales. Los programadores no deberían perder el tiempo pensando en ellos en la gran mayoría de los casos.

Sí, while(1)es mucho más rápido que while(2), para un ser humano a leer! Si veo while(1)en una base de código desconocida, inmediatamente sé lo que pretendía el autor, y mis globos oculares pueden continuar a la siguiente línea.

Si yo veo while(2) , probablemente me detendré y trataré de averiguar por qué el autor no escribió while(1). ¿Se deslizó el dedo del autor sobre el teclado? ¿Los mantenedores de esta base de código usan while(n)como un oscuro mecanismo de comentarios para hacer que los bucles se vean diferentes? ¿Es una solución cruda para una advertencia espuria en alguna herramienta de análisis estático roto? ¿O es esta una pista de que estoy leyendo el código generado? ¿Es un error resultante de un mal aconsejado de buscar y reemplazar todo, o una mala fusión, o un rayo cósmico? Tal vez se supone que esta línea de código haga algo dramáticamente diferente. Tal vez se suponía que debía leer while(w)o while(x2). Será mejor que encuentre al autor en el historial del archivo y le envíe un correo electrónico "WTF" ... y ahora he roto mi contexto mental.while(2)while(1) habría tomado una fracción de segundo!

Estoy exagerando, pero solo un poco. La legibilidad del código es realmente importante. ¡Y eso vale la pena mencionarlo en una entrevista!

Las respuestas existentes que muestran el código generado por un compilador particular para un objetivo particular con un conjunto particular de opciones no responden completamente la pregunta, a menos que la pregunta se haya hecho en ese contexto específico ("Lo que es más rápido usando gcc 4.7.2 para x86_64 con opciones predeterminadas? ", por ejemplo).

En lo que respecta a la definición del lenguaje, en la máquina abstracta se while (1) evalúa la constante entera 1y se while (2)evalúa la constante entera 2; en ambos casos, el resultado se compara para igualdad a cero. El estándar del lenguaje no dice absolutamente nada sobre el rendimiento relativo de las dos construcciones.

Me imagino que un compilador extremadamente ingenuo podría generar un código de máquina diferente para las dos formas, al menos cuando se compila sin solicitar la optimización.

Por otro lado, los compiladores de C absolutamente deben evaluar algunas expresiones constantes en el momento de la compilación, cuando aparecen en contextos que requieren una expresión constante. Por ejemplo, esto:

int n = 4;
switch (n) {
    case 2+2: break;
    case 4:   break;
}

requiere un diagnóstico; un compilador diferido no tiene la opción de diferir la evaluación 2+2hasta el momento de la ejecución. Dado que un compilador debe tener la capacidad de evaluar expresiones constantes en el momento de la compilación, no hay una buena razón para no aprovechar esa capacidad incluso cuando no es necesaria.

El estándar C ( N1570 6.8.5p4) dice que

Una instrucción de iteración hace que una instrucción llamada cuerpo del bucle se ejecute repetidamente hasta que la expresión de control se compare igual a 0.

Entonces, las expresiones constantes relevantes son 1 == 0y 2 == 0, las cuales se evalúan según el intvalor0 . (Estas comparaciones están implícitas en la semántica del whilebucle; no existen como expresiones C reales).

Un compilador perversamente ingenuo podría generar un código diferente para las dos construcciones. Por ejemplo, para el primero podría generar un bucle infinito incondicional (tratando 1como un caso especial), y para el segundo podría generar una comparación explícita de tiempo de ejecución equivalente a2 != 0 . Pero nunca he encontrado un compilador de C que realmente se comportara de esa manera, y dudo seriamente de que exista ese compilador.

La mayoría de los compiladores (estoy tentado a decir que todos los compiladores con calidad de producción) tienen opciones para solicitar optimizaciones adicionales. Bajo tal opción, es aún menos probable que cualquier compilador genere un código diferente para las dos formas.

Si su compilador genera un código diferente para las dos construcciones, primero verifique si las diferentes secuencias de código realmente tienen un rendimiento diferente. Si lo hacen, intente compilar nuevamente con una opción de optimización (si está disponible). Si aún difieren, envíe un informe de error al proveedor del compilador. No es (necesariamente) un error en el sentido de una falla para cumplir con el estándar C, pero es casi seguro que es un problema que debe corregirse.

En pocas palabras: while (1)y while(2) casi con seguridad tienen el mismo rendimiento. Tienen exactamente la misma semántica, y no hay una buena razón para que ningún compilador genere un código idéntico.

Y aunque es perfectamente legal para un compilador generar un código más rápido para while(1)que para while(2), es igualmente legal para un compilador generar un código más rápido while(1)que para otra aparición while(1)en el mismo programa.

(Hay otra pregunta implícita en la que usted hizo: ¿Cómo lidiar con un entrevistador que insiste en un punto técnico incorrecto? Probablemente sea una buena pregunta para el sitio de Workplace ).

Espera un minuto. El entrevistador, ¿se parecía a este tipo?

Ya es bastante malo que el propio entrevistador haya fallado en esta entrevista, ¿qué pasa si otros programadores de esta compañía han "pasado" esta prueba?

No. Evaluar las declaraciones 1 == 0y 2 == 0 debe ser igualmente rápido. Podríamos imaginar implementaciones de compiladores deficientes donde una podría ser más rápida que la otra. Pero no hay una buena razón por la cual uno debería ser más rápido que el otro.

Incluso si hay alguna circunstancia oscura en la que la afirmación sería cierta, los programadores no deberían ser evaluados en base al conocimiento de trivialidades oscuras (y en este caso espeluznantes). No se preocupe por esta entrevista, el mejor movimiento aquí es alejarse.

Descargo de responsabilidad: Esta NO es una caricatura original de Dilbert. Esto es simplemente un mashup .

Tu explicación es correcta. Esta parece ser una pregunta que pone a prueba su autoconfianza además del conocimiento técnico.

Por cierto, si respondiste

Ambas piezas de código son igualmente rápidas, porque ambas tardan un tiempo infinito en completarse

el entrevistador diría

Pero while (1)puede hacer más iteraciones por segundo; ¿puedes explicar porque? (esto no tiene sentido; prueba tu confianza nuevamente)

Entonces, respondiendo como lo hizo, ahorró algo de tiempo que de lo contrario perdería al discutir esta mala pregunta.

Aquí hay un código de ejemplo generado por el compilador en mi sistema (MS Visual Studio 2012), con las optimizaciones desactivadas:

yyy:
    xor eax, eax
    cmp eax, 1     (or 2, depending on your code)
    je xxx
    jmp yyy
xxx:
    ...

Con optimizaciones activadas:

xxx:
    jmp xxx

Entonces, el código generado es exactamente el mismo, al menos con un compilador de optimización.

La explicación más probable para la pregunta es que el entrevistador cree que el procesador verifica los bits individuales de los números, uno por uno, hasta que alcanza un valor distinto de cero:

1 = 00000001
2 = 00000010

Si el "es cero?" El algoritmo comienza desde el lado derecho del número y tiene que verificar cada bit hasta que alcanza un bit distinto de cero, el while(1) { }bucle tendría que verificar el doble de bits por iteración que el while(2) { }bucle.

Esto requiere un modelo mental muy erróneo de cómo funcionan las computadoras, pero tiene su propia lógica interna. Una forma de verificar sería preguntar si sería while(-1) { }o while(3) { }sería igualmente rápido, o si while(32) { }sería aún más lento .

Por supuesto, no conozco las intenciones reales de este gerente, pero propongo una visión completamente diferente: al contratar a un nuevo miembro en un equipo, es útil saber cómo reacciona ante situaciones de conflicto.

Te condujeron al conflicto. Si esto es cierto, son inteligentes y la pregunta era buena. Para algunas industrias, como la banca, publicar su problema en Stack Overflow podría ser un motivo de rechazo.

Pero, por supuesto, no lo sé, solo propongo una opción.

Creo que la pista se encuentra en "preguntado por un gerente superior". Obviamente, esta persona dejó de programar cuando se convirtió en gerente y luego le tomó varios años convertirse en gerente superior. Nunca perdió interés en la programación, pero nunca escribió una línea desde aquellos días. Por lo tanto, su referencia no es "ningún compilador decente" como mencionan algunas respuestas, sino "el compilador con el que esta persona trabajó hace 20-30 años".

En ese momento, los programadores pasaban un porcentaje considerable de su tiempo probando varios métodos para hacer que su código fuera más rápido y más eficiente, ya que el tiempo de CPU del 'minicomputador central' era tan valioso. Al igual que la gente que escribía compiladores. Supongo que el compilador único que su compañía puso a disposición en ese momento optimizó sobre la base de 'declaraciones frecuentes que se pueden optimizar' y tomó un poco de atajo cuando encontró un momento (1) y evaluó todo más, incluido un rato (2). Habiendo tenido tal experiencia podría explicar su posición y su confianza en ella.

El mejor enfoque para que lo contraten es probablemente uno que le permita al gerente senior dejarse llevar y dar una conferencia de 2 a 3 minutos sobre "los buenos viejos tiempos de la programación" antes de que USTED lo guíe suavemente hacia el próximo tema de la entrevista. (El buen momento es importante aquí, demasiado rápido e interrumpe la historia, demasiado lento y se le etiqueta como alguien con un enfoque insuficiente). Dígale al final de la entrevista que estaría muy interesado en aprender más sobre este tema.

Deberías haberle preguntado cómo llegó a esa conclusión. Bajo cualquier compilador decente, los dos compilan con las mismas instrucciones asm. Entonces, él debería haberte dicho también el compilador para comenzar. Y aun así, tendrías que conocer muy bien el compilador y la plataforma para incluso hacer una suposición teórica. Y al final, realmente no importa en la práctica, ya que hay otros factores externos como la fragmentación de la memoria o la carga del sistema que influirán en el ciclo más que este detalle.

En aras de esta pregunta, debo agregar que recuerdo a Doug Gwyn del Comité C escribiendo que algunos de los primeros compiladores de C sin la aprobación del optimizador generarían una prueba en ensamblado para el while(1)(en comparación con el for(;;)que no lo tendría).

Le respondería al entrevistador dándole esta nota histórica y luego le diría que, aunque me sorprendería mucho que algún compilador hiciera esto, un compilador podría tener:

• sin optimizador pasar el compilador generar una prueba para ambos while(1)ywhile(2)
• Con el paso del optimizador, el compilador recibe instrucciones de optimizar (con un salto incondicional) todo while(1)porque se consideran idiomáticos. Esto dejaría al while(2)examen y, por lo tanto, hace una diferencia de rendimiento entre los dos.

Por supuesto, agregaría al entrevistador que no considerar while(1)y while(2)el mismo constructo es un signo de optimización de baja calidad, ya que estos son constructos equivalentes.

Otra versión de esa pregunta sería ver si tienes el coraje de decirle a tu gerente que él / ella está equivocado. Y cuán suavemente puedes comunicarlo.

Mi primer instinto habría sido generar una salida de ensamblaje para mostrarle al administrador que cualquier compilador decente debería encargarse de ello, y si no lo hace, enviará el próximo parche para ello :)

Para ver a tanta gente profundizar en este problema, muestra exactamente por qué esto podría ser una prueba para ver qué tan rápido desea micro-optimizar las cosas.

Mi respuesta sería; no importa mucho, prefiero centrarme en el problema comercial que estamos resolviendo. Después de todo, eso es lo que me pagarán.

Además, elegiría while(1) {}porque es más común, y otros compañeros de equipo no necesitarían pasar tiempo para descubrir por qué alguien iría por un número mayor que 1.

Ahora ve a escribir un código. ;-)

Si está tan preocupado por la optimización, debe usar

for (;;)

porque eso no tiene pruebas (modo cínico)

Me parece que esta es una de esas preguntas de entrevista conductual enmascaradas como una pregunta técnica. Algunas compañías hacen esto: harán una pregunta técnica que debería ser bastante fácil de responder para cualquier programador competente, pero cuando el entrevistado dé la respuesta correcta, el entrevistador les dirá que están equivocados.

La compañía quiere ver cómo reaccionarás en esta situación. ¿Te sientas en silencio y no presionas para que tu respuesta sea correcta, ya sea por dudas o por temor a molestar al entrevistador? ¿O estás dispuesto a desafiar a una persona con autoridad que sabes que está mal? Quieren ver si está dispuesto a defender sus convicciones, y si puede hacerlo con tacto y respeto.

Solía ​​programar el código C y ensamblado cuando este tipo de tonterías podrían haber hecho una diferencia. Cuando marcó la diferencia, lo escribimos en la Asamblea.

Si me hicieran esa pregunta, habría repetido la famosa cita de 1974 de Donald Knuth sobre la optimización prematura y habría caminado si el entrevistador no se reía y continuaba.

Tal vez el entrevistador hizo una pregunta tan tonta intencionalmente y quería que hicieras 3 puntos:

1. Razonamiento básico Ambos bucles son infinitos, es difícil hablar de rendimiento.
2. Conocimiento sobre niveles de optimización. Quería saber de usted si deja que el compilador haga alguna optimización por usted, optimizaría la condición, especialmente si el bloque no estaba vacío.
3. Conocimiento sobre arquitectura de microprocesador. La mayoría de las arquitecturas tienen una instrucción especial de CPU para comparar con 0 (aunque no necesariamente más rápido).

Aquí hay un problema: si realmente escribe un programa y mide su velocidad, ¡la velocidad de ambos bucles podría ser diferente! Para alguna comparación razonable:

unsigned long i = 0;
while (1) { if (++i == 1000000000) break; }

unsigned long i = 0;
while (2) { if (++i == 1000000000) break; }

con un código agregado que imprime el tiempo, algún efecto aleatorio como la forma en que se coloca el bucle dentro de una o dos líneas de caché podría marcar la diferencia. Por pura casualidad, un bucle podría estar completamente dentro de una línea de caché, o al comienzo de una línea de caché, o podría abarcar dos líneas de caché. Y como resultado, cualquier cosa que el entrevistador afirme que es más rápida podría ser realmente más rápida, por coincidencia.

En el peor de los casos: un compilador de optimización no se da cuenta de lo que hace el bucle, pero se da cuenta de que los valores producidos cuando se ejecuta el segundo bucle son los mismos que los producidos por el primero. Y generar código completo para el primer bucle, pero no para el segundo.

Ambos son iguales, lo mismo.

Según las especificaciones, todo lo que no sea 0 se considera verdadero, por lo que incluso sin ninguna optimización, y un buen compilador no generará ningún código para while (1) o while (2). El compilador generaría una verificación simple para != 0.

A juzgar por la cantidad de tiempo y esfuerzo que la gente ha pasado probando, probando y respondiendo a esta pregunta directa, diría que ambos se hicieron muy lentos al hacer la pregunta.

Y así pasar más tiempo en ello ...

"while (2)" es ridículo porque,

"while (1)" y "while (true)" se usan históricamente para hacer un ciclo infinito que espera que se llame "break" en algún momento dentro del ciclo en función de una condición que ciertamente ocurrirá.

El "1" simplemente está ahí para evaluar siempre como verdadero y, por lo tanto, decir "while (2)" es tan tonto como decir "while (1 + 1 == 2)" que también evaluará como verdadero.

Y si quieres ser completamente tonto solo usa: -

while (1 + 5 - 2 - (1 * 3) == 0.5 - 4 + ((9 * 2) / 4)) {
    if (succeed())
        break;
}

Me gustaría pensar que su codificador cometió un error tipográfico que no afectó la ejecución del código, pero si intencionalmente usó el "2" solo para ser extraño, despídalo antes de que ponga todo lo extraño en su código, lo que hace difícil leer y trabajar con

Eso depende del compilador.

Si optimiza el código, o si evalúa 1 y 2 como verdadero con el mismo número de instrucciones para un conjunto de instrucciones en particular, la velocidad de ejecución será la misma.

En casos reales, siempre será igual de rápido, pero sería posible imaginar un compilador particular y un sistema particular cuando esto se evaluaría de manera diferente.

Quiero decir: esta no es realmente una pregunta relacionada con el lenguaje (C).

Dado que las personas que buscan responder a esta pregunta quieren el ciclo más rápido, habría respondido que ambos están compilando igualmente en el mismo código de ensamblaje, como se indica en las otras respuestas. Sin embargo, puede sugerirle al entrevistador que use 'desenrollar bucle'; a do {} while loop en lugar del while while.

Cauteloso: debe asegurarse de que el ciclo al menos siempre se ejecute una vez .

El bucle debe tener una condición de ruptura en el interior.

También para ese tipo de bucle preferiría personalmente el uso de do {} while (42) ya que cualquier número entero, excepto 0, haría el trabajo.

La respuesta obvia es: según lo publicado, ambos fragmentos ejecutarían un bucle infinito igualmente ocupado, lo que hace que el programa sea infinitamente lento .

Aunque redefinir las palabras clave C como macros técnicamente tendría un comportamiento indefinido, es la única forma en que puedo pensar para hacer que cualquiera de los fragmentos de código sea rápido: puede agregar esta línea sobre los 2 fragmentos:

#define while(x) sleep(x);

de hecho hará el while(1)doble de rápido (o la mitad de lento) que while(2).

La única razón por la que puedo pensar por qué while(2)sería más lento es:

1. El código optimiza el ciclo para

   cmp eax, 2

2. Cuando ocurre la resta, estás esencialmente restando

   a. 00000000 - 00000010 cmp eax, 2

   en vez de

   si. 00000000 - 00000001 cmp eax, 1

cmpsolo establece banderas y no establece un resultado. Entonces, en los bits menos significativos, sabemos si necesitamos pedir prestado o no con b . Mientras que con un tiene que realizar dos restas antes de obtener un préstamo.