Multiple threads slowing down overall dictionary access?

Question

I am profiling a C# application and it looks like two threads each calling Dictionary<>.ContainsKey() 5000 time each on two separate but identical dictionaries (with only two items) is twice as slow as one thread calling Dictionary<>.ContainsKey() on a single dictionary 10000 times.

I am measuring the "thread time" using a tool called JetBrains dotTrace. I am explicitly using copies of the same data, so there are no synhronization primitives that I am using. Is it possible that .NET is doing some synchronization behind the scenes?

I have a dual core machine, and there are three threads running: one is blocked using Semaphore.WaitAll() while the work is done on two new threads whose priority is set to ThreadPriority.Highest.

Obvious culprits like, not actually running the code in parallel, and not using a release build has been ruled out.

EDIT:

People want the code. Alright then:

    private int ReduceArrayIteration(VM vm, HeronValue[] input, int begin, int cnt)
    {
        if (cnt <= 1)
            return cnt;

        int cur = begin;

        for (int i=0; i < cnt - 1; i += 2)
        {
            // The next two calls are effectively dominated by a call 
            // to dictionary ContainsKey
            vm.SetVar(a, input[begin + i]);
            vm.SetVar(b, input[begin + i + 1]);
            input[cur++] = vm.Eval(expr);
        }

        if (cnt % 2 == 1)
        {
            input[cur++] = input[begin + cnt - 1];
        }

        int r = cur - begin;
        Debug.Assert(r >= 1);
        Debug.Assert(r < cnt);
        return r;
    }

    // From VM
    public void SetVar(string s, HeronValue o)
    {
        Debug.Assert(o != null);
        frames.Peek().SetVar(s, o);
    }

    // From Frame
    public bool SetVar(string s, HeronValue o)
    {
        for (int i = scopes.Count; i > 0; --i)
        {
            // Scope is a derived class of Dictionary
            Scope tbl = scopes[i - 1];
            if (tbl.HasName(s))
            {
                tbl[s] = o;
                return false;
            }
        }
        return false;
    }

Now here is the thread spawning code, which might be retarded:

public static class WorkSplitter
{
    static WaitHandle[] signals;

    public static void ThreadStarter(Object o)
    {
        Task task = o as Task;
        task.Run();
    }

    public static void SplitWork(List<Task> tasks)
    {
        signals = new WaitHandle[tasks.Count];
        for (int i = 0; i < tasks.Count; ++i)
            signals[i] = tasks[i].done;
        for (int i = 0; i < tasks.Count; ++i)
        {
            Thread t = new Thread(ThreadStarter);
            t.Priority = ThreadPriority.Highest;
            t.Start(tasks[i]);
        }
        Semaphore.WaitAll(signals);
    }        
}

Answer 1

Even if there was any locking in Dictionary (there isn't), it could not affect your measurements since each thread is using a separate one. Running this test 10,000 times is not enough to get reliable timing data, ContainsKey() only takes 20 nanoseconds or so. You'll need at least several million times to avoid scheduling artifacts.