Add System.Collections.Concurrent.ConcurrentHashSet<T>

[LeaFrock]

Background and Motivation

We already have ConcurrentDictionary which takes great advantages at concurrent environment comparing to Dictionary. However, HashSet doesn't have a Concurrent version.
Sometimes(maybe very often in fact), we hope to use ConcurrentHashSet easily which its elements are never duplicated, with an O(1) operation for contains or remove methods at concurrent environment. It's quite different from ConcurrentBag and provides another choice for suitable usage.
You can also see details at issue #16443 . Almost 5 years passes, nobody gives an API proposal, so I'm here to finish it.

Proposed API

    public partial class ConcurrentHashSet<T> : System.Collections.Generic.ICollection<T>, System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.ICollection,System.Collections.IEnumerable where T : notnull
    {
        public ConcurrentHashSet() { }
        public ConcurrentHashSet(System.Collections.Generic.IEnumerable<T> collection) { }
        public ConcurrentHashSet(System.Collections.Generic.IEnumerable<T> collection, System.Collections.Generic.IEqualityComparer<T>? comparer) { }
        public ConcurrentHashSet(System.Collections.Generic.IEqualityComparer<T>? comparer) { }
        public ConcurrentHashSet(int concurrencyLevel, System.Collections.Generic.IEnumerable<T> collection, System.Collections.Generic.IEqualityComparer<T>? comparer) { }
        public ConcurrentHashSet(int concurrencyLevel, int capacity) { }
        public ConcurrentHashSet(int concurrencyLevel, int capacity, System.Collections.Generic.IEqualityComparer<T>? comparer) { }

        public int Count { get { throw null; } }
        public bool IsEmpty { get { throw null; } }
        bool System.Collections.Generic.ICollection<T>.IsReadOnly { get { throw null; } }
        bool System.Collections.ICollection.IsSynchronized { get { throw null; } }
        object System.Collections.ICollection.SyncRoot { get { throw null; } }

        public void Clear() { }
        public bool Contains(T item) { throw null; }
        public System.Collections.Generic.IEnumerator<T> GetEnumerator() { throw null; }
        public T GetOrAdd(T item) { throw null; }
        void System.Collections.Generic.ICollection<T>.Add(T item) { }
        bool System.Collections.Generic.ICollection<T>.Contains(T item) { throw null; }
        void System.Collections.Generic.ICollection<T>.CopyTo(T[] array, int index) { }
        bool System.Collections.Generic.ICollection<T>.Remove(T item) { throw null; }
        void System.Collections.ICollection.CopyTo(System.Array array, int index) { }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { throw null; }
        public T[] ToArray() { throw null; }
        public bool TryAdd(T item) { throw null; }
        public bool TryRemove(T item) { throw null; }

        public System.Collections.Generic.HashSet<T> ToHashSet() { } //optional
    }

Usage Examples

The main goal of ConcurrentHashSet is to improve performance and reduce cost, taking replace of HashSet-With-Lock pattern for concurrent environment. If we have it, the code can be written like below,

public class Sample()
{
     // private readonly object _syncRoot = new object();

     private readonly ConcurrentHashSet<Guid> _concurrentGuidSet = new ConcurrentHashSet<Guid>();
     // private readonly HashSet<Guid> _guidSet = new Hash<Guid>();

     public async Task Generate()
     {
          for(int i = 0; i < 100; i++)
          {
               Task.Run( () =>
               {
                    // The goal is to improve the performance, and ease the way of programming here.
                    _concurrentGuidSet.TryAdd(Guid.NewGuid());
                    //lock(_syncRoot)
                    //{
                    //     _guidSet.Add(Guid.NewGuid());
                    //}
               })
          }
     }
}

The difference could be very similiar to the one between Dictionary and ConcurrentDictionary.

Alternative Designs

1. Many developers tell that they use ConcurrentDictionary<T, byte> as a replace when meeting the requirement. They don't want the Value actually which is meaningless and totally a waste of memory. However, someones suggest that the first version of ConcurrentHashSet can be implemented by underlying ConcurrentDictionary<T, byte>, in order to add the APIs as soon as possible. Individually, I prefer to an independent implementation which is necessary to be discussed between excellent engineers of Microsoft & our community.

2. Do we need it to inherit ISet<T>/IReadOnlySet<T>? Though it's the concurrent version of HashSet, I'm not sure whether each API of HashSet needs a copy. In my opinion, not all APIs make sense while running in a concurrent environment. Of course, the discussion is required.

3. Do we need this API public HashSet<T> ToHashSet() to get a synchronous instance for easy usage?

Risks

It might not own concurrent version of the whole APIs of HashSet. Because it's a new collection, no break changes will occur. It just needs a pretty design :).

[LeaFrock]

By the way, this issue is not duplicated of #15326 , though we have almost the same requirement.

Tagging subscribers to this area: @eiriktsarpalis
See info in area-owners.md if you want to be subscribed.

[danmoseley]

Thanks for doing this. Could you please update the proposal to be complete? No implementation is needed, but everything that would be public, eg.,

• all constructors
• all members fulfiling the interface contracts - whether explicit or implicit. Eg., there's no getter for the generic enumerator, etc.
• to your question in Get core-setup building in the consolidated repo. #2, does it need ISet and IReadOnlySet-- it sounds like your use case is for storage and retrieval, not set operations like intersect and superset. Better to mimimally satisfy demonstrated needs, the interfaces can always be added later without breaking code, if use case emerges.
• CopyTo probably should be hidden in explicit interface implementation, as for ConcurrentDictionary
• Remove should probably be TryRemove
• do we need XXAdd overloads with a factory delegate, as for ConcurrentDictionary?
• do we need AddOrUpdate?
• do we need TryUpdate?
• does it need IsEmpty? this is syntactic sugar that with present JIT may be less efficient than checking Count == 0. (Fix CA1836 rule violations excluding Memory/Span #39890 (comment))

[LeaFrock]

@danmosemsft Updated, thanks!

• all constructors

Just take reference of ConcurrentDictionary<TKey, TValue>.

• all members fulfiling the interface contracts - whether explicit or implicit. Eg., there's no getter for the generic enumerator, etc.
• CopyTo probably should be hidden in explicit interface implementation, as for ConcurrentDictionary

Sorry, I'm confused whether the whole members of interface contract should be listed above? I deleted overloads of CopyTo and added getter for the generic enumerator.

• to your question in Get core-setup building in the consolidated repo. #2, does it need ISet and IReadOnlySet-- it sounds like your use case is for storage and retrieval, not set operations like intersect and superset. Better to mimimally satisfy demonstrated needs, the interfaces can always be added later without breaking code, if use case emerges.

Agreed. I moved the related content to 'Alternative Designs'.

• Remove should probably be TryRemove

Agreed & done.

• do we need XXAdd overloads with a factory delegate, as for ConcurrentDictionary?
• do we need AddOrUpdate?
• do we need TryUpdate?

I think NO, because it's a simpler collection than ConcurrentDictionary. For ConcurrentDictionary, we usually use AddOrUpdate/TryUpdate or factory delegate overloads to update Value only. ConcurrentHashSet owns the Key part only, so I don't see any point in them. Any comments welcomed.

• does it need IsEmpty? this is syntactic sugar that with present JIT may be less efficient than checking Count == 0.

I think we can add it. The following is the reasons from the perspective of my view,

• ConcurrentDictionary owns it
• it really simplify codes
• the performance gap is acceptable and I believe JIT performance here will be optimized sooner or later

[danmoseley]

Thanks

Sorry, I'm confused whether the whole members of interface contract should be listed above?

We're looking for the same format as in this file
https://github.com/dotnet/runtime/blob/master/src/libraries/System.Collections.Concurrent/ref/System.Collections.Concurrent.cs#L75

[LeaFrock]

@danmosemsft Done.

[danmoseley]

Ok thanks. The owners of this area will take a look. It might be a little while since we are focused on shipping 5.0 right now.

[eiriktsarpalis]

Many developers tell that they use ConcurrentDictionary<T, byte> as a replace when meeting the requirement. They don't want the Value actually which is meaningless and totally a waste of memory.

This is a compromise that has more or less worked fine, at least for my own requirements in the past. It would be interesting if we could quantify any performance improvements that come out of a dedicated ConcurrentHashSet implementation.

[bennidhamma]

Even if you just used a ConcurrentDictionary<T, byte> initially, under the covers, people could start using a cleaner interface.