Escolhendo a melhor lista de simultaneidade em Java [fechado]

98

Meu pool de threads tem um número fixo de threads. Esses tópicos precisam escrever e ler de uma lista compartilhada com frequência.

Portanto, qual estrutura de dados (melhor ser uma lista, deve ser sem monitor) no java.util.concurrentpacote é a melhor neste caso?

java concurrency 象 嘉 道
fonte
5
Depende do que você deseja fazer com a coleção. Veja minha postagem no blog (embora seja sobre .Net, os conceitos são os mesmos). É improvável que você consiga escrever o código thread-safe correto com um List.
SLaks de
1
Agora, estou usando CopyOnWriteArrayList , mas a exceção ConcurrentModificationException ainda é lançada ocasionalmente.
象 嘉 道
2
Inclua mais informações sobre o que você está fazendo com a coleção para que as pessoas possam responder melhor, caso contrário, é apenas um palpite.
mattsh de
2
O ConcurrentModificationExceptionpode não vir de um problema de sincronização; também surge, por exemplo, em um loop for sobre uma coleção, onde você tenta remover um elemento da coleção.
toto2 de
1
Eu sei que não faz parte do pacote, mas alguém já experimentou Vector?
WesternGun

Respostas:

96

é melhor ser List

A única List implementação em java.util.concurrenté CopyOnWriteArrayList . Também existe a opção de uma lista sincronizada, como Travis Webb menciona.

Dito isso, tem certeza de que precisa que seja um List? Existem muito mais opções para Queues e s simultâneos Map(e você pode fazer Sets a partir de Maps), e essas estruturas tendem a fazer mais sentido para muitos dos tipos de coisas que você deseja fazer com uma estrutura de dados compartilhada.

Para filas, você tem um grande número de opções e a mais adequada depende de como você precisa usá-la:

ColinD
fonte
14
CopyOnWriteArrayListtem a desvantagem de ser muito caro na gravação (mas barato para leituras). Se você estiver fazendo muitas gravações, será melhor usar uma lista sincronizada ou uma fila.
Peter Lawrey
67

Qualquer coleção Java pode ser feita para ser thread-safe, como:

List newList = Collections.synchronizedList(oldList);

Ou para criar uma nova lista de 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
fonte
7
Por esse motivo, você não encontrará implementações de lista em java.util.concurrent - Uhm, existe um ConcurrentHashMapembora haja um Collections.synchronizedMapmétodo.
aioobe
7
Leia os Javadocs em ConcurrentHashMap. Os detalhes da implementação da sincronização são diferentes. usar os synchronizedmétodos Collectionsbasicamente envolve a classe em um monitor Java. ConcurrentHashMapusa recursos de simultaneidade mais inteligentes.
Travis Webb
1
Sim. Ainda assim, torna sua última frase meio inválida.
aioobe
1
Se usar um monitor, o desempenho do programa é muito ruim :-(
象 嘉 道
5
Só para adicionar, iteração em newList não é thread-safe. !!
bluelurker
9

Se o tamanho da lista for fixo, você poderá usar um AtomicReferenceArray . Isso permitiria a você realizar atualizações indexadas em um slot. Você pode escrever uma exibição de lista, se necessário.

Ben Manes
fonte
6

Você pode querer dar uma olhada em ConcurrentDoublyLinkedList escrito por Doug Lea com base na "A Practical Lock-Free Doubly-Linked List" de Paul Martin. Ele não implementa a interface java.util.List, mas oferece a maioria dos métodos que você usaria em uma Lista.

De acordo com o javadoc:

Uma implementação de lista vinculada simultânea de um Deque (fila dupla). As operações simultâneas de inserção, remoção e acesso são executadas com segurança em vários threads. Os iteradores são fracamente consistentes , retornando elementos que refletem o estado do deque em algum ponto durante ou desde a criação do iterador. Eles não lançam ConcurrentModificationException e podem prosseguir simultaneamente com outras operações.

shams
fonte
5

ConcurrentLinkedQueueusa uma fila livre de bloqueio (com base na instrução CAS mais recente ).

eSniff
fonte
7
... que não implementa a Listinterface.
aioobe de
1
eSniff, como você faria para implementar List.set(int index, Object element)com ConcurrentLinkedQueue?
John Vint de
4
A maioria dos Listmétodos específicos não serão implementados usando um Queue(adicionar / definir em um índice específico, por exemplo) ou podem ser implementados, mas serão ineficientes (obter de um índice). Então eu não acho que você poderia realmente embrulhar isso. Dito isso, acho que a sugestão de a Queueestá bem, pois o OP não explicou realmente por que eles precisam de a List.
ColinD de
1
@ColinD era essa a resposta que eu procurava. Existem boas razões pelas quais o CLQ não pode ser agrupado em uma lista. Embora eu concorde, não posso descartar a interface da fila.
John Vint de
1
❗️ Vale a pena notar que: "Cuidado que, ao contrário da maioria das coleções, o método de tamanho NÃO é uma operação de tempo constante. Devido à natureza assíncrona dessas filas, determinar o número atual de elementos requer um percurso dos elementos."
Behrang Saeedzadeh
3

Se definido for suficiente, ConcurrentSkipListSet pode ser usado. (Sua implementação é baseada em ConcurrentSkipListMap, que implementa uma lista de pular .)

O custo de tempo médio esperado é log (n) para as operações de contém, adiciona e remove; o método de tamanho não é uma operação de tempo constante.

anre
fonte