Choix de la meilleure liste d'accès concurrentiel en Java [fermé]

98

Mon pool de threads a un nombre fixe de threads. Ces threads ont besoin d' écrire et de lire fréquemment à partir d'une liste partagée.

Alors, quelle structure de données (il vaut mieux être une liste, doit être sans moniteur) dans le java.util.concurrentpackage est la meilleure dans ce cas?

java concurrency 象 嘉 道
la source
5
Cela dépend de ce que vous voulez faire de la collection. Voir mon article de blog (bien qu'il s'agisse de .Net, les concepts sont les mêmes). Il est peu probable que vous puissiez écrire un code thread-safe correct avec un List.
SLaks
1
Maintenant, j'utilise CopyOnWriteArrayList , mais l' exception ConcurrentModificationException est toujours lancée occasionnellement.
象 嘉 道
2
Veuillez inclure plus d'informations sur ce que vous faites avec la collection afin que les gens puissent mieux répondre, sinon ce n'est qu'une supposition.
samedi
2
Le ConcurrentModificationExceptionpeut ne pas venir d'un problème de synchronisation; il survient également par exemple dans une boucle for sur une collection où vous essayez de supprimer un élément de la collection.
toto2
1
Je sais que cela ne fait pas partie du package, mais quelqu'un a-t-il essayé Vector?
WesternGun

Réponses:

96

ferait mieux d'être List

La seule List implémentation dans java.util.concurrentest CopyOnWriteArrayList . Il y a aussi l'option d'une liste synchronisée comme le mentionne Travis Webb.

Cela dit, êtes-vous sûr que vous en avez besoin pour être un List? Il y a beaucoup plus d'options pour les Queues et Maps simultanés (et vous pouvez faire Sets à partir de Maps), et ces structures ont tendance à être les plus logiques pour la plupart des types de choses que vous souhaitez faire avec une structure de données partagée.

Pour les files d'attente, vous disposez d'un grand nombre d'options et celle qui est la plus appropriée dépend de la manière dont vous devez l'utiliser:

ColinD
la source
14
CopyOnWriteArrayLista l'inconvénient d'être très coûteux en écriture (mais bon marché en lecture). Si vous faites beaucoup d'écritures, vous êtes mieux avec une liste synchronisée ou une file d'attente.
Peter Lawrey
67

Toute collection Java peut être rendue sûre pour les threads comme ceci:

List newList = Collections.synchronizedList(oldList);

Ou pour créer une toute nouvelle liste thread-safe:

List newList = Collections.synchronizedList(new ArrayList());

http://download.oracle.com/javase/6/docs/api/java/util/Collections.html#synchronizedList(java.util.List)

Travis Webb
la source
7
Pour cette raison, vous ne trouverez aucune implémentation de liste dans java.util.concurrent - Euh, il y a un ConcurrentHashMapmême s'il existe une Collections.synchronizedMapméthode.
aioobe
7
Lisez les Javadocs sur ConcurrentHashMap. Les détails de l'implémentation de la synchronisation sont différents. l'utilisation des synchronizedméthodes en Collectionsfait simplement envelopper la classe dans un moniteur Java. ConcurrentHashMaputilise des fonctionnalités de concurrence plus intelligentes.
Travis Webb
1
Oui. Pourtant, cela rend votre dernière phrase invalide.
aioobe
1
Si vous utilisez un moniteur, les performances du programme sont vraiment mauvaises :-(
象 嘉 道
5
Juste pour ajouter, l'itération sur newList n'est pas thread-safe. !!
bluelurker
9

Si la taille de la liste est fixe, vous pouvez utiliser un AtomicReferenceArray . Cela vous permettrait d'effectuer des mises à jour indexées sur un emplacement. Vous pouvez écrire une vue de liste si nécessaire.

Ben Manes
la source
6

Vous voudrez peut-être regarder ConcurrentDoublyLinkedList écrit par Doug Lea sur la base de "A Practical Lock-Free Double-Linked List" de Paul Martin. Il n'implémente pas l'interface java.util.List, mais propose la plupart des méthodes que vous utiliseriez dans une liste.

Selon le javadoc:

Une implémentation de liste chaînée simultanée d'un Deque (double queue). Les opérations d'insertion, de suppression et d'accès simultanées s'exécutent en toute sécurité sur plusieurs threads. Les itérateurs sont faiblement cohérents , renvoyant des éléments reflétant l'état du deque à un moment donné ou depuis la création de l'itérateur. Ils ne lancent pas d' exception ConcurrentModificationException et peuvent se poursuivre en même temps que d'autres opérations.

shams
la source
5

ConcurrentLinkedQueueutilise une file d'attente sans verrouillage (basée sur la nouvelle instruction CAS ).

eSniff
la source
7
... qui n'implémente pas l' Listinterface.
aioobe
1
eSniff, comment procéderiez-vous pour l'implémentation List.set(int index, Object element)avec ConcurrentLinkedQueue?
John Vint
4
La plupart des Listméthodes spécifiques ne seront pas implémentables en utilisant un Queue(ajouter / définir à un index spécifique, par exemple) ou peuvent en quelque sorte être implémentées mais seront inefficaces (extraites d'un index). Donc je ne pense pas que vous puissiez vraiment l'envelopper. Cela dit, je pense que la suggestion d'un Queueest bien puisque le PO n'a pas vraiment expliqué pourquoi ils ont besoin d'un List.
ColinD
1
@ColinD c'est la réponse que je recherchais. Il y a de bonnes raisons pour lesquelles le CLQ ne peut pas être inclus dans une liste. Bien que je sois d'accord, je ne peux pas exclure l'interface de file d'attente.
John Vint
1
❗️ À noter que: "Attention, contrairement à la plupart des collections, la méthode de taille n'est PAS une opération à temps constant. En raison de la nature asynchrone de ces files d'attente, la détermination du nombre actuel d'éléments nécessite une traversée des éléments."
Behrang Saeedzadeh
3

Si set est suffisant, ConcurrentSkipListSet peut être utilisé. (Son implémentation est basée sur ConcurrentSkipListMap qui implémente une liste à sauter .)

Le coût en temps moyen prévu est log (n) pour les opérations contenant, ajouter et supprimer; la méthode de taille n'est pas une opération à temps constant.

anre
la source