Skip navigation

Le parcours d’une Collection en Java est assez simple. Cependant si votre Collection est partagée par plusieurs threads et que certains itèrent dessus pendant que d’autres la modifient ça se complique… Plusieurs possibilités s’offrent à vous, mais il n’y a pas de recette miracle…

Tout d’abord un petit rappel : Utiliser la boucle « for améliorée » en Java (correspondant à un foreach dans d’autres langages) renvient exactement au même qu’à utiliser un Iterator. Le compilateur Java transforme la boucle for en un Iterator lors de la compilation du code source en bytecode. Ces deux morceaux de code sont strictement identique au niveau du bytecode généré :

List<Integer>  a = new ArrayList<Integer>();
for (Integer integer : a)
{
  integer.toString();
}
// …
List<Integer>  a = new ArrayList<Integer>();
for (Iterator iterator = a.iterator(); iterator.hasNext();)
{
  Integer integer = (Integer) iterator.next();
  integer.toString();
}

Revenons à nos moutons… Heu… nos itérations ! Tout d’abord si la liste ne subit aucune modification, que les différents threads ne font qu’itérer sur la Collection, alors aucun problème. Par contre comment gérer le cas d’un thread effectuant des modifications sur une Collection lorsqu’un autre thread est en train d’itérer sur cette même Collection ? Qu’est ce qui fonctionne et qu’est ce qui ne fonctionne pas ? Nous allons le voir par la suite.

    1) Ce qui fonctionne

    a. Ne pas partager la référence de la Collection

Cela parait bête mais c’est le meilleur moyen de ne pas avoir de problèmes de concurrence. Cette règle ne s’applique pas qu’aux Collections. Pour ne pas avoir de problèmes de concurrence d’accès à une ressource il « suffit » de ne pas la partager. Pour ne pas partager une Collection il faut en faire une copie (un clone) avant de la transmettre à un thread. Cependant si votre Collection est trop grande il sera parfois impossible de passer une copie de la collection à chacun des threads tant la consommation mémoire deviendra importante.

    b. Utiliser des Collections décorées par Collections.synchronizedXXX() et un block synchronised

La Collection partagée doit être décorée avec une des méthodes Collections.synchronizedXXX (où XXX = Set, Map, List, …) avant d’être transmise aux différents threads .Ensuite l’itération sur cette Collection doit utiliser un block synchronized

Collection<Integer> sharedSynchronizedCollection = Collections.synchronizedSet(new HashSet<Integer>());
// …
synchronized (sharedCollection) {
    for (Integer element : sharedCollection) {
        // would do stuff here in real world
    }
}

Cette méthode n’est valable que si le travail effectué dans le for n’est pas trop couteux, car pendant tout le temps de l’itération l’accès à la Collection est interrompu.

     c. Utiliser des Collections décorrée par Collections.synchronizedXXX() et la méthode toArray()

Si le travail effectué dans le for est trop long, une alternative possible est de transformer la Collection en tableau juste avant d’itérer dessus :

Collection<Integer> sharedSynchronizedCollection = Collections.synchronizedSet(new HashSet<Integer>());
// …
Integer[] integers = sharedSynchronizedCollection.toArray(new Integer[sharedSynchronizedCollection.size()]);
for (Integer element : integers) {
    // long work here
}

Cette méthode plus gourmande en mémoire vous permettra de ne bloquer l’accès à la Collection que le temps de la conversion de la Collection en tableau. Vous itérez par contre deux fois sur la Collection, une fois pour la conversion, une fois pour effectuer votre traitement métier.

     d. Utiliser un CopyOnWriteArraySet ou CopyOnWriteArrayList

Si les modifications dans la Collection sont peu fréquentes alors vous pouvez décorer un Set ou une List avec l’une de ces deux classes. L’Iterator renvoyé pour le parcours de la Collection contiendra tous les éléments de la liste présents au début de l’itération. Toutes les modifications faites par la suite sur la Collection ne seront pas visible à partir de l’Iterator. A chaque modification de la Collection une copie du tableau interne est effectuée, c’est la raison pour laquelle cette implémentation est à utiliser uniquement si les modifications ont peu de chances de se produire.

Collection<Integer> sharedCopyOnWriteArraySet = new CopyOnWriteArraySet<Integer>(new HashSet<Integer>());
// …
for (Integer element : sharedCopyOnWriteArraySet) {
    // would do stuff here in real world
}

 

    2. Ce qui ne fonctionne pas

     a. Une boucle for sur une Collection synchronisée

Comme le précise la Javadoc l’utilisation d’une boucle for sur une collection synchronisée engendrera un comportement non déterministe si l’itération n’est pas entourée d’un block synchronized. Il est fort probable qu’une ConcurrentModificationException soit lancée dans ce cas :

Collection<Integer> sharedSynchronizedCollection = Collections.synchronizedSet(new HashSet<Integer>());
// …
for (Integer element : sharedSynchronizedCollection) {
    // would do stuff here in real world<
}

    b. Entourer le for d’un block synchronized sur une collection non sonchronisée

Entourer une Collection qui n’a pas été décorée par Collections.synchronizedXXX() d’un block synchronized ne fonctionne pas :

Collection<Integer> sharedCollection = new HashSet<Integer>();
// …
synchronized (sharedCollection) {
    for (Integer element : sharedCollection) {
        // would do stuff here in real world
    }
}

D’autres thread pourront ajouter des éléments à la Collection ce qui provoquera une ConcurrentModificationException.

     c. Utiliser la méthode toArray() sur un Collection non synchronisée

Un toArray utilise dans certains cas un Iterator (selon l’implémentation réelle se cachant derrière la Collection). Comme nous avons vu ci-dessus qu’un block synchronized sur une liste non synchronisée ne fonctionne pas avec un for, il ne fonctionnera pas non plus avec un Iterator (cf le rappel en début d’article) :

Collection<Integer> sharedCollection = new HashSet<Integer>();
// …
Integer[] integers = sharedCollection.toArray(new Integer[sharedCollection.size()]);
for (Integer element : sharedCollection) {
    // would do stuff here in real world
}

 

Comme je l’écrivais en début d’article. Il existe plusieurs moyens de parcourir une Collection de façon thread-safe. De mon point de vue, la solution 1)a. est la meilleure solution lorsqu’elle peut être appliquée, les solutions 1)c. et 1)d. sont de bonnes candidates sinon. La solution 1)b. n’est à appliquer que si le traitement dans le for est extrêmement rapide et que l’accès en concurrence très faible. Ci-dessous un test Junit que vous pouvez exécuter pour vous convaincre de ce que je vous ai décrit dans cet article :

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.concurrent.Callable;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
 
import org.junit.Before;
import org.junit.Test;
 
public class IterationCollectionTest {
 
  private static final int COLLECTION_SIZE = 500;
 
  private static final int NUMBER_OF_THREAD_IN_PARALLEL = 8;
 
  private static final int NUMBER_OF_TASKS = 50;
 
  private static final long millis = 0;
 
  private static final int nanos = 500;
 
  private Exception exception = null;
  private Collection<Integer> sharedSynchronizedCollection;
  private Collection<Integer> sharedCollection;
 
  Collection<Callable<Object>> tasks;
 
  @Before
  public void initTest() {
    exception = null;
 
    sharedSynchronizedCollection = Collections.synchronizedSet(new HashSet<Integer>(COLLECTION_SIZE));
    sharedCollection = new HashSet<Integer>(COLLECTION_SIZE);
    for (int i = 0; i < COLLECTION_SIZE; i++) {
      sharedSynchronizedCollection.add(i);
      sharedCollection.add(i);
    }
 
    tasks = new ArrayList<Callable<Object>>();
  }
 
  /** Illustration 1) b. */
  @Test
  public void assertForLoopWithinSynchronizedBlockOnSharedSynchronizedCollectionInMultithreadEnvironnementWork() throws Exception
  {
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new SynchronyzedForAndModifyRunnable(sharedSynchronizedCollection));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  /** Illustration 1) c. */
  @Test
  public void assertForLoopWithToArrayOnSharedSynchronizedCollectionInMultithreadEnvironnementWork() throws Exception {
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new ToArrayForAndModifyRunnable(sharedSynchronizedCollection));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  /** Illustration 1) d. */
  @Test
  public void assertForLoopOnSharedCopyOnWriteArraySetInMultithreadEnvironnementWork() throws Exception {
    Collection<Integer> sharedCopyOnWriteArraySet = new CopyOnWriteArraySet<Integer>(sharedCollection);
 
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new ForAndModifyRunnable(sharedCopyOnWriteArraySet));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  /** Illustration 2) a. */
  @Test(expected = ConcurrentModificationException.class)
  public void assertForLoopOnSharedSynchronizedCollectionInMultithreadEnvironnementDoesNotWork() throws Exception {
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new ForAndModifyRunnable(sharedSynchronizedCollection));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  /** Illustration 2) b. */
  @Test(expected = ConcurrentModificationException.class)
  public void assertForLoopWithinSynchronizedBlockOnSharedCollectionInMultithreadEnvironnementDoesNotWork() throws Exception
  {
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new SynchronyzedForAndModifyRunnable(sharedCollection));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  /** Illustration 2) c. */
  @Test(expected = ConcurrentModificationException.class)
  public void assertForLoopWithToArrayOnSharedCollectionInMultithreadEnvironnementDoesNotWork() throws Exception {
    for (int i = 0; i < NUMBER_OF_TASKS; i++) {
      tasks.add(new ToArrayForAndModifyRunnable(sharedCollection));
    }
 
    ExecutorService threadPool = Executors.newFixedThreadPool(NUMBER_OF_THREAD_IN_PARALLEL);
    threadPool.invokeAll(tasks);
    threadPool.shutdown();
 
    throwExceptionIfHappened();
  }
 
  private class ForAndModifyRunnable implements Callable<Object> {
 
    Collection<Integer> collection;
 
    public ForAndModifyRunnable(Collection<Integer> collection) {
      this.collection = collection;
    }
 
    @Override
    public Object call() throws Exception {
      try {
        collection.add(collection.size());
        for (Integer element : collection) {
          workInLoop(element);
        }
      }
      catch (Exception e) {
        saveException(e);
      }
      return null;
    }
  }
 
  private class SynchronyzedForAndModifyRunnable implements Callable<Object> {
 
    Collection<Integer> collection;
 
    public SynchronyzedForAndModifyRunnable(Collection<Integer> collection) {
      this.collection = collection;
    }
 
    @Override
    public Object call() throws Exception {
      try {
        collection.add(collection.size());
        synchronized (collection) {
          for (Integer element : collection) {
            workInLoop(element);
          }
        }
      }
      catch (Exception e) {
        saveException(e);
      }
      return null;
    }
  }
 
  private class ToArrayForAndModifyRunnable implements Callable<Object> {
 
    Collection<Integer> collection;
 
    public ToArrayForAndModifyRunnable(Collection<Integer> collection) {
      this.collection = collection;
    }
 
    @Override
    public Object call() throws Exception {
      try {
        collection.add(collection.size());
 
        Integer[] integers = collection.toArray(new Integer[collection.size()]);
        for (Integer element : integers) {
          workInLoop(element);
        }
      }
      catch (Exception e) {
        saveException(e);
      }
      return null;
    }
  }
 
  private void saveException(Exception error) {
    this.exception = error;
  }
 
  private void throwExceptionIfHappened() throws Exception {
    if (exception != null) {
      throw exception;
    }
  }
 
  private void workInLoop(Integer element) {
    try {
      Thread.sleep(millis, nanos);
    }
    catch (InterruptedException e) {
      e.printStackTrace();
    }
  }
}