List<..> with lock(..) { } is much faster then ConcurrentBag !!!

Question

Hi,

I don't get it. I just played around with the new concurrend collections in Visual Studio 2010 BETA and found out, that for my sample an simple generic List<...> is much faster then a ConcurrentBag or a BlockingCollection.

At the end of this posting, I will insert some snippets of my sample, which creates passwords for a brute force attack. To compare the several Collections, I use a custom IResultSet. There are IResultSet implementations for List (using locking), LinkedList (using locking too), ConcurrentBag, BlockingCollection and ConcurrentLinkedList. The ResultSet using List<...> is the fastest one ...

How do you think about this? Why is the implementation using List<..> faster then the implementation using ConcurrentBag ??

Regards,
Manfred

 [...]

        public void BruteForce(String s, int count, IResultSet r)







        {







            if (s.Length == count)







            {







                r.Add(s);







                return;







            }















            for (char c = 'a'; c <= 'z'; c++)







            {







                BruteForce(s + c, count, r);







            }







        }















        public void BruteForceP3(String s, int count, IResultSet r)







        {







            if (s.Length == count)







            {







                r.Add(s);







                return;







            }















            //for (char c = 'a'; c <= 'z'; c++)







            Parallel.For('a', 'z' + 1, c =>







            {







                if (s.Length >= 2)







                {







                    BruteForce(s + (char)c, count, r);







                }







                else







                {







                    BruteForceP3(s + (char)c, count, r);







                }







            });







        }

[...]

    interface IResultSet







    {







        void Add(string result);







        string[] ToArray();







    }

[...]

 

    class LinkedListResultSet: IResultSet







    {







        private LinkedList<string> ll = new LinkedList<string>();















        public void Add(string result)







        {







            lock (ll)







            {







                ll.AddLast(result);







            }







        }















        public string[] ToArray()







        {







            lock (ll)







            {







                return ll.ToArray<string>();







            }







        }







    }

[...]

    class ConcurrentBagResultSet: IResultSet







    {







        private ConcurrentBag<string> cb = new ConcurrentBag<string>();























        public void Add(string result)







        {







            cb.Add(result);







        }















        public string[] ToArray()







        {







            return cb.ToArray();







        }







    }

and so on ...

 

 

 

 

        static void TestBruteForce()

        {

            TPLSamples samples = new TPLSamples();

            List<Pizza> warenkorb = Pizza.GenerateSurpriseMenu(1000);





            IResultSet lrs = new ListResultSet();

            IResultSet bcrs = new BlockingCollectionResultSet();

            IResultSet cbrs = new ConcurrentBagResultSet();

            IResultSet llrs = new LinkedListResultSet();

            IResultSet cllrs = new ConcurrentLinkedListResultSet();



            Time(() => { samples.BruteForceP3("", 6, lrs); });

            Time(() => { samples.BruteForceP3("", 6, bcrs); });

            Time(() => { samples.BruteForceP3("", 6, cbrs); });

            Time(() => { samples.BruteForceP3("", 3, llrs); });

            Time(() => { samples.BruteForceP3("", 3, cllrs); });

        }





        static void Time(Action a)

        {

            Console.WriteLine("Start {0}", a.Method.Name);

            

            Stopwatch sw = new Stopwatch();

            sw.Start();



            a();



            sw.Stop();

            Console.WriteLine("Stop {0}, Time: {1} msec", a.Method.Name, sw.ElapsedMilliseconds);



            Console.WriteLine("<Enter>"); 

            Console.ReadLine();

            Console.WriteLine();



        }

Answer 1

Hi Manfred,

Thanks for the post.  I'm having trouble reading your example and it looks like major pieces might be missing but here is my first reaction:

How are threads interacting with the ConcurrentBag<T>?  Is it a producer consumer relationship where the thread that removes the item is usually a different thread than the one that added the item?

Thanks,

Josh

Answer 2

Hi Josh,

there are several tasks, which populate this bag with results they find. After all tasks have finsished, I read the results from the bag.

Below I retry to submit this sample. Now, everything is in one single class and the static BruteForce.TestBruteForce() is the entry point.

Regards,
Manfred

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

namespace ParallelSamples.TPL.test
{
    public interface IResultSet
    {
        void Add(string result);
        string[] ToArray();
    }

    class ConcurrentBagResultSet : IResultSet
    {
        private ConcurrentBag<string> cb = new ConcurrentBag<string>();


        public void Add(string result)
        {
            cb.Add(result);
        }

        public string[] ToArray()
        {
            return cb.ToArray();
        }
    }



    class BlockingCollectionResultSet : IResultSet
    {
        private BlockingCollection<string> bc = new BlockingCollection<string>();

        public void Add(string result)
        {
            bc.Add(result);
        }

        public string[] ToArray()
        {
            return bc.ToArray();
        }
    }

    class ListResultSet : IResultSet
    {
        List<string> results = new List<string>();

        public void Add(string result)
        {
            lock (results)
            {
                results.Add(result);
            }
        }

        public string[] ToArray()
        {
            lock (results)
            {
                return results.ToArray<string>();
            }

        }
    }

    public class BurteForce
    {

        public void BruteForce(String s, int count, IResultSet r)
        {
            if (s.Length == count)
            {
                r.Add(s);
                return;
            }

            for (char c = 'a'; c <= 'z'; c++)
            {
                BruteForce(s + c, count, r);
            }
        }

        public void BruteForceP3(String s, int count, IResultSet r)
        {
            if (s.Length == count)
            {
                r.Add(s);
                return;
            }

            //for (char c = 'a'; c <= 'z'; c++)
            Parallel.For('a', 'z' + 1, c =>
            {
                if (s.Length >= 2)
                {
                    BruteForce(s + (char)c, count, r);
                }
                else
                {
                    BruteForceP3(s + (char)c, count, r);
                }
            });
        }

        private static void Time(Action a)
        {
            Console.WriteLine("Start {0}", a.Method.Name);
            
            Stopwatch sw = new Stopwatch();
            sw.Start();

            a();

            sw.Stop();
            Console.WriteLine("Stop {0}, Time: {1} msec", a.Method.Name, sw.ElapsedMilliseconds);

            Console.WriteLine("<Enter>"); 
            Console.ReadLine();
            Console.WriteLine();

        }

            public static void TestBruteForce()
        {
            BurteForce samples = new BurteForce();

            IResultSet lrs = new ListResultSet();
            IResultSet bcrs = new BlockingCollectionResultSet();
            IResultSet cbrs = new ConcurrentBagResultSet();

            Time(() => { samples.BruteForceP3("", 5, lrs); });
            Time(() => { samples.BruteForceP3("", 5, bcrs); });
            Time(() => { samples.BruteForceP3("", 5, cbrs); });
        }

}
}

Answer 3

Manfred,

Thanks for the code.  After profiling your example I was able to tell what was going on.  Internally, List<T> uses a growable array to store elements. ConcurrentBag<T> and many other collections in the BCL, however, do not.  ConcurrentBag<T> actually uses a dictionary of linked lists.  Therefore, every time an item is added to ConcurrentBag<T> a node object has to be allocated and inserted into a thread local list.  When 18 million items are being added to ConcurrentBag<T> the time spent allocating objects in the heap really adds up.  Try the comparison with LinkedList<T>, which also stores items inside of a Node objects -- ConcurrentBag<T> fares better. 

That said, it's fair to compare List<T> and ConcurrentBag<T>, you want to use whatever performs better.  I'm fairly certain that ConcurrentBag<T> will trump even List<T> if their is sufficiently high contention.  Like 4 cores constantly adding items and/or holding the lock for longer than just an add operation.  In that case, the cost of object allocations will be amortized by reducing contention.

Also, try it with the server GC on.  It helps!

Josh

Answer 4

Hi Josh, thx. That means, that a List using lock(..) {} can be faster then a ConcurrentBag. It just depends on the situation. Is that right? Can you provide me with a (tiny) example-implementation, which uses a ConcurrentBag and is faster than as if it would use a List with lock(..) ? As I read in [1] there is no common super-class/ interface for concurrent collections and "non-concurrent" collections, like List. Are there plans to extend this that way, so that one doesn't have to write adapter-classes to compare the performance of them for a specific use-case, as I did? Regards, Manfred [1] http://msdn.microsoft.com/en-us/library/dd381779(VS.100).aspx

Answer 5

Manfred,

Unfortunately, even if I provide an example that is faster on my machine, it doesn't gaurantee that it will be faster on your machine. There are two things you can fiddle with, however.  First off, try doing more under the lock.  Say you actually needed to update three data structures and one of the updates was non-trivial like adding to a dictionary instead of to a list.  Second, increase the parallelism which, of course, might require a hardware upgrade or borrowing someone's machine. ;)

RE: Interfaces

While it's true that there is no common interface for all concurrent and non-concurrent collections, there is some overlap.  A lot of them share ICollection (which probably isn't too useful).  Also, take a look at IProducerConsumerCollection<T>, which ConcurrentQueue<T>, ConcurrentStack<T>, and ConcurrentBag<T> all implement.  The reason there isn't a universal interface to rule all the collections is that many collections have some restrictions to achieve certain goals, like performance.  For example, ConcurrentBag<T> doesn't implement ICollection<T> like List<T> does because it would need to implement Remove(T) which would significantly harm the performance and scalability of the type.  

If you're worried about readability, you can use extension methods to make your code look a little cleaner.  Check out the BlockingCollection<T>.ToProducerConsumer() example in the parallel extensions sample on code gallery.  

Thanks again for the great questions!

Josh