Haga que Java sea rápido: ¡Optimice!

Según el científico informático pionero Donald Knuth, "la optimización prematura es la raíz de todos los males". Cualquier artículo sobre optimización debe comenzar señalando que generalmente hay más razones para no optimizar que para optimizar.

  • Si su código ya funciona, optimizarlo es una forma segura de introducir errores nuevos y posiblemente sutiles

  • La optimización tiende a hacer que el código sea más difícil de entender y mantener.

  • Algunas de las técnicas presentadas aquí aumentan la velocidad al reducir la extensibilidad del código

  • Optimizar el código para una plataforma puede empeorarlo en otra plataforma

  • Se puede dedicar mucho tiempo a la optimización, con poca ganancia en rendimiento, y puede resultar en código ofuscado

  • Si está demasiado obsesionado con optimizar el código, la gente lo llamará nerd a sus espaldas

Antes de optimizar, debe considerar cuidadosamente si necesita optimizar en absoluto. La optimización en Java puede ser un objetivo difícil de alcanzar ya que los entornos de ejecución varían. El uso de un algoritmo mejor probablemente producirá un aumento de rendimiento mayor que cualquier cantidad de optimizaciones de bajo nivel y es más probable que proporcione una mejora en todas las condiciones de ejecución. Como regla general, se deben considerar las optimizaciones de alto nivel antes de realizar optimizaciones de bajo nivel.

Entonces, ¿por qué optimizar?

Si es tan mala idea, ¿por qué optimizar? Bueno, en un mundo ideal no lo harías. Pero la realidad es que a veces el mayor problema con un programa es que simplemente requiere demasiados recursos, y estos recursos (memoria, ciclos de CPU, ancho de banda de red o una combinación) pueden ser limitados. Es probable que los fragmentos de código que ocurren varias veces en un programa sean sensibles al tamaño, mientras que el código con muchas iteraciones de ejecución puede ser sensible a la velocidad.

¡Haz que Java sea rápido!

Como lenguaje interpretado con un código de bytes compacto, la velocidad o la falta de este es lo que más a menudo aparece como un problema en Java. Principalmente, veremos cómo hacer que Java se ejecute más rápido en lugar de hacerlo encajar en un espacio más pequeño, aunque señalaremos dónde y cómo estos enfoques afectan la memoria o el ancho de banda de la red. La atención se centrará en el lenguaje principal en lugar de en las API de Java.

Por cierto, una cosa que no discutiremos aquí es el uso de métodos nativos escritos en C o ensamblador. Si bien el uso de métodos nativos puede brindar el máximo impulso al rendimiento, lo hace a costa de la independencia de la plataforma de Java. Es posible escribir tanto una versión Java de un método como versiones nativas para plataformas seleccionadas; esto conduce a un mayor rendimiento en algunas plataformas sin renunciar a la capacidad de ejecutarse en todas las plataformas. Pero esto es todo lo que voy a decir sobre el tema de reemplazar Java con código C. (Consulte el Consejo de Java, "Escribir métodos nativos" para obtener más información sobre este tema.) Nuestro enfoque en este artículo es cómo hacer que Java sea rápido.

90/10, 80/20, choza, choza, ¡caminata!

Como regla general, el 90 por ciento del tiempo de excitación de un programa se dedica a ejecutar el 10 por ciento del código. (Algunas personas usan la regla del 80 por ciento / 20 por ciento, pero mi experiencia escribiendo y optimizando juegos comerciales en varios idiomas durante los últimos 15 años ha demostrado que la fórmula del 90 por ciento / 10 por ciento es típica para los programas que requieren un gran rendimiento, ya que pocas tareas tienden a realizarse con gran frecuencia). La optimización del otro 90 por ciento del programa (donde se dedicó el 10 por ciento del tiempo de ejecución) no tiene un efecto notable en el rendimiento. Si pudiera hacer que el 90 por ciento del código se ejecute dos veces más rápido, el programa solo sería un 5 por ciento más rápido. Entonces, la primera tarea para optimizar el código es identificar el 10 por ciento (frecuentemente es menos que esto) del programa que consume la mayor parte del tiempo de ejecución. Esto es n't siempre donde esperas que esté.

Técnicas generales de optimización

Hay varias técnicas de optimización comunes que se aplican independientemente del idioma que se utilice. Algunas de estas técnicas, como la asignación global de registros, son estrategias sofisticadas para asignar recursos de la máquina (por ejemplo, registros de CPU) y no se aplican a los códigos de bytes de Java. Nos centraremos en las técnicas que básicamente implican reestructurar código y sustituir operaciones equivalentes dentro de un método.

Reducción de fuerza

La reducción de fuerza ocurre cuando una operación es reemplazada por una operación equivalente que se ejecuta más rápido. El ejemplo más común de reducción de fuerza es usar el operador de turno para multiplicar y dividir números enteros por una potencia de 2. Por ejemplo, x >> 2se puede usar en lugar de x / 4y x << 1reemplaza x * 2.

Eliminación de subexpresión común

La eliminación de subexpresión común elimina los cálculos redundantes. En lugar de escribir

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

la subexpresión común se calcula una vez y se usa para ambos cálculos:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Movimiento de código

El movimiento de código mueve el código que realiza una operación o calcula una expresión cuyo resultado no cambia o es invariante . El código se mueve para que solo se ejecute cuando el resultado pueda cambiar, en lugar de ejecutarse cada vez que se requiera el resultado. Esto es más común con bucles, pero también puede involucrar código repetido en cada invocación de un método. El siguiente es un ejemplo de movimiento de código invariante en un bucle:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

se convierte en

picosy doble = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = picosy;

Desenrollar bucles

El desenrollado de bucles reduce la sobrecarga del código de control de bucle al realizar más de una operación cada vez a través del bucle y, en consecuencia, ejecutar menos iteraciones. Partiendo del ejemplo anterior, si sabemos que la longitud de x[]es siempre un múltiplo de dos, podríamos reescribir el ciclo como:

picosy doble = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = picosy; x [i + 1] * = picosy; }

En la práctica, desenrollar bucles como este, en el que el valor del índice de bucle se usa dentro del bucle y debe incrementarse por separado, no produce un aumento de velocidad apreciable en Java interpretado porque los códigos de bytes carecen de instrucciones para combinar eficientemente el +1"en el índice de la matriz.

Todos los consejos de optimización de este artículo incorporan una o más de las técnicas generales enumeradas anteriormente.

Poniendo el compilador a trabajar

Los compiladores modernos de C y Fortran producen código altamente optimizado. Los compiladores de C ++ generalmente producen código menos eficiente, pero aún están en el camino hacia la producción de código óptimo. Todos estos compiladores han pasado por muchas generaciones bajo la influencia de una fuerte competencia del mercado y se han convertido en herramientas finamente perfeccionadas para exprimir hasta la última gota de rendimiento del código ordinario. Es casi seguro que utilicen todas las técnicas generales de optimización presentadas anteriormente. Pero todavía quedan muchos trucos para hacer que los compiladores generen código eficiente.

compiladores de código nativo, JIT y javac

El nivel de optimización que se javacrealiza al compilar código en este punto es mínimo. De forma predeterminada, hace lo siguiente:

  • Plegado constante: el compilador resuelve cualquier expresión constante tal que i = (10 *10)compila en i = 100.

  • Plegado de ramas (la mayoría de las veces): gotose evitan los códigos de bytes innecesarios .

  • Eliminación limitada de códigos muertos: no se produce ningún código para declaraciones como if(false) i = 1.

El nivel de optimización que proporciona javac debería mejorar, probablemente drásticamente, a medida que el lenguaje madura y los proveedores de compiladores comienzan a competir en serio sobre la base de la generación de código. Java acaba de obtener compiladores de segunda generación.

Luego están los compiladores Just-In-Time (JIT) que convierten los códigos de bytes de Java en código nativo en tiempo de ejecución. Varios ya están disponibles y, aunque pueden aumentar la velocidad de ejecución de su programa de manera espectacular, el nivel de optimización que pueden realizar está limitado porque la optimización se produce en tiempo de ejecución. Un compilador JIT se preocupa más por generar el código rápidamente que por generar el código más rápido.

Los compiladores de código nativo que compilan Java directamente en código nativo deberían ofrecer el mayor rendimiento pero a costa de la independencia de la plataforma. Afortunadamente, muchos de los trucos presentados aquí serán logrados por futuros compiladores, pero por ahora se necesita un poco de trabajo para aprovechar al máximo el compilador.

javacofrece una opción de rendimiento que puede habilitar: invocar la -Oopción para hacer que el compilador inserte ciertas llamadas a métodos:

javac -O MyClass

Al insertar una llamada a un método, se inserta el código del método directamente en el código que realiza la llamada al método. Esto elimina la sobrecarga de la llamada al método. Para un método pequeño, esta sobrecarga puede representar un porcentaje significativo de su tiempo de ejecución. Tenga en cuenta que sólo los métodos declarados como cualquiera private, statico finalpueden ser considerados para la inclusión entre líneas, ya que sólo estos métodos se resuelven de forma estática por el compilador. Además, los synchronizedmétodos no estarán incluidos. El compilador solo incluirá métodos pequeños en línea que generalmente constan de solo una o dos líneas de código.

Desafortunadamente, las versiones 1.0 del compilador javac tienen un error que genera código que no puede pasar el verificador de bytecode cuando -Ose usa la opción. Esto se ha solucionado en JDK 1.1. (El verificador de código de bytes verifica el código antes de que se le permita ejecutarse para asegurarse de que no viola ninguna regla de Java). Se integrarán los métodos que hacen referencia a miembros de clase inaccesibles para la clase que llama. Por ejemplo, si las siguientes clases se compilan juntas usando la -Oopción

clase A {privado estático int x = 10; public static void getX () {return x; }} clase B {int y = A.getX (); }

la llamada a A.getX () en la clase B se incluirá en la clase B como si B se hubiera escrito como:

clase B {int y = Ax; }

Sin embargo, esto hará que la generación de códigos de bytes acceda a la variable privada Ax que se generará en el código de B. Este código se ejecutará bien, pero dado que viola las restricciones de acceso de Java, el verificador lo marcará con una IllegalAccessErrorla primera vez que se ejecute el código.

Este error no hace que la -Oopción sea inútil, pero debes tener cuidado con cómo la usas. Si se invoca en una sola clase, puede incorporar ciertas llamadas a métodos dentro de la clase sin riesgo. Se pueden integrar varias clases juntas siempre que no existan restricciones de acceso potenciales. Y algunos códigos (como las aplicaciones) no están sujetos al verificador de códigos de bytes. Puede ignorar el error si sabe que su código solo se ejecutará sin estar sujeto al verificador. Para obtener información adicional, consulte mis preguntas frecuentes sobre javac-O.

Perfiladores

Afortunadamente, el JDK viene con un generador de perfiles incorporado para ayudar a identificar dónde se pasa el tiempo en un programa. Realizará un seguimiento del tiempo invertido en cada rutina y escribirá la información en el archivo java.prof. Para ejecutar el generador de perfiles, use la -profopción al invocar el intérprete de Java:

java -prof myClass

O para usar con un applet:

java -prof sun.applet.AppletViewer myApplet.html

Hay algunas advertencias para usar el generador de perfiles. La salida del perfilador no es particularmente fácil de descifrar. Además, en JDK 1.0.2 trunca los nombres de los métodos a 30 caracteres, por lo que puede que no sea posible distinguir algunos métodos. Desafortunadamente, con Mac no hay forma de invocar al generador de perfiles, por lo que los usuarios de Mac no tienen suerte. Además de todo esto, la página del documento Java de Sun (ver Recursos) ya no incluye la documentación para la -profopción). Sin embargo, si su plataforma admite la -profopción, se puede usar HyperProf de Vladimir Bulatov o ProfileViewer de Greg White para ayudar a interpretar los resultados (ver Recursos).

También es posible "perfilar" el código insertando tiempos explícitos en el código:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()devuelve el tiempo en 1/1000 de segundo. Sin embargo, algunos sistemas, como una PC con Windows, tienen un temporizador de sistema con menos (mucho menos) resolución que una milésima de segundo. Incluso una milésima de segundo no es suficiente para cronometrar con precisión muchas operaciones. En estos casos, o en sistemas con temporizadores de baja resolución, puede ser necesario medir el tiempo que se tarda en repetir la operación n veces y luego dividir el tiempo total entre n para obtener el tiempo real. Incluso cuando se dispone de perfiles, esta técnica puede ser útil para cronometrar una tarea u operación específica.

Aquí hay algunas notas finales sobre la creación de perfiles:

  • Siempre cronometra el código antes y después de realizar cambios para verificar que, al menos en la plataforma de prueba, tus cambios mejoraron el programa.

  • Intente realizar cada prueba de cronometraje en condiciones idénticas

  • Si es posible, cree una prueba que no se base en ninguna entrada del usuario, ya que las variaciones en la respuesta del usuario pueden hacer que los resultados fluctúen

El applet de Benchmark

El subprograma Benchmark mide el tiempo que lleva realizar una operación miles (o incluso millones) de veces, resta el tiempo dedicado a realizar operaciones distintas de la prueba (como la sobrecarga del bucle) y luego usa esta información para calcular cuánto tiempo dura cada operación tomó. Ejecuta cada prueba durante aproximadamente un segundo. En un intento por eliminar retrasos aleatorios de otras operaciones que la computadora puede realizar durante una prueba, ejecuta cada prueba tres veces y usa el mejor resultado. También intenta eliminar la recolección de basura como factor en las pruebas. Debido a esto, cuanta más memoria esté disponible para el punto de referencia, más precisos serán los resultados del mismo.