Thread safe, (almost) lock free, fast data structure used for heavy writes, then heavy reads

Question

I'm running some experiments, based on the .NET thread safe, and non-thread safe dictionary's, as well as my custom one.

The results for writing 20,000,000 (20 million) ints to each are as follows:

1. Non-thread safe: 909 milliseconds (less then 1 second) Dictionary
2. Thread safe: 11914 milliseconds (more then 11 seconds) ConcurrentDictionary
3. Custom: 909 milliseconds (less then 1 second) 2 dictionary's
4. Thread safe (ConcurrentTryAdd): 12697 milliseconds (more then 12 seconds) No better then #2

These tests were conducted in a single threaded environment, I'm trying to get the speed of the non-thread safe dictionary, with the safety of the thread safe one.

The results are promising so far, I'm surprised how poorly the ConcurrentDictionary handled, maybe its meant for certain scenarios only?

Anyway, below is the code I used to test the three dictionary's, can you tell me if my custom one is thread safe? Do I have to add a lock to if (_list.ContainsKey(threadId))? I don't think so since its only a read, and when the dictionary has an element added to it (a write) its protected by a lock, blocking other threads trying to read it.

There is no locks once the thread has the dictionary, because another thread cannot write to that same dictionary, since each thread gets their own dictionary (based on the ManagedThreadId), making it as safe as a single thread.

Main

using System;
using System.Diagnostics;

namespace LockFreeTests
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();
            int i = 20000000;  // 20 million

            IWork work = new Custom(); // Replace with: Control(), Concurrent(), or Custom()
            work.Start(i);

            sw.Stop();
            Console.WriteLine("Total time: {0}\r\nPress anykey to continue...", sw.Elapsed.TotalMilliseconds);
            Console.ReadKey(true);
        }
    }
}

Non-thread safe

using System.Collections.Generic;

namespace LockFreeTests
{
    class Control : IWork
    {
        public void Start(int i)
        {
            var list = new Dictionary<int, int>();
            for (int n = 0; n < i; n++)
            {
                list.Add(n, n);
            }
        }
    }
}

Thread safe

using System.Collections.Concurrent;

namespace LockFreeTests
{
    class Concurrent : IWork
    {
        public void Start(int i)
        {
            var list = new ConcurrentDictionary<int, int>();
            for (int n = 0; n < i; n++)
            {
                list.AddOrUpdate(n, n, (a, b) => b);
            }
        }
    }
}

Thread Safe (try add)

using System.Collections.Concurrent;

namespace LockFreeTests
{
    class ConcurrentTryAdd : IWork
    {
        public void Start(int i)
        {
            var list = new ConcurrentDictionary<int, int>();
            for (int n = 0; n < i; n++)
            {
                bool result = list.TryAdd(n, n);
                if (!result)
                {
                    n--;
                }
            }
        }
    }
}

Custom

using System.Collections.Generic;
using System.Threading;

namespace LockFreeTests
{
    class Custom : IWork
    {
        private static Dictionary<int, Dictionary<int, int>> _list = null;

        static Custom()
        {
            _list = new Dictionary<int, Dictionary<int, int>>();
        }

        public void Start(int i)
        {
            int threadId = Thread.CurrentThread.ManagedThreadId;

            Dictionary<int, int> threadList = null;
            bool firstTime = false;

            lock (_list)
            {
                if (_list.ContainsKey(threadId))
                {
                     threadList = _list[threadId];
                }
                else
                {
                    threadList = new Dictionary<int, int>();
                    firstTime = true;
                 }
            }

            for (int n = 0; n < i; n++)
            {
                threadList.Add(n, n);
            }

            if (firstTime)
            {
                lock (_list)
                {
                    _list.Add(threadId, threadList);
                }
            }

        }
    }
}

IWorK

namespace LockFreeTests
{
    public interface IWork
    {
        void Start(int i);
    }
}

Multi-threaded Example

using System;
using System.Diagnostics;
using System.Threading.Tasks;

namespace LockFreeTests
{
    class Program
    {
        static void Main(string[] args)
        {
            var sw = Stopwatch.StartNew();
            int totalWork = 20000000;  // 20 million
            int cores = Environment.ProcessorCount;
            int workPerCore = totalWork / cores;

            IWork work = new Custom(); // Replace with: Control(), Concurrent(), ConcurrentTryAdd(), or Custom()
            var tasks = new Task[cores];

            for (int n = 0; n < cores; n++)
            {
                tasks[n] = Task.Factory.StartNew(() =>
                    {
                        work.Start(workPerCore);
                    });
            }

            Task.WaitAll(tasks);
            sw.Stop();
            Console.WriteLine("Total time: {0}\r\nPress anykey to continue...", sw.Elapsed.TotalMilliseconds);
            Console.ReadKey(true);
        }
    }
}

The above code runs in 528 milliseconds, that's a 40% speed improvement (from the single thread test)

Answer 1

It's not thread-safe.

Do I have to add a lock to if (_list.ContainsKey(threadId))? I don't think so since its only a read, and when the dictionary has an element added to it (a write) its protected by a lock, blocking other threads trying to read it.

Yes, you do need a lock here to make it thread-safe.