Java Quiz #44

FR:
Le but de ce quiz est de rendre ce code plus performant d'un ordre de magnitude uniquement en ajoutant 1 ligne. Evidemment, le benchmark doit toujours réaliser la même fonction, c'est-à-dire mesurer le temps nécessaire pour transformer le tableau d'entiers en tableau de wrappers d'entiers.
Mes résultats : avant : 1700ms (très variable), après : 65ms (très stable)
La réponse sera apportée dans une semaine !

EN:
The goal of this quiz is to make this code run an order of magnitude faster, simply by adding a single line. Please note that the benchmark must still measure the time nessary to copy an int array into an Integer array.
Results on my box : before : 1700ms with high variability, after : 65ms, very stable.
The answer will be given in a week.

public class Quiz44 {
 
    private static final int NB_VALUES = 10000000;
    private static final int MAX_VALUE = 1000;
    private static final int NB_RUNS = 10;   
 
    public static void main(String[] args) {
 
        Integer[] boxedValues = new Integer[NB_VALUES];
        int[] values = initValues();
 
        System.out.println("Benchmarking...");
        for (int run = 1; run <= NB_RUNS; run++) {
            long t1 = System.currentTimeMillis();
            for (int i = 0; i < NB_VALUES; i++) {
                boxedValues[i] = values[i];
            }
            long t2 = System.currentTimeMillis();
            System.out.printf("Run %2d : %4dms%n", run, t2 - t1);
        }
    }
 
    /** Nothing important here, just values init. */
    private static int[] initValues() {
        System.out.println("Generating values...");
        int[] values = new int[NB_VALUES];
        Random random = new Random();
        for (int i = 0; i < values.length; i++) {
            values[i] = random.nextInt(MAX_VALUE);
        }
 
        return values;
    }
 
}

Réponse (FR) :
Au sein de la boucle, on transfère une valeur d'un tableau d'int vers un tableau d'Integer. Depuis Java 5, il n'est plus nécessaire d'effectuer la transformation de type manuellement, grâce à une fonctionnalité appelée "autoboxing" : en coulisse, le compilateur insère à notre place les instructions nécessaires (ici, un Integer.valueOf()), afin de simplifier la vie du développeur.

Comme ces opérations de boxing / unboxing sont fréquentes et qu'il serait coûteux de construire un nouveau wrapper Integer à chaque fois, la classe Integer gère un cache qui couvre la plage de valeurs la plus utilisée (par défaut, -128 à +127). Ce cache est utilisé par la méthode Integer.valueOf() insérée par le compilateur :

public static Integer valueOf(int i) {
        if(i >= -128 && i <= IntegerCache.high)
            return IntegerCache.cache[i + 128];
        else
            return new Integer(i);
    }

Comme le quiz utilise des entiers de 0 à 1000, le cache n'est que peu efficace. Selon une mesure, plus de 16 millions de wrappers sont créés et occupent plus de 260Mo sur les 330Mo alloués !


Quiz44-before.png

Pour réduire la consommation mémoire et la charge du Garbage Collector, il serait intéressant d'augmenter la plage d'action du cache, en fixant sa borne supérieure à 1000. L'examen du code de la classe Integer fournit la solution (classe Integer, lignes 557+ sur le JDK 6.0.24) :

/**
 * Cache to support the object identity semantics of autoboxing for values between 
 * -128 and 127 (inclusive) as required by JLS.
 *
 * The cache is initialized on first usage. During VM initialization the
 * getAndRemoveCacheProperties method may be used to get and remove any system
 * properites that configure the cache size. At this time, the size of the
 * cache may be controlled by the vm option -XX:AutoBoxCacheMax=<size>.
 */

Lançons donc le Quiz 44 avec cette option :

java -XX:AutoBoxCacheMax=1000 Quiz44

Les performances sont améliorées d'un ordre de grandeur (plus de 30X sur ma machine), et la consommation mémoire en chute libre : plus que 1200 Integers présents en mémoire, pour à peine 20Mo. La consommation totale du programme descend également aux alentours de 80Mo.


Quiz44-after.png

Conclusions :

  1. Méfiez-vous de l'autoboxing, spécialement au sein des boucles !
  2. Pour convertir un type primitif en son wrapper, il faut toujours utiliser valueOf() qui tente d'utiliser le cache, ou laisser faire l'autoboxing. Instancier manuellement un wrapper est inefficace.
  3. Si votre application effectue des calculs intensifs dans une plage de valeurs données, il peut être intéressant de tuner le cache des entiers -- mais toujours mesurer avant de tuner !

Quelques remarques supplémentaires :

  • L'option AutoBoxCacheMax est apparue avec le JDK 6. Dans le JDK 5, le cache est déclaré avec une taille fixe :
static final Integer cache[] = new Integer[-(-128) + 127 + 1];
  • Tous les wrappers n'ont pas droit au même traitement : Integer possède un cache réglable; Long possède un cache de taille fixe (-128 à +127).
    Plus surprenant, Float et Double ne possèdent aucun cache et renvoient directement une nouvelle instance, contrairement à ce que précise leur Javadoc !
/**
 * Returns a <tt>Double</tt> instance representing the specified
 * <tt>double</tt> value.
 * If a new <tt>Double</tt> instance is not required, this method
 * should generally be used in preference to the constructor
 * {@link #Double(double)}, as this method is likely to yield
 * significantly better space and time performance by caching
 * frequently requested values.
 *
 * @param  d a double value.
 * @return a <tt>Double</tt> instance representing <tt>d</tt>.
 * @since  1.5
 */
public static Double valueOf(double d) {
    return new Double(d); // Aucun cache !
}
  • Détail amusant, avec le JDK 6, dans la classe Integer, le code qui lit la valeur du paramètre AutoBoxCacheMax ne peut pas utiliser les méthodes de la classe Integer, car elles initialiseraient le cache de manière précoce. Integer utilise donc Long.decode() à la place ! Ce code a apparemment été changé dans le JDK 7 et utilise désormais Integer.parseInt() (merci à Heinz Kabutz pour la précision !).




Solution (EN) :

In the loop body, we transfer the content of an int array into an Integer array. Since Java 5, there is no need to convert manually the primitive types to or from their wrapper counterparts anymore, thanks to the "autoboxing" feature : behing the scenes, the compiler will insert the required code for us (here, a call to Integer.valueOf()), to ease the developers' life.

Because boxing operations are frequent and because it would be very costly to instanciate a new wrapper each time, the Integer class manages a cache that contains the values its developers thought would be used the most (from -128 to +127). This cache is used by the Integer.valueOf() method gracefully inserted by the compiler.

public static Integer valueOf(int i) {
        if(i >= -128 && i <= IntegerCache.high)
            return IntegerCache.cache[i + 128];
        else
            return new Integer(i);
    }

Unfortunately, the quiz uses values from 0 to 1000, so the cache is not very effective in this case. A quick measure show that more than 16 million Integers are instanciated, and weigh over 260Mo out of the 330M allocated by the JVM.


Quiz44-before.png

To reduce the memory consumption, the object churn-out, and make the GC's life easier, it could be interesting to increase the cache size and set its upper bound to 1000. The solution lies in the code of the Integer class (lines 557+ in JDK 6.0.24) :

/**
 * Cache to support the object identity semantics of autoboxing for values between 
 * -128 and 127 (inclusive) as required by JLS.
 *
 * The cache is initialized on first usage. During VM initialization the
 * getAndRemoveCacheProperties method may be used to get and remove any system
 * properites that configure the cache size. At this time, the size of the
 * cache may be controlled by the vm option -XX:AutoBoxCacheMax=<size>.
 */

Let's run the quiz again with this new VM option :

java -XX:AutoBoxCacheMax=1000 Quiz44

The performance is now better by an order of magnitude (30X on my machine) and memory consumption plummets : only 1200 Integer instances for a total of about 20Mo. The total memory usage is now around 80Mo only.


Quiz44-after.png

Conclusion :

  1. Be careful with the autoboxing feature, especially in loops !
  2. To convert a primitive type to its wrapper counterpart, always use valueOf() that may use the cache, or let autoboxing do it for you. Never instanciate a wrapper manually !
  3. If your application does massive number crunching in a fixed range of numbers, consider tuning the Integer cache. But always measure first !

Other interesting facts :

  • The AutoBoxCacheMax option is quite new, it appeared in JDK 6. In JDK 5, the cache was declared with a fixed range :
static final Integer cache[] = new Integer[-(-128) + 127 + 1];
  • All numeric wrappers are not equal : Integer has a configurable cache; Long has a fixed-range cache (from -128 to +127). But the most surprising fact is that Float and Double do not have any cache, contrary to what their Javadocs advertise !
/**
 * Returns a <tt>Double</tt> instance representing the specified
 * <tt>double</tt> value.
 * If a new <tt>Double</tt> instance is not required, this method
 * should generally be used in preference to the constructor
 * {@link #Double(double)}, as this method is likely to yield
 * significantly better space and time performance by caching
 * frequently requested values.
 *
 * @param  d a double value.
 * @return a <tt>Double</tt> instance representing <tt>d</tt>.
 * @since  1.5
 */
public static Double valueOf(double d) {
    return new Double(d); // Look Ma, no cache !
}
  • Finally, I find it amusing that, in the JDK 6 Integer class, the code fragment that parses the AutoBoxCacheMax value cannot use other Integer methods, because that would cause the cache to be initialized too early. Integer must therefore resort to using Long.decode() instead ! This is no more the case in JDK 7 (many thanks to Heinz Kabutz for pointing this out !).

I hope you enjoyed this quiz, thanks for reading !


Commentaires

1. Le vendredi 15 avril 2011, 00:36 par Will

-Djava.lang.Integer.IntegerCache.high=1000

2. Le vendredi 15 avril 2011, 07:38 par lgosselin

Is it something like tuning the integer cache size?
Messing around with -XX:AutoBoxCacheMax or doing something like System.setProperty("java.lang.Integer.IntegerCache.high", MAX_VALUE) as first thing in the main() ?

3. Le vendredi 15 avril 2011, 07:44 par Sylvain FRANCOIS

Moi je propose un gros gain (similaire à celui attendu ?) sans ajouter une seule ligne :) Mais que pour Java 6.

Simplement en augmentant la taille du cache des Integer, avec l'option -Djava.lang.Integer.IntegerCache.high=1000

4. Le vendredi 15 avril 2011, 08:51 par Guillaume Leone

En faisant une boucle simplifié ?

for (Integer i : values) {

    boxedValues[i] = i;

}

5. Le vendredi 15 avril 2011, 08:55 par Yannick

Bonjour,

Il me semble qu'il y a un micro piège dans l'énoncé :)
Je suis tombé sur cette feature en tentant de trouver une explication à ce bout de code

   	Integer a = Integer.valueOf(10);
   	Integer b = Integer.valueOf(10);
   	System.out.println(a == b);

par contre, je pense que la solution n'est pas portable, je me trompe ?

6. Le vendredi 15 avril 2011, 08:58 par Yannick

Autant pour moi, il y a une solution portable

7. Le vendredi 15 avril 2011, 09:25 par romaintaz

Hum, juste comme ça (il faut que je teste), mais en forçant le cache de la classe Integer à 10000 au lieu des 128 par défaut, ça devrait améliorer les choses, non ? En gros, l'option à ajouter dans la ligne de commande est "-XX:AutoBoxCacheMax=10000"...

Sinon, une ligne qui permet d'améliorer encore plus la rapidité : rajouter "if (false)" juste avant la boucle "for". Bon, on est vendredi, on a le droit ;o)

8. Le vendredi 15 avril 2011, 09:34 par domak

Je n'arrive pas à passer l'option -XX:AutoBoxCacheMax (je ne la vois même pas en faisant "java -XX:+AggressiveOpts -XX:+UnlockDiagnosticVMOptions -XX:+PrintFlagsFinal -version") mais en créant mon propre IntegerCache j'ai des temps stables à 125ms (faut que je demande une machine plus puissante car en initial je suis proche des 5s...).
Mais du coup, j'ai plus qu'une seule ligne.

9. Le vendredi 15 avril 2011, 10:08 par Eric Meallier

LyonJug en force: -Djava.lang.Integer.IntegerCache.high=1024 comme argument de la JVM

=> on augmente la taille du cache des Integer à 1024 (128 par defaut)

Bonne journee et merci,
Eric Meallier

10. Le vendredi 15 avril 2011, 10:17 par arn88

Without changing the java code: -Djava.lang.Integer.IntegerCache.high=1000
Is it allowed? ;)

11. Le vendredi 15 avril 2011, 10:49 par Ptitourson

Je dirais qu'il faut d'abord ajouter avant toute mention de la classe Integer, donc en première ligne de la méthode main :

System.getProperties().put("java.lang.Integer.IntegerCache.high", 999);

...histoire d'accroître l'étendu du cache d'Integer initialisé statiquement, couvrant ainsi tous les entiers générés aléatoirement.

Ensuite, utiliser la méthode Integer.valueOf(int i) qui en interne utilise le cache :

boxedValues[i] = Integer.valueOf(values[i]);

Remarque : mon OpenJDK 1.6.0_20 (IcedTea6 1.9.7) contient toujours l'ancienne implémentation du cache d'entiers, c'est à dire une plage fixe à valeurs entre -127 et 128. Ce changement n'affecte donc en rien les performances du benchmark!

12. Le vendredi 15 avril 2011, 11:06 par Benoît Courtine

Première analyse, à vue de nez :

"boxedValues[i] = values[i];" va utiliser l'autoboxing pour convertir les int en Integer, donc en utilisant la méthode "Integer.valueOf()".
Pour les entiers compris entre 0 et 127, le cache de la JVM devrait rendre l'opération efficace. Ce qui est pénalisant, c'est la création d'un nouvel Integer pour tous les autres !

La solution réside donc sans doute en l'utilisation d'un cache plus vaste (au hazard... les 1000 premiers entiers).

Par contre, mettre ça en place en ligne... pour le moment je sèche !

13. Le vendredi 15 avril 2011, 12:46 par angelsafrania

Moi je dit qu'il faut mettre ca :

   static {
   	System.getProperties().put("java.lang.Integer.IntegerCache.high", 1024);
   }
14. Le vendredi 15 avril 2011, 14:10 par anonyme

...
System.out.println("Benchmarking...");
Arrays.fill(values, 0); // <-- here is the new line
for (int run = 1; run <= NB_RUNS; run++) {
...

15. Le vendredi 15 avril 2011, 16:06 par gecos

Entre les lignes :
long t2 = System.currentTimeMillis();
System.out.printf("Run %2d : %4dms%n", run, t2 - t1);

Ajouter la ligne : t2=t1+65; :)))

Ok je sors

16. Le vendredi 15 avril 2011, 19:21 par Damish

Setter la taille du cache via le code ne peut pas fonctionner car elle est lue à l'init du thread: System.initializeSystemClass() appelle Integer.getAndRemoveCacheProperties()

S'il y a vraiment une solution en une ligne de code, sans changer les valeurs initiales alors je dis chapeau bas.

17. Le vendredi 15 avril 2011, 20:42 par xav

Après
values[i] = random.nextInt(MAX_VALUE);
rajouter la ligne
values[i] = random.nextInt(127);

le benchmark réalise toujours bien la même fonction :)

18. Le samedi 16 avril 2011, 21:52 par Cynyx

In order to have the benefit of the default IntegerCache, just change the value MAX_VALUE to 100.

Dunno if it's the real answer because it's not really a new line ... but I'm sure the benchmark should be executed in a constant time and faster (because using the java integer cache).

19. Le dimanche 17 avril 2011, 11:44 par David Gageot

Ajouter la ligne :
private static final Object IGNORE = System.getProperties().put("java.lang.Integer.IntegerCache.high", MAX_VALUE);

20. Le dimanche 17 avril 2011, 13:16 par Tony

Augmenter la plage du cache des Integer me parait être une bonne solution: -Djava.lang.Integer.IntegerCache.high=1000

Par défaut, ce cache est utilisé pour les entiers dont la valeur est comprise entre -127 et 128.
On génère ici des entiers compris entre 0 et 1000. Si on ne veut pas augmenter cette plage on peut réduire le MAX_VALUE à 128 pour ne pas dépasser cette limite par défaut et ainsi utiliser le cache.

21. Le jeudi 21 avril 2011, 11:26 par HollyDays

To everyone : changing the value of the property "java.lang.Integer.IntegerCache.high" was a good idea, but doing it in the code does not do the trick at all! This property is read (then removed from the system properties) while the class java.lang.System is loaded by the JVM. You'll have a hard time to get your Java code of yours run before java.lang.System is loaded!

Now I reckon anonyme's idea (comment #14) was interesting. Though what it suggests sounds stupid at first: erasing the SOURCE array before using it is definitely NOT what we want. On the other hand, this (1):

       System.out.println("Benchmarking...");
       for (int run = 1; run <= NB_RUNS; run++) {
           Arrays.fill(boxedValues, null);

and that (2):

       System.out.println("Benchmarking...");
       for (int run = 1; run <= NB_RUNS; run++) {
           boxedValues = new Integer[NB_VALUES];

make the code much faster and more stable in time, because clearing/recreating the array helps the GC a lot to clean up the old Integers.

Running the modified code confirms the guess, though I didn't get the incredibly short times Olivier got: on my PC, (1) always stably runs in 1.5 seconds and (2) in 1.1 seconds (still stable) while the reference code (0) runs in 3.9 to 6.0 seconds (except the first run, which always lasts 2.5 sec).
anonyme's suggestion runs in 0.09 seconds, which confirms that what Olivier got is actually PREVENTING all the Integer instances from being created.

I didn't find any way to do it except... by activating the JVM optimization called "escape analysis". Sun has introduced this option in Java 6 (HotSpot server only), starting JDK 1.6.0_14. This very powerful option aims at detecting useless object creations and allocate values and objects on the stack rather than in the heap as often as possible. To get it activated, just add the JVM parameters "-server -XX:+DoEscapeAnalysis -XX:+AggressiveOpts" in the Java command line. The result is... impressive. Changing the quiz code even becomes useless!

PS: To Olivier: use System.nanoTime() rather than System.currentTimeMillisec() to measure elapsed times. As far as I know, it is more reliable.

PS 2: Combined with JVM options -XX:-EliminateLocks and -XX:+UseBiasedLocking, the "-server -XX:+DoEscapeAnalysis -XX:+AggressiveOpts" options make Eclipse and IntelliJ IDEA run significantly faster. Just try and see...

22. Le jeudi 21 avril 2011, 13:52 par HollyDays

Incidentally, if you succeed preventing the Integer instances from being created, you'll see that running

       for (int i = NB_VALUES; --i >= 0; ) {
           boxedValues[i] = values[i];
       }

is about 10-15% faster than

       for (int i = 0; i < NB_VALUES; i++) {
           boxedValues[i] = values[i];
       }

Because checking the sign bit of a int is something the processor can perform faster than comparing two ints. It is even more visible with the "-server -XX:+DoEscapeAnalysis -XX:+AggressiveOpts" JVM options, which make the Java programme behave more like a C or C++ programme in terms of short-term memory management (use more the stack and less the heap).

23. Le jeudi 21 avril 2011, 14:00 par Olivier Croisier

Actually, the stack/heap optimization is due only to the escape analysis tuning.
Also, enabling escape analysis is redundant with the aggrsesiveOpts parameter.

On jdk-6u20, the AggressiveOpts option does the following :
- activates "EliminateAutoBox" (don't know what it does exactly, but
it looks interesting to investigate)
- sets the Integer cache to 20k
- turns on escape analysis
- configures biased locking to kick in earlier (500ms)

(See jdk\hotspot\src\share\vm\runtime\arguments.cpp in Hotspot's sourcecode.)

24. Le jeudi 21 avril 2011, 16:02 par HollyDays

Interesting...

But though it does most of the trick for your quiz, -XX:+DoEscapeAnalysis doesn't do all of it. I noticed the running times printed out by your quiz aren't far as stable with -XX:+DoEscapeAnalysis alone as with -XX:+AggressiveOpts also: on my PC, they all remain around 80 ms with both options, while they oscillate between 80 and 150 ms with -XX:+DoEscapeAnalysis alone (I ran you quiz with JDK 1.6.0_24).

When you say “sets the Integer cache to 20k”, are you indeed talking about the java.lang.Integer.IntegerCache? The one many people here have been talking about?

Incidentally, I just discovered a very useful JVM option: -XX:+PrintFlagsFinal
It prints out each and every one of the numerous JVM options (about 650!) and their value. It shows that with JRE-6u24, -server implies -XX:+DoEscapeAnalysis but not -XX:+AggressiveOpts.

25. Le jeudi 21 avril 2011, 16:13 par Olivier Croisier

What does AggressiveOpts do is enable an experimental set of options and values, that result from empirical tests from the VM team. They can change from one version (even minor update) to the next, and are not recommended in production.

The good results you see in your setup all come from the Integer cache tuning (the cache that contains Integers from -128 to +127 by default) that comes with AggressiveOpts, not from the EscapeAnalysis.

26. Le dimanche 1 mai 2011, 14:48 par Jan Goyvaerts

So, what's the solution then ? :-)

Adding a line that resets the values in -128/127 range ?

27. Le samedi 21 mai 2011, 09:16 par jujujuju

so we will never get the solution ?

28. Le dimanche 22 mai 2011, 03:47 par Olivier Croisier

Huh ?
The solution has been available for ages now ! Just below the question, in both French and English.

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.