Description

I had a bet with a co-worker that C# would outperform F# for a simple counting exercise. This turned out to be quite a surprise for many reasons. In this blog post I will try to explain why.

Problem

Sum the numbers from 1 to n using brute force (can't use the (1 + N)*(N/2) equation). Do this in both C# and F# and compare the speed. Since F# needs to do this recursively I thought this should be a no contest win for C#.

Using F#

We initially wrote the code without using tail recursion which immediately ended with a stack overflow. So we went back and wrote it doing it the functional way, with tail recursion. Here is what we came up with.

module FSharpLib

	let sumNum fromNum toNum =
		let rec sumNumTail fromNum toNum result =
			if fromNum > toNum then 
				result 
			else 
				sumNumTail (fromNum+1L) toNum (result+fromNum)
		sumNumTail fromNum toNum 0L

Using C# - Attempt 1

You'll see later why I say attempt 1. But, this is the simplest C# code I could think of.

public static long CSharpForLoop(long fromNumber, long toNumber) {
	long result = 0;
	for (long i = fromNumber; i <= toNumber; i++) {
		result += i;
	}
	return result;
}

The Results - Attempt 1

This is the results of running the above code using a fromNumber of 1 and a toNumber of 10000000 and running it 10 times alternating between C# and F# to filter out start-up times, etc.

Reflector is an amazing tool

I turned to my good friend Reflector to see what was going on. Here is what the F# code looked like when viewing it as C# code.

public static long sumNum(long fromNum, long toNum)
{
    FastFunc<long, FastFunc<long, FastFunc<long, long>>> sumNumTail = new clo@7();
    return FastFunc<long, long>.InvokeFast3<long, long>(sumNumTail, fromNum, toNum, 0L);
}

public override long Invoke(long fromNum, long toNum, long result)
{
	while (fromNum <= toNum)
	{
		result += fromNum;
		toNum = toNum;
		fromNum += 1L;
	}
	return result;
}

C# - Attempt 2

public static long CSharpWhileLoop(long fromNumber, long toNumber) {
	long result = 0;
	while (fromNumber <= toNumber)
	{
		result += fromNumber;
		// I left out the toNum = toNum because it didn't do anything.
		fromNumber += 1L;
	}
	return result;
}

To the IL code Batman

This is the IL for the F# code.

	L_0000: nop              // while loop
	L_0001: nop 
	L_0002: ldarg.1          // fromNum <= toNum
	L_0003: ldarg.2 
	L_0004: ble.s L_0009     
	L_0006: nop              // return result
	L_0007: ldarg.3 
	L_0008: ret              
	L_0009: nop              // result += fromNum
	L_000a: ldarg.1 
	L_000b: ldc.i8 1
	L_0014: add              
	L_0015: ldarg.2          // fromNum += 1L
	L_0016: ldarg.3 
	L_0017: ldarg.1 
	L_0018: add              
	L_0019: starg.s result   // loop
	L_001b: starg.s toNum
	L_001d: starg.s fromNum
	L_001f: br.s L_0000      
	

	L_0000: nop                   // long result = 0L
	L_0001: ldc.i4.0
	L_0002: conv.i8 
	L_0003: stloc.0               
	L_0004: br.s L_0012           // while loop
	L_0006: nop                   // result += fromNumber
	L_0007: ldloc.0 
	L_0008: ldarg.0 
	L_0009: add                   
	L_000a: stloc.0               // fromNumber += 1L
	L_000b: ldarg.0 
	L_000c: ldc.i4.1 
	L_000d: conv.i8 
	L_000e: add                   
	L_000f: starg.s fromNumber    
	L_0011: nop 
	L_0012: ldarg.0               // fromNumber <= toNumber
	L_0013: ldarg.1 
	L_0014: cgt 
	L_0016: ldc.i4.0 
	L_0017: ceq 
	L_0019: stloc.2 
	L_001a: ldloc.2 
	L_001b: brtrue.s L_0006       // loop
	L_001d: ldloc.0 
	L_001e: stloc.1 
	L_001f: br.s L_0021
	L_0021: ldloc.1 
	L_0022: ret 
	

What just happened.

Wow, the C# compiler is quite a bit more verbose. First of all, C# makes the while loop into a do/while loop. Secondly, in the loop condition C# creates a temporary variable to store the comparison and then checks for 'true' ("brtrue.s"). If you look at the F# IL you'll see the use of the "ble.s" instructions (branch if less or equal) instead. Finally we see that C# uses a few "conv.i8" instructions (convert to 8 byte/64-bit int) which I can only guess adds to it's defeat.

Conclusion

So is F# just a more performant language or is C# just compiling to more robust IL code which as F# matures will end up suffering the same fate? I personally think (hope actually) the later is true. I'm not an expert in compilers but I would have to assume the C# compiler team is using every trick in the book to make highly performant IL code without sacrificing robustness and I can only assume that F# will get to a point where it needs to make the same concessions to handle some obscure cases.

I wrote my first firmware for the DEFCON badge. Doesn't do much other than replace the default Knight Rider LED sequence with my own, but it's a first step. I did want to note a couple of things that were not mentioned in the badge hacking information that might make it easier to get started.

There are two drivers for windows, one when the badge is in USB bootloader mode and one while the badge is in normal mode. To get to bootloader mode you need to hold down the mode select button while inserting the battery. The driver provided on the CD is for normal mode which took me a while to figure out. To get to the normal mode you need to plug the USB cord in BEFORE you insert the battery. Looking at the firmware I noticed the check for a USB connection is done as one of the very first things. Windows will then recognize the device and you can install the driver from the CD. The driver for bootloader mode is actually part of the Freescale JM60 bootloader program which can also be found on the CD but must be installed before you try bootloader mode.

Also, I couldn't get the full version of Code Warrior so the next best thing was the demo from Freescale. But, the demo has a 32k firmware limit which means removing some of the original firmware code. I removed fat.c from the project and recompiled and fixed until I got it working. This will of course remove your ability to read or write to the SD card using FAT.

Next step is to make the final hack which will hopefully be done by tomorrow so we can show it off to Kingpin. I'll post the final hack information and code tomorrow if it gets done.

Code You Write To Make It Work

   1:  IEnumerable<int> numbers = Enumerable.Range(0, 500);
   2:  RemoteContext remoteContext = new RemoteContext(
   3:     new[] { this.GetType().Assembly }, 
   4:     new[] { "localhost", "someremotehost" },
   5:     7776);
   6:  RemoteOptions remoteOptions = new RemoteOptions();
   7:  IEnumerable<int> results = numbers.AsRemotable(remoteContext, remoteOptions).Select(i => DoSomeWork(i));

Let's walk through the code.

• Line 1, gives us an enumerable of numbers from 0 to 500 for processing.
• Line 2, creates the RemoteContext. This is really just a client which has a list of server connections to which we can send work.
• Line 3, is a list of assemblies that contain the necessary code to run your LINQ statement. The client will actually send a copy of the dll to the RemoteLINQ server so that the server will have a copy of the "DoSomeWork" (line 7) method so that it can execute it.
• Line 4, is the list of servers to divvy the work across.
• Line 5, is just the port that the client will try to connect to the server on.
• Line 6, contains any options to direct how the work gets split across the servers, etc.
• Line 7, is your LINQ statement. Notice the "AsRemotable". This is where all the magic starts. This will actually return a IRemoteEnumerable which knows how to take anything to the right of it and run it remotely.

How it works

Lets start out with what lambda expression look like in compiled code. When we compile lambda expressions they are moved into a new method with a compiler generated name. If you reflect on a class with lambdas and get all the methods on that type you will see a bunch of method names which you didn't create. Those are your lambdas. The fact that they are first class methods allows us from the outside, with reflection of course, to call those methods. So when we call "Select" on an IRemoteEnumerable, RemoteLINQ is taking the lambda expression passed in, and storing information about it into a serializable object (assembly, declaring type, method name, etc.). This will allow us to send that information to the server, who can then call the method without all the other stuff around it.

On the server side of things, when we start up a RemoteLINQ server, it will create a worker thread for each processor in the machine. The worker thread will wait quietly until new work arrives on the socket connection. When work arrives we take the serialized object I mentioned before and find the assembly, type, and method and execute that method with the work given to us. In this case the work will be one of the numbers from 0 to 500. The client will handle load balancing the servers by choosing the server with the least amount of pending work per processor. The amount of work queued up on the server is sent back after each unit of work is completed so that the client will have the most up to date picture of what the servers are doing to make the best guess as to where to send the next piece of work.

That's about it. You now have a way to split complex LINQ tasks across multiple machine with just a single call on your LINQ statement.

Download The Code

The Test Data

<root>
  <child id='123'/>
  <child id='234'/>
  ...
</root>

The Test

XmlDocument.Load

private static void XmlDocumentReader(string fileName) {
    XmlDocument doc = new XmlDocument();
    doc.Load(fileName);
    XmlNodeList nodes = doc.SelectNodes("//child");
    if (nodes == null) {
        throw new ApplicationException("invalid data");
    }
    foreach (XmlNode node in nodes) {
        string id = node.Attributes["id"].Value;
        ProcessId(id);
    }
}

LINQ to XML

private static void XDocumentReader(string fileName) {
    XDocument doc = XDocument.Load(fileName);
    if (doc == null | doc.Root == null) {
        throw new ApplicationException("invalid data");
    }
    foreach (XElement child in doc.Root.Elements("child")) {
        XAttribute attr = child.Attribute("id");
        if (attr == null) {
            throw new ApplicationException("invalid data");
        }
        string id = attr.Value;
        ProcessId(id);
    }
}

XmlReader

private static void XmlReaderReader(string fileName) {
    using (XmlReader reader = new XmlTextReader(fileName)) {
        while (reader.Read()) {
            if (reader.NodeType == XmlNodeType.Element) {
                if (reader.Name == "child") {
                    reader.MoveToAttribute("id");
                    string id = reader.Value;
                    ProcessId(id);
                }
            }
        }
    }
}

The Results

UTF8Encoding

ASCIIEncoding

UTF32Encoding

Conclusion