Pourquoi string.intern() est-il si lent ?

Question

Avant que quiconque remette en question le fait d'utiliser string.intern() en général, laissez-moi dire que je en ai besoin dans mon application particulière pour des raisons de mémoire et de performances. [1]

Donc, jusqu'à présent, j'ai utilisé String.intern() en pensant que c'était la manière la plus efficace de le faire. Cependant, j'ai remarqué depuis des lustres que c'était un goulot d'étranglement dans le logiciel. [2]

Ensuite, récemment, j'ai essayé de remplacer le String.intern() par une énorme map où je mets/récupère les chaînes de caractères afin d'obtenir à chaque fois une instance unique. Je m'attendais à ce que cela soit plus lent... mais c'était exactement le contraire! C'était extrêmement plus rapide! Remplacer le intern() par pousser/tirer d'une map (qui réalise exactement la même chose) a résulté en une vitesse plus de dix fois plus rapide.

La question est : pourquoi intern() est-il si lent ?!? Pourquoi n'est-il pas simplement soutenu par une map (ou en fait, juste un ensemble personnalisé) et serait-il extrêmement plus rapide ? Je suis perplexe.

[1] : Pour ceux qui ne sont pas convaincus : il s'agit de traitement de langage naturel et doit traiter des gigaoctets de texte, donc il doit éviter de nombreuses instances d'une même chaîne de caractères pour éviter de faire exploser la mémoire et pour que la comparaison de chaînes de caractères référentielles soit suffisamment rapide.

[2] : sans lui (chaînes de caractères normales) c'est impossible, avec lui, cette étape particulière reste la plus intensive en calcul

ÉDITION :

En raison de l'intérêt surprenant pour ce post, voici un peu de code pour le tester :

http://pastebin.com/4CD8ac69

Et les résultats de la mise en intern de un peu plus d'un million de chaînes de caractères :

• HashMap : 4 secondes
• String.intern() : 54 secondes

Pour éviter tout préchauffage / mise en cache E/S du système d'exploitation et des choses comme ça, l'expérience a été répétée en inversant l'ordre des deux tests :

• String.intern() : 69 secondes
• HashMap : 3 secondes

Comme vous pouvez le constater, la différence est très remarquable, plus de dix fois. (En utilisant OpenJDK 1.6.0_22 64bits ... mais en utilisant celui de Sun a donné des résultats similaires je pense)

Answer 1

Raison la plus probable de la différence de performances: String.intern() est une méthode native, et appeler une méthode native entraîne des frais considérables.

Alors pourquoi est-ce une méthode native? Probablement parce qu'elle utilise le pool de constantes, qui est une construction VM de bas niveau.

Answer 2

@Michael Borgwardt a dit ceci dans un commentaire:

intern() n'est pas synchronisé, du moins au niveau du langage Java.

Je pense que vous voulez dire que la méthode String.intern() n'est pas déclarée comme synchronized dans le code source de la classe String. Et en effet, c'est une affirmation correcte.

Cependant:

• Déclarer intern() comme synchronized verrouillerait uniquement l'instance actuelle de String, car c'est une méthode d'instance, et non une méthode statique. Ainsi, ils ne pourraient pas implémenter la synchronisation du pool de chaînes de cette manière.

• Si vous prenez du recul et y réfléchissez, le pool de chaînes doit effectuer une sorte de synchronisation interne. Sinon, il serait inutilisable dans une application multi-threadée, car il n'y a tout simplement aucun moyen pratique pour que tout le code utilisant la méthode intern() fasse une synchronisation externe.

Ainsi, la synchronisation interne que le pool de chaînes effectue pourrait être un goulot d'étranglement dans une application multi-threadée qui utilise intensément intern().

Answer 3

Je ne peux pas parler d'une grande expérience avec cela, mais d'après la documentation de String :

"Lorsque la méthode intern est invoquée, si le pool contient déjà une chaîne égale à cet objet String tel que déterminé par la méthode {@link #equals(Object)}, alors la chaîne du pool est retournée. Sinon, cet objet String est ajouté au pool et une référence à cet objet String est retournée."

Lorsqu'il s'agit de traiter un grand nombre d'objets, toute solution impliquant le hachage sera plus performante que celle qui n'en utilise pas. Je pense que vous ne faites que voir le résultat d'une utilisation incorrecte d'une fonctionnalité du langage Java. L'interning n'est pas là pour agir comme une Map de chaînes pour votre usage. Vous devriez utiliser une Map pour cela (ou un Set, selon le cas). La table de chaînes est pour l'optimisation au niveau du langage, pas au niveau de l'application.

Answer 4

Cet article discute de la mise en œuvre de String.intern(). En Java 6 et 7, l'implémentation utilisait une table de hachage de taille fixe (1009), de sorte que plus le nombre d'entrées grandissait, plus les performances devenaient de l'ordre de O(n). La taille fixe peut être modifiée en utilisant -XX:StringTableSize=N. Apparemment, sous Java 8, la taille par défaut est plus grande mais le problème reste le même.