Diversi tipi di set thread-safe in Java

Question

Sembra esserci un sacco di diverse implementazioni e modi per generare set thread-safe in Java. Alcuni esempi includono

1) CopyOnWriteArraySet

2) Collections.synchronizedSet(Set set)

3) ConcurrentSkipListSet

4) Collections.newSetFromMap(new ConcurrentHashMap())

5) Altri set generati in un modo simile a (4)

Questi esempi provengono da Concurrency Pattern: Concurrent Set implementations in Java 6

Qualcuno potrebbe semplicemente spiegare le differenze, i vantaggi e gli svantaggi di questi esempi e di altri? Ho difficoltà a capire e tenere tutto direttamente da Java Std Docs.

Answer 1

1) Il CopyOnWriteArraySet è un'implementazione abbastanza semplice, in pratica ha un elenco di elementi in un array e quando si modifica l'elenco, copia l'array. Le iterazioni e altri accessi in corso in questo momento continuano con il vecchio array, evitando la necessità di sincronizzazione tra lettori e scrittori (sebbene la scrittura stessa debba essere sincronizzata). Le operazioni di impostazione normalmente veloci (in particolare) sono piuttosto lente qui, poiché gli array verranno ricercati in tempo lineare.

Utilizzare questo solo per set molto piccoli che verranno letti (ripetuti) spesso e modificati di rado. (Gli oscillatori listener-set sarebbero un esempio, ma questi non sono realmente insiemi e dovrebbero essere comunque utilizzati solo dall'EDT.)

2) Collections.synchronizedSet semplicemente avvolgerà un blocco sincronizzato attorno a ciascun metodo del set originale. Non si dovrebbe accedere direttamente al set originale. Ciò significa che non è possibile eseguire simultaneamente due metodi dell'insieme (uno bloccherà fino a quando l'altro non termina) - questo è sicuro per i thread, ma non si avrà concorrenza se più thread stanno effettivamente utilizzando il set. Se si utilizza l'iteratore, di solito è necessario sincronizzare esternamente per evitare ConcurrentModificationExceptions quando si modifica il set tra le chiamate iteratore. Le prestazioni saranno come le prestazioni del set originale (ma con un overhead di sincronizzazione e il blocco se utilizzato contemporaneamente).

Utilizzare questo se si ha solo una concorrenza bassa e si vuole essere sicuri che tutte le modifiche siano immediatamente visibili agli altri thread.

3) ConcurrentSkipListSet è l'implementazione simultanea di SortedSet, con la maggior parte delle operazioni di base in O (log n). Consente l'aggiunta/rimozione simultanea e la lettura/iterazione, in cui l'iterazione può o non può indicare le modifiche da quando è stato creato l'iteratore. Le operazioni di massa sono semplicemente più chiamate singole e non atomicamente - altri thread possono osservare solo alcuni di essi.

Ovviamente è possibile utilizzare questo solo se si dispone di un ordine totale sui vostri elementi. Questo sembra un candidato ideale per situazioni ad alta concorrenza, per insiemi non troppo grandi (a causa della O (log n)).

4) Per la ConcurrentHashMap (e il set da esso derivato): Qui opzioni di base sono (in media, se si dispone di una buona e veloce hashCode()) a O (1) (ma potrebbe degenerare a O (n)), come per HashMap/HashSet. Esiste una concorrenza limitata per la scrittura (la tabella è partizionata e l'accesso in scrittura sarà sincronizzato sulla partizione necessaria), mentre l'accesso in lettura è completamente concorrente a se stesso e ai thread di scrittura (ma potrebbe non vedere ancora i risultati delle modifiche attualmente in corso scritto). L'iteratore può o non può vedere le modifiche da quando è stato creato e le operazioni di massa non sono atomiche. Il ridimensionamento è lento (come per HashMap/HashSet), quindi cerca di evitare questo stimando la dimensione necessaria alla creazione (e usando circa 1/3 in più di ciò, quando si ridimensiona a 3/4).

Da utilizzare quando si dispone di set di grandi dimensioni, una buona (e veloce) funzione di hash e può stimare la dimensione impostata e la concorrenza necessaria prima di creare la mappa.

5) Esistono altre implementazioni di mappe simultanee che è possibile utilizzare qui?

Answer 2

Se i Javadoc non aiutano, probabilmente dovresti semplicemente trovare un libro o un articolo da leggere sulle strutture dei dati. A colpo d'occhio:

• CopyOnWriteArraySet fa una nuova copia della matrice sottostante ogni volta che si Mutate the raccolta, così scrive sono lenti e Iteratori sono veloci e coerenti.
• Collections.synchronizedSet() utilizza chiamate di metodo sincronizzate vecchia scuola per creare un set di thread protetto. Questa sarebbe una versione a basso rendimento.
• ConcurrentSkipListSet offre scritture performanti con operazioni batch incoerenti (addAll, removeAll, ecc.) E Iterators.
• Collections.newSetFromMap (new ConcurrentHashMap()) ha la semantica di ConcurrentHashMap, che a mio avviso non è necessariamente ottimizzata per letture o scritture, ma come ConcurrentSkipListSet, ha operazioni batch incoerenti.

Answer 3

È possibile combinare l' prestazioni di HashSet con le proprietà concorrenza connessi di CopyOnWriteArraySet utilizzando il AtomicReference<Set> e sostituendo l'intera serie su ogni modifica.

Lo schizzo implementazione:

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; 
      } 
     } 
    } 

}