Monday, May 31, 2010

CLR: Verification for Runtime Code Generation

The CLR's lightweight code generation via DynamicMethod is pretty useful, but it's sometimes difficult to debug the generated code and ensure that it verifies. In order to verify generated code, you must save the dynamic assembly to disk and run the peverify.exe tool on it, but DynamicMethod does not have any means to do so. In order to save the assembly, there's a more laborious process of creating dynamic assemblies, modules and types, and then finally adding a method to said type.

This is further complicated by the fact that a MethodBuilder and DynamicMethod don't share any common interfaces or base types for generating IL, despite both of them supporting a GetILGenerator() method.

This difficulty in switching between saved codegen and pure runtime codegen led me to add a CodeGen class to Sasa, which can generate code for either case based on a bool parameter. Since no common interface is available for code generation, it also accepts a delegate to which it dispatches for generating the code:
/// <summary>
/// Create a dynamic method.
/// </summary>
/// <typeparam name="T">The type of the dynamic method to create.</typeparam>
/// <param name="type">The type to which this delegate should be a member.</param>
/// <param name="methodName">The name of the delegate's method.</param>
/// <param name="attributes">The method attributes.</param>
/// <param name="saveAssembly">Flag indicating whether the generated code should be saved to a dll.</param>
/// <param name="generate">A call back that performs the code generation.</param>
/// <returns>An dynamically created instance of the given delegate type.</returns>
public static T Function<T>(
Type type,
string methodName,
MethodAttributes attributes,
bool saveAssembly,
Action<ILGenerator> generate)
where T : TypeConstraint<Delegate>;

You can also see Sasa's ilrewrite tool at work here with the T : TypeConstraint<Delegate>. This function will generate either a DynamicMethod or a dynamic assembly and save that assembly to disk, based on the 'saveAssembly' parameter. The assembly name is generated based on the type and methodName parameters.

In debugging the Sasa.Dynamics reflection code, I also came across a strange error which was not adequately explained anywhere that I could find. peverify.exe spit out an error to the effect of:
[X.dll : Y/Z][offset 0x0000001D] Unable to resolve token

Where X is the name of the generated dll, Y the namespace path, and Z is the class name. In my case, this occurred when the dynamically generated code was referencing a private class, which should not be possible from a separate dll.

Thursday, May 20, 2010

Peirce's Criterion: command-line tool

I've written a simple command-line tool filter out statistical outliers using the rigourous Peirce's Criterion.

The algorithm has been available in Sasa for awhile, and will be in the forthcoming v0.9.3 release.

I've also packaged the command-line tool binary for running Peirce's Criterion over multi-column CSV files (LGPL source available here).

The Cost of Type.GetType()

Most framework-style software spends an appreciable amount of time dynamically loading code. Some of this code is executed quite frequently. I've recently been working on a web framework where URLs map to type names and methods, so I've been digging into these sort of patterns a great deal lately.

The canonical means to map a type name to a System.Type instance is via System.Type.GetType(string). In a framework which performs a significant number of these lookups, it's not clear what sort of performance characteristics one can expect from this static framework function.

Here's the source for a simple test pitting Type.GetType() against a cache backed by a Dictionary<string, Type>. All tests were run on a Core 2 Duo 2.2 GHz, .NET CLR 3.5, and all numbers indicate the elapsed CPU ticks.

Type.GetType()Dictionary<string, Type>
623607064051351056
623619385651440360
623746622451463192
623821048851583336
624064581651599480
624208940051687448
624445039251719808
624520166451757472
624832704851793696
624925373651800056
625064067251859704
625113391251885992
625354476851897264
625433663251946408
625511787252046512
625606064852106936
625615917652140984
625945356852391000
Average
6247464250.6751803928

Each program was run 20 times, and the resulting timing statistics were run through Peirce's Criterion to filter out statistical outliers.

You can plainly see that using a static dictionary cache is over two orders of magnitude faster than going through GetType(). This is a huge savings when the number of lookups being performed is very high.

Edit: Type.GetType is thread-safe, so I updated the test to verify that these performance numbers hold even when locking the dictionary. The dictionary is still two orders of magnitude faster. There would have to be significant lock contention in a concurrent program to justify using Type.GetType instead of a dictionary cache.

LINQ Transpose Extension Method

I had recent need for a transpose operation which could swap the columns and rows of a nested IEnumerable sequence, it's simple enough to express in LINQ but after a quick search, all the solutions posted online are rather ugly. Here's a concise and elegant version expressed using LINQ query syntax:
/// <summary>
/// Swaps the rows and columns of a nested sequence.
/// </summary>
/// <typeparam name="T">The type of elements in the sequence.</typeparam>
/// <param name="source">The source sequence.</param>
/// <returns>A sequence whose rows and columns are swapped.</returns>
public static IEnumerable<IEnumerable<T>> Transpose<T>(
this IEnumerable<IEnumerable<T>> source)
{
return from row in source
from col in row.Select(
(x, i) => new KeyValuePair<int, T>(i, x))
group col.Value by col.Key into c
select c as IEnumerable<T>;
}
It simply numbers the columns in each row, flattens the sequence of cells, and groups the entries by number. If the table has entries that are missing, this algorithm has the side-effect of compacting all entries so that only the last row or column will be missing the elements. This may or may not be suitable for your application.

This extension method will be available in the forthcoming Sasa 0.9.3 release.

Monday, May 17, 2010

Asymmetries in CIL

Most abstractions of interest have a natural dual, for instance, IEnumerable and IObservable, induction and co-induction, algebra and co-algebra, objects and algebraic data types, message-passing and pattern matching, etc.

Programs are more concise and simpler when using the proper abstraction, be that some abstraction X or its dual. For instance, reactive programs written using the pull-based processing semantics of IEnumerable are far more unwieldy than those using the natural push-based semantics of IObsevable. As a further example, symbolic problems are more naturally expressed via pattern matching than via message-passing.

This implies that any system is most useful when we ensure that every abstraction provided is accompanied by its dual. This also applies to virtual machine instruction sets like CIL, as I recently discovered while refining my safe reflection abstraction for the CLR.

A CIL instruction stream embeds some necessary metadata required for the CLR's correct operation. Usually this metadata is type information of some sort, such as the type of a local or the name and/or signature of a target method. For instance, here's a Hello World! example:
ldstr "Hello World!"
call void [mscorlib]System.Console::WriteLine(string)

Unfortunately, the CIL instruction set suffers from some asymmetries which make some types of programming difficult.

For example, the ldtoken instruction takes an embedded metadata token and pushes the corresponding runtime type handle onto the evaluation stack; this is the instruction executed when using the typeof() operator in C#.

While this operation is useful, we sometimes want its dual, which is to say, we want the metadata used in a subsequent instruction to depend on the object or type handle at the top of the evaluation stack. A related operation is supported on the CLR, namely virtual dispatch, which depends on the concrete type, but dispatch is not general enough to support all of these scenarios because the vtable is immutable.

Consider a scenario where you have an untyped object, like a reference to System.Object "obj", and you want to call into some generic code, like a method Foo<T>(T value), but pass the concrete type of obj for T, instead of System.Object. Currently, you must go through a laborious process where you call GetType() on the object to obtain it's type handle, then obtain the method handle via reflection or some clever CIL hackery, then call MethodInfo.MakeGenericMethod in order to instantiate the type argument on Foo<T>, and finally, you must perform a dynamic invocation via reflection or allocate a custom delegate of type Action<T> and perform a virtual call, even though the call is statically known.

Each step of this process is expensive, and it makes typeful programming on the CLR painful when working on the boundary between typed and untyped code. Many reflection problems, like serialization, become simpler once we're dealing with fully typeful code.

Consider a dual instruction to ldtoken called "bind" which takes a type handle obtained via GetType() and then binds the resulting type handle into the executing instruction stream for the subsequent generic call to Foo<T>. This instruction could be easily and efficiently supported by any VM. Some restrictions are clearly needed for this instruction to remain verifiable, namely that the type constraints required by the target method are a subset of the type constraints of the statically known type, but the verifier already performs this analysis, and all of the information needed is available at the call site.

Fully polymorphic functions like Foo<T> trivially satisfy this condition since it has no constraints whatsoever. Serialize<T>/Deserialize<T> operations are duals, and in fact exhibit exactly the same sort of fully polymorphic type signature as Foo<T>.

There are many more programs that exhibit this structure, but they are unnecessarily difficult to write due to these asymmetries in CIL. This unfortunately requires developers to write a lot of ad-hoc code to get the results they want, and more code results in more bugs, more time, and more headaches.

CIL Verification and Safety

I've lamented here and elsewhere some unfortunate inconveniences and asymmetries in the CLR -- for example, we have nullable structs but lack non-nullable reference types, an issue I address in my Sasa class library.

I've recently completed some Sasa abstractions for safe reflection, and an IL rewriter based on Mono.Cecil which allows C# source code to specify type constraints that are supported by the CLR but unnecessarily restricted in C#. In the process, I came across another unjustified decision regarding verification: the jmp instruction.

The jmp instruction strikes me as potentially incredibly useful for alternative dispatch techniques, and yet I recently discovered that it's classified as unverifiable. This seems very odd, since the instruction is fully statically typed, and I can't think of a way its use could corrupt the VM.

In short, the instruction performs a control transfer to a named method with a signature matching exactly the current method's signature, as long as the evaluation stack is empty and you are not currently in a try-catch block (see section 3.37 of the ECMA specification).

This seems eminently verifiable given a simple control-flow analysis, an analysis which the verifier already performs to verify control-flow safety of some other verifiable instructions. If anyone can shed some light on this I would appreciate it.