Why is concurrent modification of arrays so slow?

Question

I was writing a program to illustrate the effects of cache contention in multithreaded programs. My first cut was to create an array of long and show how modifying adjacent items causes contention. Here's the program.

const long maxCount = 500000000; const int numThreads = 4; const int Multiplier = 1; static void DoIt() {     long[] c = new long[Multiplier * numThreads];     var threads = new Thread[numThreads];      // Create the threads     for (int i = 0; i < numThreads; ++i)     {         threads[i] = new Thread((s) =>             {                 int x = (int)s;                 while (c[x] > 0)                 {                     --c[x];                 }             });     }      // start threads     var sw = Stopwatch.StartNew();     for (int i = 0; i < numThreads; ++i)     {         int z = Multiplier * i;         c[z] = maxCount;         threads[i].Start(z);     }     // Wait for 500 ms and then access the counters.     // This just proves that the threads are actually updating the counters.     Thread.Sleep(500);     for (int i = 0; i < numThreads; ++i)     {         Console.WriteLine(c[Multiplier * i]);     }      // Wait for threads to stop     for (int i = 0; i < numThreads; ++i)     {         threads[i].Join();     }     sw.Stop();     Console.WriteLine();     Console.WriteLine("Elapsed time = {0:N0} ms", sw.ElapsedMilliseconds); } 

I'm running Visual Studio 2010, program compiled in Release mode, .NET 4.0 target, "Any CPU", and executed in the 64-bit runtime without the debugger attached (Ctrl+F5).

That program runs in about 1,700 ms on my system, with a single thread. With two threads, it takes over 25 seconds. Figuring that the difference was cache contention, I set Multipler = 8 and ran again. The result is 12 seconds, so contention was at least part of the problem.

Increasing Multiplier beyond 8 doesn't improve performance.

For comparison, a similar program that doesn't use an array takes only about 2,200 ms with two threads when the variables are adjacent. When I separate the variables, the two thread version runs in the same amount of time as the single-threaded version.

If the problem was array indexing overhead, you'd expect it to show up in the single-threaded version. It looks to me like there's some kind of mutual exclusion going on when modifying the array, but I don't know what it is.

Looking at the generated IL isn't very enlightening. Nor was viewing the disassembly. The disassembly does show a couple of calls to (I think) the runtime library, but I wasn't able to step into them.

I'm not proficient with windbg or other low-level debugging tools these days. It's been a really long time since I needed them. So I'm stumped.

My only hypothesis right now is that the runtime code is setting a "dirty" flag on every write. It seems like something like that would be required in order to support throwing an exception if the array is modified while it's being enumerated. But I readily admit that I have no direct evidence to back up that hypothesis.

Can anybody tell me what is causing this big slowdown?

Answer 1

You've got false sharing. I wrote an article about it here