miércoles, 1 de octubre de 2008

Propuestas de optimizaciones para Strings

Al hilo de lo comentado en los posts Copy-on-write optimization for StringBuilder and StringBuffer y Copy-on-write optimization for StringBuilder and StringBuffer (II), he estado trabajando más de la mitad del mes de septiembre (robándole tiempo a mi mujer, al sueño y a la tele por se orden) en una idea que yo pensaba que era cojonuda, aunque aviso de antemano que probablemente no sea buena, vistos los comentarios y estadísticas recogidas por mi... :-(

Por cierto, antes de seguir leyendo, si no estás familiarizado con cómo están implementados los StringBuilders y StringBuffer en el JDK, échale un vistazo a esos fuentes y al Java Language Specifications, porque si no esto pierde todo su encanto. En general es una buena práctica revisar cómo la gente del JDK ha hecho ciertas cosas, yo he aprendido de ellos mucho-mucho en los últimos 11 años... al menos demuestra algo de interés por el tema :-)

La nueva idea básicamente consiste en intentar ver la creación de Strings desde una perspectiva nueva: si el 95% de las operaciones sobre un StringBuilder son appends (y no inserts, deletes, etc), quizás eso nos puede dar una pista de reimplementación basada en almacenar la lista de cadenas que se quieren concatenar y sólo hacer la concatenación efectiva al invocar al método toString().

Desde el punto de vista teórico supone una ventaja importante frente al modelo actual de StringBuilder ya que no es necesario crear un array de chars interno, una vez llenado crear otro más grande y copiar los contenidos de uno a otro, y finalmente volver a hacer una creación de array de chars con el tamaño exacto y copia de los caracteres allí, en el toString().

Después de muchas vueltas y muchos intentos y benchmarkings, mi propuesta pasaba por crear una clase java.lang.StringAppender, que contiene internamente una lista de Strings...

El principal problema es con la inserción de un sólo carácter, operación que es tremendamente frecuente a la vista de las pruebas. Mi solución es entre un 5 y un 160% mejor al concatenar Strings, pero más de un 100% peor al concatenar chars individualmente. Como digo he probado otras combinaciones (almacenar char[][], almacenar dos listas, una para Strings y otra para chars, modificar StringBuilder para que pueda funcionar en "fast mode" y "normal mode" según interese... pero la opción más limpia y de mejor rendimiento en los casos que son típicos en un desarrollador de aplicaciones web (y que yo suponía que esto era extrapolable a cualquier otro desarrollo, incluyendo el del JDK, Netbeans, etc), es la que adjunto.

Pero no es suficiente, o al menos sería difícil de justificar el cambio de API (que es algo que no gusta mucho, evidentemente)...

En el archivo de la lista de correo de desarrollo de las librerías de núcleo para JDK 7 puede verse el detalle completo, las distintas respuestas públicas (también hubo unos cuantos consejos "privados"), y descargar el código fuente tanto en los cambios a String.java propuestos como la nueva clase StringAppender.java (nota: si hay interés en descargarlo, tómese la última versión publicada, no la primera)... así que no me enrollaré mucho más.

Ahí dejo el enlace al thread: http://mail.openjdk.java.net/pipermail/core-libs-dev/2008-September/000734.html. Y esta es la copia literal de mi primer y mi tercer mensaje que son un resumen ejecutivo de la idea, las estadísticas y las conclusiones.

El primer mensaje a la lista (http://mail.openjdk.java.net/pipermail/core-libs-dev/2008-September/000734.html):

(...) This is my proposal to be discussed:


THE GOAL:

Boost the overall String concatenation / append operations.


BACKGROUND / HISTORY:

  • At the beginning (JDK 1.0 days) we had String.concat() and StringBuffer to build Strings. Both approaches had initially bad performance.
  • Starting at JDK 1.4 (I think), a share-on-copy strategy was introduced in StringBuffer. The performance gain was obvious, but increased the needed heap and in some cases produced some memory leak when reusing StringBuffer.
  • Starting at JDK 1.5, StringBuilder was introduced as the “unsyncronized version”, but also the copy-on-write optimization was undo, becoming an "always copy" scenario. Also, the String + operator is translated to StringBuilder.append() by javac. This has been discussed but no better alternative was found (seehttp://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6219959 ).
  • This current implementation generates several System.arraycopy() calls: at least one per append/insert/delete (two if expanding capacity)... and a final one in the toString() method!


STUDYING THE USES:

  • If we look at the uses of StringBuilder (both inside JDK code, in application servers and/or final applications), in nearly 99% of times it is only used to create a String in a single-threaded context and (the most important fact) only using the append() and toString() methods.
  • Also, only in 5% of the instantiatings, the coder establishes the initial capacity. Many times doesn’t matter, but other times it is impossible to guess it or calculate it. And even worst: some times the coder fails in his guess: establishes to much initial capacity or too few.


MY PROPOSAL:

  • Create a new class java.lang.StringAppender implements Appendable.
    1. Mostly same in its exposed public constructors and methods than StringBuilder, but the only operations are the “append()” ones (no insert, no delete, no replace).
    2. Internally represented as a String array.
    3. Only arraycopy() or create char arrays once, inside the toString() method (well, this isn’t completely true: also arraycopies when appending objects/variables other than String instances or char arrays, but the most typical operation is appending strings!).
    4. Doesn’t need to stablish an initial capacity. Never more calculating it or guessing it.
  • Add a new constructor in the java.lang.String class (actually 5 new constructors for performance reasons, see below):
    1. public String(String... strs)
    2. public String(String str0, String str1)
    3. public String(String str0, String str1, String str2)
    4. public String(String str0, String str1, String str2, String str3)
  • (NOTE: these 3 additional constructors are needed to boost appends of a small number of Strings, in which case the overload of creating the array and then looping inside is much greater than passing 2, 3 or 4 parameters in the constructor invocation).
  • Change the javac behavior: the String + operator must be translated into“new String(String...);instead of into “new StringBuilder().append().append()... ..toString();”.
  • Revise other JDK sourcecodes to use StringAppender, and the rest of programs all around the world. (By the way in the Glassfish V2 sourcecode I see several String.concat() invocations; seems strange to me... ).
  • So the new blueprints for String concatenation should be:
    1. For append-only, not conditional String concatenations, use the new String constructor. Example: String result = new String(part1, part2, part3,part4);
    2. For append-only, conditional or looped concatenations, or for appending other Objects/types, use the StringAppender class.
    3. For other manipulations (insert, delete, replace), use StringBuilder.
    4. For a thread-safe version, use StringBuffer.


THE BOOST:

As you can see in my microbenchmark results, executed in Linux x64 and Windows 32 bits (-server, -client, and -XX:+AggressiveOpts versions), we can achieve a boost between 1% and 167% (depends on the scenario and architecture). Well, those values are the extremes, the typical gains go between 20% and 70%. I think these results are good enough to be taken intoconsideration :-)


THE SOURCE CODE:

See attachments, String.java.diff with the added code (it is clear), and StringAppender.java with the new proposed class.


THE MICROBENCHMARK CODE:

See attachment. Of course should be revised. I think I have made it correctly.


THE MICROBENCHMARK RESULTS (varied to me about +/-1% in different executions due to the host load or whatever):

See attached file. I think they are great...


What do you think?
Best regards,



Y este ha sido de momento :-) mi último mail de respuesta (http://mail.openjdk.java.net/pipermail/core-libs-dev/2008-September/000747.html)...

Hi all.

I have measured the number of AbstractStringBuilder method invocations when executing NetBeans 6 (and making some work for 5 minutes) and when executing for a while a Glassfish V2 with a typical web application (Struts+Spring+Hibernate). These are the interesting and empirical results:


My conclusions:

  • The number of append(char) is bigger than append(String) and much bigger than other inserts (mainly in the Netbeans execution), so my StringAppender approach wouldn't perform good as predicted by Rémi and others. But the number of append(int), append(float), append(Boolean) is very low.
  • In a very few situations a Builder/Buffer is reutilized after calling toString().
  • expandCapacity() is invoked a lot of times!!!
  • Other operations (different than appends) are invoked a very few times.

So I suppose that my two proposals have few sense in general (haven't they?), but maybe these figures can help to reconsider the value of the default buffer length or can help others trying to make String/StringBuilder faster. Heap allocation and System.arraycopy calls must be reduced anyway!

P.S: Nevertheless I attach the "final" version of my modification to String.java and of StringAppender.java, which has some optimizations to append(char) but not sufficient... I think.

Best regards,


A mi personalmente me frustra la cantidad de alojamientos de heap y copias de arrays que podrían ser innecesarios en muchos casos, pero parece complejo encontrar una solución más eficiente... Bueno, en realidad tampoco es que se trate de un desastre absoluto porque afortunadamente los arraycopys están muy optimizados al menos en Solaris, Linux y Windows (me consta que ha habido mucho trabajao conjunto de los ingenieros de Sun con los de Intel y los de AMD)...

Y por otro lado la solución (sea la que sea) tiene que ser una solución "universal" en el sentido de que el código se migre mayoritariamente desde StringBuilder a StringAppender (o mejor, optimizando StringBuilder claro), como pasó en la migración masiva de StringBuffer a StringBuilder en los tiempos de la 1.5... o si no nuestro querido Hotspot puede decidir no compilar nativamente todos los sus métodos (qué asco, pero esa historia y lo chulos que son los compiladores nativos de verdad merece un post aparte).

Es decir, la mencionada nueva clase podría también crearse en Apache Commons o dentro de mis proyectos, pero si se usa millones de veces StringBuilder, malamente la JVM va a pensar que StringAppender tiene sus "hotspots"...

Por cierto que hay otras inciativas de optimizar las clases AbstractStringBuilder, StringBuilder y StringBuffer, pero van en otra línea más de inlinings y esos rollos. Y en alguna de ellas voy a echar una mano en pruebas microbenchmarkings, si sale algo positivo ya os contaré...

Y vosotros ¿qué opináis? ¿o soy yo el único que le ve interés a este asunto del rendimiento de los Strings????

:-)

2 comentarios:

angelborroy dijo...

Los viejos rockeros nunca mueren XD

Server Performance dijo...

Pero cada días les cuesta más, y después de subirse al escenario necesitan más tiempo de recuperación...