Concurrent HashSet <T> w .NET Framework?


151

Mam następującą klasę.

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

Muszę zmienić pole „Dane” z różnych wątków, więc chciałbym poznać opinie na temat mojej obecnej implementacji bezpiecznej wątkowo.

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

Czy jest lepsze rozwiązanie, aby przejść bezpośrednio do pola i zabezpieczyć je przed równoczesnym dostępem wielu wątków?


Co powiesz na wykorzystanie jednej z kolekcji podSystem.Collections.Concurrent
I4V

8
Oczywiście uczyń to prywatnym.
Hans Passant,

3
Z punktu widzenia współbieżności nie widzę nic złego w tym, co zrobiłeś, poza tym, że pole danych jest publiczne! Możesz uzyskać lepszą wydajność odczytu za pomocą ReaderWriterLockSlim, jeśli jest to problem. msdn.microsoft.com/en-us/library/…
Allan Elder

@AllanElder ReaderWriterLockbędzie pomocny (wydajny), gdy wielu czytelników i jeden pisarz. Musimy wiedzieć, czy tak jest w przypadku OP
Sriram Sakthivel

2
Obecna implementacja nie jest tak naprawdę „współbieżna” :) Jest po prostu bezpieczna wątkowo.
nieokreślony

Odpowiedzi:


164

Twoja implementacja jest prawidłowa. .NET Framework nie zapewnia niestety wbudowanego współbieżnego typu hashset. Istnieją jednak pewne obejścia.

ConcurrentDictionary (zalecane)

Pierwszym jest użycie klasy ConcurrentDictionary<TKey, TValue>w przestrzeni nazw System.Collections.Concurrent. W takim przypadku wartość jest bezcelowa, więc możemy użyć prostego byte(1 bajt w pamięci).

private ConcurrentDictionary<string, byte> _data;

Jest to zalecana opcja, ponieważ typ jest bezpieczny dla wątków i zapewnia te same korzyści, co HashSet<T>klucz z wyjątkiem i wartość to różne obiekty.

Źródło: Social MSDN

ConcurrentBag

Jeśli nie masz nic przeciwko zduplikowanym wpisom, możesz użyć klasy ConcurrentBag<T>w tej samej przestrzeni nazw, co poprzednia klasa.

private ConcurrentBag<string> _data;

Samodzielna realizacja

Wreszcie, tak jak to zrobiłeś, możesz zaimplementować własny typ danych, używając blokady lub innych sposobów, które zapewnia .NET, aby zapewnić bezpieczeństwo wątków. Oto wspaniały przykład: Jak zaimplementować ConcurrentHashSet w .Net

Jedyną wadą tego rozwiązania jest to, że typ HashSet<T>nie jest oficjalnie równoczesny, nawet w przypadku operacji odczytu.

Cytuję kod posta, do którego prowadzi link (pierwotnie napisany przez Bena Moshera ).

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

EDYCJA: Przenieś metody blokady wejścia poza trybloki, ponieważ mogą one zgłosić wyjątek i wykonać instrukcje zawarte w finallyblokach.


8
słownik z niepotrzebnymi wartościami to lista
Ralf,

44
@Ralf Cóż, to zestaw, a nie lista, ponieważ jest nieuporządkowana.
Servy

11
Według raczej krótkiego dokumentu MSDN „Kolekcje i synchronizacja (bezpieczeństwo wątków)” , klasy w System.Collections i powiązane przestrzenie nazw mogą być bezpiecznie odczytywane przez wiele wątków. Oznacza to, że HashSet może być bezpiecznie odczytywany przez wiele wątków.
Hank Schultz

7
@Oliver, odwołanie zużywa znacznie więcej pamięci na wpis, nawet jeśli jest nullreferencją (odwołanie wymaga 4 bajtów w 32-bitowym czasie wykonywania i 8 bajtów w 64-bitowym czasie wykonywania). W związku z tym użycie bytepustej struktury lub podobnej może zmniejszyć zużycie pamięci (lub może nie, jeśli środowisko wykonawcze wyrównuje dane w granicach pamięci natywnej w celu uzyskania szybszego dostępu).
Lucero

4
Samoimplementacja nie jest ConcurrentHashSet, ale raczej ThreadSafeHashSet. Istnieje duża różnica między tymi dwoma i dlatego Micorosft porzucił SynchronizedCollections (ludzie źle to zrozumieli). Aby być „współbieżnymi”, operacje takie jak GetOrAdd itp. Powinny być zaimplementowane (podobnie jak słownik), w przeciwnym razie nie można zapewnić współbieżności bez dodatkowego blokowania. Ale jeśli potrzebujesz dodatkowego blokowania poza klasą, dlaczego nie użyjesz prostego HashSet od samego początku?
George Mavritsakis

36

Zamiast zawijać ConcurrentDictionarylub blokować plik HashSet, utworzyłem rzeczywisty ConcurrentHashSetoparty na ConcurrentDictionary.

Ta implementacja obsługuje podstawowe operacje na element bez HashSetustawionych operacji, ponieważ mają one mniej sensu w współbieżnych scenariuszach IMO:

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

concurrentHashSet.TryRemove("foo");

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

Wyjście: 2

Możesz go pobrać z NuGet tutaj i zobaczyć źródło na GitHub tutaj .


3
To powinna być akceptowana odpowiedź, świetna realizacja
smirkingman

Nie powinno Dodaj zostać zmieniona na TryAdd więc, że jest to zgodne z ConcurrentDictionary ?
Neo

8
@Neo No ... ponieważ celowo używa semantyki HashSet <T> , w której wywołujesz Add i zwraca wartość logiczną wskazującą, czy element został dodany (prawda), czy już istniał (fałsz). msdn.microsoft.com/en-us/library/bb353005(v=vs.110).aspx
G-Mac

Czy nie powinien zaimplementować ISet<T>interfejsu bo faktycznie pasującego do HashSet<T>semantyki?
Nekromancer,

1
@Nekromancer, jak powiedziałem w odpowiedzi, nie wydaje mi się sensowne dostarczanie tych ustawionych metod we współbieżnej implementacji. Overlapsna przykład musiałby albo zablokować instancję na czas jej działania, albo udzielić odpowiedzi, która może już być błędna. Obie opcje są złe IMO (i mogą być dodawane zewnętrznie przez konsumentów).
i3arnon,

21

Ponieważ nikt inny o tym nie wspomniał, zaproponuję alternatywne podejście, które może, ale nie musi być odpowiednie dla twojego konkretnego celu:

Niezmienne kolekcje firmy Microsoft

Z posta na blogu zespołu MS odpowiedzialnego za:

Chociaż tworzenie i uruchamianie współbieżne jest łatwiejsze niż kiedykolwiek, jeden z podstawowych problemów nadal istnieje: zmienny stan współdzielony. Czytanie z wielu wątków jest zazwyczaj bardzo łatwe, ale gdy stan musi zostać zaktualizowany, staje się znacznie trudniejszy, szczególnie w projektach wymagających blokowania.

Alternatywą dla blokowania jest wykorzystanie niezmiennego stanu. Niezmienne struktury danych mają gwarancję, że nigdy się nie zmienią i dzięki temu mogą być swobodnie przekazywane między różnymi wątkami bez obawy o nadepnięcie czyimś palcom.

Ten projekt stwarza jednak nowy problem: Jak zarządzać zmianami stanu bez kopiowania całego stanu za każdym razem? Jest to szczególnie trudne w przypadku kolekcji.

W tym miejscu pojawiają się niezmienne kolekcje.

Te kolekcje obejmują ImmutableHashSet <T> i ImmutableList <T> .

Występ

Ponieważ niezmienne kolekcje używają drzewiastych struktur danych pod spodem, aby umożliwić współużytkowanie strukturalne, ich charakterystyki wydajnościowe różnią się od kolekcji zmiennych. W porównaniu z blokującą kolekcją mutowalną, wyniki będą zależeć od rywalizacji o blokady i wzorców dostępu. Jednak zaczerpnięte z innego posta na blogu o niezmiennych kolekcjach:

P: Słyszałem, że niezmienne kolekcje są powolne. Czy te są inne? Czy mogę ich używać, gdy ważna jest wydajność lub pamięć?

O: Te niezmienne kolekcje zostały w dużym stopniu dostrojone, aby mieć konkurencyjną charakterystykę wydajności w porównaniu z kolekcjami zmiennymi, jednocześnie równoważąc współdzielenie pamięci. W niektórych przypadkach są one prawie tak szybkie, jak zbiory podlegające zmianom, zarówno algorytmicznie, jak iw czasie rzeczywistym, czasami nawet szybsze, podczas gdy w innych przypadkach są algorytmicznie bardziej złożone. Jednak w wielu przypadkach różnica będzie znikoma. Ogólnie rzecz biorąc, do wykonania zadania należy użyć najprostszego kodu, a następnie dostroić wydajność w razie potrzeby. Niezmienne kolekcje ułatwiają pisanie prostego kodu, zwłaszcza gdy należy wziąć pod uwagę bezpieczeństwo wątków.

Innymi słowy, w wielu przypadkach różnica nie będzie zauważalna i powinieneś wybrać prostszy wybór - który w przypadku zestawów współbieżnych byłby odpowiedni ImmutableHashSet<T>, ponieważ nie masz istniejącej blokującej mutowalnej implementacji! :-)


1
ImmutableHashSet<T>niewiele pomaga, jeśli zamierzasz zaktualizować stan udostępniony z wielu wątków lub czy czegoś tu brakuje?
holownik

7
@tugberk Yes and no. Ponieważ zestaw jest niezmienny, będziesz musiał zaktualizować odniesienie do niego, w czym sama kolekcja ci nie pomoże. Dobra wiadomość jest taka, że ​​ograniczyłeś złożony problem aktualizowania współdzielonej struktury danych z wielu wątków do znacznie prostszego problemu aktualizowania współdzielonego odniesienia. Biblioteka udostępnia metodę ImmutableInterlocked.Update , która pomaga w tym.
Søren Boisen

1
@ SørenBoisen po prostu przeczytał o niezmiennych kolekcjach i próbował wymyślić, jak z nich korzystać. ImmutableInterlocked.Updatewydaje się być brakującym ogniwem. Dziękuję Ci!
xneg

4

Najtrudniejsze w tworzeniu ISet<T>współbieżności jest to, że metody zestawu (suma, przecięcie, różnica) mają charakter iteracyjny. Musisz przynajmniej wykonać iterację po wszystkich n elementach jednego ze zbiorów zaangażowanych w operację, jednocześnie blokując oba zestawy.

Tracisz zalety a, ConcurrentDictionary<T,byte>gdy musisz zablokować cały zestaw podczas iteracji. Bez blokowania operacje te nie są bezpieczne dla wątków.

Biorąc pod uwagę dodatkowe koszty ConcurrentDictionary<T,byte>, prawdopodobnie rozsądniej jest po prostu użyć mniejszej wagi HashSet<T>i po prostu otoczyć wszystko zamkami.

Jeśli nie potrzebujesz operacji na zestawach, użyj ConcurrentDictionary<T,byte>i po prostu użyj default(byte)jako wartości podczas dodawania kluczy.


2

Wolę kompletne rozwiązania, więc zrobiłem to: Pamiętaj, że mój Count jest zaimplementowany w inny sposób, ponieważ nie widzę, dlaczego należy zabronić odczytywania hashsetu podczas próby policzenia jego wartości.

@Zen, dziękujemy za rozpoczęcie.

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

Zamek zostaje usunięty ... ale co z wewnętrznym hashsetem, kiedy jego pamięć zostaje zwolniona?
David Rettenbacher

1
@Warappa jest wydawany po usunięciu elementów bezużytecznych. Jedyny przypadek, w którym ręcznie zeruję elementy i usuwam ich całą obecność w klasie, ma miejsce, gdy tematy zawierają zdarzenia, a zatem MOŻE przeciekać pamięci (tak jak w przypadku użycia ObservableCollection i zmienionego zdarzenia). Jestem otwarty na sugestie, jeśli możesz dodać do mojego zrozumienia wiedzę na ten temat. Spędziłem kilka dni na zbieraniu śmieci i zawsze jestem ciekawy nowych informacji
Dbl.

@ AndreasMüller dobra odpowiedź, jednak zastanawiam się, dlaczego używasz „_lock.EnterWriteLock ();”, a następnie „_lock.EnterReadLock ();” w niektórych metodach, takich jak „IntersectWith”, myślę, że nie ma tu potrzeby używania wyglądu do odczytu, ponieważ blokada zapisu uniemożliwi odczyt (y) przy wejściu domyślnie.
Jalal powiedział

Jeśli zawsze musisz EnterWriteLock, dlaczego w EnterReadLockogóle istnieje? Czy nie można użyć blokady odczytu do metod takich jak Contains?
ErikE

2
To nie jest ConcurrentHashSet, ale raczej ThreadSafeHashSet. Zobacz mój komentarz na temat odpowiedzi @ZenLulz dotyczącej samodzielnej realizacji. Jestem na 99% pewien, że każdy, kto korzystał z tych implementacji, będzie miał poważny błąd w swojej aplikacji.
George Mavritsakis
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.