jenkz.org

Following on from my past blog on effective parallelism I’ve continued digging into the functional language F#. I’m getting there – slowly and I am loving immutability. It’s quite a mindset change from my day-to-day work in imperative languages but I can see a little bit of progress in my functional thinking every day.

I’m doing quite a lot of C#->F#->C# interop (writing a distributed Erlang-like message passer, with agents using F#’s MailboxProcessor) and I came across a problem where I needed to convert a Dictionary produced in my C# layer to an immutable F# equivalent: Map.

Digging around online so far regarding F# is proving slow, it’s a new language, and there isn’t the plethora of code-snippets there are for other languages. The F# Manual also is nothing like MSDN – where code-snippets and examples are all over the place.

Anyway, here is a trivial little example of what I have come up with. I have an F# assembly, TestMap.dll, which exposes a module TestMap. A type in this module, ExampleDictionaryToMap, has a method Convert that takes a C# Dictionary and returns an F# immutable

The F# performing the conversion:

#light

module TestMap

open System.Collections.Generic

type ExampleDictionaryToMap =
  // Convert a C# Dictionary<string,int> to a Map<string,int>
  static member Convert(_dict: Dictionary<string, int>) =
     List.fold_left (fun acc idx -> Map.add idx _dict.[idx] acc) Map.empty (Seq.to_list _dict.Keys)

  // Convert a C# Dictionary<string,int> to a Map<string,int>
  // Steps are broken down:-
  //   (1) define an accumulator: function "accumulator"
  //   (2) define an initial value for the accumulator: "initialAccumulatorValue"
  //   (3) create the list to fold using Seq.to_list on the C# Dictionaries Keys emuerator: "list"
  static member StepByStepConvert(_dict: Dictionary<string, int>) =
     let accumulator acc idx = Map.add idx _dict.[idx] acc
     let initialAccumulatorValue = Map.empty
     let list = Seq.to_list _dict.Keys
     List.fold_left accumulator initialAccumulatorValue list

Then calling this F# from C#, Map is the F# type from Fsharp.Core:

Dictionary<string, int> csharpDictionary = new Dictionary<string,int>();
csharpDictionary.Add("value1", 1);
csharpDictionary.Add("value2", 2);
csharpDictionary.Add("value3", 3);
csharpDictionary.Add("value4", 4);

Map<string,int> fsharpMap = TestMap.ExampleDictionaryToMap.Convert(csharpDictionary);

I’m sure there is a more efficient way so any comments welcome!

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.

Well, I’ve been using Visual Studio Express (C#) as my development environment at home for a while now. I am use to standard Visual Studio Standard at work, but use Express at home. I’ve recently got a copy of Vista Home Basic (x64) and Visual C# 2008 Express builds “Any CPU” assemblies which seems to default to the current architecture. You can’t, at least via the interface that I can find, specify what assembly to produce (x86 x86) in Express. In standard you can setup build configurations for Debug/Release/x86/x64/Any CPU combinations. Express, on the other hand, is naff when it comes to this.

Long story short, I have been coding for Managed DirectX which are 32bit assemblies (x86) and my application level code has been compiling to x64 under Express as I have a 64bit machine. Result is a BadImageException at runtime as it load’s the 32bit Managed DirectX assembly from the GAC into a 64bit runtime application. Joy.

My solution has been to edit every one of my .csproj files manually to add the PlatformTarget tag like so:

<WarningLevel>4</WarningLevel>
<PlatformTarget>x86</PlatformTarget>
</PropertyGroup>

I think I’m going to write an XNA renderer as hopefully XNA has 64bit assemblies…

Well Kris and myself finally hit level 50 in Lord of the Rings Online (or “lo”-”tro”, what a stupid name). We’ve been playing it casually since Christmas, and really casually - like maybe a couple of hours a week. It’s quite suited to casual play for leveling, it’s very quest centric and there’s a bonus XP that builds up if you are offline. I think we leveled entirely in bonus XP.

Now we’ve hit 50 though, the kind of realisation hits that you need to finish your character setup - that involves getting equipment, and traits. Traits involve farming NPCs, and the higher traits involve farming stupid numbers of NPCs - like 400+ Yawn, time-sink. The other aspect equipment, is another story. For a decent setup you need a couple of bits of highest-tier crafted, which are expensive as hell (like 5-8g, and 1g takes ~1 hour to farm unless you get lucky drops). The other aspect of equipment is drops from raiding. I dont think it’s remotely like DAoC high end raiding (i.e. Caer Sidi or ML10 dungeon) but still, it’s more raiding.

We’re also going to try out the PvP aspect, which is a little weird. It’s called PvMP (Player vs Monster Player). Which is a battle between the “free people” (the characters you level to 50) and player controlled monster characters. Anyone past a certain level, I think 15, or 20 or so, can make a monster character. These can only be played in the PvMP zone, and I think they rank up, and you equip them from PvMP encounters. I don’t know anything about it really, but I’ll probably post a comparison with DAoC RvR after trying it for a bit. DAoC RvR obviously had much more attachment, actually fighting other people’s main characters, rather than some PvP alt, but we’ll see…

I have two machines at work for network development, and well, I often find myself either not using my second machine, or knocking mice all over the place as I switch between them. A colleague pointed out Synergy - I’m hooked. It’s amazing. It’s just like dual monitor behaviour, mouse + keyboard events get transitioned across screen boundaries. Easy debugging with Visual Studio on two machines with no need to switch mouse/keyboard.

Was a little bit of a faff to setup, but it’s all working and extremely useful. Great for productivity, and it doesn’t feel like a second machine now

I got Kris and myself an iPod Touch over the weekend, after seeing a friends. Wow… They are so cool and I have been totally hooked, including watching the BBC via iPlayer. I’ve also noticed a world of pod casts that I’ve been totally blind to before. Downloaded a load of them, including:

The Drone Bay - Average EVE podcast, quite newbie focused. Maybe it’ll get better..
Game Design - Horrible quality sound. Hurt my head. Couldn’t listen to it due to that, so can’t comment on quality of content.
Game Theory - Podcast entitled “Death, Rebirth” Talk about the possible death of PC game print magazines, due to the emergence of online consoles. also about bringing some old game franchises back to life. Pretty interesting.
Indie Game Development - MIT Grad student talks about a face book game, including design methodologies including paper prototyping.
Guardian Film Weekly - Little bit pretentious, Probably check out a couple more before dismissing it.
NY Times Front Page - Brief to the point, news updates from NY Times
Radio 5live Wake Up to Money - Business/Finance update
Warhamma - What a shite name. Quite well done, catch up on War-hammer Online happenings.
Men of the Rings - LotRO podcast with three jolly American guys. Made the PvMP stuff sound remotely interesting.
Polymorphic Podcast - .NET podcast, about Model-View-Controller in some ASP.NET MVC framework. Seemed pretty decent if the subject gets more interesting/relevant
Pragmatic Podcasts - Very cool introduction to Core Animation in OSX/iPhone. I need OSX and the iPhone SDK!

It’s made me really want to get OSX installed, and check out the iPhone SDK… Can’t wait for the App Store.

Alex Tomkins (a.k.a GReaper) is kindly lending his server resources to host my website, DNS, and SVN server. I’ve done away with my old web host, they put up their prices, are basically naff. Alex is so much better He also hosts www.legionsplayers.com so he is clearly just amazing. Thanks Alex!

In the process of moving, I’ve also done away with my old phpBB driven website backend, replaced with a “Web 2.0″ extravaganza. This site is now powered by Wordpress 2.5….. It has meant I’ve lost most of my stuff, including my portfolio, but I’m not too bothered. I’ve transitioned what I wanted to keep including my articles, files, images etc.

I actually really like Wordpress. The admin features are very cool. It was damn easy to setup. I just need a better header. *whips out gimp and pretends to be an artist*. Hopefully I’ll actually update the blog a bit more now too… Now that it’s easier to manage and all

Oh, theres steak cooking, from West End Butchers. It smells bloody great.