No Concurrentlist<T> in .Net 4.0

No ConcurrentList T in .Net 4.0?

I gave it a try a while back (also: on GitHub). My implementation had some problems, which I won't get into here. Let me tell you, more importantly, what I learned.

Firstly, there's no way you're going to get a full implementation of IList<T> that is lockless and thread-safe. In particular, random insertions and removals are not going to work, unless you also forget about O(1) random access (i.e., unless you "cheat" and just use some sort of linked list and let the indexing suck).

What I thought might be worthwhile was a thread-safe, limited subset of IList<T>: in particular, one that would allow an Add and provide random read-only access by index (but no Insert, RemoveAt, etc., and also no random write access).

This was the goal of my ConcurrentList<T> implementation. But when I tested its performance in multithreaded scenarios, I found that simply synchronizing adds to a List<T> was faster. Basically, adding to a List<T> is lightning fast already; the complexity of the computational steps involved is miniscule (increment an index and assign to an element in an array; that's really it). You would need a ton of concurrent writes to see any sort of lock contention on this; and even then, the average performance of each write would still beat out the more expensive albeit lockless implementation in ConcurrentList<T>.

In the relatively rare event that the list's internal array needs to resize itself, you do pay a small cost. So ultimately I concluded that this was the one niche scenario where an add-only ConcurrentList<T> collection type would make sense: when you want guaranteed low overhead of adding an element on every single call (so, as opposed to an amortized performance goal).

It's simply not nearly as useful a class as you would think.

Why isn't there a ConcurrentList T

Random access doesn't make much sense on a data structure that's changed from another thread.

If you look at the concurrent collections, you'll notice that their interface is specifically designed to work well with multi threaded access. I can't think of a useful list-like interface that works well with multithreaded code.

Random multi threaded access can make sense if the elements are never moved, but then you have an array.

Thread safe collections in .NET

The .NET 4.0 Framework introduces several thread-safe collections in the System.Collections.Concurrent Namespace:

ConcurrentBag<T>
      Represents a thread-safe, unordered collection of objects.

ConcurrentDictionary<TKey, TValue>
    Represents a thread-safe collection of key-value pairs that can be accessed by multiple threads concurrently.

ConcurrentQueue<T>
    Represents a thread-safe first in-first out (FIFO) collection.

ConcurrentStack<T>
    Represents a thread-safe last in-first out (LIFO) collection.

---

Other collections in the .NET Framework are not thread-safe by default and need to be locked for each operation:

lock (mySet)
{
    mySet.Add("Hello World");
}

Workaround for issue in .NET 4.0 where SynchronizationContext.Current is null

I created several extension methods that matched ContinueWith and StartNew except that they also take an additional SyncronizationContext. I then use this argument to restore the expected SynchronizationContext before executing the action:

Below, I've given examples:

public static class TaskExtensionMethods
{
    public static Task ContinueWith_UsingSyncContextWorkaround(this Task task, Action<Task> continuationAction, CancellationToken cancellationToken, TaskContinuationOptions continuationOptions, TaskScheduler scheduler, SynchronizationContext sc)
    {
        Action<Task> actionWithWorkaround = t =>
        {
            SynchronizationContext.SetSynchronizationContext(sc);
            continuationAction(t);
        };

        return task.ContinueWith(actionWithWorkaround, cancellationToken, continuationOptions, scheduler);
    }

    public static Task StartNew_UsingSyncContextWorkaround(this TaskFactory taskFactory, Action action, CancellationToken cancellationToken, TaskCreationOptions creationOptions, TaskScheduler scheduler, SynchronizationContext sc)
    {
        Action actionWithWorkaround = () =>
        {
            SynchronizationContext.SetSynchronizationContext(sc);
            action();
        };

        return taskFactory.StartNew(actionWithWorkaround, cancellationToken, creationOptions, scheduler);
    }
}

I then use these extension methods in place of .ContinueWith or .StartNew

Related Question:

• How to create a generic Task.ContinueWith extension method

.NET 4.0 Threading.Tasks

There are numerous examples here:

http://code.msdn.microsoft.com/ParExtSamples

There's a great white paper which covers a lot of the details you mention above here:

"Patterns for Parallel Programming: Understanding and Applying Parallel Patterns with the .NET Framework 4"

http://www.microsoft.com/downloads/details.aspx?FamilyID=86b3d32b-ad26-4bb8-a3ae-c1637026c3ee&displaylang=en

Off the top of my head I think you can do all the things you list in your question.

• Dependencies etc: Task.WaitAll(Task[] tasks)
• Scheduler: The library supports numerous options for limiting number of threads in use and supports providing your own scheduler. I would avoid altering the priority of threads if at all possible. This is likely to have negative impact on the scheduler, unless you provide your own.

List T concurrent removing and adding

Yes, adding and removing items from a List<> is not thread safe, so you need to synchronise the access, for example using lock.

Mind that the lock keyword in no ways locks the object that you use as identifier, it only prevents two threads to enter the same code block at the same time. You will need locks around all code that accesses the list, using the same object as identifier.

.Net 4.0 C# - Adding to collections without manual loop

A little bit of LINQ will do the trick

wheels.AddRange(vehicles.SelectMany(v => v.Wheels));

Thanks Fourth, I should point out the other case. If there is just one wheel then Select will work:

wheels.AddRange(vehicles.Select(v => v.Wheel));

C# list concurrency

There are two ways to solve this problem:

• Using a lock to synchronize access between two threads, or
• Doing all access from a single thread.

The first way is simple: add lock(users) {...} block around the code that reads or modifies the users list.

The second way is slightly more involved: define two concurrent queues, toAdd and toRemove in your class. Instead of adding or removing users directly from the users list, add them to the toAdd and toRemove queues. When the sleeping thread wakes up, it should first empty both queues, performing the modifications as necessary. Only then it should hand out the currency.

ConcurrentQueue<string> toAdd = new ConcurrentQueue<string>();
ConcurrentQueue<string> toRemove = new ConcurrentQueue<string>();

private void parseIRCMessage(msg){
    if (msgType == "JOIN"){
        toAdd.Enqueue(user);
    }
    else if (msgType == "PART"){
        toRemove.Enqueue(user);
    }
}
private void doWork(){
    while (true) {
        string user;
        while (toAdd.TryDequeue(out user)) {
            users.Add(user);
        }
        while (toRemove.TryDequeue(out user)) {
            users.Remove(user);
        }
        if (streamOnline() && handOutTime()){
            handOutCurrency();
        }
        Thread.Sleep(60000);
    }
}

---

Related Topics