ConcurrentBag<T> and lock(List<T>) which is faster to add or remove?

Question

I need to perform some thread safe operations on List<T>. Usually I just simply use:

lock(List<T>)
{
   List<T>.Add();
   List<T>.Remove();
}

I know there is another way, using ConcurrentBag<T>. But I don't know which is faster, or any other differences.

Edit:

Some people just recommend I use ConcurrentBag, because that's safer. But I worry it will make my operation slower.

I have a lot of threads needing to add or remove objects from a List<T>, I want to know which way is better for performance.

Answer 1

You can easily measure the performance of different approaches just by trying them out! That is what I just got:

lock list: 2.162s
ConcurrentBag: 7.264s

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading.Tasks;

public class Test
{
    public const int NumOfTasks = 4;
    public const int Cycles = 1000 * 1000 * 4;

    public static void Main()
    {
        var list = new List<int>();
        var bag = new ConcurrentBag<int>();

        Profile("lock list", () => { lock (list) list.Add(1); });
        Profile("ConcurrentBag", () => bag.Add(1));
    }

    public static void Profile(string label, Action work)
    {
        var s = new Stopwatch();
        s.Start();

        List<Task> tasks = new List<Task>();

        for (int i = 0; i < NumOfTasks; ++i)
        {
            tasks.Add(Task.Factory.StartNew(() =>
            {
                for (int j = 0; j < Cycles; ++j)
                {
                    work();
                }
            }));
        }

        Task.WaitAll(tasks.ToArray());

        Console.WriteLine(string.Format("{0}: {1:F3}s", label, s.Elapsed.TotalSeconds));
    }
}

Answer 2

Don't use ConcurrentBag<T> to replace a locked List<T> unless you're certain of your thread's access patterns because it uses thread local storage under the covers.

MSDN talks about the preferred usage:

"ConcurrentBag<T> is a thread-safe bag implementation, optimized for scenarios where the same thread will be both producing and consuming data stored in the bag."

It's also important to note that List<T> is ordered and ConcurrentBag<T> is unordered. If you don't care about order in your collection I would use a ConcurrentQueue<T>.

Regarding performance, below is some code from ConcurrentBag<T>. But the primary thing to consider is if you do a Take and your thread local storage is empty it will steal from other threads which is expensive.

When it needs to steal, note that it is locking. Also note it can lock several times on one Take since TrySteal can fail and get called more than once from Steal (not shown).

private bool TrySteal(ConcurrentBag<T>.ThreadLocalList list, out T result, bool take)
{
    lock (list)
    {
        if (this.CanSteal(list))
        {
            list.Steal(out result, take);
            return true;
        }
        result = default (T);
        return false;
    }
}

There is also possible spin waiting during CanSteal.

private bool CanSteal(ConcurrentBag<T>.ThreadLocalList list)
{
    if (list.Count <= 2 && list.m_currentOp != 0)
    {
        SpinWait spinWait = new SpinWait();
        while (list.m_currentOp != 0)
            spinWait.SpinOnce();
    }
    return list.Count > 0;
} 

And finally, even adding can cause a lock to be taken.

private void AddInternal(ConcurrentBag<T>.ThreadLocalList list, T item)
{
    bool lockTaken = false;
    try
    {
        Interlocked.Exchange(ref list.m_currentOp, 1);
        if (list.Count < 2 || this.m_needSync)
        {
            list.m_currentOp = 0;
            Monitor.Enter((object) list, ref lockTaken);
        }
        list.Add(item, lockTaken);
    }
    finally
    {
        list.m_currentOp = 0;
        if (lockTaken)
            Monitor.Exit((object) list);
    }
}

Answer 3

List operations add and remove are O(n), meaning that the duration of your lock will depend on how big the list is. The larger your list, the less concurrency you have. However, if you are always adding to the end and removing from the end, you effectively have a stack. In that case the add and remove operations are O(1) and you will have shorter locks.

ConcurrentBag is implemented as a linked list of linked lists (one per thread. Operations add and take are O(1) and do not require a lock in the general case. The fact that locks can usually be avoided means it is likely to be faster.