C#•4mo ago

Concurrent collection type similar to Dictionary<TKey, List<TValue>>

For example, I don't think ConcurrentDictionary<string, List<string>> or even ConcurrentDictionary<string, ConcurrentBag<string>> would be thread safe when accessing one of the lists. The simplest solution would be to lock whenever accessing the dictionary, but I was wondering if there is a better solution?

23 Replies

nathanAjacobsOP•4mo ago

I guess ConcurrentDictionary<string, ImmutableList<string>> would suffice. As it ensures when accessing the list via key it could never be modified, only replaced

canton7•4mo ago

Why would ConcurrentDictionary<string, ConcurrentBag<string>> not be safe?

333fred•4mo ago

If it wasn't safe, that would be a bug

canton7•4mo ago

And yeah, you could build one with an ImmutableList and some looping (and probably cheaper? Depends on workload I guess.)

nathanAjacobsOP•4mo ago

I feel like I thought of a case in the past where it would be problematic retrieving the concurrent bag via key from two separate threads and performing operations on the bag would be problematic. I may have been mistaken though

333fred•4mo ago

If it was problematic, that would be a bug. The point of a ConcurrentBag is to be able to do that safely

canton7•4mo ago

The only potentially racey case is two threads adding a new ConcurrentBag at the same time, and ConcurrentDictoinary handles that fine if you use it right ConcurrentDictionary doesn't lock the value in calls to e.g. AddOrUpdate, so using a List<T> wouldn't be OK. Maybe that's what you're thinking of?

nathanAjacobsOP•4mo ago

Yeah maybe, trying to come up with an implementation again to see if I can remember Tbh I probably wasn't using ConcurrentDictionary right I think it was relating to trimming the Dictionary on removal when the sub collection becomes empty. For example I don't think this Remove method is safe at all.

private ConcurrentDictionary<string, ConcurrentDictionary<string, byte>> _dict = [];

public void Add(string key, string valToAdd)
{
    _dict.AddOrUpdate<string>(key,
        (key, valToAdd) =>
        {
            ConcurrentDictionary<string, byte> subDict = new ConcurrentDictionary<string, byte>
            {
                [valToAdd] = 0
            };

            return subDict;
        },
        (key, subDict, valToAdd) =>
        {
            subDict.TryAdd(valToAdd, 0);
            return subDict;
        },
        valToAdd);
}

public void Remove(string key, string valToRemove)
{
    if (_dict.TryGetValue(key, out var subDict))
    {
        subDict.TryRemove(valToRemove, out _);
        
        // If the sub-dictionary is empty, remove it from the main dictionary
        if (subDict.IsEmpty)
        {
            _dict.TryRemove(key, out _);
        }
    }
}

private ConcurrentDictionary<string, ConcurrentDictionary<string, byte>> _dict = [];

public void Add(string key, string valToAdd)
{
    _dict.AddOrUpdate<string>(key,
        (key, valToAdd) =>
        {
            ConcurrentDictionary<string, byte> subDict = new ConcurrentDictionary<string, byte>
            {
                [valToAdd] = 0
            };

            return subDict;
        },
        (key, subDict, valToAdd) =>
        {
            subDict.TryAdd(valToAdd, 0);
            return subDict;
        },
        valToAdd);
}

public void Remove(string key, string valToRemove)
{
    if (_dict.TryGetValue(key, out var subDict))
    {
        subDict.TryRemove(valToRemove, out _);
        
        // If the sub-dictionary is empty, remove it from the main dictionary
        if (subDict.IsEmpty)
        {
            _dict.TryRemove(key, out _);
        }
    }
}

I essentially want to remove the key if the sub collection becomes empty. I am not sure of how to achieve that in a safe way though

canton7•4mo ago

Yeah, that's fair That's probably easier with an ImmutableList

nathanAjacobsOP•4mo ago

It'd be nice if there was some type of GetOrRemove method on ConcurrentDictionary that would let me execute logic and return a bool of whether it should be removed or not.

canton7•4mo ago

I don't think that would help, as the logic wouldn't be executed in a lock

nathanAjacobsOP•4mo ago

True, yeah I thought it would be. I think ImmutableList would have the same issue. The main issue I am seeing is that if multiple threads try to remove from the same key it is not safe because the sub collection could be stale when checking if it is empty

canton7•4mo ago

ImmuableList would be fine There's a TryRemove overload which takes both key and value (why it takes them as a kvp I have no idea), and only matches if the value hasn't changed So:

bool success;
do
{
    if (dict.TryGetValue(key, out var list))
    {
        var newlist = list.Remove(...);
        if (newList.IsEmpty)
        {
            success = dict.TryRemove(KeyValuePair.Create(key, list));
        }
        else
        {
            success = dict.TryUpdate(key, newList, list);
        }
    }
} while (!success);

bool success;
do
{
    if (dict.TryGetValue(key, out var list))
    {
        var newlist = list.Remove(...);
        if (newList.IsEmpty)
        {
            success = dict.TryRemove(KeyValuePair.Create(key, list));
        }
        else
        {
            success = dict.TryUpdate(key, newList, list);
        }
    }
} while (!success);

Something like that? (I haven't properly convinced myself that's correct, and it's late, but something like that anyway)

333fred•4mo ago

That looks correct to me

nathanAjacobsOP•4mo ago

Okay ty, much appreciated! Why is it in a while loop though? I think it uses KeyValuePair to avoid conflicting with the other overload

canton7•4mo ago

I guess should probably add a check that the list contained the element, ie that list != newList. I'm not sure if TryUpdate short-circuits in that case

333fred•4mo ago

Try, try, try again Until you succeed

canton7•4mo ago

In case another thread jumped in and modified the list in the meantime. In which case we discard our modified copy and try the whole thing again

nathanAjacobsOP•4mo ago

I see, that makes sense. Thanks again!

canton7•4mo ago

Typical immutable-with-multithreading pattern

333fred•4mo ago

Unless you just use locks to avoid needing them This type of pattern is very good if you expect to be doing a lot of reading, with very little writing. If you expect writing to be more common, you may be better served by a simple lock

nathanAjacobsOP•4mo ago

Good to know! My use case will definitely be more read heavy. Ty

canton7•4mo ago

The updates will be pretty quick, so unless you're heavily writing any particular key it's unlikely to have to loop in practice (in case it wasn't clear, note that the TryUpdate and TryRemove overloads both take a parameter which is used to make sure that the value hasn't unexpectedly been changed by another thread)

Gaming

Programming

Concurrent collection type similar to Dictionary<TKey, List<TValue>>

Did you find this page helpful?