2006-10-20 18:30:04

C# implementation of Map with multicore support

A month or two ago, Joel Spolsky posted a piece on his blog entitled "Can Your Programming Language Do This?"  In a nutshell, he wrote about how languages with anonymous functions can do things similar to the notions of map and reduce (from functional programming) which (in the absence of side effects) can make it easier to make things "trivially parallelizable".

(This is the point where I stopped writing this blog entry and paused to reflect on the fact that Microsoft Word drew a red squiggly line under the word "blog" but not under the word "parallelizable".)

Lots of people responded to the challenge in the title of Joel's blog entry by writing an implementation of Map and/or Reduce in their favorite language.  Most of these implementations didn't actually contain any functionality for parallel execution on multiple threads or processes.  They simply demonstrated the language-level features necessary to call Map.  In other words, these implementations were primarily examples of how to do anonymous functions as arguments.  I didn't mind, because my primary machine had only one core anyway.

Then a few weeks ago I bought a Sony Vaio SZ with a Core 2 Duo processor, and suddenly I was unhappy.  A non-parallel implementation of Map doesn't help me at all!  If my primary machine has two cores, I want ways to use both of them.

(BTW, I really like my new Vaio laptop.  Highly recommended.)

So I wrote a multicore library in C# using the .NET ThreadPool.  It contains several implementations of Map, customized for specific situations.

(I did not implement Reduce, mostly because I didn't see much use for it.  A parallel Reduce doesn't bring as much benefit as a parallel Map.)

If you'd like to see the code, you can download it here (8KB zip).  The main file is multicore.cs.  It contains the Map code as well as a bunch of comments with additional information and URLs for related sources of information.  A Visual Studio 2005 project file is included, as well as a small suite of NUnit tests.

I'm using this code to speed up some of the solid modeling operations in my woodworking app.  It seems to work pretty well.

Updates:

• 22 October 2006:  Oops!  Somebody pointed out that my code does bad things when the inputs list is empty.  Fixed.
• 26 October 2006:  Somebody pointed out that Map_AnyTrue could possibly end up referencing an object after it was disposed.  Fixed.

Enjoy!