posted by Rüdiger Klaehn on Wed 6th Oct 2004 20:31 UTC

".NET Generics, Page 2/3"
The Solution

Fortunately there is a solution to this problem. When a type parameter is a valuetype, calls to its methods do not involve any kind of dynamic method invocation even if the type parameter is constrained by interface constraints. You can take advantage of this with e.g. the IComparable<T> interface. The call to CompareTo in the following code snipplet does not involve any cast or dynamic method invocation as long as T is a struct.

public static class Utils
{
    public static void Swap<T>(ref T a,ref T b)
    {
        T t=a;a=b;b=t;
    }
    public static void Sort<T>(ref T a,ref T b) 
        where T:IComparable<T>
    {
        if(a.CompareTo(b)>0)
            Swap(ref a,ref b);
    }
}

So an approach to avoid dynamic method invocation would be to use a valuetype for the type containing the operations. That way, calls to the operator methods will be nonvirtual. Since the operator methods like T Add(T a,T b) are usually very short, they will be inlined even by the current less than optimal JIT compiler. For primitive types, the runtime cost of the abstraction is zero.

The first person to come up with this idea was Jeroen Frijters.

Here is a short example for this approach:

interface ICalculator<T>
{
    T Sum(T a,T b);
}

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

struct FloatAdder ...
struct DoubleAdder ...

class Lists<T,C>
    where T:new() 
    where C:ICalculator<T>,new();
{
    private static C calculator=new C();
    public static T Sum(List<T> list)
    {
        T sum=new T();
        for(int i=0;i<list.Count;i++)
            sum=calculator.Add(sum,list[i]);
        return sum;
    }
}

The use of this class is a bit awkward since you now need to provide two type parameters. But you can alleviate this by using aliases such as using IntLists=Lists<int,IntAdder>;

List<int> list1;
List<float> list2;
List<decimal> list3;
...
int sum1=Lists<int,IntAdder>.Sum(list1);
float sum2=Lists<float,FloatAdder>.Sum(list2);
decimal sum3=Lists<decimal,DecimalAdder>.Sum(list3);    

As you can see, the generic Lists type now has two type parameters, one for the storage type and one for the methods that do the calculations. This is of course not as short as it would be if the primitive types would implement an interface like IArithmetic<T>. But it works, and the performance is similar to the non-generic version.

Performance

To test the performance of this approach, I wrote a small benchmark program that compares summing up the elements of a large list with both generic and non-generic versions. The performance of the generic version is identical to the performance of the non-generic version, so apparently the call to the calculator.Add method is inlined.

Please make sure that you run the performance test in release mode, since some very important optimizations such as method inlining are disabled in debug mode.

Other Benefits

Since this approach decouples the storage type (T) and the type that is used to perform calculations on T (C), you can do some other neat things. For example you could have a CheckedIntCalculator that performs overflow checks when performing arithmetic operations:

struct CheckedIntCalculator : ICalculator<T> {
    public T Add(T a,T b) { checked { return a+b; } }
}

Or you could have a DoubleComparer that has a different definition of equals than the default comparison operations. Often you want to define two floating point numbers as equal if the difference is lower than some predefined threshold to avoid fake inequalities due to rounding errors.

struct FuzzyDoubleComparer : IComparer<T> {
    public bool Equals(double a,double b)
    {
        return Math.Abs(a-b)<1e-10;
    }
    ...
}
Table of contents
  1. ".NET Generics, Page 1/3"
  2. ".NET Generics, Page 2/3"
  3. ".NET Generics, Page 3/3"
e p (0)    32 Comment(s)

Technology White Papers

See More