Runtime: ConcurrentList<T>

[luizfernandonb]

Background and Motivation

An easier way to handle lists in different threads.

Proposed API

As far as I know, there is no thread-safe collection that works exactly with List<T>, there isConcurrentBag<T>, but let's face it, it is not the same thing, nor can we remove an exact object that we want when using it, and this is definitely not a good thing.

My proposal is in the title, create a ConcurrentList<T>, or improve the ConcurrentBag<T>.

```C#
namespace System.Collections.Concurrent
{

• public class ConcurrentList { }
  }

## Usage Examples
``` C#
var concurrentList = new ConcurrentList<string>();

for (var i = 0; i < 100; ++i)
    concurrentList.TryAdd($"Look at this beautiful number: {i}");

concurrentList.TryRemove(20);

// Anyway, all thread-safe methods should exist in the ConcurrentList<T>.

Alternative Designs

Nothing.

Risks

None that I know of.

[msftbot[bot]]

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

[stephentoub]

What is the exact surface area you're proposing? And how do you propose it be implemented? Just using a lock around every operation doesn't fit with the intention of these Concurrent* data structures, and can easily be done by someone using List<T>.

[Clockwork-Muse]

... how is:

// It's unclear whether you meant index or element here - the index-removing method on a list is RemoveAt
concurrentList.TryRemove(20);

different from:

concurrentBag.TryTake(20);

Note that an ordered collection with multiple readers/writers is essentially impossible without locking the entire collection, at which point you might as well just use a normal list. For example, attempting to access something by index - for any operation - is inherently prone to race conditions.

What features do you think ConcurrentBag needs?

[luizfernandonb]

What is the exact surface area you're proposing? And how do you propose it be implemented? Just using a lock around every operation doesn't fit with the intention of these Concurrent* data structures, and can easily be done by someone using List<T>.

I don't have much idea of the implementation, but it would be similar to ConcurrentBag , thread-safe and compatible with data of type List , at least I believe, the idea of having the ConcurrentList was out of the blue, no I thought a lot before making this issue, sorry.

... how is:

// It's unclear whether you meant index or element here - the index-removing method on a list is RemoveAt
concurrentList.TryRemove(20);

different from:

concurrentBag.TryTake(20);

Note that an ordered collection with multiple readers/writers is essentially impossible without locking the entire collection, at which point you might as well just use a normal list. For example, attempting to access something by index - for any operation - is inherently prone to race conditions.

What features do you think ConcurrentBag needs?

I already suspected that Concurrent classes were special to be accessed because they are natively thread-safe, but the way I thought, the ConcurrentList<T> would have the native methods of a List<T>, modified natively to suit the thread- safe, for example: .Add(item) is changed to .TryAdd(item), as we have in ConcurrentDictionary<T>, for example. What I thought about the class was practically just that, because in my usability ConcurrentBag is not useful, there is no way for me to remove a specific element with the .TryTake (item).

I may not have been very explicit about how it should be and etc, if I didn't go, I apologize, it was an idea that I had due to the codes I had recently, I honestly think it is a good idea, there is no native thing in C# that is thread-safe that directly touches it.

[Clockwork-Muse]

... actually, some of that is on me, for not reading enough of the documentation for TryTake.

That said, concurrent writers are still problematic; you still have data race conditions between threads adding and removing specific elements; you'd have no guarantee that the item is ever removed (that is, for maximum safety your code should always assume the item is still present). Note that this is actually still a potential problem even if you lock the entire list - you'd need some way to block future inclusion. Usually, you're just going to want to ignore "unwanted" values when you read them. Or implement a pipeline with _multiple_ ConcurrentWhatevers, and have a pipeline step dropping unwanted values by just not passing them on.

[luizfernandonb]

... actually, some of that is on me, for not reading enough of the documentation for TryTake.

That said, concurrent writers are still problematic; you still have data race conditions between threads adding and removing specific elements; you'd have no guarantee that the item is ever removed (that is, for maximum safety your code should always assume the item is still present). Note that this is actually still a potential problem even if you lock the entire list - you'd need some way to block future inclusion. Usually, you're just going to want to ignore "unwanted" values when you read them. Or implement a pipeline with _multiple_ ConcurrentWhatevers, and have a pipeline step dropping unwanted values by just not passing them on.

Oh ok, so isn't it feasible to have a ConcurrentList<T>?

[Clockwork-Muse]

... the existing concurrent classes are somewhat deliberately hard to misuse, and the single method you've proposed so far is essentially always unsafe.

You haven't stated what makes you think you need this behavior in the first place. What problem is it you're currently experiencing that you think this would have solved?

[luizfernandonb]

... the existing concurrent classes are somewhat deliberately hard to misuse, and the single method you've proposed so far is essentially always unsafe.

You haven't stated what makes you think you need this behavior in the first place. What problem is it you're currently experiencing that you think this would have solved?

Here: https://github.com/luizstudios/Tars/blob/master/Tars.ScheduledEvents/Extensions/DiscordBotBaseExtensions.cs#L14

I'm doing an improvisation to make this work in thread-safe, I'm using ConcurrentDictionary because the TryAdd and TryRemove methods help a lot. The byte in TValue is just to take up space, because I have nothing to put there, so a ConcurrentList would be useful these hours, in addition to removing this improvisation that I did, it is useful in countless other things.

[ygra]

@luizfernandonb The whole point of List is to be an _ordered_ collection of items, accessible by index. Since you're already using ConcurrentDictionary only for its keys, I'd say that ConcurrentBag is pretty much exactly what you're looking for (since obviously, the order in which you put stuff into your collection isn't particularly important).

If you desperately need the collection to be a set to avoid duplicates, then I guess for your use case using an actual set and just using locking when accessing it should be fine, too.

[Clockwork-Muse]

@luizfernandonb - Your code is not threadsafe. There are severe defects.

Add

/// <summary>
/// Static method for adding a scheduled event.
/// </summary>
/// <param name="scheduledEvents">Instantiate the scheduled events here.</param>
/// <exception cref="InvalidOperationException"></exception>
/// <exception cref="NullReferenceException"></exception>
public static void AddScheduledEvents(this TarsBase _, params Event[] scheduledEvents)
{
    if (scheduledEvents == null)
        throw new NullReferenceException("The scheduled events list can't be null!");

    if (scheduledEvents.Any(e => e == null))
        throw new NullReferenceException("An event scheduled in the list can't be null!");

    if (_scheduledEvents == null)
        _scheduledEvents = new ConcurrentDictionary<Event, byte>();

    foreach (Event scheduledEvent in scheduledEvents)
    {
        if (!_scheduledEvents.Keys.Contains(scheduledEvent))
            _scheduledEvents.TryAdd(scheduledEvent, 0);
    }
}

Severe problems:

if (_scheduledEvents == null)
    _scheduledEvents = new ConcurrentDictionary<Event, byte>();

_scheduledEvents is going to end up set multiple times (two threads both read the null status at the same time). If you expect this is going to usually be set, you would normally just set it up in a static constructor. Otherwise, you'd need Interlocked.CompareExchange(...). Note, however, that static variables can make testing extremely difficult, especially since many frameworks run tests in parallel.

foreach (Event scheduledEvent in scheduledEvents)
{
    if (!_scheduledEvents.Keys.Contains(scheduledEvent))
        _scheduledEvents.TryAdd(scheduledEvent, 0);
}

Keys captures a _snapshot_ of the keys. It tells you nothing about the ongoing status of the collection (and also makes this an O(n^2) algorithm). Keys may have the listed event, but TryAdd would succeed (return true) because the event has already been processed. Or the opposite might happen. If the intent is to _throttle_ the events then you need the (usually single-threaded) reader to keep a "last processed time" for the event data. Note that you don't deactivate events not added, which is possibly a bug.

Remove has even worse problems:

var scheduledEventFind = _scheduledEvents.Keys.FirstOrDefault(e => e.Name == scheduledEvent.Name);

... O(n^2) algorithm...

if (scheduledEventFind != null)
{
    // ....
}
else
    throw new InvalidOperationException("An event was not found in the list of events scheduled to be removed.");

... most collections don't error if the item is not found. This is especially egregious when dealing with concurrent modifications, where the item may disappear when you least expect it.

@ygra - Maybe. It depends on how time-sensitive "avoid duplicates" is.

[luizfernandonb]

The whole point of List is to be an _ordered_ collection of items, accessible by index. Since you're already using ConcurrentDictionary only for its keys, I'd say that ConcurrentBag is pretty much exactly what you're looking for (since obviously, the order in which you put stuff into your collection isn't particularly important).

If you desperately need the collection to be a set to avoid duplicates, then I guess for your use case using an actual set and just using locking when accessing it should be fine, too.

I understand what you mean, but there is no way for me to remove an element in the ConcurrentBag by specifying it. TryTake does not do this.

@luizfernandonb - Your code is not threadsafe. There are severe defects.

Add

/// <summary>
/// Static method for adding a scheduled event.
/// </summary>
/// <param name="scheduledEvents">Instantiate the scheduled events here.</param>
/// <exception cref="InvalidOperationException"></exception>
/// <exception cref="NullReferenceException"></exception>
public static void AddScheduledEvents(this TarsBase _, params Event[] scheduledEvents)
{
    if (scheduledEvents == null)
        throw new NullReferenceException("The scheduled events list can't be null!");

    if (scheduledEvents.Any(e => e == null))
        throw new NullReferenceException("An event scheduled in the list can't be null!");

    if (_scheduledEvents == null)
        _scheduledEvents = new ConcurrentDictionary<Event, byte>();

    foreach (Event scheduledEvent in scheduledEvents)
    {
        if (!_scheduledEvents.Keys.Contains(scheduledEvent))
            _scheduledEvents.TryAdd(scheduledEvent, 0);
    }
}

Severe problems:

if (_scheduledEvents == null)
    _scheduledEvents = new ConcurrentDictionary<Event, byte>();

_scheduledEvents is going to end up set multiple times (two threads both read the null status at the same time). If you expect this is going to usually be set, you would normally just set it up in a static constructor. Otherwise, you'd need Interlocked.CompareExchange(...). Note, however, that static variables can make testing extremely difficult, especially since many frameworks run tests in parallel.

foreach (Event scheduledEvent in scheduledEvents)
{
    if (!_scheduledEvents.Keys.Contains(scheduledEvent))
        _scheduledEvents.TryAdd(scheduledEvent, 0);
}

Keys captures a _snapshot_ of the keys. It tells you nothing about the ongoing status of the collection (and also makes this an O(n^2) algorithm). Keys may have the listed event, but TryAdd would succeed (return true) because the event has already been processed. Or the opposite might happen. If the intent is to _throttle_ the events then you need the (usually single-threaded) reader to keep a "last processed time" for the event data. Note that you don't deactivate events not added, which is possibly a bug.

Remove has even worse problems:

var scheduledEventFind = _scheduledEvents.Keys.FirstOrDefault(e => e.Name == scheduledEvent.Name);

... O(n^2) algorithm...

if (scheduledEventFind != null)
{
    // ....
}
else
    throw new InvalidOperationException("An event was not found in the list of events scheduled to be removed.");

... most collections don't error if the item is not found. This is especially egregious when dealing with concurrent modifications, where the item may disappear when you least expect it.

@ygra - Maybe. It depends on how time-sensitive "avoid duplicates" is.

Thanks for notifying the possible bugs in the code, I will try to solve them, but what I meant was just about using the ConcurrentDictionary with a value that is useless, which in this case is the byte, so I think I could have a ConcurrentList, I'm not saying that the class will only serve to get the byte out of there, but also for other purposes.

[Clockwork-Muse]

You would have those exact same problems if you had some sort of concurrent list or set; the fundamental problem is the way you're attempting to read and modify the contents.

In this particular case it's not at all clear why you're not using ConcurrentQueue.

[luizfernandonb]

You would have those exact same problems if you had some sort of concurrent list or set; the fundamental problem is the way you're attempting to read and modify the contents.

In this particular case it's not at all clear why you're not using ConcurrentQueue.

Because as far as I know there is no way for me to remove specific elements from a ConcurrentQueue<T> or a ConcurrentBag<T>.

[Clockwork-Muse]

Because as far as I know there is no way for me to remove specific elements from a ConcurrentQueue<T> or a ConcurrentBag<T>.

No, but you're missing the point: you have almost no chance of meaningfully removing them to begin with. Whether or not any sort of Remove operation succeeds in this use case is a data race condition. There isn't any reasonable way to do what you're attempting here, whether there was a ConcurrentList<T>, or a wrapper around a normal List<T> with a lock. You should always assume that Remove _fails_, and that the event will be processed, with what you're asking for.

"I'd like a Remove(specificElement) operation because ConcurrentBag<T> doesn't have one, and I want to remove items" verges on an XY Problem; what's the underlying problem you're trying to solve with this? Why are you (attempting) removing items in the first place? If items aren't removed, what problems might it cause?

---

Note that (because I haven't gone through that entire repository) this is assuming this is some sort of intermediate processing step or buffer (and thus it's likely a ConcurrentQueue<T> would be appropriate). If you instead are doing something like displaying the results to a screen (client application), then normally that's a regular List that you update on a specific single thread. At that point, either you have a queue feeding update commands of some sort, or you're using async/await to do that. Or you might want to look at getting some sort of in-memory database.

[luizfernandonb]

Because as far as I know there is no way for me to remove specific elements from a ConcurrentQueue<T> or a ConcurrentBag<T>.

No, but you're missing the point: you have almost no chance of meaningfully removing them to begin with. Whether or not any sort of Remove operation succeeds in this use case is a data race condition. There isn't any reasonable way to do what you're attempting here, whether there was a ConcurrentList<T>, or a wrapper around a normal List<T> with a lock. You should always assume that Remove _fails_, and that the event will be processed, with what you're asking for.

"I'd like a Remove(specificElement) operation because ConcurrentBag<T> doesn't have one, and I want to remove items" verges on an XY Problem; what's the underlying problem you're trying to solve with this? Why are you (attempting) removing items in the first place? If items aren't removed, what problems might it cause?

Note that (because I haven't gone through that entire repository) this is assuming this is some sort of intermediate processing step or buffer (and thus it's likely a ConcurrentQueue<T> would be appropriate). If you instead are doing something like displaying the results to a screen (client application), then normally that's a regular List that you update on a specific single thread. At that point, either you have a queue feeding update commands of some sort, or you're using async/await to do that. Or you might want to look at getting some sort of in-memory database.

Well, what this extension class does is add and remove scheduled events that run every time, nothing is displayed on the screen or anything like that, at least natively in the library, no.

If items aren't removed, what problems might it cause?

Responding according to the way I thought of the class, if the event is not removed, it will be running in the background and will not stop until the application closes.

[Clockwork-Muse]

... Hrm. I think I've normally seen this done with just a lock around a normal List<T>. Note that at a minimum you have to snapshot the entire collection when you process events, or you get phantoms.

That said, given the way the other remove operations work, a bool ConcurrentBag<T>.Remove(Func<T, bool> predicate, out T element); would fit; I don't know if it would be _implementable_ without locking the entire collection (since either you need to snapshot to guarantee a removal, or you make a best-effort to remove from the inner collections). Note that the item has to be returned to handle the case that the element implements IDisposable.

[eiriktsarpalis]

As others have already mentioned, if the motivation here is to add a type that duplicates the API surface of List in a thread safe way, I don't see how we could meaningfully implement this. Using a lock over List is probably the simplest solution, or depending on the use case, pick one of the existing Concurrent* types.

I'm going to close this issue.