domingo, enero 27, 2008

Optimización de código en Java

Hace poco descubrí algo que me dejó algo trastornando.

Java no realiza optimización de código (Con Java me refiero a javac). Increíble pero cierto.

Hace poco, en esos impulsos que no tengo idea de donde surgen me dieron ganas de hacer un pequeño lenguaje de programación. Una vez realicé uno que generaba código para Parrot usando SableCC, pero como suele suceder con las cosas que no se hacen con gusto, éste lenguaje de programación cumplía exclusivamente lo que pedía el profesor sin hacer ningún tipo de innovación.

Pues bien, en estos momentos no tengo claro que código generaré... He estado mirando otras opciones que me sugirieron y tal vez me decida por la VM de Lua o Ocaml. Pero también me pasó en algún momento por la cabeza generar para la JVM y pues estaba viendo bytecode y me dio por hacer una prueba sencilla para ver como optimizaba el código Java.

Un Ejemplo

Digamos que tenemos esto en Java

int a = 2;
int b = 0;
int c = 0;
for(int i = 0; i < 1000; i++){
b = a * a;
c += b;
}


Lo predecible... (lo que cualquier imbécil haría) sería sacar el b = a * a del for... Esta es de las técnicas de optimización de código mas elementales. Invariantes de for creo que se llama y javac no las hace!!!

aqui está el bytecode:


0: iconst_2 // int a = 2
1: istore_1
2: iconst_0 // int b = 0
3: istore_2
4: iconst_0 // int c = 0
5: istore_3
6: iconst_0 // for(int i = 0;
7: istore 4
9: iload 4
11: sipush 1000
14: if_icmpge 31 // i < 1000;
17: iload_1 // {b = a * a;
18: iload_1
19: imul
20: istore_2
21: iload_3 // c += b;}
22: iload_2
23: iadd
24: istore_3
25: iinc 4, 1 // i++)
28: goto 9


Otra técnica es "reducción de fuerza" es decir... la multiplicación por 2 se puede reemplazar por un corrimiento de bits... en fin esas son las cosas que se me ocurren.

Que Pasa?

Entonces teniendo claro el hecho de que "debe haber alguna buena razón para eso" me puse a leer por ahí y encontre dos versiones:

1. Alguien decía que la idea era delegar esas cosas al IDE... es decir, si tengo una "Tail recursion" eclipse sacaría una ventana y diria "desea reemplazar esto por código iterativo?".

Tiendo a pensar que puede funcionar con tail recursion... pero:

más código autogenerado = más verbose en el fuente = MÁS FEO

Mi intuición me dice que algunas optimizaciones se pueden hacer solo en bytecode. Cosas que impliquen reordenación a un bajo nivel... no se me ocurre un ejemplo.

2. Otra versión es que las optimizaciones se realizan en la máquina virtual.

Creo que algunas optimizaciones parten de asunciones de la semántica del lenguaje de arriba y la verdad sería problemático interoperabilidad con otros lenguajes con semánticas diferentes... Dichas asunciónes dejarían de ser válidas.

Me gustaría leer una verdadera respuesta en vez de perderme en mares de suposiciones e intuiciones mías. Al final tal vez solo el manual de referencia de la JVM me podría responder.

Nota Aparte:

Corrí el mismo código en gcc con -O1... gcc se "da cuenta" que al final el resultado es sumar 4 mil veces... y eso, como decía mi profesor de Cálculo, "casi siempre" da 4000. gcc reemplaza todo el for por un mov $4000.


Witchcraft... pero impresionante.

10 comentarios:

febuiles dijo...

Después de averiguar un poco, resulta que a nivel de "javac" si hay algunas optimizaciones, pero la mayoría de las cosas se hacen a nivel de HotSpot. De todas formas, las optimizaciones se hacen a todos los niveles del proceso "Java -> Bytecode -> Código Nativo". Mirando http://java.sun.com/products/hotspot/whitepaper.html se puede ver referencias a cosas locas como convertir código bytecode a código nativo por eficiencia, para devolver a bytecode 5 segundos después si hay subclassing con métodos virtuales o cosas por el estilo. Según lo que estoy viendo, hay mucho que leer al respecto.

diegoeche dijo...

La pregunta que... será que todas las optimizaciones son visibles a nivel de Bytecode?

Las optimizaciones sencillas no es mejor dejarselas al compilador?

febuiles dijo...

>> La pregunta que... será que todas las optimizaciones son visibles a nivel de Bytecode?

No, algunas se hacen cuando se está traduciendo de bytecode a código nativo. De hecho, esta es la mayoría de las optimizaciones.

>> Las optimizaciones sencillas no es mejor dejarselas al compilador?

El mismo compilador puede generar código para varias máquinas virtuales, así que este código creo que debe ser tan sencillo como sea posible, aunque no estoy seguro en eso, habría que mirar más a fondo las implementaciones.

chrono dijo...

Yo me topé con esa interrogante hace poco. De hecho aposté con un profesor acerca de esto. Él aseguraba que javac optimizaba cierto código y yo había leído que no...

Me interesa saber dónde leíste que javac no genera bytecode. Yo lo leí en un artículo de ibm:
http://www.ibm.com/developerworks/ibm/library/it-haggar_bytecode/

No he encontrado nada concreto que asegure o descarte la optimización de código por que en clase probamos algunos casos y resulta que en uno sí optimizaba y en otro no!!...

Hay que seguir investigando

diegoeche dijo...

Hola chrono.

La máquina virtual si genera bytecode. Busque en el post donde digo que no lo hace para corregirlo, pero no lo encontré.

Pese a que no es el tema del post a veces menciona estrategias de optimización en interpretación: http://tinyurl.com/6a6den

tiendo a pensar que de alguna forma gran parte de las optimizaciones ocurren en la JVM.

Neofox dijo...

Hola estimado no se si podrias ayudarme estoy haciendo videos tutoriales de como hacer blog y ganar con adesense: http://es.youtube.com/user/neofoxer, quiero integrar un codigo html en el blog pero me sale mucho espacio en blanco como puedes ver aqui: http://juegobolsadevalores.blogspot.com/

Te agradecría si puedes ayudarme yo te doy los creditos necesarios en el curso gratuito, que tu puedes aprovechar para obtener dinero con adsense. Saludos contactame

marirubi dijo...

hola como estan ..me pueden decir como se obtienen los bytecode los necesito para un proyecto. gracias

marirubi dijo...

:)

Esteban dijo...

javac al parecer antes sí hacía optimizaciones, pero ahora la mayor parte se delega a Hotspot, por ejemplo: sustituir a*2 por a<<1, javac no puede saber de antemano qué es más rápido! Puede ser que alguien raro en el futuro inventen una máquina que multiplica más rapidamente que un corrimiento a la izquierda (y puede ser que hasta haya computadoras no binarias...), entonces javac lo que hace es traducir lo que quiere el programador a bytecodes.

Hotspot sí sabe las características de la máquina (PowerPC, x86, AMD64, algún bicho raro trinario) y entonces sí puede hacer las optimizaciones bien. También hay optimizaciones loops que serían diferentes en mononúcleo o polinúcleo y esto nuevamente le cae a hotspot...

diegoeche dijo...

Hola Esteban. Tiene sentido tu comentario para optimizaciones de "reducción de fuerza" como en el caso de sustitución de multiplicación por corrimiento.

Creo que hay ciertas optimizaciones en el código que son independientes de la arquitectura y se podrían realizar de una buena vez en compilación (tail calls, invariantes de loop)