CopyOnWriteArrayList est une implémentation de liste concurrente fournie par le package java.util.concurrent. Elle garantit la sécurité des threads et permet des opérations de lecture sans verrouillage. Les opérations d'écriture, en revanche, sont gérées en créant une nouvelle copie du tableau sous-jacent. Cette stratégie, souvent appelée "copie sur écriture", est similaire à celle utilisée par CopyOnWriteArraySet.

Principe de fonctionnement

Alors que ArrayList n'est pas thread-safe et que Vector utilise un verrouillage qui peut nuire aux performances, CopyOnWriteArrayList adopte une approche différente adaptée aux scénarios où les lectures sont beaucoup plus fréquentes que les écritures.

Dans un environnement où les lectures prédominent, CopyOnWriteArrayList permet des lectures simultanées sans verrouillage, ce qui améliore considérablement les performances. Pour les opérations d'écriture, comme l'ajout d'un élément, le processus implique :

1. La création d'une copie de la liste actuelle.
2. L'exécution de l'opération d'écriture sur cette nouvelle copie.
3. La mise à jour de la référence de la liste d'origine pour pointer vers la nouvelle liste modifiée.

Avantages et inconvénients

Comprendre le mécanisme de CopyOnWriteArrayList facilite l'évaluation de ses avantages et de ses limites :

Avantages :

• Performances de lecture élevées : Les opérations de lecture ne nécessitent aucune synchronisation, ce qui les rend très efficaces, surtout dans les scénarios à forte prédominacne de lectures.
• Aucune ConcurrentModificationException lors de l'itération : Contrairement aux listes standard où la modification pendant l'itération peut entraîner une ConcurrentModificationException, CopyOnWriteArrayList évite ce problème. Les itérateurs opèrent sur une "instantané" de la liste au moment de leur création, sans être effectés par les modifications ultérieures des autres threads.

Inconvénients :

• Consommation mémoire : Chaque opération d'écriture entraîne la copie de l'intégralité du tableau sous-jacent. Pour des listes volumineuses, cela peut entraîner une consommation mémoire importante et potentiellement déclencher des cycles de garbage collection fréquents.
• Absence de cohérence immédiate : CopyOnWriteArrayList n'offre pas la même cohérence forte que Vector, qui verrouille à la fois les lectures et les écritures. Pendant qu'une opération d'écriture est en cours, les lectures peuvent continuer à accéder aux données de l'ancienne version de la liste, ce qui signifie que les modifications les plus récentes ne sont pas immédiatement visibles pour les lecteurs.

Analyse du code source

Examinons quelques méthodes clés pour illustrer le principe de fonctionnement :

Opération d'ajout :

import java.util.concurrent.locks.ReentrantLock;
import java.util.Arrays;

// ... dans la classe CopyOnWriteArrayList

private final ReentrantLock lock = new ReentrantLock(); // Verrou pour synchroniser les écritures

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // Acquiert le verrou pour l'opération d'écriture
    try {
        Object[] elements = getArray(); // Récupère le tableau actuel
        int len = elements.length;
        // Crée un nouveau tableau avec une taille augmentée
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e; // Ajoute le nouvel élément à la fin du nouveau tableau
        setArray(newElements); // Met à jour la référence pour pointer vers le nouveau tableau
        return true;
    } finally {
        lock.unlock(); // Libère le verrou
    }
}

L'opération d'ajout commence par acquérir un verrou, crée une copie du tableau existant, ajoute le nouvel élément à cette copie, puis met à jour la référence pour qu'elle pointe vers le nouveau tableau. Le verrou est libéré à la fin de l'opération.

Opération de suppression :

import java.util.concurrent.locks.ReentrantLock;
import java.util.Arrays;

// ... dans la classe CopyOnWriteArrayList

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // Acquiert le verrou pour l'opération d'écriture
    try {
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index); // Récupère l'élément à supprimer
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0) {
            // Si l'élément à supprimer est le dernier, crée un tableau plus petit
            newElements = Arrays.copyOf(elements, len - 1);
        } else {
            // Sinon, copie les éléments avant et après l'élément à supprimer
            newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
        }
        setArray(newElements); // Met à jour la référence
        return oldValue;
    } finally {
        lock.unlock(); // Libère le verrou
    }
}

La suppression fonctionne de manière similaire : un verrou est acquis, une nouvelle copie du tableau est créée en omettant l'élément à supprimer, puis la référence est mise à jour. Cela s'applique également aux suppressions à la fin de la liste.

Opération de lecture :

// ... dans la classe CopyOnWriteArrayList

public E get(int index) {
    return get(getArray(), index); // Lecture directe sans verrou
}

private E get(Object[] a, int index) {
    return (E) a[index]; // Accès direct à l'élément du tableau
}

Les opérations de lecture, comme la méthode get(int index), accèdent directement au tableau sous-jacent sans nécessiter de verrouillage, ce qui explique leur haute performance.

Conclusion

CopyOnWriteArrayList est une solution efficace pour les scénarios où les opérations de lecture sont fréquentes et les modifications rares. Sa stratégie de "copie sur écriture" offre des lectures sans verrouillage et prévient les ConcurrentModificationException lors des itérations, mais au prix d'une consommation mémoire potentiellement plus élevée et d'une cohérence des données moins immédiate lors des écritures. Le choix entre différentes structures de données concurrentes dépendra toujours des exigences spécifiques du cas d'utilisation.