performance - que - tipos de compiladores
¿Por qué los compiladores son tan estúpidos? (28)
Siempre me pregunto por qué los compiladores no pueden descifrar cosas simples que son obvias para el ojo humano. Hacen muchas optimizaciones simples, pero nunca algo incluso un poco complejo. Por ejemplo, este código tarda aproximadamente 6 segundos en mi computadora para imprimir el valor cero (usando java 1.6):
int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
x += x + x + x + x + x;
}
System.out.println(x);
Es totalmente obvio que x nunca cambia, por lo que no importa la frecuencia con la que se agrega 0 a sí mismo, permanece cero. Entonces, el compilador en teoría podría reemplazar esto con System.out.println (0).
O mejor aún, esto demora 23 segundos:
public int slow() {
String s = "x";
for (int i = 0; i < 100000; ++i) {
s += "x";
}
return 10;
}
Primero, el compilador podría notar que realmente estoy creando una cadena de 100000 "x" para que pueda usar s StringBuilder automáticamente, o incluso mejor, reemplazarlo directamente con la cadena resultante, ya que siempre es el mismo. Segundo, ¡no reconoce que en realidad no uso la cadena para que todo el ciclo pueda descartarse!
¿Por qué, después de que tanta mano de obra entra en compiladores rápidos, siguen siendo tan tontos?
EDITAR : por supuesto, estos son ejemplos estúpidos que nunca deberían usarse en ningún lado. Pero cada vez que tengo que reescribir un código hermoso y muy legible en algo ilegible para que el compilador esté contento y produzca código rápido, me pregunto por qué los compiladores o alguna otra herramienta automatizada no pueden hacer este trabajo por mí.
No me gusta hablar de esto en una vieja pregunta tan (cómo he llegado hasta aquí, de todos modos?), Pero creo que parte de esto podría ser algo así como un reducto de los días de la Commodore 64.
A principios de la década de 1980, todo transcurrió en un reloj fijo. No hubo Turbo Impulsar y el código siempre fue creado para un sistema específico con un procesador específico y la memoria específica, etc. En Commodore BASIC, el método estándar para la implementación de delays se parecía mucho a:
10 FOR X = 1 TO 1000
20 NEXT : REM 1-SECOND DELAY
(En realidad, en la práctica, más se parecía mucho 10FORX=1TO1000:NEXT, pero ya sabes lo que quiero decir.)
Si fueran a optimizar esto, sería romper todo-nada nunca podría ser el tiempo. No sé de ningún ejemplo, pero estoy seguro de que hay un montón de pequeñas cosas como esta dispersos a través de la historia de los lenguajes compilados que impedían cosas de ser optimizado.
Es cierto que estos no-optimizaciones no son necesarios hoy en día. Probablemente hay, sin embargo, alguna regla no escrita entre los desarrolladores del compilador no para optimizar este tipo de cosas. No sabría.
Sólo se alegre de que el código está optimizado tanto, a diferencia de código en el C64. Viendo un mapa de bits en el C64 podría tardar hasta 60 segundos con los bucles básicos más eficientes; por lo tanto, la mayoría de los juegos, etc. fueron escritos en lenguaje de máquina. Escribiendo juegos en lenguaje de máquina no es divertido.
Sólo mis pensamientos.
Premisa: Estudié en la universidad compiladores.
El compilador javac es extremadamente estúpida y realiza ninguna optimización porque se basa en el tiempo de ejecución de Java para hacerlas. El tiempo de ejecución se captura esa cosa y optimizarlo, pero va a tomar sólo después de la operación se ejecuta unos pocos miles de veces.
Si utiliza una mejor compilador (como gcc) que permite optimizaciones, optimizará su código, porque es toda una optimización obvia de hacerlo.
¿Compiló para liberar el código? Creo que un buen compilador detecta en su segundo ejemplo que la cadena nunca se usa y elimina todo el ciclo.
¿Seriamente? ¿Por qué alguien escribiría un código del mundo real como ese? En mi humilde opinión, el código, no el compilador es la entidad "estúpida" aquí. Por mi parte, estoy perfectamente feliz de que los escritores de compiladores no se molesten en perder el tiempo tratando de optimizar algo así.
Edición / aclaración: Sé que el código de la pregunta es solo un ejemplo, pero eso prueba mi punto: o tienes que intentarlo, o no tienes ni idea de escribir un código supremamente ineficiente como ese. No es tarea del compilador sostenernos de la mano para no escribir código horrible. Es nuestra responsabilidad, como personas que escriben el código, saber lo suficiente sobre nuestras herramientas para escribir de manera eficiente y clara.
Casi se considera una mala práctica optimizar cosas como esta cuando se compila en un bytecode de JVM. Sun''s javac tiene algunas optimizaciones básicas, al igual que scalac , groovyc , etc. En resumen, cualquier cosa que sea verdaderamente específica del lenguaje puede optimizarse dentro del compilador. Sin embargo, cosas como esta, que obviamente son tan artificiales como para ser independientes del idioma, pasarán simplemente fuera de la política.
La razón de esto es que permite que HotSpot tenga una vista mucho más consistente del bytecode y sus patrones. Si los compiladores comienzan a perder el conocimiento con casos extremos, eso reduce la capacidad de la máquina virtual de optimizar el caso general, que puede no ser aparente en el momento de la compilación. A Steve Yeggie le gusta insistir en esto: la optimización a menudo es más fácil cuando se realiza en tiempo de ejecución mediante una ingeniosa máquina virtual. Incluso llegó a afirmar que HotSpot elimina las optimizaciones de javac. Si bien no sé si esto es cierto, no me sorprendería.
Para resumir: los compiladores que se dirigen a máquinas virtuales tienen un conjunto de criterios muy diferente, particularmente en el área de optimización y cuando es apropiado. No culpe a los escritores del compilador por dejar el trabajo en la JVM mucho más capaz. Como se señaló varias veces en este hilo, los compiladores modernos que apuntan a la arquitectura nativa (como la familia gcc ) son extremadamente inteligentes, produciendo código obscenamente rápido a través de algunas optimizaciones muy inteligentes.
Como otros han abordado la primera parte de su pregunta de forma adecuada, intentaré abordar la segunda parte, es decir, "automáticamente usa StringBuilder".
Hay varias buenas razones para no hacer lo que está sugiriendo, pero el factor más importante en la práctica es probable que el optimizador funcione mucho después de que el código fuente real haya sido digerido y olvidado. Los optimizadores generalmente operan en el código de bytes generado (o ensamblado, código de tres direcciones, código de máquina, etc.) o en los árboles de sintaxis abstracta que resultan de analizar el código. Los optimizadores generalmente no conocen nada de las bibliotecas de tiempo de ejecución (o de ninguna biblioteca en absoluto), y en su lugar operan en el nivel de instrucción (es decir, flujo de control de bajo nivel y asignación de registro).
En segundo lugar, a medida que las bibliotecas evolucionan (especialmente en Java) mucho más rápido que los lenguajes, mantenerse al día con ellos y saber qué es lo que menosprecia qué y qué otro componente de la biblioteca podría ser más adecuado para la tarea sería una tarea hercúlea. También es probable que sea imposible, ya que este optimizador propuesto tendría que comprender con precisión tanto su intención como la intención de cada componente de biblioteca disponible, y de alguna manera encontrar un mapeo entre ellos.
Finalmente, como otros han dicho (creo), el escritor del compilador / optimizador puede suponer razonablemente que el programador que escribe el código de entrada no tiene muerte cerebral. Sería una pérdida de tiempo dedicar un esfuerzo significativo a resolver casos especiales como estos cuando abundan otras optimizaciones más generales. Además, como también han mencionado otros, el código aparentemente con muerte cerebral puede tener un propósito real (un bloqueo de giro, espera ocupada antes de un rendimiento a nivel del sistema, etc.), y el compilador tiene que respetar lo que el programador solicita (si es sintáctica y semánticamente válido).
Creo que está subestimando cuánto trabajo es para asegurarse de que una parte del código no afecte a otra parte del código. Con solo un pequeño cambio en los ejemplos x, i y s, todos podrían apuntar a la misma memoria. Una vez que una de las variables es un puntero, es mucho más difícil saber qué código puede tener efectos secundarios, dependiendo de qué punto señalar.
Además, creo que las personas que programan cumplidores preferirían perder tiempo haciendo optimizaciones que no son tan fáciles de hacer para los humanos.
De lo que más te quejas es ''¿por qué el compilador de Java es tan estúpido?'', Ya que la mayoría de los compiladores de otros lenguajes son mucho más inteligentes.
La razón de la estupidez de los compiladores de Java es histórica. En primer lugar, las implementaciones originales de java se basaban en el intérprete y el rendimiento se consideraba poco importante. En segundo lugar, muchos de los puntos de referencia de Java originales eran problemáticos para optimizar. Recuerdo un punto de referencia que se parecía mucho a tu segundo ejemplo. Desafortunadamente, si el compilador optimiza el bucle de distancia, el índice de referencia obtendría una excepción de división por cero cuando intentara dividir un número de referencia por el tiempo transcurrido para calcular su puntaje de rendimiento. Por lo tanto, al escribir un compilador optimizado para Java, tenía que tener mucho cuidado de NO optimizar algunas cosas, ya que las personas afirmarían que su compilador no funcionaba.
El compilador HotSpot JIT solo optimizará el código que se ha estado ejecutando durante un tiempo. Para cuando su código esté caliente, el bucle ya se ha iniciado y el compilador JIT debe esperar hasta la próxima vez que se ingrese el método para buscar formas de optimizar el bucle. Si llama al método varias veces, es posible que vea un mejor rendimiento.
Esto está cubierto en las Preguntas frecuentes de HotSpot , bajo la pregunta "Escribo un ciclo simple para sincronizar una operación simple y es lento. ¿Qué estoy haciendo mal?".
En realidad, Java debería usar un generador de cadenas en su segundo ejemplo.
El problema básico al tratar de optimizar estos ejemplos es que hacerlo requeriría la demostración del teorema . Lo que significa que el compilador necesitaría construir una prueba matemática de lo que tu código realmente hará. Y esa no es una tarea pequeña en absoluto. De hecho, ser capaz de demostrar que todo código realmente tiene un efecto es equivalente al problema de detención.
Claro, puedes encontrar ejemplos triviales, pero la cantidad de ejemplos triviales es ilimitada. Siempre se puede pensar en otra cosa, por lo que no hay forma de atraparlos a todos.
Por supuesto, es posible que algún código se pruebe que no tiene ningún efecto, como en sus ejemplos. Lo que desearía hacer es hacer que el compilador optimice cada problema que pueda probarse sin usar en tiempo P.
Pero de todos modos, eso es mucho trabajo y no te da tanto. Las personas pasan mucho tiempo tratando de descubrir maneras de evitar que los programas tengan errores en ellas, y los sistemas de tipo como los de Java y Scala son intentos de prevenir errores, pero en este momento nadie está usando sistemas tipo para hacer declaraciones sobre el tiempo de ejecución , por lo que sé.
Es posible que desee buscar en Haskel, que creo que tiene la teoría más avanzada que prueba cosas, aunque no estoy seguro de eso. Yo no lo sé yo mismo.
Es una eterna carrera armamentista entre escritores de compiladores y programadores.
Los ejemplos no artificiales funcionan muy bien: la mayoría de los compiladores efectivamente optimizan el código obviamente inútil.
Los exámenes controlados siempre bloquearán el compilador. Prueba, si fue necesaria, de que cualquier programador es más inteligente que cualquier otro programa.
En el futuro, necesitará más ejemplos artificiales que el que ha publicado aquí.
Hablando desde un punto de vista C / C ++:
Su primer ejemplo será optimizado por la mayoría de los compiladores. Si el compilador Java de Sun realmente ejecuta este ciclo, es culpa de los compiladores, pero asuma mi palabra de que cualquier compilador de C, C ++ o Fortran publicado después de 1990 elimina por completo ese tipo de bucle.
Su segundo ejemplo no se puede optimizar en la mayoría de los idiomas porque la asignación de memoria ocurre como un efecto secundario de concatenación de cadenas. Si un compilador optimiza el código, el patrón de asignación de memoria cambiará, y esto podría generar efectos que el programador intenta evitar. La fragmentación de la memoria y los problemas relacionados son problemas que los programadores incrustados aún enfrentan todos los días.
En general, estoy satisfecho con las optimizaciones que los compiladores pueden hacer en estos días.
Los compiladores en general son muy inteligentes.
Lo que debes tener en cuenta es que deben tener en cuenta todas las posibles excepciones o situaciones en las que optimizar o volver a factorizar el código podría causar efectos secundarios no deseados.
Cosas como, programas con subprocesos, alias de puntero, código enlazado dinámicamente y efectos colaterales (llamadas de sistema / asignación de memoria) etc. hacen que la refacturación prooving formal sea muy difícil.
Aunque su ejemplo es simple, todavía puede haber situaciones difíciles a considerar.
En cuanto a su argumento de StringBuilder, NO es un trabajo de compiladores para elegir qué estructuras de datos usar para usted.
Si desea optimizaciones más potentes, cambie a un lenguaje con más caracteres fuertes, como fortran o haskell, donde los compiladores reciben mucha más información para trabajar.
La mayoría de los cursos que enseñan compiladores / optimización (incluso de forma automática) dan una sensación de aprecio acerca de cómo hacer formalmente proponer optimizaciones en lugar de piratear casos específicos es un problema muy difícil.
Porque simplemente no estamos allí todavía. Podrías tan fácilmente haber preguntado, "¿por qué todavía necesito escribir programas ... por qué no puedo simplemente ingresar el documento de requisitos y hacer que la computadora escriba la aplicación para mí?"
Los escritores de compilación pasan tiempo en las pequeñas cosas, porque esos son los tipos de cosas que los programadores de aplicaciones tienden a perder.
Además, no pueden asumir demasiado (¿tal vez tu ciclo fue algún tipo de demora en el ghetto o algo así)?
Este es un ejemplo de código de procedimiento v. Código funcional.
Usted ha detallado un procedimiento para el compilador a seguir, por lo que las optimizaciones van a ser en torno al procedimiento detallado y reducirá al mínimo cualquier efecto secundario o no optimizar donde no va a hacer lo que usted espera. Esto hace que sea más fácil de depurar.
Si se pone en una descripción del funcionamiento de lo que quiere, por ejemplo. SQL, entonces están dando el compilador de una amplia gama de opciones para optimizar.
Tal vez algún tipo de análisis de código sería capaz de encontrar este tipo de problema o perfilado en tiempo de ejecución, pero entonces tendrá que cambiar la fuente a algo más sensata.
Nunca he visto el punto de eliminación de código muerto en el primer lugar. ¿Por qué el programador de escribir que ?? Si vas a hacer algo sobre el código muerto, declarar que un error de compilación! Es casi seguro que significa que el programador ha cometido un error - y para los pocos casos que no, una directiva de compilación de utilizar una variable sería la respuesta adecuada. Si pongo el código muerto en una rutina quiero que ejecuta - Estoy probablemente planificación para inspeccionar los resultados en el depurador.
El caso en el que el compilador podría hacer algo bueno está sacando invariantes de bucle. A veces la claridad dice que codificar el cálculo en el bucle y tener el compilador de tracción tales cosas sería bueno.
Obliga a usted (el programador) a pensar en lo que estás escribiendo. Obligando a los compiladores a hacer su trabajo para usted no ayuda a nadie: hace que los compiladores mucho más complejo, y te hace más estúpidos y menos atento a su código (y más lento!).
En su primer ejemplo, es una optimización que solo funciona si el valor es cero. La declaración if extra en el compilador necesaria para buscar esta cláusula rara vez vista puede no valer la pena (ya que tendrá que verificar esto en cada variable). Además, ¿qué tal esto?
int x = 1;
int y = 1;
int z = x - y;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
z += z + z + z + z + z;
}
System.out.println(z);
Obviamente, esto sigue siendo lo mismo, pero ahora hay un caso adicional que tenemos que codificar en el compilador. Hay un número infinito de formas en que puede terminar siendo cero y no vale la pena codificarlo, y supongo que podrías decir que si vas a tener uno de ellos, podrías tenerlos a todos.
Algunas optimizaciones se ocupan del segundo ejemplo que ha publicado, pero creo que lo he visto más en lenguajes funcionales y no tanto en Java. Lo más importante que lo hace difícil en los idiomas más nuevos es el parche de monos . Ahora += puede tener un efecto secundario, lo que significa que si lo optimizamos, es potencialmente incorrecto (por ejemplo, agregar funcionalidad a += que imprime el valor actual significará un programa diferente por completo).
Pero todo se reduce a lo mismo una y otra vez: hay demasiados casos que debes buscar para asegurarte de que no se estén produciendo efectos secundarios que puedan alterar el estado del programa final.
Simplemente es más fácil tomar un momento extra y asegurarse de que lo que está escribiendo sea lo que realmente quiere que haga la computadora. :)
Los compiladores son tan inteligentes como los hacemos. No sé demasiados programadores que molestarían a escribir un compilador que comprobar si hay construcciones tales como los que utilizó. La mayoría se concentra en las formas más típicas para mejorar el rendimiento.
Es posible que algún día vamos a tener el software, incluyendo compiladores, que en realidad puede aprender y crecer. Cuando llegue ese día más, a lo mejor de todo, los programadores estarán fuera de trabajo.
Los compiladores que pueden hacer optimizaciones estricta-aliasing, optimizarán primer ejemplo cabo. Ver aquí .
Segundo ejemplo no puede ser optimizado debido a que la parte más lenta aquí es la memoria de asignación / reasignación y el operador + = se redefine en una función que hace las cosas de memoria. Diferentes implementaciones de cuerdas utilizan diferentes estrategias de asignación.
Yo también preferiría gustaría tener malloc (100000) que miles de malloc (100) demasiado al hacer s + = "s"; pero en este momento lo que está fuera del alcance de los compiladores y tiene que ser optimizada por la gente. Esto es lo que el lenguaje D trata de resolver mediante la introducción de funciones puras .
Como se ha mencionado aquí en otras respuestas, Perl segundo ejemplo hace en menos de un segundo, ya que asigna más memoria de la que solicitada por si acaso se necesita más memoria más adelante.
Bueno, solo puedo hablar de C ++, porque soy un principiante de Java totalmente. En C ++, los compiladores son libres de ignorar cualquier requisito de idioma establecido por el Estándar, siempre y cuando el comportamiento observable sea el mismo si el compilador realmente emuló todas las reglas establecidas por el Estándar. El comportamiento observable se define como cualquier lectura y escritura en datos volátiles y llamadas a funciones de la biblioteca . Considera esto:
extern int x; // defined elsewhere
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
x += x + x + x + x + x;
}
return x;
El compilador de C ++ tiene permitido optimizar ese fragmento de código y solo agregar el valor adecuado a x que resultaría de ese bucle una vez, porque el código se comporta como si el bucle nunca hubiera sucedido y no hubiera datos volátiles ni funciones de biblioteca involucradas. eso podría causar efectos secundarios necesarios. Ahora considere las variables volátiles:
extern volatile int x; // defined elsewhere
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
x += x + x + x + x + x;
}
return x;
El compilador ya no puede hacer la misma optimización, porque no puede probar que los efectos secundarios causados por escribir en x no puedan afectar el comportamiento observable del programa. Después de todo, x podría establecerse en una celda de memoria vigilada por algún dispositivo de hardware que se activaría en cada escritura.
Hablando de Java, he probado tu loop, y sucede que el compilador Java de GNU ( gcj ) tarda demasiado tiempo en terminar tu ciclo (simplemente no terminó y lo maté). Activaba indicadores de optimización (-O2) y sucedió que se imprimió 0 inmediatamente:
[js@HOST2 java]$ gcj --main=Optimize -O2 Optimize.java
[js@HOST2 java]$ ./a.out
0
[js@HOST2 java]$
Tal vez esa observación podría ser útil en este hilo? ¿Por qué es tan rápido para gcj? Bueno, una de las razones es que gcj se compila en código máquina, por lo que no tiene posibilidad de optimizar ese código en función del comportamiento en tiempo de ejecución del código. Se necesita toda su fortaleza y trata de optimizar todo lo que pueda en tiempo de compilación. Sin embargo, una máquina virtual puede compilar el código Just in Time, ya que esta salida de Java se muestra para este código:
class Optimize {
private static int doIt() {
int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
x += x + x + x + x + x;
}
return x;
}
public static void main(String[] args) {
for(int i=0;i<5;i++) {
doIt();
}
}
}
Salida para java -XX:+PrintCompilation Optimize :
1 java.lang.String::hashCode (60 bytes)
1% Optimize::doIt @ 4 (30 bytes)
2 Optimize::doIt (30 bytes)
Como vemos, JIT compila la función doIt 2 veces. Basado en la observación de la primera ejecución, la compila por segunda vez. Pero sucede que tiene el mismo tamaño que bytecode dos veces, lo que sugiere que el bucle todavía está en su lugar.
Como muestra otro programador, el tiempo de ejecución para ciertos bucles muertos incluso aumenta en algunos casos para el código compilado posteriormente. Informó sobre un error que se puede leer aquí , y es el 24 de octubre de 2008.
Debido a que los autores de compiladores intentan añadir optimizaciones para las cosas que importan (espero) y que se miden en los puntos de referencia de piedra * (me temo).
Hay millones y millones de otros fragmentos de código posible como la suya, que no hacen nada y podría ser optimizados con el aumento del esfuerzo sobre el escritor del compilador, pero que casi nunca se encuentran.
Lo que siento vergüenza es que incluso hoy en día la mayoría de los compiladores generan código para comprobar la switchValue es mayor que 255 para un interruptor denso o casi lleno en un carácter sin signo. Eso se suma a 2 Instrucciones de bucle interno más el código de bytes de intérprete.
El significado de los dos ejemplos es inútil, inútil y sólo hizo para engañar al compilador.
El compilador no es capaz (y no debe ser) para ver el significado de un método, un bucle o un programa. Ahí es donde entra en la imagen. Se crea un método para una cierta funcionalidad / significado, no importa lo estúpido que es. Es el mismo caso para los problemas simples o complejos programas extremas.
En su caso, el compilador puede optimizar, porque "piensa" que debe ser optimizado de otra forma, pero ¿por qué alojarse allí?
otra situación extrema. Tenemos un compilador inteligente compilación de Windows. Toneladas de código para compilar. Pero si es inteligente, hierve abajo a 3 líneas de código ...
"starting windows"
"enjoy freecell/solitaire"
"shutting down windows"
El resto del código es obsoleto, porque nunca ha utilizado, tocado, visitada. ¿En verdad queremos eso?
Los compiladores están diseñados para ser predecibles . Esto puede hacer que se vean estúpidos de vez en cuando, pero eso está bien. Los objetivos del escritor del compilador son
Debería poder mirar su código y hacer predicciones razonables sobre su desempeño.
Pequeños cambios en el código no deberían generar diferencias dramáticas en el rendimiento.
Si un pequeño cambio le parece al programador que debería mejorar el rendimiento, al menos no debería degradar el rendimiento (a menos que suceda algo sorprendente en el hardware).
Todos estos criterios van en contra de las optimizaciones "mágicas" que se aplican solo a casos de esquina.
Ambos ejemplos tienen una variable actualizada en un bucle pero no se usa en ningún otro lado . En realidad, este caso es bastante difícil de recoger a menos que esté utilizando algún tipo de marco que pueda combinar la eliminación de código muerto con otras optimizaciones como la propagación de copias o la propagación constante. Para un optimizador de flujo de datos simple, la variable no parece estar muerta. Para comprender por qué este problema es difícil, consulte el documento de Lerner, Grove y Chambers en POPL 2002 , que usa este mismo ejemplo y explica por qué es difícil.
Oh, no sé. A veces los compiladores son bastante inteligentes. Considere el siguiente programa C:
#include <stdio.h> /* printf() */
int factorial(int n) {
return n == 0 ? 1 : n * factorial(n - 1);
}
int main() {
int n = 10;
printf("factorial(%d) = %d/n", n, factorial(n));
return 0;
}
En mi versión de GCC (4.3.2 en las pruebas de Debian ), cuando se compila sin optimizaciones, o -O1, genera código para factorial () como era de esperar, usando una llamada recursiva para calcular el valor. Pero en -O2, hace algo interesante: se compila en un ciclo cerrado:
factorial:
.LFB13:
testl %edi, %edi
movl $1, %eax
je .L3
.p2align 4,,10
.p2align 3
.L4:
imull %edi, %eax
subl $1, %edi
jne .L4
.L3:
rep
ret
Muy impresionante. La llamada recursiva (ni siquiera recursiva de cola) se ha eliminado por completo, por lo que factorial ahora usa O (1) espacio de pila en lugar de O (N). Y aunque solo tengo un conocimiento muy superficial del ensamblaje x86 (en realidad, AMD64 en este caso, pero no creo que ninguna de las extensiones AMD64 se estén utilizando anteriormente), dudo que pueda escribir una versión mejor a mano. Pero lo que realmente me impresionó fue el código que generó en -O3. La implementación de factorial se mantuvo igual. Pero main () cambió:
main:
.LFB14:
subq $8, %rsp
.LCFI0:
movl $3628800, %edx
movl $10, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
addq $8, %rsp
ret
¿Ves la línea movl $3628800, %edx ? gcc es un factorial de precomputación (10) en tiempo de compilación. Ni siquiera llama a factorial (). Increíble. Mi sombrero está fuera del equipo de desarrollo de GCC.
Por supuesto, se aplican todos los descargos de responsabilidad habituales, esto es solo un ejemplo de juguete, la optimización prematura es la raíz de todo mal, etc., pero ilustra que los compiladores suelen ser más inteligentes de lo que crees. Si crees que puedes hacer un mejor trabajo a mano, casi seguro que estás equivocado.
(Adaptado de una publicación en mi blog )
En el modo de disparo VS 2010 C ++ esto no toma ningún tiempo para correr. Sin embargo el modo de depuración es otra historia.
#include <stdio.h>
int main()
{
int x = 0;
for (int i = 0; i < 100 * 1000 * 1000 * 1000; ++i) {
x += x + x + x + x + x;
}
printf("%d", x);
}
En mi opinión, no creo que el trabajo del compilador sea corregir lo que, honestamente, es una mala codificación. Usted, explícitamente, le dijo al compilador que quiere que se ejecute el primer bucle. Es lo mismo que:
x = 0
sleep 6 // Let''s assume this is defined somewhere.
print x
No me gustaría que el compilador elimine mi frase de sleep solo porque no hizo nada. Puede argumentar que la declaración de suspensión es una solicitud explícita de una demora, mientras que su ejemplo no lo es. Pero luego permitirá que el compilador tome decisiones de alto nivel sobre lo que su código debería hacer, y creo que eso es algo malo.
El código y el compilador que lo procesa son herramientas y usted debe ser un herrero de herramientas si desea usarlos de manera efectiva. ¿Cuántas motosierras de 12 "se negarán a intentar talar un árbol de 30"? ¿Cuántas fresas cambiarán automáticamente al modo martillo si detectan una pared de concreto?
Ninguno, sospecho, y esto se debe a que el costo de diseñar esto en el producto sería horrendo para empezar. Pero, lo que es más importante, no debe usar taladros o motosierras si no sabe lo que hace. Por ejemplo: si no sabe qué es el retroceso (una manera muy fácil para que un novato se quite el brazo), aléjese de las motosierras hasta que lo haga.
Estoy a favor de permitir que los compiladores sugieran mejoras, pero prefiero mantener el control yo mismo. No debería depender del compilador decidir unilateralmente que un ciclo es innecesario.
Por ejemplo, hice loops de temporización en sistemas integrados donde la velocidad de reloj de la CPU se conoce exactamente, pero no hay un dispositivo de tiempo confiable disponible. En ese caso, puede calcular con precisión la duración de un bucle determinado y utilizarlo para controlar la frecuencia con la que suceden las cosas. Eso no funcionaría si el compilador (o el ensamblador en ese caso) decidiera que mi ciclo era inútil y lo hubiera optimizado para que no existiera.
Habiendo dicho eso, permítanme que les deje con una vieja historia de un compilador VAX FORTRAN que estaba experimentando un punto de referencia para el rendimiento y se encontró que era muchos órdenes de magnitud más rápido que su competidor más cercano.
Resultó que el compilador notó que el resultado de los bucles de referencia no se estaba utilizando en ningún otro lado y optimizó los bucles en el olvido.
optimización absoluta es un problema indecidible, lo que significa, no hay ninguna máquina de Turing (y, por lo tanto, ningún programa de ordenador) que pueden producir la versión óptima de cualquier programa dado.
Algunas optimizaciones simples pueden ser (y, de hecho, están) hecho, pero, en los ejemplos que diste ...
Para detectar que su primer programa imprime siempre cero, el compilador tendría que detectar que x se mantiene constante a pesar de todas las iteraciones del bucle. ¿Cómo se puede explicar (lo sé, no es la mejor palabra, pero no puedo pensar en otro) que a un compilador?
¿Cómo puede el compilador sabe que el StringBuilder es la herramienta adecuada para el trabajo sin ninguna referencia a ella?
En una aplicación real, si la eficiencia es fundamental en una parte de su solicitud, que debe estar escrito en un lenguaje de bajo nivel como C (Jaja, en serio, he escrito esto?)