Concurrent HashSet <T> dalam .NET Framework?

151

Saya memiliki kelas berikut.

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

Saya perlu mengubah bidang "Data" dari utas yang berbeda, jadi saya ingin beberapa pendapat tentang implementasi utas saat ini yang aman.

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

Apakah ada solusi yang lebih baik, langsung ke lapangan dan melindunginya dari akses bersamaan dengan beberapa utas?

kukab
sumber
Bagaimana kalau menggunakan salah satu koleksi di bawahSystem.Collections.Concurrent
I4V
8
Tentu saja, buat itu pribadi.
Hans Passant
3
Dari perspektif konkurensi, saya tidak melihat banyak kesalahan dengan apa yang telah Anda lakukan selain bidang Data yang dibuka untuk umum! Anda bisa mendapatkan kinerja baca yang lebih baik menggunakan ReaderWriterLockSlim jika itu menjadi masalah. msdn.microsoft.com/en-us/library/…
Allan Elder
@ AllanElder ReaderWriterLockakan membantu (efisien) ketika banyak pembaca dan satu penulis. Kita harus tahu apakah ini kasus OP
Sriram Sakthivel
2
Implementasi saat ini tidak benar-benar 'bersamaan' :) Ini hanya thread-safe.
tidak ditentukan

Jawaban:

164

Implementasi Anda benar. Sayangnya, NET Framework. Tidak menyediakan tipe hashset bersamaan built-in. Namun, ada beberapa solusi.

ConcurrentDictionary (disarankan)

Yang pertama ini menggunakan kelas ConcurrentDictionary<TKey, TValue>di namespace System.Collections.Concurrent. Dalam kasus ini, nilainya tidak ada gunanya, jadi kita bisa menggunakan yang sederhana byte(1 byte dalam memori).

private ConcurrentDictionary<string, byte> _data;

Ini adalah opsi yang disarankan karena jenisnya aman untuk thread dan memberi Anda keuntungan yang sama daripada HashSet<T>kunci kecuali dan nilai adalah objek yang berbeda.

Sumber: MSDN sosial

ConcurrentBag

Jika Anda tidak keberatan dengan entri duplikat, Anda bisa menggunakan kelas ConcurrentBag<T>di namespace yang sama dengan kelas sebelumnya.

private ConcurrentBag<string> _data;

Implementasi diri

Akhirnya, seperti yang Anda lakukan, Anda bisa mengimplementasikan tipe data Anda sendiri, menggunakan kunci atau cara lain yang disediakan oleh .NET agar Anda aman dari thread. Berikut adalah contoh yang bagus: Bagaimana mengimplementasikan ConcurrentHashSet di .Net

Satu-satunya kelemahan dari solusi ini adalah bahwa jenisnya HashSet<T>tidak secara bersamaan mengakses, bahkan untuk operasi membaca.

Saya mengutip kode dari posting terkait (aslinya ditulis oleh 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: Pindahkan metode kunci pintu masuk tryblok, karena mereka bisa melempar pengecualian dan menjalankan instruksi yang terkandung dalam finallyblok.

ZenLulz
sumber
8
kamus dengan nilai sampah adalah daftar
Ralf
44
@Ralf Yah, itu satu set, bukan daftar, karena tidak teratur.
Servy
11
Menurut dokumen MSDN yang agak singkat tentang "Koleksi dan Sinkronisasi (Keamanan Utas)" , kelas-kelas dalam Sistem. Koleksi dan ruang nama terkait dapat dibaca oleh banyak utas dengan aman. Ini berarti HashSet dapat dibaca dengan aman oleh banyak utas.
Hank Schultz
7
@Liver, referensi menggunakan lebih banyak memori per entri, bahkan jika itu adalah nullreferensi (referensi membutuhkan 4 byte dalam runtime 32-bit dan 8 byte dalam runtime 64-bit). Oleh karena itu, menggunakan a byte, struct kosong, atau sejenisnya dapat mengurangi jejak memori (atau mungkin tidak jika runtime menyelaraskan data pada batas memori asli untuk akses yang lebih cepat).
Lucero
4
Implementasi mandiri bukan ConcurrentHashSet melainkan ThreadSafeHashSet. Ada perbedaan besar antara 2 itu dan itulah sebabnya Micorosft meninggalkan SynchronizedCollections (orang-orang salah). Untuk menjadi operasi "Bersamaan" seperti GetOrAdd dll harus dilaksanakan (seperti kamus) atau concurrency tidak dapat dipastikan tanpa penguncian tambahan. Tetapi jika Anda membutuhkan penguncian tambahan di luar kelas maka mengapa Anda tidak menggunakan HashSet sederhana sejak awal?
George Mavritsakis
36

Alih-alih membungkus ConcurrentDictionaryatau mengunci HashSetsaya membuat ConcurrentHashSetberdasarkan aktual ConcurrentDictionary.

Implementasi ini mendukung operasi dasar per item tanpa HashSetoperasi yang ditetapkan karena kurang masuk akal dalam skenario bersamaan IMO:

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

concurrentHashSet.TryRemove("foo");

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

Output: 2

Anda bisa mendapatkannya dari NuGet di sini dan lihat sumbernya di GitHub di sini .

i3arnon
sumber
3
Ini harus menjadi jawaban yang diterima, implementasi yang bagus
smirkingman
Tidak harus Tambahkan diubah namanya menjadi TryAdd sehingga konsisten dengan ConcurrentDictionary ?
Neo
8
@No Tidak ... karena ini sengaja menggunakan semantik HashSet <T> , tempat Anda memanggil Tambah dan mengembalikan boolean yang menunjukkan apakah item ditambahkan (benar), atau sudah ada (salah). msdn.microsoft.com/en-us/library/bb353005(v=vs.110).aspx
G-Mac
Tidakkah seharusnya mengimplementasikan ISet<T>antarmuka yang benar-benar cocok dengan HashSet<T>semantik?
Nekromancer
1
@Nekromancer seperti yang saya katakan dalam jawaban, saya tidak berpikir itu masuk akal untuk memberikan metode yang ditetapkan ini dalam implementasi bersamaan. Overlapsmisalnya akan perlu mengunci instance selama menjalankannya, atau memberikan jawaban yang mungkin sudah salah. Kedua opsi tersebut adalah IMO yang buruk (dan dapat ditambahkan secara eksternal oleh konsumen).
i3arnon
21

Karena tidak ada orang lain yang menyebutkannya, saya akan menawarkan pendekatan alternatif yang mungkin atau mungkin tidak sesuai untuk tujuan khusus Anda:

Microsoft Immutable Collections

Dari posting blog oleh tim MS di belakang:

Sementara membuat dan menjalankan secara bersamaan lebih mudah dari sebelumnya, salah satu masalah mendasar masih ada: keadaan bersama yang bisa berubah. Membaca dari banyak utas biasanya sangat mudah, tetapi begitu keadaan perlu diperbarui, itu menjadi jauh lebih sulit, terutama dalam desain yang membutuhkan penguncian.

Alternatif untuk penguncian adalah memanfaatkan keadaan tidak berubah. Struktur data yang tidak dapat diubah dijamin tidak akan pernah berubah dan dengan demikian dapat dilewatkan secara bebas di antara berbagai utas tanpa khawatir menginjak jari kaki orang lain.

Desain ini menciptakan masalah baru: Bagaimana Anda mengelola perubahan dalam kondisi tanpa menyalin seluruh kondisi setiap waktu? Ini sangat sulit ketika koleksi terlibat.

Di sinilah koleksi abadi datang.

Koleksi ini termasuk ImmutableHashSet <T> dan ImmutableList <T> .

Performa

Karena koleksi abadi menggunakan struktur data pohon di bawahnya untuk memungkinkan pembagian struktural, karakteristik kinerjanya berbeda dari koleksi yang bisa berubah. Ketika membandingkan dengan koleksi penguncian yang dapat diubah, hasilnya akan tergantung pada pertikaian kunci dan pola akses. Namun, diambil dari posting blog lain tentang koleksi yang tidak dapat diubah:

T: Saya pernah mendengar bahwa koleksi abadi lambat. Apakah ini berbeda? Bisakah saya menggunakannya saat kinerja atau memori penting?

A: Koleksi yang tidak dapat diubah ini telah sangat disesuaikan untuk memiliki karakteristik kinerja yang kompetitif untuk koleksi yang dapat diubah sambil menyeimbangkan berbagi memori. Dalam beberapa kasus mereka hampir secepat koleksi yang bisa berubah baik secara algoritmik dan dalam waktu aktual, kadang-kadang bahkan lebih cepat, sementara dalam kasus lain mereka secara algoritmik lebih kompleks. Namun dalam banyak kasus perbedaannya dapat diabaikan. Secara umum Anda harus menggunakan kode paling sederhana untuk menyelesaikan pekerjaan dan kemudian menyesuaikan kinerja sesuai kebutuhan. Koleksi abadi membantu Anda menulis kode sederhana, terutama ketika keamanan utas harus dipertimbangkan.

Dengan kata lain, dalam banyak kasus perbedaannya tidak akan terlihat dan Anda harus pergi dengan pilihan yang lebih sederhana - yang untuk set bersamaan akan digunakan ImmutableHashSet<T>, karena Anda tidak memiliki implementasi penguncian yang bisa berubah yang ada! :-)

Søren Boisen
sumber
1
ImmutableHashSet<T>tidak banyak membantu jika maksud Anda adalah untuk memperbarui keadaan bersama dari beberapa utas atau apakah saya melewatkan sesuatu di sini?
tugberk
7
@tugberk Ya dan tidak. Karena set tidak dapat diubah, Anda harus memperbarui referensi untuk itu, yang koleksi itu sendiri tidak membantu Anda. Kabar baiknya adalah bahwa Anda telah mengurangi masalah kompleks memperbarui struktur data bersama dari beberapa utas menjadi masalah yang lebih sederhana untuk memperbarui referensi bersama. Perpustakaan memberi Anda metode ImmutableInterlocked.Update untuk membantu Anda.
Søren Boisen
1
@ SørenBoisen baru saja membaca tentang koleksi yang tidak dapat diubah dan mencoba mencari cara untuk menggunakannya dengan aman. ImmutableInterlocked.Updatetampaknya merupakan tautan yang hilang. Terima kasih!
xneg
4

Bagian rumit tentang membuat ISet<T>konkuren adalah bahwa metode yang ditetapkan (persatuan, persimpangan, perbedaan) bersifat iteratif. Paling tidak Anda harus mengulangi semua anggota dari salah satu set yang terlibat dalam operasi, sambil mengunci kedua set.

Anda kehilangan keuntungan ConcurrentDictionary<T,byte>ketika Anda harus mengunci seluruh set selama iterasi. Tanpa penguncian, operasi ini tidak aman untuk thread.

Mengingat tambahan overhead ConcurrentDictionary<T,byte>, mungkin lebih bijaksana hanya menggunakan bobot yang lebih ringan HashSet<T>dan hanya mengelilingi segala sesuatu di kunci.

Jika Anda tidak memerlukan operasi yang ditetapkan, gunakan ConcurrentDictionary<T,byte>dan gunakan saja default(byte)sebagai nilai saat Anda menambahkan kunci.

anjing pugby
sumber
2

Saya lebih suka solusi lengkap jadi saya melakukan ini: Pikirkan Anda, hitung saya diimplementasikan dengan cara yang berbeda karena saya tidak mengerti mengapa orang dilarang membaca hashset ketika mencoba menghitung nilainya.

@ Zen, Terima kasih sudah memulainya.

[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
sumber
Kuncinya dibuang ... tapi bagaimana dengan hashset batin, kapan ingatannya dilepaskan?
David Rettenbacher
1
@ Warappa dirilis pada pengumpulan sampah. Satu-satunya waktu saya secara manual membatalkan hal-hal dan menghapus seluruh kehadiran mereka dalam kelas adalah ketika subjek berisi peristiwa dan dengan demikian MUNGKIN membocorkan memori (seperti ketika Anda akan menggunakan ObservableCollection dan acara yang diubah). Saya terbuka untuk saran jika Anda dapat menambah pengetahuan pada pemahaman saya tentang subjek. Saya telah menghabiskan beberapa hari untuk meneliti pengumpulan sampah juga dan saya selalu ingin tahu tentang informasi baru
Dbl
@ AndreasMüller jawaban yang baik, namun saya bertanya-tanya mengapa Anda menggunakan '_lock.EnterWriteLock ();' diikuti oleh '_lock.EnterReadLock ();' dalam beberapa metode seperti 'IntersectWith' Saya pikir tidak perlu untuk membaca baca di sini karena kunci tulis akan mencegah pembacaan ketika masuk secara default.
Jalal Said
Jika Anda selalu harus EnterWriteLock, mengapa EnterReadLockada? Tidak bisakah kunci baca digunakan untuk metode seperti Contains?
ErikE
2
Ini bukan ConcurrentHashSet tetapi ThreadSafeHashSet. Lihat komentar saya pada jawaban @ ZenLulz tentang implementasi mandiri. Saya 99% yakin bahwa siapa pun yang menggunakan implementasi tersebut akan memiliki bug serius dalam aplikasi mereka.
George Mavritsakis