Wybór najlepszej listy współbieżności w Javie [zamknięte]

98

Moja pula wątków ma stałą liczbę wątków. Wątki te muszą często pisać i czytać z udostępnionej listy.

Jaka więc struktura danych (lepiej lista, musi być wolna od monitora) w java.util.concurrentpakiecie jest najlepsza w tym przypadku?

java concurrency

— 象嘉道
źródło

5

To zależy, co chcesz zrobić z kolekcją. Zobacz mój wpis na blogu (chociaż dotyczy .Net, koncepcje są takie same). Jest mało prawdopodobne, abyś był w stanie napisać poprawny kod bezpieczny dla wątków z rozszerzeniem List.

— SLaks

1

Teraz używam CopyOnWriteArrayList , ale wyjątek ConcurrentModificationException jest nadal czasami generowany .

— 象嘉道

2

Podaj więcej informacji o tym, co robisz z kolekcją, aby użytkownicy mogli lepiej odpowiedzieć, w przeciwnym razie to tylko przypuszczenie.

— mattsh

2

ConcurrentModificationExceptionMoże nie pochodzić z problemem synchronizacji; pojawia się również na przykład w pętli for nad kolekcją, w której próbujesz usunąć element z kolekcji.

— toto2

1

Wiem, że to nie jest część pakietu, ale czy ktoś próbował Vector?

— WesternGun

98

lepiej by było List

Tylko List realizacja w java.util.concurrentto CopyOnWriteArrayList . Istnieje również opcja zsynchronizowanej listy, o której wspomina Travis Webb.

To powiedziawszy, czy na pewno potrzebujesz, aby to był List? Istnieje o wiele więcej opcji dla współbieżnych Queues i Maps (i można utworzyć Sets z Maps), a te struktury mają zwykle największy sens w przypadku wielu rodzajów rzeczy, które chcesz zrobić ze wspólną strukturą danych.

W przypadku kolejek masz ogromną liczbę opcji i to, która z nich jest najbardziej odpowiednia, zależy od tego, jak chcesz z niej skorzystać:

— ColinD
źródło

14

CopyOnWriteArrayListma tę wadę, że jest bardzo kosztowny przy zapisie (ale tani jak na odczyt). Jeśli robisz dużo zapisów, lepiej będzie mieć zsynchronizowaną listę lub kolejkę.

— Peter Lawrey,

69

Dowolną kolekcję Java można ustawić jako bezpieczną dla wątków, na przykład:

List newList = Collections.synchronizedList(oldList);

Lub utworzyć zupełnie nową listę bezpiecznych wątków:

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

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

— Travis Webb
źródło

7

Z tego powodu nie znajdziesz implementacji list w java.util.concurrent - Uhm, jest ConcurrentHashMapchociaż Collections.synchronizedMapmetoda.

— aioobe

7

Przeczytaj Javadocs dalej ConcurrentHashMap. Szczegóły implementacji synchronizacji są różne. używanie tych synchronizedmetod w Collectionszasadzie po prostu opakowuje klasę w monitorze Java. ConcurrentHashMapwykorzystuje bardziej inteligentne funkcje współbieżności.

— Travis Webb

1

Tak. Mimo to sprawia, że twoje ostatnie zdanie jest trochę nieważne.

— aioobe

1

Jeśli używasz monitora, wydajność programu jest naprawdę zła :-(

— 象嘉道

5

Dodam, że iteracja po newList nie jest bezpieczna wątkowo. !!

— bluelurker

9

Jeśli rozmiar listy został ustalony, możesz użyć AtomicReferenceArray . Umożliwiłoby to wykonanie indeksowanych aktualizacji slotu. W razie potrzeby możesz napisać widok listy.

— Ben Manes
źródło

6

Możesz spojrzeć na ConcurrentDoublyLinkedList napisaną przez Douga Leę na podstawie „Praktycznej listy podwójnie połączonej bez blokad” Paula Martina. Nie implementuje interfejsu java.util.List, ale oferuje większość metod, których można użyć na liście.

Według javadoc:

Współbieżna implementacja listy połączonej Deque (kolejka dwustronna). Jednoczesne operacje wstawiania, usuwania i uzyskiwania dostępu są bezpiecznie wykonywane w wielu wątkach. Iteratory są słabo spójne , zwracając elementy odzwierciedlające stan deque w pewnym momencie lub od chwili utworzenia iteratora. Oni nie rzucać ConcurrentModificationException i może postępować równolegle z innymi operacjami.

— pozory
źródło

5

ConcurrentLinkedQueueużywa kolejki bez blokady (opartej na nowszej instrukcji CAS ).

— eSniff
źródło

7

... który nie implementuje Listinterfejsu.

— aioobe

1

eSniff, jak zabrałbyś się za wdrożenie List.set(int index, Object element)z ConcurrentLinkedQueue?

— John Vint,

4

Większość Listmetod specyficznych albo nie będzie możliwa do zaimplementowania przy użyciu Queue(na przykład dodawania / ustawiania w określonym indeksie) lub może zostać zaimplementowana, ale będzie nieefektywna (pobierz z indeksu). Więc nie sądzę, żebyś naprawdę mógł to opakować. To powiedziawszy, myślę, że sugestia a Queuejest w porządku, ponieważ OP tak naprawdę nie wyjaśnił, dlaczego potrzebują List.

— ColinD,

1

@ColinD to odpowiedź, do której dążyłem. Istnieją dobre powody, dla których CLQ nie może zostać umieszczony na liście. Chociaż zgadzam się, nie mogę wykluczyć interfejsu kolejki.

— John Vint,

1

❗️ Warto zauważyć, że: „Uważaj, w przeciwieństwie do większości kolekcji metoda size NIE jest operacją działającą w czasie stałym. Ze względu na asynchroniczny charakter tych kolejek, określenie bieżącej liczby elementów wymaga przejścia przez elementy”.

— Behrang Saeedzadeh

3

Jeśli set jest wystarczający, można użyć ConcurrentSkipListSet . (Jego implementacja jest oparta na ConcurrentSkipListMap, która implementuje listę pominięć ).

Oczekiwany średni koszt czasu to log (n) dla operacji zawierania, dodawania i usuwania; metoda rozmiaru nie jest operacją działającą w czasie stałym.

— anre
źródło