Linq Expressions – Calculating with generics


You can find the full code for this post here:
http://www.puzzleframework.com/Roger/GenericMath.cs.txt 

The .NET framework lacks support for calculating with generic types.
There is no way to ensure that a generic type supports operations like Add, Sub, Div and Mul etc.

More about the problem can be found here:
http://www.thescripts.com/forum/thread278230.html

“They are not. There have been a few threads on this subject before,
and the conclusion was that it is impossible to perform any of the
built-in mathematical operations on generic types.”

Many have tried to come up with solutions for calculating with generic types, most of them based on provider solutions where you have to provide a “Calculator” class for each type that you want your generic class to support.
Quirky to say the least..

One such solution exists here: http://www.codeproject.com/KB/cs/genericnumerics.aspx

And don’t get me wrong, I’m NOT saying that those are bad implementations, it was just not possible to solve this in any clean way before.

But now when we have Linq Expression Trees we can solve this. and do it quite nicely.

We can produce delegates that performs the math operations for us.
Like this:

private static Func<T, T, T> CompileDelegate 
 (Func<Expression,Expression,Expression> operation) 
{ 
    //create two inprameters 
    ParameterExpression leftExp = 
 Expression.Parameter(typeof(T), "left");                   

    ParameterExpression rightExp = 
 Expression.Parameter(typeof(T), "right");                   

    //create the body from the delegate that we passed in 
    Expression body = operation (leftExp,rightExp);              

    //create a lambda that takes two args of T and returns T 
    LambdaExpression lambda = 
Expression.Lambda(typeof(Func<T, T, T>), body, leftExp, rightExp);              

     //compile the lambda to a delegate 
    // that takes two args of T and returns T 
    Func<T, T, T> compiled = (Func<T, T, T>)lambda.Compile(); 
    return compiled; 
}

 We can now call this method and get our typed delegates for math operations:

private static readonly Func<T, T, T> Add = 
    CompileDelegate(Expression.Add);

And this is pretty much all the magic we need to solve the problem with generics and math operations.
I have created a generic class that support all the standard operators based on this approach.

You can find the full code here:
http://www.puzzleframework.com/Roger/GenericMath.cs.txt

This makes it possible to use code like this:

private static T DoStuff<T>(T arg1, T arg2, T arg3) 
{ 
    if (!Number<T>.IsNumeric) 
        throw new Exception("The type is not numeric");       

    Number<T> v1 = arg1; 
    Number<T> v2 = arg2; 
    Number<T> v3 = arg3; 
         
    return v1 * v2 - v3; //not possible with normal generics 
}

OK that was a very naive example, but atleast you can see that it is possible to perform calcualtions on the generic type.
So no more provider based calculator classes, just fast typed delegates :-)

Enjoy

[Edit]
For those who are interested in this kind of stuff, there is a project called MiscUtil that can be found here:
http://www.yoda.arachsys.com/csharp/miscutil/

They do the same stuff as in this article, but much more complete and polished code than my sample.

//Roger

13 thoughts on “Linq Expressions – Calculating with generics

  1. Pingback: Linq Expressions - Access private fields « Roger Alsing Weblog

  2. Very elegant.

    But it has the overhead of a delegate invocation. Since delegate invocations are never inlined by the CLR, the overhead when working on primitive types such as double will be huge (a factor of 10 or more).

  3. But would you say that the delegate approach gives much higher overhead than the “Calculator” provider version?

    Wouldn’t you get the same perf penalty there because you make a virt call to an iface member? (That cannot be inlined either)

  4. Rüdiger,

    “Since delegate invocations are never inlined by the CLR”,

    Do you mean inlined by csc? Because I thought the CLR didn’t do JIT compilation (actually I thought it did until recently when someone told me it didn’t :-P )

    /Mats

  5. Rüdiger,

    Doh, please disregard that brain fart :-P I shouldn’t post on my vacation, I’m probably still drunk from yesterday ! ;-)

    I was thinking about how the CLR doesn’t dynamically _re-JIT_ stuff depending on context (as far as I know) but that doesn’t really bear on this case. Of course the CLR will JIT to native the first time hitherto uncompiled code is called.

    /Mats

  6. @Jon

    Why aren’t you guys storing the compiled delegate in static vars like I do in my version?

    Just initialize the delegates in the static ctor (or directly on the static fields)

    and then simply call the delegates from your Add/Subtract/Div/Mul functions.

    [edit]
    Apparently you do, I didnt see that the code on the page was just sample code..

  7. > Why aren’t you guys storing the compiled delegate
    > in static vars like I do in my version?

    We are; in the MiscUtil code they are in the static Operator class; I’m amazed how similar our code is, actually!

    > (Rüdiger Klaehn)
    > a factor of 10 or more
    No; a factor of roughly 2 if used correctly.

    > (Jon Skeet)
    > Marc is currently working on a .NET 2.0 version – I’m > not entirely sure how it’s going to work though…
    it uses Delegate.CreateDelegate on the MethodInfo; it will use the necessary “op_Foo” methods if they exist (also had to provide the missing operators for int, float, etc), also with support for Nullable (lifted operators).
    Fully working now for all primatives, all inside 2.0 ;-p
    (but like yourself, I started with 3.5 Expressions)

    Marc

  8. >>I’m amazed how similar our code is, actually!

    Yeah, I’ve just downloaded your code and checked it out.
    But I see that yours is way more complete and advanced.
    (btw. brilliant idea to throw exceptions from delegates on types that don’t support math operations)

    I also added a link to your project in my post, there are quite a bit of nifty stuff in there :-)

  9. A factor of two? Hard to believe, since a delegate call is the same kind of thing (at the machine language level) as a virtual method call. In fact it may be slower (I heard a vague statement somewhere that LCG delegate calls were slower than “normal” delegate calls.) The guy who wrote this article…

    http://www.codeproject.com/KB/cs/genericoperators.aspx

    …used LCG, which is the same thing lambda.Compile() does, but he got a 7x slowdown compared to directly adding numbers.

    Keep in mind when you measure the speed of a loop like

    for (int i = 0; i < 1000000000; i++)
    a = a + b;

    Where a and b are integers/doubles, the CPU is not well utilized. It spends more time managing the loop than adding b to a. So if this loop is, for example, 4x (or 2x or 7x) faster than calling the delegate…

    for (int i = 0; i < 1000000000; i++)
    a += LCG_Number_Adder (a, b);

    …actually the delegate is much more than 4x slower because the loop overhead is polluting your measurement.

    At least using LCG directly has the advantage that it will work in .NET Framework 2.0; lambda.Compile() requires .NET Framework 3.5.

  10. Hi,
    My problem is rather simplistic compared to those being discussed above. However it is nonetheless frustrating. It illustrates how what I thought was a very simple matter in C# could prove to be not so simple in VB. Essentially I’ve got a generic LINQ to SQL query that doesn’t do anything but test for equality of one of the properties of a generic type (which is itself a generic type) to a supplied value.

    The query is of the form:

    Public Function GetbyID(ID as IdT) as EntityIT
    Dim q = From e In ContextEntities Where e.ID.Equals(ID) Select e
    Return DirectCast(q.Single(), EntityIT)
    End Sub

    Here ‘e’ is a generic type with the following constraints {Entitybase(of IdT),EntityIT,New} and EntityIT is an interface that inherits IEntity(of IdT)

    IEntity(of IdT) is an interface with one member relevant to this discussion, i.e. ID which is of type IdT.

    In my test environment, I’ve defined a concrete class called Customer which inherits from EntityBase(of Integer) (thus setting IdT to Integer) and implements ICustomer which inherits from IEntity(of Integer). EntityIT above becomes ICustomer.

    I then attempt to retrieve a single customer entity by Id using the above method. The VB code above fails with the following error:

    System.InvalidOperationException: {“No coercion operator is defined between types ‘Data.Tests.Customer’ and ‘Domain.Entities.EntityBase(of IdT)’.”}

    And yet, the C# equivalent of the above VB code runs perfectly:

    public GetByID(ID as IdT) as EntityIT
    {
    var q = from e in ContextEntities where e.PrimaryKey.Equals(id) select e;
    return q.Single() as EntityIT;
    }

    As you can see the two methods are exactly the same and yet one works and the other doesn’t. Anyone have any ideas why this is the case, ’cause I’m really stumped.

  11. As “the guy” who wrote the LCG-based article, I’d suggest reading Pobar’s article I reference early on, which outlines the invocation speedups in .NET 2. I don’t know the specifics of any experiments that have been run since, particularly on .NET 4′s CLR, but I can pretty much guarantee that both delegates and expression tree manipulations would be things to count on receiving attention. They are, after all, the basis for very important technologies (LINQ, DLR, etc).

    It’ll never be as fast as the bare code, but the runtime folks have motivation to do what they can to make it fast enough.

  12. Pingback: Tech, food and spirit. / C# constraints on the operators (Reloaded)

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