threadlocalrandom - thread pool java

Diferentes tipos de conjuntos seguros para subprocesos en Java

Question

Parece que hay muchas implementaciones diferentes y formas de generar conjuntos seguros para subprocesos en Java. Algunos ejemplos incluyen

1) CopyOnWriteArraySet

2) Collections.synchronizedSet (Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap (nuevo ConcurrentHashMap ())

5) Otros conjuntos generados de forma similar a (4)

Estos ejemplos provienen del patrón de concurrencia: implementaciones de conjuntos concurrentes en Java 6

¿Podría alguien explicar las diferencias, ventajas y desventajas de estos ejemplos y otros? Tengo problemas para entender y mantener todo en orden desde los Java Std Docs.

Answer 1

Es posible combinar el rendimiento de contains() de HashSet con las propiedades relacionadas con la concurrencia de CopyOnWriteArraySet utilizando AtomicReference<Set> y reemplazando todo el conjunto en cada modificación.

El boceto de implementación:

public abstract class CopyOnWriteSet<E> implements Set<E> {
private final AtomicReference<Set<E>> ref;
protected CopyOnWriteSet( Collection<? extends E> c ) {
ref = new AtomicReference<Set<E>>( new HashSet<E>( c ) );
}
@Override
public boolean contains( Object o ) {
return ref.get().contains( o );
}
@Override
public boolean add( E e ) {
while ( true ) {
Set<E> current = ref.get();
if ( current.contains( e ) ) {
return false;
}
Set<E> modified = new HashSet<E>( current );
modified.add( e );
if ( ref.compareAndSet( current, modified ) ) {
return true;
}
}
}
@Override
public boolean remove( Object o ) {
while ( true ) {
Set<E> current = ref.get();
if ( !current.contains( o ) ) {
return false;
}
Set<E> modified = new HashSet<E>( current );
modified.remove( o );
if ( ref.compareAndSet( current, modified ) ) {
return true;
}
}
}
}

Answer 2

Si los Javadocs no ayudan, probablemente deba encontrar un libro o artículo para leer acerca de las estructuras de datos. De un vistazo:

• CopyOnWriteArraySet realiza una nueva copia de la matriz subyacente cada vez que mute la colección, por lo que las escrituras son lentas y los iteradores son rápidos y consistentes.
• Collections.synchronizedSet () usa llamadas a métodos sincronizados de la vieja escuela para hacer que un conjunto sea seguro. Esta sería una versión de bajo rendimiento.
• ConcurrentSkipListSet ofrece escrituras de rendimiento con operaciones por lotes inconsistentes (addAll, removeAll, etc.) e iteradores.
• Collections.newSetFromMap (nuevo ConcurrentHashMap ()) tiene la semántica de ConcurrentHashMap, que creo que no está necesariamente optimizado para lecturas o escrituras, pero al igual que ConcurrentSkipListSet, tiene operaciones por lotes inconsistentes.

Answer 3

1) CopyOnWriteArraySet es una implementación bastante simple: básicamente tiene una lista de elementos en una matriz, y al cambiar la lista, copia la matriz. Las iteraciones y otros accesos que se están ejecutando en este momento continúan con la matriz anterior, evitando la necesidad de sincronización entre lectores y escritores (aunque la escritura en sí misma debe estar sincronizada). Las operaciones normalmente rápidas (especialmente contains() ) son bastante lentas aquí, ya que las matrices se buscarán en tiempo lineal.

Úselo solo para conjuntos realmente pequeños que se leerán (iterarán) a menudo y se cambiarán rara vez. (Los conjuntos de escuchas de Swings serían un ejemplo, pero estos no son realmente conjuntos, y de todos modos solo deberían usarse desde el EDT).

2) Collections.synchronizedSet simplemente ajustará un bloque sincronizado alrededor de cada método del conjunto original. No debe acceder al conjunto original directamente. Esto significa que no se pueden ejecutar simultáneamente dos métodos del conjunto (uno se bloqueará hasta que el otro finalice): esto es seguro para subprocesos, pero no tendrá concurrencia si varios subprocesos realmente usan el conjunto. Si usa el iterador, generalmente aún necesita sincronizarlo externamente para evitar ConcurrentModificationExceptions al modificar el conjunto entre llamadas de iterador. El rendimiento será similar al rendimiento del conjunto original (pero con cierta sobrecarga de sincronización y bloqueo si se usa al mismo tiempo).

Úselo si solo tiene concurrencia baja y quiere asegurarse de que todos los cambios sean visibles inmediatamente para los otros hilos.

3) ConcurrentSkipListSet es la implementación SortedSet concurrente, con la mayoría de las operaciones básicas en O (log n). Permite agregar / eliminar concurrentemente y leer / iterar, donde la iteración puede o no indicar cambios desde que se creó el iterador. Las operaciones masivas son simplemente llamadas múltiples, y no atómicamente, otros subprocesos pueden observar solo algunas de ellas.

Obviamente, puedes usar esto solo si tienes un orden total en tus elementos. Esto parece un candidato ideal para situaciones de alta concurrencia, para conjuntos no demasiado grandes (debido a la O (log n)).

4) Para ConcurrentHashMap (y el conjunto derivado de él): Aquí la mayoría de las opciones básicas son (en promedio, si tiene un hashCode() bueno y rápido hashCode() ) en O (1) (pero puede degenerar en O (n)), como para HashMap / HashSet. Existe una concurrencia limitada para la escritura (la tabla está particionada y el acceso de escritura se sincronizará en la partición necesaria), mientras que el acceso de lectura es totalmente simultáneo consigo mismo y en los hilos de escritura (aunque es posible que todavía no vea los resultados de los cambios escrito). El iterador puede ver o no los cambios desde que se creó, y las operaciones masivas no son atómicas. El cambio de tamaño es lento (como para HashMap / HashSet), por lo tanto trate de evitar esto estimando el tamaño necesario en la creación (y usando aproximadamente 1/3 más de eso, ya que cambia el tamaño cuando 3/4 está lleno).

Úselo cuando tenga conjuntos grandes, una función de hash buena (y rápida) y pueda estimar el tamaño del conjunto y la concurrencia necesaria antes de crear el mapa.

5) ¿Hay otras implementaciones de mapas simultáneos que se podrían usar aquí?