c# - Why is ConcurrentBag<T> so slow in .Net (4.0)? Am I doing it wrong?

Question

Before I started a project, I wrote a simple test to compare the performance of ConcurrentBag from (System.Collections.Concurrent) relative to locking & lists. I am extremely surprised that ConcurrentBag is over 10 times slower than locking with a simple List. From what I understand, the ConcurrentBag works best when the reader and writer is the same thread. However, I hadn't thought it's performance would be so much worse than traditional locks.

I have run a test with two Parallel for loops writing to and reading from a list/bag. However, the write by itself shows a huge difference:

private static void ConcurrentBagTest()
   {
        int collSize = 10000000;
        Stopwatch stopWatch = new Stopwatch();
        ConcurrentBag<int> bag1 = new ConcurrentBag<int>();

        stopWatch.Start();


        Parallel.For(0, collSize, delegate(int i)
        {
            bag1.Add(i);
        });


        stopWatch.Stop();
        Console.WriteLine("Elapsed Time = {0}", 
                          stopWatch.Elapsed.TotalSeconds);
 }

On my box, this takes between 3-4 secs to run, compared to 0.5 - 0.9 secs of this code:

       private static void LockCollTest()
       {
        int collSize = 10000000;
        object list1_lock=new object();
        List<int> lst1 = new List<int>(collSize);

        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();


        Parallel.For(0, collSize, delegate(int i)
            {
                lock(list1_lock)
                {
                    lst1.Add(i);
                }
            });

        stopWatch.Stop();
        Console.WriteLine("Elapsed = {0}", 
                          stopWatch.Elapsed.TotalSeconds);
       }

As I mentioned, doing concurrent reads and writes doesn't help the concurrent bag test. Am I doing something wrong or is this data structure just really slow?

[EDIT] - I removed the Tasks because I don't need them here (Full code had another task reading)

[EDIT] Thanks a lot for the answers. I am having a hard time picking "the right answer" since it seems to be a mix of a few answers.

As Michael Goldshteyn pointed out, the speed really depends on the data. Darin pointed out that there should be more contention for ConcurrentBag to be faster, and Parallel.For doesn't necessarily start the same number of threads. One point to take away is to not do anything you don't have to inside a lock. In the above case, I don't see myself doing anything inside the lock except may be assigning the value to a temp variable.

Additionally, sixlettervariables pointed out that the number of threads that happen to be running may also affect results, although I tried running the original test in reverse order and ConcurrentBag was still slower.

I ran some tests with starting 15 Tasks and the results depended on the collection size among other things. However, ConcurrentBag performed almost as well as or better than locking a list, for up to 1 million insertions. Above 1 million, locking seemed to be much faster sometimes, but I'll probably never have a larger datastructure for my project. Here's the code I ran:

        int collSize = 1000000;
        object list1_lock=new object();
        List<int> lst1 = new List<int>();
        ConcurrentBag<int> concBag = new ConcurrentBag<int>();
        int numTasks = 15;

        int i = 0;

        Stopwatch sWatch = new Stopwatch();
        sWatch.Start();
         //First, try locks
        Task.WaitAll(Enumerable.Range(1, numTasks)
           .Select(x => Task.Factory.StartNew(() =>
            {
                for (i = 0; i < collSize / numTasks; i++)
                {
                    lock (list1_lock)
                    {
                        lst1.Add(x);
                    }
                }
            })).ToArray());

        sWatch.Stop();
        Console.WriteLine("lock test. Elapsed = {0}", 
            sWatch.Elapsed.TotalSeconds);

        // now try concurrentBag
        sWatch.Restart();
        Task.WaitAll(Enumerable.Range(1, numTasks).
                Select(x => Task.Factory.StartNew(() =>
            {
                for (i = 0; i < collSize / numTasks; i++)
                {
                    concBag.Add(x);
                }
            })).ToArray());

        sWatch.Stop();
        Console.WriteLine("Conc Bag test. Elapsed = {0}",
               sWatch.Elapsed.TotalSeconds);

Answer 1

Let me ask you this: how realistic is it that you'd have an application which is constantly adding to a collection and never reading from it? What's the use of such a collection? (This is not a purely rhetorical question. I could imagine there being uses where, e.g., you only read from the collection on shutdown (for logging) or when requested by the user. I believe these scenarios are fairly rare, though.)

This is what your code is simulating. Calling List<T>.Add is going to be lightning-fast in all but the occasional case where the list has to resize its internal array; but this is smoothed out by all the other adds that happen quite quickly. So you're not likely to see a significant amount of contention in this context, especially testing on a personal PC with, e.g., even 8 cores (as you stated you have in a comment somewhere). Maybe you might see more contention on something like a 24-core machine, where many cores can be trying to add to the list literally at the same time.

Contention is much more likely to creep in where you read from your collection, esp. in foreach loops (or LINQ queries which amount to foreach loops under the hood) which require locking the entire operation so that you aren't modifying your collection while iterating over it.

If you can realistically reproduce this scenario, I believe you will see ConcurrentBag<T> scale much better than your current test is showing.

---

Update: Here is a program I wrote to compare these collections in the scenario I described above (multiple writers, many readers). Running 25 trials with a collection size of 10000 and 8 reader threads, I got the following results:

Took 529.0095 ms to add 10000 elements to a List<double> with 8 reader threads.
Took 39.5237 ms to add 10000 elements to a ConcurrentBag<double> with 8 reader threads.
Took 309.4475 ms to add 10000 elements to a List<double> with 8 reader threads.
Took 81.1967 ms to add 10000 elements to a ConcurrentBag<double> with 8 reader threads.
Took 228.7669 ms to add 10000 elements to a List<double> with 8 reader threads.
Took 164.8376 ms to add 10000 elements to a ConcurrentBag<double> with 8 reader threads.
[ ... ]
Average list time: 176.072456 ms.
Average bag time: 59.603656 ms.

So clearly it depends on exactly what you're doing with these collections.