Pourquoi Arrays.fill n'est plus utilisé dans HashMap.clear ?

Question

Regarder dans HashMap.clear() mise en œuvre, j'ai remarqué une chose étrange. Voici comment cela se présente dans OpenJDK 7u40 :

public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

Et voici à quoi cela ressemble en OpenJDK 8u40 :

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

Je comprends que maintenant le table peut être nul pour une carte vide, donc une vérification supplémentaire et une mise en cache dans une variable locale sont nécessaires. Mais pourquoi Arrays.fill a été remplacée par une boucle for ?

Il semble que le changement ait été introduit en cet engagement . Malheureusement, je n'ai pas trouvé d'explication sur la raison pour laquelle une simple boucle for pourrait être meilleure que Arrays.fill . Est-ce plus rapide ? Ou plus sûr ?

Answer 1

Je vais essayer de résumer trois versions moins raisonnables qui ont été proposées dans les commentaires.

@Holger dit :

Je suppose que c'est pour éviter que la classe java.util.Arrays ne soit chargée comme un effet secondaire de cette méthode. Pour le code de l'application, ce n'est généralement pas un problème.

C'est la chose la plus facile à tester. Compilons un tel programme :

public class HashMapTest {
    public static void main(String[] args) {
        new java.util.HashMap();
    }
}

Exécutez-le avec java -verbose:class HashMapTest . Cela imprimera les événements de chargement de classe au fur et à mesure qu'ils se produisent. Avec le JDK 1.8.0_60, je vois plus de 400 classes chargées :

... 155 lines skipped ...
[Loaded java.util.Set from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.AbstractSet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptySet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableCollection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableRandomAccessList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.Reflection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.HashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.HashMap$Node from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$3 from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$ReflectionData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$Atomic from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.AbstractRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.GenericDeclRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.ClassRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$AnnotationData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.annotation.AnnotationType from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.WeakHashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.ClassValue$ClassValueMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.Modifier from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.LangReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.ReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.Arrays from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
...

Comme vous pouvez le voir, HashMap est chargé bien avant le code de l'application et Arrays est chargé seulement 14 classes après HashMap . Le site HashMap La charge est déclenchée par sun.reflect.Reflection initialisation comme il a HashMap champs statiques. Le site Arrays La charge est susceptible d'être déclenchée par WeakHashMap charge qui a en fait Arrays.fill dans le clear() méthode. Le site WeakHashMap La charge est déclenchée par java.lang.ClassValue$ClassValueMap qui prolonge WeakHashMap . Le site ClassValueMap est présent dans chaque java.lang.Class instance. Il me semble donc que sans Arrays le JDK ne peut pas être initialisé du tout. De même, la classe Arrays L'initialisateur statique est très court, il ne fait qu'initialiser le mécanisme d'assertion. Ce mécanisme est utilisé dans de nombreuses autres classes (dont, par exemple, java.lang.Throwable qui est chargé très tôt). Aucune autre étape d'initialisation statique n'est effectuée dans java.util.Arrays . La version de @Holger me semble donc incorrecte.

Ici, nous avons aussi trouvé des choses très intéressantes. Le site WeakHashMap.clear() utilise toujours Arrays.fill . C'est intéressant quand il est apparu là, mais malheureusement, cela va à temps préhistoriques (elle était déjà présente dans le tout premier dépôt public d'OpenJDK).

Ensuite, @MarcoTopolnik dit :

Plus sûr sûrement pas, mais il pourrait être plus rapide lorsque le fill n'est pas inlined et tab est court. Sur HotSpot, tant la boucle que l'explicite fill aura pour résultat un compilateur intrinsèque rapide (dans un scénario de jour heureux).

C'était en fait surprenant pour moi que Arrays.fill n'est pas directement intrinsiqué (voir liste intrinsèque généré par @apangin ). Il semble qu'une telle boucle puisse être reconnue et vectorisée par la JVM sans traitement intrinsèque explicite. Il est donc vrai que l'appel supplémentaire peut ne pas être inlined dans des cas très spécifiques (par exemple si MaxInlineLevel est atteinte). D'un autre côté, il s'agit d'une situation très rare et d'un seul appel, ce n'est pas un appel à l'intérieur d'une boucle, et c'est un appel statique, pas virtuel/interface, donc l'amélioration des performances pourrait être seulement marginale et seulement dans certains scénarios spécifiques. Ce n'est pas ce qui intéresse généralement les développeurs de JVM.

Il convient également de noter que même le compilateur "client" de C1 (niveau 1-3) est capable de mettre en ligne les éléments suivants Arrays.fill appelé, par exemple, dans WeakHashMap.clear() comme le journal inlining ( -XX:+UnlockDiagnosticVMOptions -XX:+PrintCompilation -XX:+PrintInlining ) dit :

36       3  java.util.WeakHashMap::clear (50 bytes)
     !m        @ 4   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 28   java.util.Arrays::fill (21 bytes)
     !m        @ 40   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 1   java.util.AbstractMap::<init> (5 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
               @ 9   java.lang.ref.ReferenceQueue::<init> (27 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
                 @ 10   java.lang.ref.ReferenceQueue$Lock::<init> (5 bytes)   unloaded signature classes
               @ 62   java.lang.Float::isNaN (12 bytes)   inline (hot)
               @ 112   java.util.WeakHashMap::newTable (8 bytes)   inline (hot)

Bien entendu, le compilateur intelligent et puissant de C2 'server' permet également de l'intégrer facilement. Je ne vois donc aucun problème ici. Il semble que la version de @Marco ne soit pas correcte non plus.

Enfin, nous avons un couple de commentaires de @StuartMarks (qui est développeur de JDK, donc une voix officielle) :

Intéressant. Mon intuition est que c'est une erreur. Le fil de discussion pour cette modification est ici et il fait référence à un fil précédent c'est-à-dire suite ici . Le message initial de ce fil de discussion précédent indique un prototype de HashMap.java dans le dépôt CVS de Doug Lea. Je ne sais pas d'où cela vient. Il ne semble pas correspondre à quoi que ce soit dans l'historique d'OpenJDK.

... Quoi qu'il en soit, il pourrait s'agir d'un vieil instantané ; la boucle for se trouvait dans la méthode clear() depuis de nombreuses années. L'appel Arrays.fill() a été introduit par la méthode cette série de modifications Il n'a donc été présent dans l'arbre que pendant quelques mois. Notez également que le calcul de puissance de deux basé sur Integer.highestOneBit() introduit par cette série de modifications a également disparu au même moment, bien que cela ait été noté mais écarté pendant l'examen. Hmmm.

En effet, le HashMap.clear() contenu la boucle de nombreuses années, a été a remplacé avec Arrays.fill le 10 avril 2013 et est restée moins d'une demi-année jusqu'au 4 septembre, date à laquelle la discussion a commencé. commettre a été introduit. Le commit discuté était en fait une réécriture majeure de l'application HashMap internes à réparer JDK-8023463 problème. C'était une longue histoire sur la possibilité d'empoisonner les HashMap avec des clés ayant des codes de hachage en double, ce qui réduit HashMap la vitesse de recherche est linéaire, ce qui la rend vulnérable aux attaques par déni de service. Les tentatives pour résoudre ce problème ont été effectuées dans le JDK-7, y compris une certaine randomisation du code de hachage des chaînes. Il semble donc que le HashMap a été bifurquée du commit précédent, développée indépendamment, puis fusionnée dans la branche principale en écrasant plusieurs changements introduits entre-temps.

Nous pouvons soutenir cette hypothèse en effectuant un test de diff. Prenez le version où Arrays.fill a été supprimé (2013-09-04) et le comparer avec version précédente (2013-07-30). Le site diff -U0 La sortie comporte 4341 lignes. Maintenant, faisons une comparaison avec le version avant un lorsque Arrays.fill a été ajouté (2013-04-01). Maintenant diff -U0 ne contient que 2680 lignes. Ainsi, la nouvelle version ressemble davantage à l'ancienne qu'à son parent immédiat.

Conclusion

Pour conclure, je suis donc d'accord avec Stuart Marks. Il n'y avait aucune raison concrète d'enlever Arrays.fill c'est juste parce que le changement entre les deux a été écrasé par erreur. En utilisant Arrays.fill est tout à fait correct tant dans le code du JDK que dans les applications de l'utilisateur et utilisé, par exemple, dans WeakHashMap . Le site Arrays est chargée de toute façon assez tôt au cours de l'initialisation du JDK, elle possède un initialisateur statique très simple et une classe Arrays.fill peut être facilement intégrée, même par le compilateur du client, de sorte qu'aucun inconvénient en termes de performances n'est à signaler.

Answer 2

Pour moi, la raison est une amélioration probable des performances, à un coût négligeable en termes de clarté du code.

Notez que l'implémentation de la fill est triviale, une simple boucle for fixant chaque élément du tableau à null. Ainsi, remplacer un appel à cette méthode par l'implémentation réelle n'entraîne pas de dégradation significative de la clarté/concision de la méthode de l'appelant.

Les avantages potentiels en termes de performances ne sont pas si négligeables, si l'on considère tout ce qui est en jeu :

1. Il ne sera pas nécessaire pour la JVM de résoudre le problème du Arrays ainsi que son chargement et son initialisation si nécessaire. Il s'agit d'un processus non trivial au cours duquel la JVM effectue plusieurs étapes. Tout d'abord, elle vérifie le chargeur de classe pour voir si la classe est déjà chargée, et ce à chaque fois qu'une méthode est appelée ; il y a bien sûr des optimisations à ce niveau, mais cela demande quand même un certain effort. Si la classe n'est pas chargée, la JVM devra passer par le processus coûteux de son chargement, de la vérification du bytecode, de la résolution des autres dépendances nécessaires et enfin de l'initialisation statique de la classe (qui peut être arbitrairement coûteuse). Étant donné que HashMap est une telle classe de base, et que Arrays est une classe si vaste (plus de 3600 lignes) que le fait d'éviter ces coûts peut se traduire par des économies notables.

2. Comme il n'y a pas de Arrays.fill(...) la JVM n'aura pas à décider si/quand elle doit intégrer la méthode dans le corps de l'appelant. Puisque HashMap#clear() a tendance à être appelé souvent, la JVM finira par effectuer l'inlining, ce qui nécessite une recompilation JIT de la fonction clear méthode. Sans appel de méthode, clear s'exécutera toujours à la vitesse maximale (une fois qu'il aura été initialement JITé).

Un autre avantage de ne plus appeler les méthodes dans Arrays est qu'il simplifie le graphe de dépendances à l'intérieur de l'application java.util car une dépendance est supprimée.

Answer 3

Je vais tirer dans le noir ici...

Mon devinez est qu'il aurait pu être modifié afin de préparer le terrain pour Spécialisation (aka generics over primitive types). Peut-être (et j'insiste sur peut-être ), ce changement est destiné à faciliter la transition vers Java 10, dans le cas où la spécialisation ferait partie du JDK.

Si vous regardez le Document sur l'état de la spécialisation , Restrictions linguistiques il est indiqué ce qui suit :

Étant donné que les variables de type quelconque peuvent prendre des valeurs ainsi que des types de référence, les règles de vérification de type impliquant de telles variables de type (désormais, "avars"). Par exemple, pour un avar T :

• Impossible de convertir null en une variable dont le type est T
• Impossible de comparer T à null
• Impossible de convertir T en objet
• Impossible de convertir T[] en Object[]
• ...

(C'est moi qui souligne).

Et en avant dans le Transformations de spécialisation section, il est dit :

Lors de la spécialisation d'une classe any-generic, le spécialisateur va effectuer un certain nombre de transformations, la plupart localisées, mais certaines nécessitant une vue globale d'une classe ou d'une méthode, notamment :

• ...
• La substitution de variables de type et le détournement de noms sont effectués sur les signatures de toutes les méthodes.
• ...

Plus loin, vers la fin du document, dans la rubrique Enquête complémentaire section, il est dit :

Bien que nos expériences aient prouvé que la spécialisation de cette manière est pratique, des recherches supplémentaires sont nécessaires. Plus précisément, nous devons réaliser un certain nombre d'expériences ciblées visant à modifier les bibliothèques de base du JDK, notamment Collections et Streams.

---

Maintenant, en ce qui concerne le changement...

Si le Arrays.fill(Object[] array, Object value) va être spécialisée, alors sa signature doit être changée en Arrays.fill(T[] array, T value) . Toutefois, ce cas est spécifiquement répertorié dans le (déjà mentionné) Restrictions linguistiques (cela violerait les articles mis en avant). Donc peut-être quelqu'un a décidé qu'il serait préférable de ne pas l'utiliser à partir de la HashMap.clear() surtout si value est null .

Answer 4

Il n'y a pas de différence réelle dans la fonctionnalité entre les deux versions de la boucle. Arrays.fill fait exactement la même chose.

Le choix de l'utiliser ou non n'est donc pas nécessairement considéré comme une erreur. C'est au développeur de décider quand il s'agit de ce genre de micro-gestion.

Il y a deux préoccupations distinctes pour chaque approche :

• en utilisant le Arrays.fill rend le code moins verbeux et plus lisible.
• en boucle directement dans le HashMap (comme la version 8) est en fait une meilleure option du point de vue des performances. Bien que l'insertion de l'élément Arrays est négligeable, elle peut le devenir lorsqu'il s'agit de quelque chose d'aussi répandu que les HashMap où chaque amélioration des performances a un effet important (imaginez la plus petite réduction de l'empreinte d'un HashMap dans une application web complète). Prenez en considération le fait que la classe Arrays n'a été utilisée que pour cette seule boucle. Le changement est suffisamment faible pour ne pas rendre la méthode clear moins lisible.

La raison précise ne peut être trouvée sans demander au développeur qui a fait cela, mais je soupçonne qu'il s'agit soit d'une erreur, soit d'une petite amélioration. Meilleure option.

A mon avis, cela peut être considéré comme une amélioration, même si ce n'est que par accident.