Ceci est un post traduit par IA.
[Java] Synchronized Collection vs Concurrent Collection
- Langue de rédaction : Coréen
- •
-
Pays de référence : Tous les pays
- •
- Technologies de l'information
0000-00-00 00:00:00
Choisir la langue
Texte résumé par l'IA durumis
- Les collections synchronisées telles que Vector, Hashtable et Collections.synchronizedXXX utilisent le mot-clé synchronized en interne pour garantir la simultanéité, mais peuvent poser des problèmes de performance en regroupant plusieurs opérations ou en réduisant les performances.
- Le package java.util.concurrent fournit diverses classes de collections parallèles telles que CopyOnWriteArrayList, ConcurrentMap, ConcurrentHashMap, qui offrent de meilleures performances que les collections synchronisées.
- Les collections parallèles telles que CopyOnWriteArrayList et ConcurrentHashMap offrent de meilleures performances en lecture que les collections synchronisées et sont efficaces pour les cas où les opérations d'écriture sont relativement rares.
Collection synchronisée
Les collections synchronisées sont représentées par les classes suivantes :
- Vector
- Hashtable
- Collections.synchronizedXXX
Toutes ces classes utilisent le mot-clé synchronized dans leurs méthodes publiques pour garantir la synchronisation et contrôler l'accès aux données internes par un seul thread à la fois.
Vector
public class Vector extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable {
...
public synchronized boolean add(E e) {
modCount++;
add(e, elementData, elementCount);
return true;
}
... Si nous examinons la méthode add() de la classe Vector, qui permet d'ajouter des éléments, nous remarquons la présence du mot-clé synchronized. Cela signifie que l'insertion d'éléments dans Vector est synchronisée.
Hashtable
public class Hashtable extends Dictionary
implements Map, Cloneable, java.io.Serializable {
...
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
... En examinant la méthode contains() de la classe Hashtable, qui vérifie la présence d'une valeur identique, nous constatons qu'elle utilise également le mot-clé synchronized, comme la classe Vector.
Collections.synchronizedXXX
Examinons maintenant la classe SynchronizedList, créée à l'aide de la méthode Collections.synchronizedList().
static class SynchronizedList extends SynchronizedCollection
implements List {
final Object mutex;
...
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
... En observant les méthodes de la classe SynchronizedList, nous constatons que toutes utilisent le mot-clé synchronized. Cependant, la synchronisation est implémentée ici via un mutex à l'aide d'un bloc synchronized. Toutes les méthodes partagent le même objet mutex. Dès qu'un thread entre dans un bloc synchronized, tous les autres threads bloquent l'accès aux blocs synchronized des autres méthodes.
Problèmes liés aux collections synchronisées
Bien que les collections synchronisées puissent être nécessaires dans des environnements multithreads, il est préférable d'utiliser d'autres méthodes de synchronisation lorsque possible. Il y a deux raisons principales à cela.
Combinaison de plusieurs opérations en une seule
Les classes de collections synchronisées garantissent la synchronisation dans des environnements multithreads. Cependant, des problèmes peuvent survenir si nous devons combiner plusieurs opérations en une seule opération. Même en utilisant ces collections synchronisées, le bon fonctionnement n'est pas garanti.
final List list = Collections.synchronizedList(new ArrayList());
final int nThreads = 2;
ExecutorService es = Executors.newFixedThreadPool(nThreads);
for (int i = 0; i < nThreads; i++) {
es.execute(new Runnable() {
public void run() {
while(true) {
try {
list.clear();
list.add("888");
list.remove(0);
} catch(IndexOutOfBoundsException e) {
e.printStackTrace();
}
}
}
}); Si le thread A exécute remove(0) tandis que le thread B exécute clear(), cela peut entraîner une erreur. Par conséquent, il est nécessaire de regrouper ces opérations dans un bloc synchronized, comme suit.
synchronized (list) {
list.clear();
list.add("888");
list.remove(0);Baisse de performances
Déclarer toutes les méthodes qui accèdent à l'objet partagé comme des méthodes synchronisées, ou définir des blocs synchronized identiques à l'intérieur des méthodes, peut entraîner une situation où un thread acquiert le verrou et les autres threads sont bloqués dans un état d'attente pour toutes les méthodes synchronisées. Cette répétition peut entraîner une baisse de performances.
Collection concurrente
Le package java.util.concurrent propose différents types de collections parallèles. Nous allons en aborder quelques-unes dans cet article.
- CopyOnWriteArrayList
- Il s'agit d'une sous-classe de List qui donne la priorité aux performances des opérations de recherche dans une liste d'objets.
- ConcurrentMap
- Une collection parallèle qui offre des opérations comme put-if-absent, replace et suppression conditionnelle, garantissant que l'ajout se fait uniquement si l'élément n'est pas déjà présent.
- ConcurrentHashMap
- Une sous-classe de ConcurrentMap qui offre une alternative parallèle à HashMap.
- ConcurrentLinkedQueue
- Une file FIFO qui offre des performances parallèles. Si aucun élément n'est disponible, la file retourne immédiatement et permet au thread d'exécuter d'autres tâches.
- LinkedBlockingQueue
- Similaire à ConcurrentLinkedQueue. Cependant, si la file est vide, l'opération de retrait d'un élément est bloquée jusqu'à ce qu'un nouvel élément soit ajouté. Inversement, si la file a une taille définie et est pleine, l'opération d'ajout d'un élément est bloquée jusqu'à ce qu'une place se libère dans la file.
- ConcurrentSkipListMap, ConcurrentSkipListSet
- Des versions améliorées des classes SortedMap et SortedSet qui offrent des performances parallèles.
Le simple remplacement des classes de collections synchronisées par des collections parallèles peut considérablement améliorer les performances sans risque particulier.
Comparons les collections synchronisées aux collections parallèles pour mieux les comprendre.
CopyOnWriteArrayList
Il existe deux méthodes pour créer une ArrayList synchronisée :
- Collections.synchronizedList()
- CopyOnWriteArrayList
Collections.synchronizedList() a été ajoutée dans la version JDK 1.2. Cette collection est synchronisée pour toutes les opérations de lecture et d'écriture, ce qui en fait une conception peu flexible. Pour remédier à cela, CopyOnWriteArrayList a été introduite.
Opérations de lecture
SynchronizedList verrouille l'instance elle-même lors des opérations de lecture et d'écriture. Cependant, CopyOnWriteArrayList crée un nouveau tableau temporaire en copiant les éléments du tableau d'origine lors de chaque opération d'écriture. Les modifications sont ensuite effectuées sur ce tableau temporaire, puis le tableau d'origine est mis à jour. Cela permet aux opérations de lecture d'être effectuées sans verrouillage, ce qui offre de meilleures performances que SynchronizedList.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
...
public E get(int index) {
return elementAt(getArray(), index);
}
... La méthode get() n'est pas synchronisée, ce qui signifie qu'elle n'est pas bloquée.
Opérations d'écriture
CopyOnWriteArrayList utilise un verrou explicite lors des opérations d'écriture. En fin de compte, les deux types de collections sont bloqués lors de cette opération. Cependant, CopyOnWriteArrayList effectue une opération de copie de tableau relativement coûteuse, ce qui peut entraîner des problèmes de performances si de nombreuses opérations d'écriture sont effectuées.
public class CopyOnWriteArrayList implements List, RandomAccess, Cloneable, java.io.Serializable {
final transient Object lock = new Object();
private transient volatile Object[] array;
public void add(int index, E element) {
synchronized (lock) {
...
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
...
}
} La méthode add() est synchronisée via un bloc synchronized et effectue une copie de tableau.
Itérateur
CopyOnWriteArrayList utilise les données de la collection au moment où l'itérateur est récupéré pour l'itération. Les ajouts et suppressions de données effectués sur la collection pendant l'itération sont reflétés dans la copie, indépendamment de l'itération. Cela garantit la compatibilité avec l'utilisation simultanée.
CopyOnWriteArraySet
Il existe deux méthodes pour créer un Set synchronisé :
- Collections.synchronizedSet()
- CopyOnWriteArraySet
Comme son nom l'indique, CopyOnWriteArraySet fonctionne de manière presque identique à CopyOnWriteArrayList, à l'exception des caractéristiques de la structure de données.
Opérations de lecture
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean contains(Object o) {
return al.contains(o);
} La méthode contains() utilise la méthode de CopyOnWriteArrayList, comme nous pouvons le constater dans la définition de CopyOnWriteArraySet qui utilise une instance interne de CopyOnWriteArrayList.
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
Object[] es = getArray();
return indexOfRange(o, es, 0, es.length);
}
private static int indexOfRange(Object o, Object[] es, int from, int to) {
if (o == null) {
for (int i = from; i < to; i++)
if (es[i] == null)
return i;
} else {
for (int i = from; i < to; i++)
if (o.equals(es[i]))
return i;
}
return -1;La méthode contains() de CopyOnWriteArrayList n'est pas bloquée.
Opérations d'écriture
public class CopyOnWriteArraySet extends AbstractSet implements java.io.Serializable {
private final CopyOnWriteArrayList al;
public boolean add(E e) {
return al.addIfAbsent(e);
} La méthode add() utilise également la méthode de CopyOnWriteArrayList.
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOfRange(e, snapshot, 0, snapshot.length) < 0
&& addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
if (current[i] != snapshot[i]
&& Objects.equals(e, current[i]))
return false;
if (indexOfRange(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}La méthode addIfAbsent() verrouille lors de l'écriture et effectue une copie de tableau. Par conséquent, il est également préférable d'éviter d'effectuer de nombreuses opérations d'écriture avec CopyOnWriteArraySet, comme avec CopyOnWriteArrayList.
ConcurrentHashMap
Il existe deux méthodes pour créer un HashMap synchronisé :
- Collections.synchronizedMap(new HashMap<>())
- ConcurrentHashMap
ConcurrentHashMap est une map basée sur un hachage, comme HashMap. Il offre une garantie de synchronisation plus efficace que synchronizedMap.
Avant Java 8, ConcurrentHashMap utilisait des segments qui héritaient de ReentrantLock pour séparer les zones et verrouiller chaque zone individuellement.
À partir de Java 8, ConcurrentHashMap verrouille chaque bac de table indépendamment. Si un nouveau nœud est inséré dans un bac vide, l'algorithme CAS est utilisé à la place d'un verrou. Les autres modifications verrouille le premier nœud du bac concerné (bloc synchronized) afin de minimiser les conflits entre les threads et garantir la synchronisation.
Examinons la méthode putVal() de ConcurrentHashMap, qui permet d'insérer de nouveaux nœuds, pour voir comment la synchronisation est assurée. Pour rappel, le code suivant est basé sur Java 11.
La méthode putVal() peut être divisée en deux cas principaux (quatre branches au total).
- Insertion d'un nœud dans un bac de hachage vide
- Un nœud existe déjà dans le bac de hachage
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node[] tab = table;;) {
Node f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// (1)
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// (2)
if (casTabAt(tab, i, null, new Node(hash, key, value)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
// (3)
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node e = f;; ++binCount) {
K ek;
// (4)
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node pred = e;
// (5)
if ((e = e.next) == null) {
pred.next = new Node(hash, key, value);
break;
}
}
}
// (6)
else if (f instanceof TreeBin) {
Node p;
binCount = 2;
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
...
}
}
... Insertion d'un nœud dans un bac de hachage vide
(1) Pour insérer un nouveau nœud, nous récupérons la valeur du bac correspondant (tabAt()) et vérifions si elle est vide.
static final Node tabAt(Node[] tab, int i) {
return (Node)U.getObjectAcquire(tab, ((long)i << ASHIFT) + ABASE); (2) Nous accédons à la variable volatile du nœud et comparons sa valeur à la valeur existante (null). Si elles sont égales, nous stockons le nouveau nœud. Sinon, nous retournons à la boucle for. Cette approche utilise l'algorithme CAS (Compare-and-Swap).
static final boolean casTabAt(Node[] tab, int i, Node c, Node v) {
return U.compareAndSetObject(tab, ((long)i << ASHIFT) + ABASE, c, v); L'algorithme CAS permet de résoudre les problèmes d'atomicité et de visibilité, assurant ainsi la synchronisation.
Un nœud existe déjà dans le bac de hachage
(3) Si un nœud existe déjà, nous utilisons un bloc synchronized pour contrôler l'accès par un seul thread à la fois. Comme un verrou est placé sur le bac de hachage non vide de type Node
(4) Le nouveau nœud est remplacé.
(5) En cas de collision de hachage, le nouveau nœud est ajouté à la chaîne séparée.
(6) En cas de collision de hachage, le nouveau nœud est ajouté à l'arbre.
Références
Questions d'entretien d'embauche prévues et réponses
Quels sont les problèmes liés aux classes Vector, HashTable et Collections.SynchronziedXXX ?
Les classes Vector, HashTable et SynchronziedXxx utilisent des méthodes ou des blocs synchronisés et partagent un seul objet de verrouillage. Par conséquent, si un thread acquiert le verrou sur la collection, tous les autres threads sont bloqués et ne peuvent pas utiliser toutes les méthodes. Cela peut entraîner une baisse de performances de l'application.
Quelle est la différence entre SynchronizedList et CopyOnArrayList ?
SynchronizedList verrouille l'instance elle-même lors des opérations de lecture et d'écriture. Cependant, CopyOnArrayList verrouille le bloc concerné lors de l'écriture, crée un nouveau tableau temporaire en copiant les éléments du tableau d'origine, effectue l'écriture sur ce tableau temporaire, puis met à jour le tableau d'origine. Cela permet aux opérations de lecture d'être effectuées sans verrouillage, ce qui offre de meilleures performances de lecture que SynchronizedList. Cependant, les opérations d'écriture sont plus lentes que SynchronizedList en raison de la copie de tableau coûteuse.
Par conséquent, CopyOnArrayList est plus efficace si les opérations de lecture sont plus nombreuses que les opérations de modification.
Quelle est la différence entre SynchronizedMap et ConcurrentHashMap ?
SynchronziedMap verrouille l'instance elle-même lors des opérations de lecture et d'écriture. Cependant, ConcurrentHashMap verrouille chaque bac de table indépendamment. Si un nouveau nœud est inséré dans un bac vide, l'algorithme CAS est utilisé au lieu d'un verrou. Les autres modifications verrouille le bac concerné pour minimiser les conflits entre les threads et garantir la synchronisation.
