Saturday, May 30, 2009

Who's on First

This is a follow-up to my previous post: Swap Ints, Two Variables, No Waiting.

While analyzing my method's CIL, I thought that maybe I could implement a faster swap. Maybe there is a way to implement a method that doesn't need a temp variable but without all the overhead we've seen with xor. Well, the following came up:

.method public hidebysig static void  SwapIntsCil(int32& first,
                                                  int32& second) cil managed
{
  // Code size       9 (0x9)
  .maxstack  4
  IL_0000:  ldarg.0
  IL_0001:  ldarg.1
  IL_0002:  ldind.i4
  IL_0003:  ldarg.1
  IL_0004:  ldarg.0
  IL_0005:  ldind.i4
  IL_0006:  stind.i4
  IL_0007:  stind.i4
  IL_0008:  ret
} // end of method IntSwapper::SwapIntsCil

Let's see what it does:

  • IL_0000 Pushes first's address into the stack.
  • IL_0001 Pushes second's address into the stack.
  • IL_0002 Pops the address to fetch and push the actual Int32 value.
  • IL_0003 Pushes second's address into the stack.
  • IL_0004 Pushes first's address into the stack.
  • IL_0005 Pops the address to fetch and push the actual Int32 value.
  • IL_0006 Pops first's value and second's address to store the value at the address.
  • IL_0007 Pops second's value and first's address to store the value at the address.
  • IL_0008 Gets the hell outta here.

Click to display diagram.

To sum up, this method would use 4 levels of stack, declare no local variables, load 4 addresses, load 2 values through these addresses, store 2 values to these addresses and perform no operations.

In order to implement this, I moved previous swaps into a separate Assembly called KeepItSharp (yes, I'm that original) and to a class called IntSwapper. Built it in release mode, opened it with ildasm and dumped the CIL code. Added my new method and compiled it with ilasm. Time to test it!

static void Main(string[] args)
{
    int a = 15;
    int b = 320;
    Console.WriteLine("a: {0}\tb: {1}", a, b);

    KeepItSharp.IntSwapper.SwapIntsCil(ref a, ref b);

    Console.WriteLine("a: {0}\tb: {1}", a, b);
}

And the result is... <drumroll>

a: 15   b: 320
a: 320  b: 15
Press any key to continue . . .

Cool… my first CIL code and it works! Well, can't wait to see if it actually is faster than the conventional swap. Here it goes:

Benchmarking code is omitted because it's analogue to the one on my previous post.

SwapIntsXor: 00.559 - SwapIntsCil: 00.190 - SwapInts: 00.200
SwapIntsXor: 00.543 - SwapIntsCil: 00.189 - SwapInts: 00.194
SwapIntsXor: 00.544 - SwapIntsCil: 00.191 - SwapInts: 00.194
SwapIntsXor: 00.545 - SwapIntsCil: 00.190 - SwapInts: 00.190
SwapIntsXor: 00.549 - SwapIntsCil: 00.193 - SwapInts: 00.192
Press any key to continue . . .

Darn it! It seems to be a close one. OK, let's call it a tie.

Now, it seemed like fun to see what Red Gate's .NET Reflector had to say about this method, and the result is pretty peculiar. Check it out:

public static void SwapIntsCil(ref int first, ref int second)
{
    second = first;
    first = second;
}

And this works? Actually I wish that reflector would have thrown an error instead of showing this mysterious piece of coding that should've never worked.

The whole time while writing these last two posts, I kept thinking about Abbott and Costello's "Who's on First". Who's on first, what's on second, and on third? I don't know, I'm not using a temp variable!

Random thoughts: Aside from being cool to code some CIL, what left me thinking most was Reflector's behavior. For one, I will not stop using Reflector since the benefits are huge and these scenarios very scarce. On another note, this means that using CIL code directly allows us to write code that can't be translated to C# with reflecting tools. This seems pretty useful for licensing code, for example, although it would be easier to just code it in C and p/invoke it.

You can download KeepItSharp.dll here.

4 comments:

  1. El lado oscuro de la fuerza lo haria asi...

    $a="rules";
    $b="php";
    list($a,$b)=array($b,$a);
    print "$a $b";

    Y el resultado:
    PHP RULES BABY!!! En mayuscula y con los signos, a ver si .net te devuelve eso jeje :P

    ReplyDelete
  2. @David: Yeah... it's really cool. I have been obsessing with the idea of using it somewhere, but it seems to be pretty useless. It does help to analyze and understand it, and even do something with it to realize what's going on behind the curtains, I believe it really helps making you a better developer/programmer.

    @Karibe: Hmmm... I need to turn comment moderation on :)

    ReplyDelete
  3. First, this is really click. IL is very fun. I just thought I'd mention - there's another useful int swap option: "a = Interlocked.Exchange(ref a, b);" It's definitely a LOT slower than any three options above, but it's atomic, so its safer in threading situations.

    ReplyDelete