Les différents types de thread-safe Jeux en Java

Question

Il semble y avoir beaucoup de différentes mises en œuvre et les moyens de générer de thread-safe Jeux en Java. Voici quelques exemples

1) CopyOnWriteArraySet

2) les Collections.synchronizedSet(Set)

3) ConcurrentSkipListSet

4) les Collections.newSetFromMap(nouveau ConcurrentHashMap())

5) d'Autres Ensembles générés dans une voie semblable (4)

Ces exemples sont fournis par le Modèle d'accès concurrentiel: L'Ensemble des implémentations en Java 6

Quelqu'un pourrait-il vous suffit d'expliquer les différences, les avantages et les inconvénient de ces exemples et d'autres? Je vais avoir de la difficulté à comprendre et en continuant tout droit de tout, de la Java Std Docs.

Answer 1

1) L' CopyOnWriteArraySet est un très simple de mise en œuvre - il y a une liste d'éléments dans un tableau, et lors de la modification de la liste, il copie le tableau. Itérations et les autres accès qui sont en cours d'exécution à ce moment de continuer avec l'ancien tableau, en évitant la nécessité de la synchronisation. Normalement rapide des opérations (en particulier contains()) sont assez lent ici, comme les tableaux seront recherchés dans le temps linéaire.

À utiliser seulement pour de très petites séries qui sera lu (itérée) souvent et changé rarement. (Sautes d'écouteur-ensembles en serait un bon exemple, mais ce ne sont pas vraiment des ensembles, et doivent être uniquement utilisées à partir de l'EDT de toute façon.)

2) Collections.synchronizedSet sera tout simplement envelopper d'une synchronisation de bloc autour de chaque méthode de l'original. Vous ne devez pas accéder au jeu original directement. Cela signifie qu'aucune des deux méthodes de la série peuvent être exécutées simultanément (on va bloquer jusqu'à ce que les autres finitions) - c'est thread-safe, mais vous n'aurez pas de simultanéité si plusieurs threads sont vraiment à l'aide de l'ensemble. Si vous utilisez l'itérateur, vous avez généralement encore besoin de synchroniser l'extérieur pour éviter ConcurrentModificationExceptions lors de la modification de l'ensemble entre itérateur appels. La performance la performance de l'ensemble original (mais avec de la surcharge de la synchronisation, et le blocage si elle est utilisée simultanément).

Utilisez cette option si vous avez seulement une faible concurrence, et que vous voulez être sûr que toutes les modifications sont immédiatement visibles par les autres threads.

3) ConcurrentSkipListSet est la concurrente SortedSet mise en œuvre, avec la plupart des opérations de base en O(log n). Il permet simultanées, l'ajout, la suppression et la lecture/l'itération, où l'itération peut ou ne peut pas dire à propos de changements depuis l'itérateur a été créé. La majeure partie des opérations sont simplement plusieurs appels seul, et pas atomiquement autres threads peut observer que certains d'entre eux.

Évidemment, vous pouvez utiliser seulement si vous avez peu d'ordre total sur vos éléments. Cela ressemble à un candidat idéal pour la haute-simultanéité des situations, pour ne pas-trop-de grands ensembles (en raison de l'O(log n)).

4) Pour l' ConcurrentHashMap (et de la série dérivée): Ici, la plupart des options de base sont (en moyenne, si vous avez un bon et rapide, hashCode()) en O(1) (mais qui peuvent dégénérer à O(n)), comme pour HashMap/HashSet. Il existe un nombre limité de simultanéité pour l'écriture (la table est partitionnée, et l'accès en écriture sera synchronisé sur la partition), tandis que l'accès en lecture est entièrement parallèlement à lui-même et à la rédaction des threads (mais qui peuvent ne pas encore voir les résultats des changements apportés en cours de rédaction). L'itérateur peut ou ne peut pas voir les changements depuis qu'il a été créé, et des opérations en bloc ne sont pas atomiques. Le redimensionnement est lent (comme pour HashMap/HashSet), donc essayer d'éviter cela par l'estimation de la taille nécessaire à la création.

Utilisez cette fonction lorsque vous avez de grands ensembles, une bonne (et rapide) fonction de hachage et peut faire l'estimation de la taille de l'ensemble et nécessaire simultanéité avant la création de la carte.

5) existe-il d'autres simultanées carte implémentations on pourrait utiliser ici?

Answer 2

Il est possible de combiner les contient() de la performance de HashSet avec la concurrence d'accès liées à des propriétés de CopyOnWriteArraySet à l'aide de la AtomicReference et le remplacement de l'ensemble de chaque modification.

La mise en œuvre de l'esquisse:

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 3

Si la Javadoc ne vous aide pas, vous devriez probablement juste de trouver un livre ou un article à lire sur les structures de données. Un coup d'œil:

• CopyOnWriteArraySet fait une nouvelle copie de la sous-matrice à chaque fois que vous muter la collection, afin d'écritures sont lents et les Itérateurs sont rapides et cohérentes.
• Les Collections.synchronizedSet() utilise la vieille école synchronisé les appels de méthode pour faire un Ensemble de threads. Ce serait un peu performantes version.
• ConcurrentSkipListSet offre performante écrit incompatible avec les opérations par lots (addAll, removeAll, etc.) et Itérateurs.
• Les Collections.newSetFromMap(nouveau ConcurrentHashMap()) a la sémantique de ConcurrentHashMap, qui je crois n'est pas forcément optimisé pour la lecture ou de l'écriture, mais comme ConcurrentSkipListSet, n'est pas cohérente d'opérations de traitement par lots.