Using .NET generics for fast numerical calculations

The current implementation of generics in .NET 2.0 does a very good job to make typed collections faster and more easy to use. But as many people have noticed, it leaves much to be desired when you want to do calculations with generic types.

The Problem

In the last article about this topic I used a Point<T> structure to illustrate this problem. But of course the problem exists in many other situations as well. For example you might want to write a method that calculates the sum of all elements of a List<T> where T is a type like int, double, decimal or any other type that can be summed.

For someone used to C++ templates this looks like a trivial problem. He would probably come up with something like this:

public class Lists {
    ...
    public static T Sum(List<T> list) 
    {
        T sum=0;
        for(int i=0;i<list.Count;i++)
            sum+=list[i];
        return sum;
    }
    ...
}

This method could then be used to calculate sums:

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

But surprisingly enough this is not possible with .NET generics. The problem is that in .NET type parameters without constraints are assumed to be of type System.Object, which is not very useful to do calculations. There is currently no way to constrain type parameters in such a way as to require the existence of a static method. And since operators in .NET are static methods it is not possible to have operator constraints.

A clean way to enable numerical computations would be to let the basic data types like int, float, double, decimal etc. implement an interface for arithmetic operations. Then this interface could be used to constrain the type parameters. This would work similar to the IComparable<T> interface that all basic data types implement.

Unfortunately the people at microsoft seem to be unable to do this in time for .NET 2.0, which will probably be released in 2005.

Many people have been thinking about this problem, among them Anders Hejlsberg and Eric Gunnerson. There are many creative solutions, such as this, which involves dynamic code generation.

As an example, lets take a look at the solution suggested by Anders Hejlsberg. I copied the code from Eric Gunnersons blog.

  • First define an abstract base class Calculator<T> for the operations to be performed:
    public abstract class Calculator<T>
    {
        public abstract T Add(T a, T b); 
    } 
    
  • Then specialize for the types we want to use:

    namespace Int32
    {
        public class Calculator: Calculator
        {
            public override int Add(int a, int b)
            {
                return a + b;
            }
        } 
    } 
    
  • Then use an appropriate Calculator for the type you want to use

    class AlgorithmLibrary<T> where T: new() 
    {
        Calculator<T> calculator;
     
        public AlgorithmLibrary(Calculator<T> calculator)
        {
            this.calculator = calculator;
        } 
    
        public T Sum(List<T> items)
        {
            T sum = new T(); 
    
    
            for (int i = 0; i < items.Count; i++)
            {
                sum = calculator.Add(sum, items[i]);
            } 
            return sum;
        }
    } 
    

All those implementations solve the problem, but unfortunately they all involve some kind of dynamic method invocation (virtual methods, interfaces or even delegates), which makes them quite slow. A virtual method adding two integers will spend only a small fraction of the time doing actual work. Most time will be used for the virtual method call itself. For most numerical applications, the overhead associated with virtual method calls and such is simply unacceptable.

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&lt;int,IntAdder&gt;;

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;
    }
    ...
}

Syntax candy

One small issue with this approach is that you still can not use operator overloading on type parameters. Instead of simply writing sum+=list[i]; in the above example, we have to call the Add method of the calculator struct like this: sum=calculator.Add(sum,list[i]);. This is usually not a big deal, but it is a problem that can be solved by using a wrapper struct:

public struct Number<T,C>
    where C:ICalculator<T<,new()
{
    private T value;
    private static C calculator=new C();
    private Number(T value) {
        this.value=value;
    }
    public static implicit operator Number<T,C>(T a) 
    {
        return new Number<T,C>(a);
    }
    public static implicit operator T(Number<T,C> a) 
    {
        return a.value;
    }
    public static Number<T,C> operator + (Number<T,C> a, Number<T,C> b)
    {
        return calculator.Add(a.value,b.value);
    }
    ...other operators...
}

By using this wrapper struct, we can rewrite the Lists<T,C> class to use operators again:

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

Unfortunately, due to some very serious limitations in the current JIT compiler inlining heuristics the version using the wrapper struct will be slower than the version that calls calculator.Add directly. But since the wrapper struct does not add any dynamic method invocation the calls to wrapper methods could easily be optimized away by a more capable JIT compiler.

Conclusion

Using valuetypes as type parameters, it is possible to write efficient classes that do arithmetic operations on type parameters. The code is not as short as it would be in C++, but that is acceptable considering the large benefits of constrained type parameters. The thing to keep in mind is that while casting a valuetype to an interface has a significant overhead due to boxing and dynamic method invocation, constraining a type parameter by an interface has no such overhead.

References

Benchmark of generic vs. nongeneric summation of list elements
Interfaces for all arithmetic calculations
Implementation of the above interfaces for the primitive types
Wrapper classes for the interfaces
A sample program that uses the above interfaces to calculate the standard deviation of a List<T>
Another creative way to use zero-size structs
Please vote on this suggestion

About the Author
Rüdiger Klaehn works as freelance programmer. He is currently trying to start a company with some friends, but in germany that is a long and tedious process. He is very interested in functional programming languages and hopes that .NET will lead to a more widespread adoption in the industry.


If you would like to see your thoughts or experiences with technology published, please consider writing an article for OSNews.

30 Comments

  1. 2004-10-06 9:24 pm
  2. 2004-10-06 10:24 pm
  3. 2004-10-06 10:52 pm
  4. 2004-10-07 12:25 am
  5. 2004-10-07 12:38 am
  6. 2004-10-07 12:39 am
  7. 2004-10-07 12:56 am
  8. 2004-10-07 1:05 am
  9. 2004-10-07 1:08 am
  10. 2004-10-07 5:13 am
  11. 2004-10-07 5:34 am
  12. 2004-10-07 5:34 am
  13. 2004-10-07 5:38 am
  14. 2004-10-07 6:30 am
  15. 2004-10-07 7:34 am
  16. 2004-10-07 8:02 am
  17. 2004-10-07 8:04 am
  18. 2004-10-07 12:16 pm
  19. 2004-10-07 2:10 pm
  20. 2004-10-07 2:49 pm
  21. 2004-10-07 3:27 pm
  22. 2004-10-07 6:13 pm
  23. 2004-10-07 7:16 pm
  24. 2004-10-07 7:25 pm
  25. 2004-10-07 11:04 pm
  26. 2004-10-07 11:26 pm
  27. 2004-10-08 7:29 am
  28. 2004-10-08 9:14 am
  29. 2004-10-08 9:36 am
  30. 2004-10-08 10:59 am