Une histoire de deux itérateurs : stratégies de modification compétitives en Java

L'auteur de la note est Grzegorz Mirek, un développeur de logiciels de Cracovie (Pologne). Il a commencé à développer en Java il y a environ 6 ans, alors qu'il était encore à l'université, et depuis lors, il perfectionne sans relâche ses compétences dans ce domaine. Il s'intéresse particulièrement aux performances et à l'optimisation des JVM, ce qu'il écrit principalement sur son blog . Certaines des questions d'entretien Java les plus populaires incluent : Quelle est la différence entre les itérateurs à échec rapide et à sécurité intégrée ? La réponse la plus simplifiée à cette question est la suivante : un itérateur à sécurité intégrée lève une ConcurrentModificationException si la collection change pendant l'itération, mais pas un itérateur à sécurité intégrée. Bien que cela semble tout à fait significatif, on ne sait toujours pas ce que l'intervieweur entend par sécurité intégrée ? Les spécifications du langage Java ne définissent pas ce terme par rapport aux itérateurs. Cependant, il existe quatre stratégies de modification compétitives.

Modification compétitive

Tout d’abord, définissons ce qu’est une modification compétitive (ou parallèle). Disons que nous avons une collection et que lorsque l'itérateur est actif, des changements se produisent qui ne proviennent pas de cet itérateur. Dans ce cas, nous obtenons une modification compétitive. Laissez-moi vous donner un exemple simple : disons que nous avons plusieurs fils de discussion. Le premier thread itère et le deuxième thread insère ou supprime des éléments de la même collection. Cependant, nous pouvons obtenir une ConcurrentModificationException lors de l'exécution dans un environnement monothread :

List<String> cities = new ArrayList<>();
cities.add(“Warsaw”);
cities.add(“Prague”);
cities.add(“Budapest”);
 
Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Échec rapide

Le fragment de code ci-dessus est un exemple d’ itérateur à échec rapide . Comme vous pouvez le voir, une ConcurrentModificationException a été levée lors de la tentative de récupération du deuxième élément de l'itérateur . Comment un itérateur sait-il que la collection a été modifiée depuis sa création ? Par exemple, la collection peut avoir un horodatage, par exemple lastModified . Lors de la création d'un itérateur, vous devez copier ce champ et le stocker dans un objet itérateur. Ensuite, chaque fois que vous appellerez la méthode next() , vous comparerez simplement la valeur lastModified de la collection avec la copie de l'itérateur. Une approche très similaire est utilisée, par exemple, dans l'implémentation de la classe ArrayList . Il possède une variable d'instance modCount qui stocke le nombre de fois où la liste a été modifiée :

final void checkForComodification() {
   if (modCount != expectedModCount)
       throw new ConcurrentModificationException();
}

Il est important de noter que les itérateurs à échec rapide fonctionnent de manière optimale, ce qui signifie qu'il n'y a aucune garantie qu'une ConcurrentModificationException sera levée en cas de modification simultanée. Vous ne devriez donc pas vous y fier, mais plutôt les utiliser pour détecter les erreurs. La plupart des collections non simultanées fournissent des itérateurs à échec rapide .

Faible cohérence

La plupart des collections simultanées du package java.util.concurrent (telles que ConcurrentHashMap et la plupart des Queue ) fournissent des itérateurs faiblement cohérents. La signification de ce terme est très bien expliquée dans la documentation :

• Ils peuvent être traités concomitamment à d’autres opérations
• Ils ne lancent jamais d' exception ConcurrentModificationException
• Ils sont garantis de traverser les éléments existants au moment où l'itérateur a été créé exactement une fois et peuvent (mais ne sont pas obligés de le faire) refléter les modifications ultérieures.

Instantané

Avec cette stratégie, l'itérateur est associé à l'état de la collection au moment de sa création - il s'agit d'un instantané de la collection. Toute modification apportée à la collection d'origine entraîne la création d'une nouvelle version de la structure de données sous-jacente. Cela laisse notre instantané inchangé, il ne reflète donc pas les modifications apportées à la collection survenues après la création de l'itérateur. Il s’agit de la bonne vieille technique de copie sur écriture (COW) . Cela résout complètement le problème des modifications simultanées, donc une ConcurrentModificationException n'est pas générée avec cette approche. De plus, les itérateurs ne prennent pas en charge les opérations qui modifient des éléments. Les collections de copie sur écriture ont tendance à être trop coûteuses à utiliser, mais il est logique de les utiliser si les modifications se produisent beaucoup moins fréquemment que les parcours d'itérateurs. Des exemples sont les classes CopyOnWriteArrayList et CopyOnWriteArraySet .

Comportement indéfini

Vous pouvez rencontrer un comportement indéfini dans les types de collections hérités tels que Vector et Hashtable . Les deux ont des itérateurs standard à échec rapide , mais en plus, ils permettent l'utilisation d'implémentations de l' interface Enumeration , et ils ne savent pas comment se comporter en cas de modification simultanée. Vous pouvez rencontrer certains éléments répétés ou manquants, voire d'étranges exceptions. Il vaut mieux ne pas jouer avec eux !