Vous aimez ce que vous lisez sur ce blog ?
Envie d'aller plus loin avec véritable formation d'expertise en Java ?
Venez suivre ma formation Masterclasse Expertise Java !

"Même un développeur experimenté a besoin de continuer à apprendre. Et dans cette formation... j'ai appris beaucoup !" - A.G., Java Champion

Prochaines sessions inter-entreprises : 28-31 mars 2017 / 13-16 juin 2017
Sessions intra-entreprises sur demande.
Inscrivez-vous vite !

Au coeur du JDK : performance des conversions

Dans l'article précédent, qui portait sur la conversion des nombres, je vous ai affirmé que la conversion d'un nombre en chaîne était plus performante en utilisant Integer.toString() que la concaténation du nombre avec une chaîne vide (""+foo).

Comme je n'ai vu aucun commentaire de type "O RLY ?" à la suite de l'article, j'imagine que vous m'avez cru sur parole. C'est bien :) Mais ça va toujours mieux en le démontrant.
J'ai donc monté un petit benchmark pour comparer les deux techniques, en usant des précautions habituelles (nettoyage de la mémoire, optimisations de la JVM déjouées, code warming...).

Le code source complet est disponible en annexe, et tous les résultats présentés ci-dessous ont été obtenus sur un Intel E6300, 3Go ram sous Windows XP 32b et Java 6.0.24.

Le benchmark

Values : 5000000
Memory : -Xms=512M -Xmx=512M 

Strategy                       | Run     | Time       | Used memory
-------------------------------+---------+------------+-------------
StringConcatenationStrategy    | 01 / 05 |    1140 ms | 304238,28 Mb
StringConcatenationStrategy    | 02 / 05 |    1094 ms | 304238,63 Mb
StringConcatenationStrategy    | 03 / 05 |    1079 ms | 304238,63 Mb
StringConcatenationStrategy    | 04 / 05 |    1093 ms | 304238,63 Mb
StringConcatenationStrategy    | 05 / 05 |    1093 ms | 304238,63 Mb
IntegerToStringStragegy        | 01 / 05 |     828 ms | 285413,44 Mb
IntegerToStringStragegy        | 02 / 05 |     828 ms | 285413,44 Mb
IntegerToStringStragegy        | 03 / 05 |     812 ms | 285413,44 Mb
IntegerToStringStragegy        | 04 / 05 |     829 ms | 285413,44 Mb
IntegerToStringStragegy        | 05 / 05 |     828 ms | 285413,44 Mb

Lorsque suffisamment de mémoire est disponible, la méthode Integer.toString() est donc environ 20% plus rapide, et consomme 5% de mémoire en moins. Intéressant.

Voyons maintenant ce qui se passe si l'on réduit la mémoire disponible.

Values : 5000000
Memory : -Xms=384M -Xmx=384M

Strategy                       | Run     | Time       | Used memory
-------------------------------+---------+------------+-------------
StringConcatenationStrategy    | 01 / 05 |    1532 ms | 322444,23 Mb
StringConcatenationStrategy    | 02 / 05 |    1453 ms | 321792,82 Mb
StringConcatenationStrategy    | 03 / 05 |    1360 ms | 321767,04 Mb
StringConcatenationStrategy    | 04 / 05 |    1343 ms | 321746,69 Mb
StringConcatenationStrategy    | 05 / 05 |    1469 ms | 321730,41 Mb
IntegerToStringStragegy        | 01 / 05 |     703 ms | 285181,73 Mb
IntegerToStringStragegy        | 02 / 05 |     703 ms | 285781,73 Mb
IntegerToStringStragegy        | 03 / 05 |     703 ms | 285998,79 Mb
IntegerToStringStragegy        | 04 / 05 |     703 ms | 283963,53 Mb
IntegerToStringStragegy        | 05 / 05 |     703 ms | 284055,02 Mb


Values : 5000000
Memory : -Xms=350M -Xmx=350M

Strategy                       | Run     | Time       | Used memory
-------------------------------+---------+------------+-------------
StringConcatenationStrategy    | 01 / 05 |    2047 ms | 304093,17 Mb
StringConcatenationStrategy    | 02 / 05 |    1844 ms | 304094,79 Mb
StringConcatenationStrategy    | 03 / 05 |    1844 ms | 304094,73 Mb
StringConcatenationStrategy    | 04 / 05 |    1953 ms | 304094,82 Mb
StringConcatenationStrategy    | 05 / 05 |    1828 ms | 304094,73 Mb
IntegerToStringStragegy        | 01 / 05 |     672 ms | 286847,95 Mb
IntegerToStringStragegy        | 02 / 05 |     672 ms | 286847,84 Mb
IntegerToStringStragegy        | 03 / 05 |     672 ms | 286684,16 Mb
IntegerToStringStragegy        | 04 / 05 |     672 ms | 283937,43 Mb
IntegerToStringStragegy        | 05 / 05 |     672 ms | 285694,12 Mb 

Lorsque la mémoire devient plus rare, l'écart se creuse considérablement entre les deux stratégies.
La raison est à chercher du côté du garbage collector. Le lancement du benchmark avec l'option -verbose:gc fait apparaître de nombreux "Full GC" particulièrement longs, dus à la collecte des chaînes de caractères temporaires créées par concaténation.

Sous le capot

Comment la méthode Integer.toString() parvient-elle à éviter cet écueil ?
Examinons son code.

Tout d'abord, une table est utilisée pour déterminer la taille de la chaîne finale, et ainsi allouer un tableau de caractères taillé sur mesure. Astucieux.

final static int [] sizeTable = 
    { 9, 99, 999, 9999, 99999, 999999, 9999999,
      99999999, 999999999, Integer.MAX_VALUE };
 
static int stringSize(int x) {
    for (int i=0; ; i++)
        if (x <= sizeTable[i])
            return i+1;
}
 
public static String toString(int i) {
    if (i == Integer.MIN_VALUE) return "-2147483648";
    int size = (i < 0) ? stringSize(-i) + 1 : stringSize(i);
    char[] buf = new char[size];
    getChars(i, size, buf);
    return new String(0, size, buf);
}

La méthode getChars() est par contre plus complexe. On appréciera notamment l'implémentation de la multiplication par 100 sous forme de décalages...

static void getChars(int i, int index, char[] buf) {
    int q, r;
    int charPos = index;
    char sign = 0;
 
    if (i < 0) {
        sign = '-';
        i = -i;
    }
 
    // Generate two digits per iteration
    while (i >= 65536) {
        q = i / 100;
        // really: r = i - (q * 100);
        r = i - ((q << 6) + (q << 5) + (q << 2));
        i = q;
        buf [--charPos] = DigitOnes[r];
        buf [--charPos] = DigitTens[r];
    }
 
    // Fall thru to fast mode for smaller numbers
    // assert(i <= 65536, i);
    for (;;) {
        q = (i * 52429) >>> (16+3);
        r = i - ((q << 3) + (q << 1));  // r = i-(q*10) ...
        buf [--charPos] = digits [r];
        i = q;
        if (i == 0) break;
    }
    if (sign != 0) {
        buf [--charPos] = sign;
    }
}

Mais au final, ce code est bien plus rapide et efficace en mémoire que la concaténation du nombre avec une chaîne vide. Surprenant, non ?

Conclusion

Comme je l'avais mentionné dans l'article précédent, l'utilisation de Integer.toString() est plus performant (quoique plus verbeux) que la concaténation du nombre avec une chaîne vide (""+foo). Pas de beaucoup, certes (le benchmark porte tout de même sur un nombre peu courant de conversions), mais le gain est quand même mesurable.

En tout cas, vous avez maintenant des arguments à opposer aux irréductibles de la concaténation !

A bientôt pour de nouvelles aventures au coeur du JDK !


Commentaires

1. Le mercredi 16 novembre 2011, 10:36 par bliz

Qu'en est-il de la méthode String.valueOf(int) ? Est-ce en fait Integer.toString(int) qui est appelée pour effectuer la conversion ?
Merci

2. Le mercredi 16 novembre 2011, 10:43 par Olivier Croisier

Oui, c'est bien Integer.toString() qui est appelé en sous-main :

public static String valueOf(int i) {
    return Integer.toString(i, 10);
}
3. Le lundi 5 décembre 2011, 07:24 par Augustus

Vous écrivez meilleurs articles, tenir bon travail. 08))

4. Le lundi 18 septembre 2017, 20:50 par Abderrahim Laakab

Article tres interessant et tres instructif, merci

Ajouter un commentaire

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