nov.
2011
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
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
Oui, c'est bien Integer.toString() qui est appelé en sous-main :
Vous écrivez meilleurs articles, tenir bon travail. 08))
Article tres interessant et tres instructif, merci