All entries for August 2006

Loopy linked lists

I've been playing with Nemerle today. It's a functional/OO hybrid for the .NET CLR. I needed a circular linked list for a project I'm working on. Basically a linked list where the end points back to the start.
Whilst Nemerle allows mutable variables, I felt dirty leaving all the beauty of "no side effects" programming behind. Luckily Nemerle allows lazy evaluation using some macro magic behind the scenes (That's right Dan, I said the "L" word ;)). This meant I could reference the first item effectively inside its own definition. (The laziness is not exactly first class like in Haskell, but it certainly works for me here.)

#pragma indent

 
using System
using Nemerle
 

class LoopList[T]
  private first : LazyValue[LoopListItem[T]]
 

  public this(values : list [T])
    def build(xs)
      | [] => first
      | head::tail => lazy( LoopListItem(head, build(tail)) )
    first = build(values)
 

  public First : LoopListItem[T]
    get
      first
 


[Record] struct LoopListItem[T]
  public Value : T
  public Next : LazyValue[LoopListItem[T]]

 

// Test code:
mutable item = LoopList([1,2,3]).First

 
repeat(10)
  Console.Write($"$(item.Value) ")
  item = item.Next
 

// Outputs:
// 1 2 3 1 2 3 1 2 3 1

Next I need to figure out a circular doubly linked list…

: 06 Aug 2006 20:36 |  Tags: Coding Dotnet Nemerle |  Comments (0) |  Close comments |  Trackbacks (1) |  Report a problem

BindingListView speedy sorting

I received some feedback about my BindingListView library saying it was very slow for sorting large lists. At first I thought 20,000 objects in a view was a bit extreme, but I tested with a DataView object and it worked OK. So I decided to hunt down the bottleneck in BindingListView sorting.
Using the CLR Profiler I determined it was reflection calls taking most of the execution time (no suprises there, reflection is very slow!)
When sorting the BLV used reflection to read the sorted property value from each object. The sorting 20,000 objects means and lot of calls to "GetValue", resulting in crippled performance.
The solution came from .NET 2.0's System.Reflection.Emit.DynamicMethod class. Using this class I was able to emit the IL (Microsoft .NET Intermediate Language) that directly accessed an object's property. (Of course the name of the property is supplied at runtime.)
I actually generate a few different methods depending on it the property is a value type or reference type. Since a value type needs to be boxed before we can compare using IComparable.
Here is one of the methods:

private static Comparison BuildRefTypeComparison(PropertyInfo pi, ListSortDirection direction)
{
    MethodInfo getMethod = pi.GetGetMethod();
    Debug.Assert(getMethod != null);

    DynamicMethod dm = new DynamicMethod("Get" + pi.Name, typeof(int), new Type[] { typeof(T), typeof(T) }, typeof(T));
    ILGenerator il = dm.GetILGenerator();

    // Get the value of the first object's property.
    il.Emit(OpCodes.Ldarg_0);
    il.EmitCall(OpCodes.Call, getMethod, null);
    
    // Get the value of the second object's property.
    il.Emit(OpCodes.Ldarg_1);
    il.EmitCall(OpCodes.Call, getMethod, null);

    // Cast the first value to IComparable and call CompareTo,
    // passing the second value as the argument.
    il.Emit(OpCodes.Castclass, typeof(IComparable));
    il.EmitCall(OpCodes.Call, typeof(IComparable).GetMethod("CompareTo"), null);

    // If descending then multiply comparison result by -1
    // to reverse the ordering.
    if (direction == ListSortDirection.Descending)
    {
        il.Emit(OpCodes.Ldc_I4_M1);
        il.Emit(OpCodes.Mul);
    }

    // Return the result of the comparison.
    il.Emit(OpCodes.Ret);

    // Create the delegate pointing at the dynamic method.
    return (Comparison)dm.CreateDelegate(typeof(Comparison));
}

Emitting IL by hand is not pretty (see my previous post for an idea to improve this problem). Using Reflector (or ILdasm) certainly is a must if, like me, you are an IL newbie. I wrote some simple example methods in C#, compiled them, then viewed in Reflector to see the IL they produced.

The end result in my speed test harness was BindingListView sort actually out performing the DataView!
Using 200,000 objects (10x more than the reported amount). Sorting on an Int32 property.
Old BindingListView took 146,823ms
New BindingListView took 16,564ms
DataView took 20,654ms

All the code is online at Source Forge

: 05 Aug 2006 16:12 |  Tags: Bindinglistview Coding Csharp Dotnet |  Comments (0) |  Close comments |  Report a problem

Runtime code generation, with macro ease

.NET 2.0 has some very cool stuff in System.Reflection.Emit, namely the DynamicMethod class. DynamicMethod will let you create a new method at runtime that lives inside your current assembly. The only hitch is that you have to create the method using IL – not a high level language like C#/VB/Boo/etc.

My thought for today is: Can we use the syntactic macro abilities of .NET languages like Boo and Nemerle to create dynamic method code whilst remaining in the source language.

For example (psuedo–Nemerle):

myMethod = dynamic( Console.WriteLine("Hello, World") );
myMethod() // Call the dynamically generated method

At compile time this would take the AST passed to the "dynamic" macro, call out to the Nemerle compiler and retrieve the IL. This IL is then used to create a sequence of Emit*() calls needed to create the dynamic method. Finally the macro creates a delegate that can be used to call the method.

Whilst that may seem rather complex, once working it totally removes the need to drop to IL to generate dynamic methods at runtime. I've not had time to think through the implementation details of this. For now I'm just throwing the idea out there – If someone wants have a go, please feel free! The main sticking point is really working out an escaping system to allow interpolation of real code and IL emits. This can probably be done using a second macro "normal" that switches back to normal code.

There is something rather magic about using compile–time macros to generate code for runtime methods. It feels like both sides of meta–programming sync up so nicely, adding a whole new dimension to "code that writes code"! :)

: 04 Aug 2006 00:46 |  Tags: Codegen Coding Dotnet Dynamicmethod Macros |  Comments (1) |  Close comments |  Report a problem