Home > Uncategorized > Revisiting recursion with Dynamic Methods

Revisiting recursion with Dynamic Methods

Dynamic methods were added to .NET back in the 2.0 release as part of Lightweight Code Generation, and lots of technologies (i.e. IronPython) use them to do their dynamic dirty work of emitting code at runtime. Dynamic methods are methods that you create at runtime through System.Reflection.Emit much like you would generate an assembly with reflection, only you don’t need to put the method in an assembly, so there isn’t an assembly hanging around in memory…GC can clean up the JIT’d code after the method goes out of scope.

The code is also a lot more concise: no AssemblyBuilder, ModuleBuilder, TypeBuilder, MethodBuilder needed before you can write a dynamic method. For an example, I’m revisiting my old recursive Fibonacci function to illustrate writing a dynamic method and also show the performance cost for the runtime to resolve dynamic methods. Recursive functions demonstrate this the best because each recursion requires dynamic method resolution to occur.

DynamicMethod dm = new DynamicMethod("Fib", typeof(int), new Type[] { typeof(int) }, true);
ILGenerator il = dm.GetILGenerator();
Label isEqZero = il.DefineLabel();
Label isNotEqZero = il.DefineLabel();
Label isNotEqOne = il.DefineLabel();
Label retLabel = il.DefineLabel();
LocalBuilder local = il.DeclareLocal(typeof(int));
il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Ldc_I4_0);
il.Emit(OpCodes.Ceq);
 
il.Emit(OpCodes.Brfalse, isNotEqZero);
// If it got here, then the input was zero, so go to return label.
il.Emit(OpCodes.Ldc_I4_0);
il.Emit(OpCodes.Stloc_0);
il.Emit(OpCodes.Br, retLabel);
 
il.MarkLabel(isNotEqZero);
il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Ceq);
il.Emit(OpCodes.Brfalse, isNotEqOne);
// If it got here, then the input was one, so go to return label.
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Stloc_0);
il.Emit(OpCodes.Br, retLabel);
 
il.MarkLabel(isNotEqOne);
// Should do recursion here.
il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Ldc_I4_1);
il.Emit(OpCodes.Sub);
il.Emit(OpCodes.Call, dm);
il.Emit(OpCodes.Ldloc_0);
il.Emit(OpCodes.Add);
il.Emit(OpCodes.Stloc_0);
il.Emit(OpCodes.Ldarg_0);
il.Emit(OpCodes.Ldc_I4_2);
il.Emit(OpCodes.Sub);
il.Emit(OpCodes.Call, dm);
il.Emit(OpCodes.Ldloc_0);
il.Emit(OpCodes.Add);
il.Emit(OpCodes.Stloc_0);
 
// Loads the first local variable onto the stack and returns it.
il.MarkLabel(retLabel);
il.Emit(OpCodes.Ldloc_0);
il.Emit(OpCodes.Ret);
 
Func<int, int> invokeDynamicMethod = (Func<int, int>)dm.CreateDelegate(typeof(Func<int, int>));
for (int i = 0; i <= 40; i++)
{
    int result = invokeDynamicMethod.Invoke(i);
    Console.WriteLine("{0} {1}", i, result);
}

If you run this, you’ll notice that it gets slower with larger numbers because bigger numbers require more invocations of the dynamic method. Of course, you could solve this problem without using recursion, but I wanted to illustrate the performance penalty. That said, Lightweight Code Generation and dynamic methods give you some great flexibility without the additional baggage of generating a full fledged .NET assembly.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: