25 July 2007

One of the limitations of C# generics is you cannot abstract over operators. That is not completely true, you can if the base class used in where clause has operators; but, since operators are more useful, and more common, on value types, that is only marginally helpful. Also, this abstraction is provided by the base class not by using generics. What I would like to do is declare that my type  parameter requires the type to implement a particular operator. For example, to create a generic Add() method I would like to specify that the type parameter must implement the + operator and then be able to use the + operator in my code such as,

// Invalid C#
static T Add<T>(T a, T b) where T: T operator +(T, T) {
    return a + b;

C# doesn't support this but you can get somewhat close by supplying a policy struct like I described in this post. The policy interface and the int policy struct would look like,

interface IAddPolicy<T> {
    T Add(T a, T b);

struct IntAddPolicy : IAddPolicy<int> {
    public int Add(int a, int b) { return a + b; }

This allows you to write the following,

static T Add<T, P>(T a, T b) where P: struct, IAddPolicy<T> {
    return new P().Add(a, b);

Unfortunately the policy struct cannot be inferred from the parameters so you have to supply the type parameter explicitly,

var i = Add<int, IntAddPolicy>(3, 4);

which doesn't look pretty and generates less than efficient code for the Add() method on an i386 architecture,

00000000  sub         esp,8
00000003  xor         eax,eax
00000005  mov         dword ptr [esp],eax
00000008  mov         dword ptr [esp+4],eax
0000000c  mov         byte ptr [esp],0
00000010  movsx       eax,byte ptr [esp]
00000014  mov         byte ptr [esp+4],al
00000018  add         ecx,edx
0000001a  mov         eax,ecx
0000001c  add         esp,8
0000001f  ret              

This generates code to initialize the policy structure we don't actually use. We can get rid of that by recasting this a bit to save the dummy struct allocation by putting the Add() method in a wrapping class that takes the type parameters. The type would allocate the struct instead of the method. This looks like,

class Adder<T, P>
    where P: struct, IAddPolicy<T>
    static P AddPolicy = new P();
    static public T Add(T a, T b) { return AddPolicy.Add(a, b); }

which generates the following code for Add(),

00000000  add         ecx,edx
00000002  mov         eax,ecx
00000004  ret              

This can be called like,

var i2 = Adder<int, IntAddPolicy>.Add(3, 4);

Note that the code in IntAddPolicy gets inlined into the Add() method. Even though this doesn't get inlined into the caller of Add(), it will still be pretty quick with the branch prediction and register aliasing of modern processors. This means that you are not paying much (and in many cases nothing) in code quality for using an AddPolicy over writing out the Add() method explicitly.

To use the Add() method above with another type, such as double, you need to create another add policy struct. This would look like,

struct DoubleAddPolicy : IAddPolicy<double> {
    public double Add(double a, double b) { return a + b; }

Using this struct to call Add() will produce the following code for the Add() method,

00000000  fld         qword ptr [esp+0Ch]
00000004  fadd        qword ptr [esp+4]
00000008  ret         10h  

This is not quite as good as the code generated for int because it uses the stack to pass the parameters but it is still pretty fast.

We now have a method that can add two values of any type T for which an AddPolicy can be created. This is pretty close to, and more general than, what I originally wanted. Unfortunately, even though the code generated is good, calling this code is very awkward; we have to call a static method of a parameterized class and the policy struct prevents the compiler from being able to use type inferencing to supply the parameters for us. Next time I will describe a more practical application of this technique where the awkwardness is not as noticiable.

blog comments powered by Disqus