Elegir la mejor lista de simultaneidad en Java [cerrado]

98

Mi grupo de subprocesos tiene un número fijo de subprocesos. Estos hilos necesitan escribir y leer de una lista compartida con frecuencia.

Entonces, ¿qué estructura de datos (es mejor una lista, debe estar libre de monitor) en el java.util.concurrentpaquete es mejor en este caso?

java concurrency 象 嘉 道
fuente
5
Eso depende de lo que quieras hacer con la colección. Vea la publicación de mi blog (aunque se trata de .Net, los conceptos son los mismos). Es poco probable que pueda escribir código seguro para subprocesos correcto con una extensión List.
SLaks
1
Ahora, estoy usando CopyOnWriteArrayList , pero la excepción ConcurrentModificationException todavía se lanza ocasionalmente.
象 嘉 道
2
Incluya más información sobre lo que está haciendo con la colección para que la gente pueda responder mejor; de lo contrario, es solo una suposición.
mattsh
2
Es ConcurrentModificationExceptionposible que no se deba a un problema de sincronización; también surge, por ejemplo, en un bucle for sobre una colección en el que intenta eliminar un elemento de la colección.
toto2
1
Sé que no es parte del paquete, pero ¿alguien lo ha intentado Vector?
WesternGun

Respuestas:

96

será mejor que sea List

La única List implementación en java.util.concurrentes CopyOnWriteArrayList . También existe la opción de una lista sincronizada como menciona Travis Webb.

Dicho esto, ¿estás seguro de que necesitas que sea un List? Hay muchas más opciones para Queues y Maps concurrentes (y puede hacer Sets a partir de Maps), y esas estructuras tienden a tener más sentido para muchos de los tipos de cosas que desea hacer con una estructura de datos compartida.

Para las colas, tiene una gran cantidad de opciones y cuál es la más adecuada depende de cómo necesite usarla:

ColinD
fuente
14
CopyOnWriteArrayListtiene la desventaja de ser muy costoso en la escritura (pero barato en las lecturas). Si está haciendo muchas escrituras, es mejor tener una Lista sincronizada o una cola.
Peter Lawrey
67

Cualquier colección de Java se puede hacer para que sea segura para subprocesos así:

List newList = Collections.synchronizedList(oldList);

O para crear una nueva lista segura para subprocesos:

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

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

Travis Webb
fuente
7
Por esta razón, no encontrará implementaciones de lista en java.util.concurrent - Uhm, hay ConcurrentHashMapun Collections.synchronizedMapmétodo aunque sí .
aioobe
7
Lea los Javadocs en ConcurrentHashMap. Los detalles de la implementación de la sincronización son diferentes. el uso de los synchronizedmétodos en Collectionsbásicamente simplemente envuelve la clase en un monitor Java. ConcurrentHashMaputiliza funciones de simultaneidad más inteligentes.
Travis Webb
1
Sí. Aún así, hace que tu última oración sea inválida.
aioobe
1
Si usa un monitor, el rendimiento del programa es realmente malo :-(
象 嘉 道
5
Solo para agregar, la iteración sobre newList no es segura para subprocesos. !!
bluelurker
9

Si el tamaño de la lista es fijo, entonces puede usar un AtomicReferenceArray . Esto le permitiría realizar actualizaciones indexadas en una ranura. Puede escribir una vista de lista si es necesario.

Ben Manes
fuente
6

Es posible que desee consultar ConcurrentDoublyLinkedList escrito por Doug Lea basado en "A Practical Lock-Free Double-Linked List" de Paul Martin. No implementa la interfaz java.util.List, pero ofrece la mayoría de los métodos que usaría en una lista.

Según el javadoc:

Una implementación concurrente de lista enlazada de un Deque (cola de dos extremos). Las operaciones de inserción, eliminación y acceso simultáneas se ejecutan de forma segura en varios subprocesos. Los iteradores son débilmente consistentes y devuelven elementos que reflejan el estado de la deque en algún momento en o desde la creación del iterador. Ellos no arrojan ConcurrentModificationException, y pueden realizar de forma concurrente con otras operaciones.

farsa
fuente
5

ConcurrentLinkedQueueutiliza una cola sin bloqueo (basada en la instrucción CAS más reciente ).

eSniff
fuente
7
... que no implementa la Listinterfaz.
aioobe
1
eSniff, ¿cómo haría para implementar List.set(int index, Object element)con ConcurrentLinkedQueue?
John Vint
4
La mayoría de los Listmétodos -específicos no serán implementables usando un Queue(agregar / establecer en un índice específico, por ejemplo) o pueden implementarse pero serán ineficientes (obtener de un índice). Así que no creo que realmente puedas envolverlo. Dicho esto, creo que la sugerencia de a Queueestá bien ya que el OP no ha explicado realmente por qué necesitan un List.
ColinD
1
@ ColinD esa es la respuesta que estaba buscando. Existen buenas razones por las que el CLQ no se puede incluir en una lista. Aunque estoy de acuerdo, no puedo descartar la interfaz de cola.
John Vint
1
❗️ Vale la pena señalar que: "Tenga en cuenta que, a diferencia de la mayoría de las colecciones, el método de tamaño NO es una operación de tiempo constante. Debido a la naturaleza asincrónica de estas colas, la determinación del número actual de elementos requiere un recorrido de los elementos".
Behrang Saeedzadeh
3

Si el conjunto es suficiente, se puede utilizar ConcurrentSkipListSet . (Su implementación se basa en ConcurrentSkipListMap que implementa una lista de omisión ).

El costo de tiempo promedio esperado es log (n) para las operaciones de contener, agregar y eliminar; el método de tamaño no es una operación de tiempo constante.

anre
fuente