Concurrent HashSet <T> dans .NET Framework?

152

J'ai la classe suivante.

class Test{
    public HashSet<string> Data = new HashSet<string>();
}

J'ai besoin de changer le champ "Données" de différents threads, donc j'aimerais avoir des opinions sur mon implémentation thread-safe actuelle.

class Test{
    public HashSet<string> Data = new HashSet<string>();

    public void Add(string Val){
            lock(Data) Data.Add(Val);
    }

    public void Remove(string Val){
            lock(Data) Data.Remove(Val);
    }
}

Existe-t-il une meilleure solution, pour aller directement sur le terrain et le protéger de l'accès simultané par plusieurs threads?

kukab
la source
Que diriez-vous d'utiliser l'une des collections sousSystem.Collections.Concurrent
I4V
8
Bien sûr, rendez-le privé.
Hans Passant
3
Du point de vue de la concurrence, je ne vois pas grand-chose de mal à ce que vous avez fait à part que le champ Données soit public! Vous pouvez obtenir de meilleures performances de lecture en utilisant ReaderWriterLockSlim si cela est un problème. msdn.microsoft.com/en-us/library/…
Allan Elder
@AllanElder ReaderWriterLocksera utile (efficace) lorsque plusieurs lecteurs et un seul écrivain. Nous devons savoir si c'est le cas pour OP
Sriram Sakthivel
2
L'implémentation actuelle n'est pas vraiment "concurrente" :) C'est juste thread-safe.
undefined

Réponses:

165

Votre implémentation est correcte. Le .NET Framework ne fournit malheureusement pas de type de hachage simultané intégré. Cependant, il existe quelques solutions de contournement.

ConcurrentDictionary (recommandé)

Cette première consiste à utiliser la classe ConcurrentDictionary<TKey, TValue>dans l'espace de noms System.Collections.Concurrent. Dans le cas, la valeur est inutile, on peut donc utiliser un simple byte(1 octet en mémoire).

private ConcurrentDictionary<string, byte> _data;

C'est l'option recommandée car le type est thread-safe et vous offre les mêmes avantages qu'une HashSet<T>clé et une valeur sauf sont des objets différents.

Source: MSDN social

ConcurrentBag

Si les entrées en double ne vous dérangent pas, vous pouvez utiliser la classe ConcurrentBag<T>dans le même espace de noms que la classe précédente.

private ConcurrentBag<string> _data;

Auto-implémentation

Enfin, comme vous l'avez fait, vous pouvez implémenter votre propre type de données, en utilisant le verrouillage ou d'autres moyens que le .NET vous offre pour être thread-safe. Voici un excellent exemple: Comment implémenter ConcurrentHashSet dans .Net

Le seul inconvénient de cette solution est que le type HashSet<T>n'a pas officiellement d'accès simultané, même pour les opérations de lecture.

Je cite le code de l'article lié (écrit à l'origine par Ben Mosher ).

using System;
using System.Collections.Generic;
using System.Threading;

namespace BlahBlah.Utilities
{
    public class ConcurrentHashSet<T> : IDisposable
    {
        private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
        private readonly HashSet<T> _hashSet = new HashSet<T>();

        #region Implementation of ICollection<T> ...ish
        public bool Add(T item)
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Add(item);
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public void Clear()
        {
            _lock.EnterWriteLock();
            try
            {
                _hashSet.Clear();
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public bool Contains(T item)
        {
            _lock.EnterReadLock();
            try
            {
                return _hashSet.Contains(item);
            }
            finally
            {
                if (_lock.IsReadLockHeld) _lock.ExitReadLock();
            }
        }

        public bool Remove(T item)
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Remove(item);
            }
            finally
            {
                if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }
        }

        public int Count
        {
            get
            {
                _lock.EnterReadLock();
                try
                {
                    return _hashSet.Count;
                }
                finally
                {
                    if (_lock.IsReadLockHeld) _lock.ExitReadLock();
                }
            }
        }
        #endregion

        #region Dispose
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }
        protected virtual void Dispose(bool disposing)
        {
            if (disposing)
                if (_lock != null)
                    _lock.Dispose();
        }
        ~ConcurrentHashSet()
        {
            Dispose(false);
        }
        #endregion
    }
}

EDIT: Déplacez les méthodes de verrouillage d'entrée à l'extérieur des tryblocs, car elles pourraient lever une exception et exécuter les instructions contenues dans les finallyblocs.

ZenLulz
la source
8
un dictionnaire avec des valeurs indésirables est une liste
Ralf
44
@Ralf Eh bien, c'est un ensemble, pas une liste, car il n'est pas ordonné.
Servy le
11
Selon le document plutôt court de MSDN sur «Collections et synchronisation (Thread Safety)» , les classes dans System.Collections et les espaces de noms associés peuvent être lues en toute sécurité par plusieurs threads. Cela signifie que HashSet peut être lu en toute sécurité par plusieurs threads.
Hank Schultz
7
@Oliver, une référence utilise beaucoup plus de mémoire par entrée, même si c'est une nullréférence (la référence nécessite 4 octets dans un runtime 32 bits et 8 octets dans un runtime 64 bits). Par conséquent, l'utilisation d'un byte, d'une structure vide ou similaire peut réduire l'encombrement de la mémoire (ou pas si le runtime aligne les données sur les limites de la mémoire native pour un accès plus rapide).
Lucero
4
L'auto-implémentation n'est pas un ConcurrentHashSet mais plutôt un ThreadSafeHashSet. Il y a une grande différence entre ces 2 et c'est pourquoi Micorosft a abandonné SynchronizedCollections (les gens se sont trompés). Pour être "simultanées", des opérations telles que GetOrAdd, etc. doivent être implémentées (comme le dictionnaire) ou bien la concurrence ne peut être assurée sans verrouillage supplémentaire. Mais si vous avez besoin d'un verrouillage supplémentaire en dehors de la classe, pourquoi n'utilisez-vous pas un simple HashSet dès le début?
George Mavritsakis
36

Au lieu d'envelopper un ConcurrentDictionaryou de verrouiller un, HashSetj'ai créé un réel ConcurrentHashSetbasé sur ConcurrentDictionary.

Cette implémentation prend en charge les opérations de base par article sans HashSetles opérations d'ensemble car elles ont moins de sens dans les scénarios simultanés IMO:

var concurrentHashSet = new ConcurrentHashSet<string>(
    new[]
    {
        "hamster",
        "HAMster",
        "bar",
    },
    StringComparer.OrdinalIgnoreCase);

concurrentHashSet.TryRemove("foo");

if (concurrentHashSet.Contains("BAR"))
{
    Console.WriteLine(concurrentHashSet.Count);
}

Sortie: 2

Vous pouvez l'obtenir à partir de NuGet ici et voir la source sur GitHub ici .

i3arnon
la source
3
Cela devrait être la réponse acceptée, une excellente mise en œuvre
Smirkingman
Add ne devrait-il pas être renommé TryAdd afin qu'il soit cohérent avec ConcurrentDictionary ?
Neo
8
@Neo No ... parce qu'il utilise intentionnellement la sémantique HashSet <T> , où vous appelez Add et il renvoie un booléen indiquant si l'élément a été ajouté (true) ou s'il existait déjà (false). msdn.microsoft.com/en-us/library/bb353005(v=vs.110).aspx
G-Mac
Ne devrait-il pas implémenter l' ISet<T>interface pour correspondre à la HashSet<T>sémantique?
Nekromancer
1
@Nekromancer comme je l'ai dit dans la réponse, je ne pense pas qu'il soit logique de fournir ces méthodes définies dans une implémentation simultanée. Overlapspar exemple, il faudrait soit verrouiller l'instance tout au long de son exécution, soit fournir une réponse qui peut déjà être erronée. Les deux options sont mauvaises IMO (et peuvent être ajoutées en externe par les consommateurs).
i3arnon le
21

Étant donné que personne d'autre ne l'a mentionné, je proposerai une approche alternative qui peut ou non être appropriée à votre objectif particulier:

Collections immuables Microsoft

À partir d'un article de blog de l'équipe MS derrière:

Bien que la création et l'exécution simultanées soient plus faciles que jamais, l'un des problèmes fondamentaux existe toujours: l'état partagé mutable. La lecture à partir de plusieurs threads est généralement très facile, mais une fois que l'état doit être mis à jour, cela devient beaucoup plus difficile, en particulier dans les conceptions nécessitant un verrouillage.

Une alternative au verrouillage consiste à utiliser l'état immuable. Les structures de données immuables sont garanties de ne jamais changer et peuvent donc être passées librement entre différents threads sans se soucier de marcher sur les orteils de quelqu'un d'autre.

Cette conception crée cependant un nouveau problème: comment gérer les changements d'état sans copier l'état entier à chaque fois? Ceci est particulièrement délicat lorsque des collections sont impliquées.

C'est là qu'interviennent les collections immuables.

Ces collections incluent ImmutableHashSet <T> et ImmutableList <T> .

Performance

Étant donné que les collections immuables utilisent des structures de données arborescentes en dessous pour permettre le partage structurel, leurs caractéristiques de performance sont différentes de celles des collections mutables. Lors d'une comparaison avec une collection mutable verrouillable, les résultats dépendront du conflit de verrouillage et des modèles d'accès. Cependant, tiré d' un autre article de blog sur les collections immuables:

Q: J'ai entendu dire que les collections immuables sont lentes. Sont-ils différents? Puis-je les utiliser lorsque les performances ou la mémoire sont importantes?

R: Ces collections immuables ont été hautement réglées pour avoir des caractéristiques de performances compétitives par rapport aux collections mutables tout en équilibrant le partage de mémoire. Dans certains cas, ils sont presque aussi rapides que les collections mutables à la fois algorithmiquement et en temps réel, parfois même plus rapides, tandis que dans d'autres cas, ils sont plus complexes sur le plan algorithmique. Dans de nombreux cas, cependant, la différence sera négligeable. En règle générale, vous devez utiliser le code le plus simple pour faire le travail, puis régler les performances si nécessaire. Les collections immuables vous aident à écrire du code simple, en particulier lorsque la sécurité des threads doit être prise en compte.

En d'autres termes, dans de nombreux cas, la différence ne sera pas perceptible et vous devriez opter pour le choix le plus simple - qui serait à utiliser pour les ensembles simultanés ImmutableHashSet<T>, car vous n'avez pas d'implémentation de verrouillage mutable existante! :-)

Søren Boisen
la source
1
ImmutableHashSet<T>n'aide pas beaucoup si votre intention est de mettre à jour l'état partagé à partir de plusieurs threads ou est-ce que je manque quelque chose ici?
tugberk
7
@tugberk Oui et non. Puisque l'ensemble est immuable, vous devrez mettre à jour la référence à celui-ci, ce que la collection elle-même ne vous aide pas. La bonne nouvelle est que vous avez réduit le problème complexe de la mise à jour d'une structure de données partagée à partir de plusieurs threads au problème beaucoup plus simple de la mise à jour d'une référence partagée. La bibliothèque vous fournit la méthode ImmutableInterlocked.Update pour vous aider.
Søren Boisen
1
@ SørenBoisen a lu des informations sur les collections immuables et a essayé de comprendre comment les utiliser thread-safe. ImmutableInterlocked.Updatesemble être le chaînon manquant. Je vous remercie!
xneg
4

La partie délicate de la création d'un ISet<T>concurrent est que les méthodes d'ensemble (union, intersection, différence) sont de nature itérative. Au minimum, vous devez parcourir les n membres de l'un des ensembles impliqués dans l'opération, tout en verrouillant les deux ensembles.

Vous perdez les avantages d'un ConcurrentDictionary<T,byte>lorsque vous devez verrouiller l'ensemble entier pendant l'itération. Sans verrouillage, ces opérations ne sont pas thread-safe.

Compte tenu des frais généraux supplémentaires ConcurrentDictionary<T,byte>, il est probablement plus sage d'utiliser le poids plus léger HashSet<T>et de tout entourer de serrures.

Si vous n'avez pas besoin des opérations définies, utilisez ConcurrentDictionary<T,byte>et utilisez simplement default(byte)comme valeur lorsque vous ajoutez des clés.

pugby
la source
2

Je préfère les solutions complètes, alors j'ai fait ceci: Attention, mon compte est implémenté d'une manière différente car je ne vois pas pourquoi on devrait interdire de lire le hashset en essayant de compter ses valeurs.

@Zen, merci d'avoir démarré.

[DebuggerDisplay("Count = {Count}")]
[Serializable]
public class ConcurrentHashSet<T> : ICollection<T>, ISet<T>, ISerializable, IDeserializationCallback
{
    private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);

    private readonly HashSet<T> _hashSet = new HashSet<T>();

    public ConcurrentHashSet()
    {
    }

    public ConcurrentHashSet(IEqualityComparer<T> comparer)
    {
        _hashSet = new HashSet<T>(comparer);
    }

    public ConcurrentHashSet(IEnumerable<T> collection)
    {
        _hashSet = new HashSet<T>(collection);
    }

    public ConcurrentHashSet(IEnumerable<T> collection, IEqualityComparer<T> comparer)
    {
        _hashSet = new HashSet<T>(collection, comparer);
    }

    protected ConcurrentHashSet(SerializationInfo info, StreamingContext context)
    {
        _hashSet = new HashSet<T>();

        // not sure about this one really...
        var iSerializable = _hashSet as ISerializable;
        iSerializable.GetObjectData(info, context);
    }

    #region Dispose

    public void Dispose()
    {
        Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (disposing)
            if (_lock != null)
                _lock.Dispose();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _hashSet.GetEnumerator();
    }

    ~ConcurrentHashSet()
    {
        Dispose(false);
    }

    public void OnDeserialization(object sender)
    {
        _hashSet.OnDeserialization(sender);
    }

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        _hashSet.GetObjectData(info, context);
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    #endregion

    public void Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.Add(item);
        }
        finally
        {
            if(_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void UnionWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.UnionWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void IntersectWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.IntersectWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void ExceptWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        _lock.EnterReadLock();
        try
        {
            _hashSet.ExceptWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            if (_lock.IsReadLockHeld) _lock.ExitReadLock();
        }
    }

    public void SymmetricExceptWith(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.SymmetricExceptWith(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsSubsetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsSubsetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsSupersetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsSupersetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsProperSupersetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsProperSupersetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool IsProperSubsetOf(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.IsProperSubsetOf(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Overlaps(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Overlaps(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool SetEquals(IEnumerable<T> other)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.SetEquals(other);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    bool ISet<T>.Add(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Add(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void Clear()
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.Clear();
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Contains(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Contains(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public void CopyTo(T[] array, int arrayIndex)
    {
        _lock.EnterWriteLock();
        try
        {
            _hashSet.CopyTo(array, arrayIndex);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public bool Remove(T item)
    {
        _lock.EnterWriteLock();
        try
        {
            return _hashSet.Remove(item);
        }
        finally
        {
            if (_lock.IsWriteLockHeld) _lock.ExitWriteLock();
        }
    }

    public int Count
    {
        get
        {
            _lock.EnterWriteLock();
            try
            {
                return _hashSet.Count;
            }
            finally
            {
                if(_lock.IsWriteLockHeld) _lock.ExitWriteLock();
            }

        }
    }

    public bool IsReadOnly
    {
        get { return false; }
    }
}
Dbl
la source
Le verrou est supprimé ... mais qu'en est-il du hashset interne, quand sa mémoire est-elle libérée?
David Rettenbacher
1
@Warappa, il est publié lors du garbage collection. Le seul moment où j'annule manuellement les choses et efface toute leur présence dans une classe, c'est lorsque les sujets contiennent des événements et donc PEUVENT perdre de la mémoire (comme lorsque vous utiliseriez ObservableCollection et son événement modifié). Je suis ouvert aux suggestions si vous pouvez ajouter des connaissances à ma compréhension du sujet. J'ai également passé quelques jours à faire des recherches sur le ramassage des ordures et je suis toujours curieux de connaître les nouvelles informations
Dbl
@ AndreasMüller bonne réponse, mais je me demande pourquoi vous utilisez '_lock.EnterWriteLock ();' suivi de '_lock.EnterReadLock ();' dans certaines méthodes comme «IntersectWith», je pense qu'il n'est pas nécessaire de regarder la lecture ici car le verrouillage en écriture empêchera toute lecture lors de la saisie par défaut.
Jalal Said le
Si vous devez toujours EnterWriteLock, pourquoi EnterReadLockexiste-t- il même? Le verrou de lecture ne peut-il pas être utilisé pour des méthodes comme Contains?
ErikE
2
Ce n'est pas un ConcurrentHashSet mais plutôt un ThreadSafeHashSet. Voir mon commentaire sur la réponse @ZenLulz concernant l'auto-implémentation. Je suis sûr à 99% que quiconque a utilisé ces implémentations aura un bug sérieux dans son application.
George Mavritsakis