Pregunta ¿Qué es más rápido: mientras (1) o mientras (2)?


Esta fue una pregunta de entrevista hecha por un gerente senior.

¿Cual es mas rápido?

while(1) {
    // Some code
}

o

while(2) {
    //Some code
}

Dije que ambos tienen la misma velocidad de ejecución, como la expresión dentro while debería finalmente evaluar a true o false. En este caso, ambos evalúan true y no hay instrucciones condicionales adicionales dentro del while condición. Entonces, ambos tendrán la misma velocidad de ejecución y yo prefiero (1).

Pero el entrevistador dijo con confianza: "Verifica tus básicos. while(1) es más rápido que while(2)" (Él no estaba probando mi confianza)

¿Es esto cierto?

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


552
2017-07-20 07:32


origen


Respuestas:


Ambos bucles son infinitos, pero podemos ver cuál lleva 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 ensamblaje 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 (utilizando gcc main.c -S -masm=intel con una bandera 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 -O2 y -O3 (Mismo resultado):

    .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 conjunto generado para el ciclo 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 el ensamblaje muy bien, pero obviamente este es un ciclo incondicional. los jmp instrucción reinicia incondicionalmente el programa de nuevo a la .L2 etiqueta sin siquiera comparar un valor contra verdadero, y por supuesto inmediatamente lo hace de nuevo hasta que el programa termine de alguna manera. Esto corresponde directamente al código C / C ++:

L2:
    goto L2;

Editar:

Curiosamente, incluso con sin optimizaciones, los siguientes bucles produjeron exactamente la misma salida (incondicional) jmp) en el montaje:

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 vuelven 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()) {}

A -O0, estos dos ejemplos realmente llaman x y realice una comparación para cada iteración.

Primer ejemplo (regresando 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 -O1 y arriba, ambos producen la misma asamblea que los ejemplos anteriores (un incondicional jmp volver a la etiqueta anterior).

TL; DR

En 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 debiera ser lo suficientemente inteligente como para optimizar casos tan triviales. Programadores no debería Pierde su tiempo pensando en ellos en la gran mayoría de los casos.

653
2017-07-20 08:03



Sí, while(1) es mucho más rápido que while(2), ¡para que un humano lea! Si yo veo while(1) en una base de código desconocida, sé de inmediato qué pretendía el autor, y mis ojos pueden continuar a la siguiente línea.

Si yo veo while(2), Probablemente me detenga en seco e intente descubrir por qué el autor no escribió while(1). ¿El dedo del autor se deslizó en el teclado? ¿Los mantenedores de esta base de código usan while(n) como un mecanismo de comentario oscuro para hacer que los bucles se vean diferentes? ¿Es una solución indirecta para una advertencia falsa 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 hallazgo y reemplazo de todo, o una mala fusión, o un rayo cósmico? Quizás se supone que esta línea de código hace 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. los while(2) podría consumir varios minutos de mi tiempo, cuando 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!


257
2017-07-22 05:51



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 a la pregunta, a menos que la pregunta se haga en ese contexto específico ("Lo cual es más rápido usando gcc 4.7.2 para x86_64 con opciones predeterminadas? ", por ejemplo).

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

Me imagino que un compilador extremadamente ingenuo podría generar códigos de máquina diferentes para los dos formularios, al menos cuando se compilan sin solicitar la optimización.

Por otro lado, los compiladores C definitivamente deben evaluar algunos expresiones constantes en tiempo de 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 perezoso no tiene la opción de aplazar la evaluación de 2+2 hasta el tiempo de ejecución. Como un compilador debe tener la capacidad de evaluar expresiones constantes en tiempo de compilación, no hay una buena razón para que no aproveche esa capacidad incluso cuando no sea necesario.

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

Una instrucción de iteración causa una declaración llamada cuerpo de bucle ser   ejecutado repetidamente hasta que la expresión de control se compare igual a   0.

Entonces las expresiones constantes relevantes son 1 == 0 y 2 == 0, ambos de los cuales evalúan al int valor 0. (Esta comparación está implícita en la semántica de la while lazo; no existen como expresiones C reales).

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

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

Si su compilador genera un código diferente para las dos construcciones, primero compruebe si las secuencias de códigos diferentes tienen un rendimiento diferente. Si lo hacen, intente compilar de nuevo 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 no cumplir con el estándar C, pero es casi seguro que un problema que debe corregirse.

Línea de fondo: while (1) y while(2)  casi sin duda tienen el mismo rendimiento. Tienen exactamente la misma semántica, y no hay una buena razón para que ningún compilador genere código idéntico.

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

(Hay otra pregunta implícita en la pregunta: ¿Cómo lidiar con un entrevistador que insiste en un punto técnico incorrecto? Esa sería probablemente una buena pregunta para el sitio de Workplace)


149
2017-07-21 00:35



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

enter image description here

Ya es suficientemente malo el entrevistador mismo ha fallado esta entrevista, ¿Qué pasa si otros programadores de esta compañía han "aprobado" esta prueba?

No. Evaluando las declaraciones 1 == 0 y 2 == 0  debiera ser igualmente rápido. Nosotros podría imaginar implementaciones pobres del compilador donde uno podría ser más rápido que el otro. Pero no hay bueno por lo que uno debería ser más rápido que el otro.

Incluso si hay alguna circunstancia oscura cuando la afirmación sería cierta, los programadores no deberían ser evaluados basándose en el conocimiento de trivialidades oscuras (y en este caso espeluznantes). No te preocupes por esta entrevista, la mejor movida aquí es alejarte.

Renuncia: Esta NO es una caricatura original de Dilbert. Esto es meramente un Triturar.


129
2017-07-24 18:31



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 al contestar como lo hiciste, ahorraste un tiempo que de otra forma desperdiciarías 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 optimizado.


75
2017-07-20 07:59



La explicación más probable para la pregunta es que el entrevistador piensa 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?" algoritmo comienza desde el lado derecho del número y tiene que verificar cada bit hasta que llegue a un bit distinto de cero, el while(1) { } loop debería verificar el doble de bits por iteración que el while(2) { } lazo.

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


58
2017-07-21 14:41



Por supuesto que no conozco las verdaderas intenciones 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.

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

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


32
2017-07-22 03:17



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

En ese momento, los programadores dedicaron un considerable porcentaje de su tiempo a probar varios métodos para hacer que su código fuera más rápido y más eficiente ya que el tiempo de CPU de "la minicomputadora central" era tan valioso. Al igual que las personas que escriben compiladores. Supongo que el único compilador que su compañía puso a disposición en ese momento optimizó sobre la base de 'declaraciones frecuentes que pueden optimizarse' y tomó un pequeño atajo cuando se encontró con un momento (1) y evaluó todo else, incluso un tiempo (2). Habiendo tenido tal experiencia podría explicar su posición y su confianza en ella.

El mejor enfoque para conseguir que lo contraten es, probablemente, uno que le permita al gerente retirarse y darle una conferencia de 2-3 minutos sobre "los viejos tiempos de la programación" antes de USTED suavemente conducirlo hacia el siguiente tema de la entrevista. (El buen momento es importante aquí - demasiado rápido y estás interrumpiendo la historia - demasiado lento y estás etiquetado 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.


25
2017-07-22 22:30



Deberías haberle preguntado cómo llegó a esa conclusión. Bajo cualquier compilador decente, los dos compilan las mismas instrucciones de asm. Entonces, debería haberte dicho que también el compilador comience. Y aún así, debería conocer muy bien el compilador y la plataforma para incluso hacer una conjetura 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 en este detalle.


19
2017-07-20 08:13