jenkz.org

Everyone is now aware that multiple cores is the direction that chip manufacturers are heading, but many of us are stuck without a way of writing reliable software that is capable of running on, say, 64 cores. Concurrency in C/C++/C#/Javaet.al. is not easy. We are getting better, but, it’s still not easy, and is error prone. Theres a lack of design expertise, a lack of development tools/debugging tools/predicting concurrency errors, and a severe lack of high-level concurrency support at the language level.

I stumbled across the Parallel Extensions Customer Technology Preview (June `08) the other day whilst researching effective concurrency in high performance server software. It’s set me off on a little bit of a functional crusade. Firstly, back to the Parallel Extensions CTP. It’s a pre-release .NET extension that provides Parallel LINQ , the Task Parallel Library, and some concurrency primitives, lazy initialisation, and thread-safe lock-free collections (the somewhat obvious stack and queue). The two aspects I have found most useful “out of the box” are:

The user-mode concurrency primitives, i.e. SemaphoreSlim, ManualResetEventSlim, rather than diving down to the kernel for synchronization primitives, they are implemented entirely in the CLR
The concurrency collections, notably concurrent queue, and blocking collection, which provided a simple and easy to use multiple producer consumer queue

Theres lots of other cool stuff in the Parallel Extensions CTP, especially PLINQ, which when using LINQ like a functional language provides what looks like a straight forward way to exploit parallelism in C#

Digging around I stumbled across a statement that functional languages are ideal for solving parallelism problems, as they have no side effects. Holy grail time. I also stumbled across Rob Pickerings blog which is a great resource for the .NET functional language F#. F# is currently being productized by Microsoft to sit nicely in the Visual Studio suite of tools, so I am expecting it to be pretty mainstream quite soon, and having tinkered with C#/F#/C#interop for about an hour I can see why. It is so simple to use, and coupled with some of the “no side effects” stuff I will touch on shortly, I can see why.

To understand “functional languages are ideal for solving parallelism problems”, it was clear I needed to grasp immutability in the context of functional languages. Every software engineer is aware of immutability,readonly data, strings in C# are immutable, and Effective C# encourages writing immutable classes. However, writing a whole system using immutable types seems a very alien concept - and that’s ignoring what appears to be major performance headache (especially in my area, Games). Here’s a very simple immutable class in C#, it’sreadonly int member can only be assigned during construction, so if you want a client’s Id to change, you have to instantiate another instance of client. There is lots of discussion on immutability and immutable C# types in this post

public class Client
{
  private readonly int m_id;
  public int Id
  {
     get { return m_id; }
  }

  public Client(int _id)
  {
    m_id = _id;
  }
}

Instantiating a new object every time is hitting garbage collection, definitely, but releases will be picked up by the fast first generation. This is the first performance concern I have with moving over to the functional world.

That’s immutability in 5seconds: state cannot change. Functional languages take this a step further, statements like x = x + 1, which is entirely valid in an imperative language, is alien to a functional language. You can have a function that returns a value plus one, but the value returned is a new value, not the previous value mutated. Functional languages provide immutable structures that are ideal for this, in F# there’sTuples and Records.

There’s a couple of videos - a discussion with Joe Armstrong (a godfather of Erlang, a distributed, concurrent, functional language) and another discussion with Simon Peyton Jones (a godfather of Haskell) that explain why functional languages aid concurrency that explain side effects, immutability in the context of functional programming languages. Both videos do a better job than I can at explaining this, and are well worth watching.

Ok, I thought, that’s it. Clearly to solve all my concurrency problems I need to use a functional language. I couldn’t get my little head around the lack of “state”. Clearly there is state, that these functions need to operate on. As mentioned in the Simon Peyton Jones video, I don’t just want to make my cores get warm, I want to observe the results… I’ve struggled for this for days now, the evangelist of “side effects = bad, NEVER!!”. Clearly I had misunderstood as I gathered on Sunday after watching the Joe Armstrong video again.

Given a “world state”, there are operations that want to read this, and there are operations that want to change this. Reading this is not a problem - they just get the latest view, and as that view is immutable (in a functional language) it’s safe to pass around, and do what you please with it - multiple cores can read this concurrently without any issue whatsoever. It’s the writing of a new “version” that I was struggling with. Given two operations that want to execute concurrently and both want to return a new state - there is an inherent race! I can’t grasp how to solve that race in this “no side effects please” world of functional languages, and to be honest, it’s been making my head hurt. I stumbled across Joe Duffy’s (a Microsoft Developer on Parallel Libraries) blog yesterday that put me at ease.

Joe presents a simple compare-exchange method for writes, where by there could be lost work by a “writing thread”. Nabbed directly from Joe’s blog. Joe also covered some issues with this approach, which are discussed in more detail in his post.

internal static World s_theWorld = new World(…);
internal void ReadTheWorld()
{
  World w = s_theWorld;
}
internal void ChangeTheWorld()
{
  World oldWorld;
  World newWorld;
  do
  {
    oldWorld = s_theWorld;
    newWorld = new World(…);
  }
  while (Interlocked.CompareExchange(ref s_theWorld,
         newWorld, oldWorld) != oldWorld);
}

I now feel I can get started using F# (via my existing C# code) creating immutable, functional assemblies that C# can quite happily make use of. I’m really looking forward to trying this out and I’ll hopefully post an update as to how it goes.

Finally, I’m really really intrigued by Erlang, which I hinted at earlier. It’s a functional language developed by Ericsson quite some time ago with a primary design goal of redundancy and fail-over. Erlang provides “processes” where each component/object/whatever you want to call it is an extremely lightweight process in the Erlang runtime. These processes only communicate by explicit message passing. The two part discussion with Joe Armstrong above is a good starting point, but I’ve bought a copy of his book to have a nosey around too, it was only £15 from Amazon. I’m not planning on usingErlang, but learning from it - and possibly adapting some of it’s good points to my distributed server code.

Tags: C#, Erlang, F#, Functional Languages, Parallelism

This entry was posted on Tuesday, July 1st, 2008 at 7:41 am and is filed under Code. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.