tengo - ¿Cuál es más rápido: mientras que(1) o mientras que(2)?

trucos para no comer (22)

¡Otra respuesta a esa pregunta sería ver si tiene valor para decirle a su gerente que él / ella está equivocado! Y cuan suavemente puedes comunicarlo.

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

Esta fue una pregunta de entrevista hecha por un alto directivo.

¿Cual es mas rápido?

while(1) { // Some code }

while(2) { //Some code }

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

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

¿Es esto cierto?

Consulte también: ¿Es "for (;;)" 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 programas siguientes 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.

Para referencia, aquí está el ensamblado generado (usando gcc main.c -S -masm=intel con 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 -O2 y -O2 (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 el ensamblaje muy bien, pero esto obviamente es un bucle incondicional. La instrucción jmp restablece incondicionalmente el programa de nuevo a la etiqueta .L2 sin siquiera comparar un valor con verdadero, y por supuesto lo vuelve a hacer hasta que el programa finaliza 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 ( jmp incondicional) 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 llaman x 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 (devolviendo 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 superior, ambos producen el mismo ensamblaje que los ejemplos anteriores (un jmp incondicional de nuevo a la etiqueta anterior).

TL; DR

Bajo GCC, los diferentes bucles se compilan a 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 se puede evaluar solo mirando el código fuente.
El compilador debe ser lo suficientemente inteligente como para optimizar tales casos triviales. Los programadores no deben perder su tiempo pensando en ellos en la gran mayoría de los casos.

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

En ese momento, los programadores pasaron 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 de "la minicomputadora central" era tan valioso. Al igual que la gente escribía compiladores Supongo que el compilador único que su compañía puso a disposición en ese momento se optimizó sobre la base de ''declaraciones frecuentes que pueden optimizarse'' y tomó un poco de atajo cuando se encontró con un momento (1) y evaluó todo más, incluyendo un tiempo (2). Haber 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 permita que el gerente senior se deje llevar y le dé una conferencia de 2 a 3 minutos sobre "los viejos tiempos de la programación" antes de que lo lleve sin problemas hacia el próximo tema de la entrevista. (El momento oportuno 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 saber más sobre este tema.

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

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

Ya es bastante malo que el entrevistador mismo haya fallado esta entrevista, ¿qué sucede si otros programadores de esta compañía han "aprobado" esta prueba?

No. La evaluación de las afirmaciones 1 == 0 y 2 == 0 debe ser igualmente rápida. Podríamos imaginar implementaciones de compilador pobres donde una podría ser más rápida que la otra. Pero no hay una buena razón para que uno sea 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 deben ser evaluados basándose en el conocimiento de trivias oscuras (y en este caso, espeluznantes). No te preocupes por esta entrevista, el mejor movimiento aquí es alejarte.

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

La explicación más probable para la pregunta es que el entrevistador piensa que el procesador comprueba 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 debe verificar cada bit hasta que alcance un bit distinto de cero, el bucle while(1) { } tendría que 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 verificar 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 .

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

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

Puedo imaginar 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 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. Dado que un compilador tiene que 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 necesario.

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

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

Así que las expresiones constantes relevantes son 1 == 0 y 2 == 0 , las cuales se evalúan al valor int 0 . (Estas comparaciones están implícitas en la semántica del bucle while; 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 1 como un caso especial), y para el segundo podría generar una comparación de tiempo de ejecución explícita equivalente a 2 != 0 . Pero nunca me he encontrado con un compilador de C que realmente se comportaría de esa manera, y dudo seriamente que exista tal compilador.

La mayoría de los compiladores (estoy tentado de decir que todos los compiladores de calidad de producción) tienen opciones para solicitar optimizaciones adicionales. Bajo tal opción, es incluso 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ódigos 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 de conformidad con el estándar C, pero es casi seguro que es un problema que debe corregirse.

Conclusión: 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 que un compilador genere un código más rápido para while(1) que para while(2) , es igualmente legal que un compilador genere un 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 que usted hizo: ¿Cómo trata a un entrevistador que insiste en un punto técnico incorrecto? Probablemente sería una buena pregunta para el sitio de Workplace ).

Me parece que esta es una de esas preguntas de entrevista de comportamiento 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 da la respuesta correcta, el entrevistador les dirá que están equivocados.

La empresa quiere ver cómo reaccionarás ante esta situación. ¿Te sientas allí tranquilamente 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 con respeto.

Por el bien de esta pregunta, debo agregar que recuerdo a Doug Gwyn, del Comité C, que escribió que algunos compiladores de C tempranos sin el pase del optimizador generarían una prueba en ensamblador para el while(1) (en comparación con for(;;) que no No lo tengo).

Le respondería al entrevistador con esta nota histórica y luego le diría que, aunque me sorprendería mucho si el compilador hiciera esto, un compilador podría tener:

sin optimizador pasar el compilador generar una prueba para ambos while(1) y while(2)
con el pase del optimizador se le indica al compilador que optimice (con un salto incondicional) todo el while(1) porque se consideran idiomáticos. Esto dejaría el while(2) con una prueba y, por lo tanto, hace una diferencia de rendimiento entre las dos.

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

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

Te llevaron a un conflicto. Si esto es cierto, son inteligentes y la pregunta fue buena. Para algunas industrias, como la banca, publicar su problema en podría ser una razón para el rechazo.

Pero claro que no lo sé, solo te propongo una opción.

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

Si 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? ¿Utilizan los mantenedores de este código base while(n) como un mecanismo de comentario oscuro para hacer que los bucles se vean diferentes? ¿Es una solución burda para una advertencia falsa en alguna herramienta de análisis estático rota? ¿O es esto una pista de que estoy leyendo el código generado? ¿Es un error que resulta de una búsqueda y reemplazo de todo mal aconsejado, o de una mala combinación o de un rayo cósmico? Tal vez esta línea de código se supone que 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. El while(2) puede consumir varios minutos de mi tiempo, while(1) que while(1) hubiera tomado una fracción de segundo!

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

Si estás preocupado por la optimización, debes usar

for (;;)

Porque eso no tiene pruebas. (modo cínico)

Solía programar C y el código de ensamblaje cuando este tipo de tonterías podría haber marcado la diferencia. Cuando hizo una diferencia lo escribimos en Asamblea.

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

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 igual de 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 es una tontería; probar tu confianza de nuevo)

Entonces, al responder como lo hizo, ahorró un tiempo que de lo contrario perdería al analizar 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 las optimizaciones activadas:

xxx: jmp xxx

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

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

Mi respuesta sería: No importa mucho, prefiero enfocarme en el problema de negocios que estamos resolviendo. Después de todo, para eso me van a pagar.

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

Ahora ve a escribir algún código. ;-)

A juzgar por la cantidad de tiempo y esfuerzo que ha gastado la gente probando, probando y respondiendo a esta pregunta muy directa, digo que ambas se hicieron muy lentas al hacer la pregunta.

Y así, para pasar aún más tiempo en él ...

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

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

El "1" simplemente está ahí para evaluar siempre a verdadero y, por lo tanto, para decir "while (2)" es tan tonto como decir "while (1 + 1 == 2)", que también se 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 programador hizo un error tipográfico que no afectó la ejecución del código, pero si él usó intencionalmente el "2" solo para ser extraño, entonces sáquelo antes de que ponga algo extraño a lo largo de su código haciendo que sea difícil Leer y trabajar con.

Ambos son iguales, iguales.

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

Eso depende del compilador.

Si optimiza el código, o si evalúa que 1 y 2 sean verdaderos 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 evalúe de manera diferente.

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

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

Razonamiento básico. Ambos bucles son infinitos, es difícil hablar de rendimiento.
Conocimientos sobre los niveles de optimización. Quería saber de ti si permites que el compilador haga alguna optimización por ti, optimizaría la condición, especialmente si el bloque no estaba vacío.
Conocimientos sobre arquitectura de microprocesadores. La mayoría de las arquitecturas tienen una instrucción de CPU especial para la comparación 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 algún 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. Un solo bucle podría estar completamente dentro de una línea de caché, o al comienzo de una línea de caché, o podría separarse de dos líneas de caché. Y como resultado, lo que el entrevistador afirma que es más rápido, en realidad podría ser más rápido, por coincidencia.

El peor escenario posible: un compilador optimizado 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 bucle.

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

Cautela: debe asegurarse de que el bucle 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, personalmente preferiría el uso de do {} while (42) ya que cualquier entero, excepto 0, haría el trabajo.

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

El código optimiza el bucle para
cmp eax, 2
Cuando ocurre la resta estás esencialmente restando
a. 00000000 - 00000010 cmp eax, 2
en lugar de
segundo. 00000000 - 00000001 cmp eax, 1

cmpsólo establece banderas y no establece un resultado. Entonces, en las partes menos significativas, sabemos si necesitamos o no un préstamo con b . Mientras que con un tiene que realizar dos restas antes de obtener un préstamo.