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.

Solution 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));
    }
}

Solution 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);
    }
}

Solution 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.

Comments

[Zer0]

Care to explain the downvote? ConcurrentBag<T> is not a suitable replacement for locking a list.

[Gabe]

Why is the use of TLS a concern?

[Scott Chamberlain]

@Gabe Please read msdn.microsoft.com/en-us/library/dd997305(v=vs.110).aspx for more information about why TLS is a concern. The main point is if the same thread that is pulling out of the bag is not the same thread that is inserting in to the bag there is a large overhead cost.

[odyss-jii]

The more general advice would probably be: don't attempt multi-threaded code unless you know what you are doing. Someone who does not fully understand what is going on behind the scenes is unlikely to stumble across a solution which improves performance.

[Dave Zych]

Isn't List.Add O(1)?

[Gabe]

I see how the ConcurrentBag is optimized for same-thread scenarios, but I don't see anything indicating that non-same-thread use would be slow or why use of TLS would be an issue.

[Zer0]

@Gabe Do a benchmark. You will see a serious performance hit. It's expensive when taking items needs to steal from other thread local storage.

[Gabe]

@DaveZych: Yes, but only amortized out over every add. Any given add may take one operation or may take N operations. If you call add 1,048,576 times in a row, the last call will have to do 1,048,576 operations.

[Servy]

@DaveZych And again, that's only adding to the end. Adding anywhere else involves moving every item after it in the list, making it O(n) even when it doesn't need to allocate a new backing array.

[Gabe]

Since no thread has access to another thread's TLS, how does the use of TLS cause a performance hit?

[Dave Zych]

@Servy right, but that would be Insert, I was specifically referencing Add.

[GodLovesATrier]

+1 for actually doing the science, it's interesting to try this example in 2021 on dotnet core 5.0 and get the following completely different results: lock list: 1.681s ConcurrentBag: 0.199s! It seems the dotnet team have been busy optimising the ConcurrentBag