Параллельный хэш-набор in.NET рамки?

Question

Параллельный хэш-набор in.NET рамки?

у меня есть следующий класс.

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

мне нужно изменить поле "Данные" из разных потоков, поэтому я хотел бы получить некоторые мнения о моей текущей потокобезопасной реализации.

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

есть ли лучшее решение, чтобы перейти непосредственно к полю и защитить его от параллельного доступа несколькими потоками?

5 105

c# blocking multithreading thread-safety mutex

5 ответов:

Вместо заключения ConcurrentDictionary или блокировка над a HashSet Я создал фактический ConcurrentHashSet на основе ConcurrentDictionary.

эта реализация поддерживает основные операции для каждого элемента без HashSet операции набора, поскольку они имеют меньше смысла в параллельных сценариях IMO:
var concurrentHashSet = new ConcurrentHashSet<string>(
    new[]
    {
        "hamster",
        "HAMster",
        "bar",
    },
    StringComparer.OrdinalIgnoreCase);

concurrentHashSet.TryRemove("foo");

if (concurrentHashSet.Contains("BAR"))
{
    Console.WriteLine(concurrentHashSet.Count);
}
выход: 2

вы можете получить его от NuGet здесь и смотрите источник на GitHub здесь.

22

поскольку никто больше не упоминал об этом, я предложу альтернативный подход, который может подходить или не подходить для конкретных целей:

Microsoft Неизменяемые Коллекции

С блоге командой MS позади:

хотя создание и одновременное выполнение проще, чем когда-либо, одна из фундаментальных проблем все еще существует: изменяемое общее состояние. Чтение из нескольких потоков, как правило, очень легко, но как только государство нуждается в обновлении, это становится намного сложнее, особенно в конструкциях, которые требуют блокировки.

альтернативой блокировке является использование неизменяемого состояния. Неизменяемые структуры данных гарантированно никогда не изменяются и, таким образом, могут свободно передаваться между различными потоками, не беспокоясь о наступлении на чужие пальцы.

этот дизайн создает новую проблему: как вы управляете изменениями в состоянии без копирования всего состояния каждый раз? Это особенно важно сложно, когда речь идет о коллекциях.

это где неизменяемые коллекции входят.

эти коллекции включают в себя ImmutableHashSet и ImmutableList.

производительность

поскольку неизменяемые коллекции используют древовидные структуры данных внизу для обеспечения структурного совместного использования, их характеристики производительности отличаются от изменяемых коллекций. При сравнении с блокировкой изменяемой коллекция, результаты будут зависеть от конкуренции блокировки и шаблонов доступа. Однако, взяты из еще один пост в блоге об immutable коллекции:

Q: я слышал, что immutable коллекции медленные. Это что-то другое? Могу ли я использовать их, когда важна производительность или память?

A: эти неизменяемые коллекции были высоко настроены, чтобы иметь конкурентоспособные характеристики производительности для изменяемых коллекций при балансировке памяти разделение. В некоторых случаях они почти так же быстры, как изменяемые коллекции как алгоритмически, так и в реальном времени, иногда даже быстрее, в то время как в других случаях они алгоритмически более сложны. Однако во многих случаях разница будет незначительной. Как правило, вы должны использовать самый простой код, чтобы выполнить работу, а затем настроить производительность по мере необходимости. Неизменяемые коллекции помогают вам писать простой код, особенно когда потокобезопасность должна быть продуманный.

другими словами, во многих случаях разница не будет заметна, и вы должны пойти с более простой выбор - что для параллельных наборов будет использовать ImmutableHashSet<T>, Так как у вас нет существующей блокировки изменяемой реализации! : -)

16

Я предпочитаю полные решения, поэтому я сделал это: имейте в виду, что мой счетчик реализован по-другому, потому что я не вижу, почему нужно запрещать читать хэш-набор при попытке подсчета его значений.

@Zen, Спасибо, что начали.

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

3

хитрая часть о ISet<T> concurrent заключается в том, что методы набора (объединение, пересечение, разность) являются итерационными по своей природе. По крайней мере, вы должны перебирать все n членов одного из наборов, участвующих в операции, при блокировке обоих наборов.

вы теряете преимущества a ConcurrentDictionary<T,byte> когда вы должны получить весь набор во время итерации. Без блокировки, эти операции не являются потокобезопасными.

учитывая дополнительные накладные расходы ConcurrentDictionary<T,byte>, вероятно, разумнее просто использовать более легкий вес HashSet<T> и просто окружить все в замках.

если вам не нужны операции набора, используйте ConcurrentDictionary<T,byte> и просто использовать default(byte) как значение при добавлении ключей.

3

ZenLulz · Accepted Answer · 2017-05-23 15:26:35

ваша реализация-это правильно. К сожалению, платформа .NET Framework не предоставляет встроенный параллельный тип hashset. Тем не менее, есть некоторые обходные пути.

ConcurrentDictionary (рекомендуется)

это первый, чтобы использовать класс ConcurrentDictionary<TKey, TValue> в пространстве имен System.Collections.Concurrent. В этом случае значение бессмысленно, поэтому мы можем использовать простой byte (1 байт памяти).
private ConcurrentDictionary<string, byte> _data;
это рекомендуемый вариант, потому что тип потокобезопасный и предоставить вам те же преимущества, чем HashSet<T> кроме ключа и значения это разные объекты.

источник: социальная MSDN

ConcurrentBag

если вы не возражаете против повторяющихся записей, вы можете использовать класс ConcurrentBag<T> в том же пространстве имен предыдущего класса.
private ConcurrentBag<string> _data;
реализации

наконец, как и вы, вы можете реализовать свои собственные данные введите, используя блокировку или другие способы, которые .NET предоставляет вам для потокобезопасности. Вот отличный пример: как реализовать ConcurrentHashSet в .Net

единственным недостатком этого решения является то, что тип HashSet<T> официально не имеет параллельного доступа, даже для операций чтения.

я цитирую код связанного сообщения (первоначально написанный Бен Мошер).
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: переместить входной замок методы, находящиеся не на try блоки, как они могли бы бросить исключение и выполнить инструкции, содержащиеся в finally блоки.