Auswahl der besten Parallelitätsliste in Java [geschlossen]

98

Mein Thread-Pool hat eine feste Anzahl von Threads. Diese Threads müssen häufig aus einer freigegebenen Liste schreiben und lesen .

Welche Datenstruktur (besser eine Liste, muss ohne Monitor sein) im java.util.concurrentPaket ist in diesem Fall am besten?

java concurrency 象 嘉 道
quelle
5
Das hängt davon ab, was Sie mit der Sammlung machen möchten. Siehe meinen Blog-Beitrag (obwohl es um .Net geht, sind die Konzepte dieselben). Es ist unwahrscheinlich, dass Sie mit a korrekten thread-sicheren Code schreiben können List.
SLaks
1
Jetzt verwende ich CopyOnWriteArrayList , aber gelegentlich wird immer noch eine ConcurrentModificationException- Ausnahme ausgelöst.
嘉 道
2
Bitte geben Sie weitere Informationen darüber an, was Sie mit der Sammlung tun, damit die Leute besser antworten können, andernfalls ist es nur eine Vermutung.
Mattsh
2
Dies ist ConcurrentModificationExceptionmöglicherweise nicht auf ein Synchronisationsproblem zurückzuführen. Dies tritt beispielsweise auch in einer for-Schleife über einer Sammlung auf, in der Sie versuchen, ein Element aus der Sammlung zu entfernen.
Toto2
1
Ich weiß, dass es nicht Teil des Pakets ist, aber hat es jemand versucht Vector?
WesternGun

Antworten:

94

sollte besser sein List

Die einzige List Implementierung in java.util.concurrentist CopyOnWriteArrayList . Es gibt auch die Option einer synchronisierten Liste, wie Travis Webb erwähnt.

Bist du sicher, dass du es brauchst, um ein zu sein List? Es gibt viel mehr Optionen für gleichzeitige Queues und Maps (und Sie können Sets aus Maps erstellen), und diese Strukturen sind für viele der Arten von Dingen, die Sie mit einer gemeinsam genutzten Datenstruktur ausführen möchten, am sinnvollsten.

Für Warteschlangen stehen eine Vielzahl von Optionen zur Verfügung. Welche Option am besten geeignet ist, hängt davon ab, wie Sie sie verwenden müssen:

ColinD
quelle
13
CopyOnWriteArrayListhat den Nachteil, dass es beim Schreiben sehr teuer ist (aber für das Lesen billig). Wenn Sie viele Schreibvorgänge ausführen, sind Sie mit einer synchronisierten Liste oder einer Warteschlange besser dran.
Peter Lawrey
66

Jede Java-Sammlung kann wie folgt threadsicher gemacht werden:

List newList = Collections.synchronizedList(oldList);

Oder um eine brandneue thread-sichere Liste zu erstellen:

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

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

Travis Webb
quelle
7
Aus diesem Grund finden Sie in java.util.concurrent keine Listenimplementierungen - Ähm, es gibt eine ConcurrentHashMapobwohl es eine Collections.synchronizedMapMethode gibt.
Aioobe
7
Lesen Sie die Javadocs weiter ConcurrentHashMap. Die Details der Synchronisationsimplementierung sind unterschiedlich. Wenn Sie die synchronizedMethoden in verwenden, wird Collectionsdie Klasse im Grunde nur in einen Java-Monitor eingeschlossen. ConcurrentHashMapVerwendet cleverere Parallelitätsfunktionen.
Travis Webb
1
Ja. Trotzdem macht es Ihren letzten Satz irgendwie ungültig.
Aioobe
1
Wenn Sie einen Monitor verwenden, ist die Leistung des Programms wirklich schlecht :-(
象 嘉 道
5
Nur um hinzuzufügen, ist die Iteration über newList nicht threadsicher. !!
Bluelurker
9

Wenn die Größe der Liste festgelegt ist, können Sie ein AtomicReferenceArray verwenden . Auf diese Weise können Sie indizierte Aktualisierungen an einem Steckplatz durchführen. Bei Bedarf können Sie eine Listenansicht schreiben.

Ben Manes
quelle
6

Vielleicht möchten Sie sich die ConcurrentDoublyLinkedList ansehen, die von Doug Lea basierend auf Paul Martins "A Practical Lock-Free Doubly-Linked List" geschrieben wurde. Die Schnittstelle java.util.List wird nicht implementiert, bietet jedoch die meisten Methoden, die Sie in einer Liste verwenden würden.

Laut dem Javadoc:

Eine gleichzeitige Implementierung einer Deque (Double-Ended Queue) in einer verknüpften Liste. Das gleichzeitige Einfügen, Entfernen und Zugreifen wird sicher über mehrere Threads ausgeführt. Iteratoren sind schwach konsistent und geben Elemente zurück, die den Zustand der Deque zu einem bestimmten Zeitpunkt oder seit der Erstellung des Iterators widerspiegeln. Sie lösen keine ConcurrentModificationException aus und können gleichzeitig mit anderen Vorgängen fortfahren.

Täuschungen
quelle
5

ConcurrentLinkedQueueverwendet eine sperrfreie Warteschlange (basierend auf der neueren CAS-Anweisung ).

eSniff
quelle
7
... was die ListSchnittstelle nicht implementiert .
Aioobe
1
eSniff, wie würden Sie List.set(int index, Object element)mit ConcurrentLinkedQueue implementieren ?
John Vint
4
Die meisten der Listspezifischen Methoden können entweder nicht mit a implementiert werden Queue(z. B. Hinzufügen / Festlegen an einem bestimmten Index) oder können implementiert werden, sind jedoch ineffizient (aus einem Index abrufen). Ich glaube also nicht, dass Sie es wirklich einpacken könnten. Trotzdem denke ich, dass der Vorschlag von a Queuein Ordnung ist, da das OP nicht wirklich erklärt hat, warum sie a brauchen List.
ColinD
1
@ColinD das ist die Antwort, die ich gesucht habe. Es gibt gute Gründe, warum der CLQ nicht in eine Liste eingeschlossen werden kann. Obwohl ich damit einverstanden bin, kann die Warteschlangenschnittstelle nicht ausgeschlossen werden.
John Vint
1
❗️ Beachten Sie Folgendes: "
Behrang Saeedzadeh
3

Wenn set ausreichend ist, kann ConcurrentSkipListSet verwendet werden. (Die Implementierung basiert auf ConcurrentSkipListMap, die eine Überspringliste implementiert .)

Die erwarteten durchschnittlichen Zeitkosten sind log (n) für die Vorgänge zum Einschließen, Hinzufügen und Entfernen. Die Größenmethode ist keine Operation mit konstanter Zeit.

anre
quelle