Generic Method Dispatch

July 9, 2010

no comments

Inside a method that is generic in T you may invoke on an expression of type T any of the System.Object methods, or methods that belong to the class or interface constraints of T. Because the JIT does not invoke a full-blown compiler when generating code for a specific type T, there is a significant difference in performance when invoking methods on value types in this fashion.

Assume the following value type describes a point in two-dimensional space. The value type overrides ValueType.Equals and provides an overload with the same name, as per the value type best practices:

struct Point
    public int X, Y;

    public override bool Equals(object obj)
        if (obj == null)
            return false;
        if (!(obj is Point))
            return false;
        Point other = (Point) obj;
        return Equals(other);

    public bool Equals(Point other)
        return X == other.X && Y == other.Y;


The following code is functionally correct, but invokes the “wrong” version of Point.Equals when used with T=Point:

class Collection<T>
    private readonly T[] _elements = ...;
    public bool Contains(T elem)

        foreach (T inst in _elements)
            if (inst.Equals(elem))
                return true;
        return false;

How do I know that? To begin with, I could place a breakpoint inside the two Equals methods and see which one was invoked. Alternatively, I could fire up WinDbg and look at the JITted code:

D:\Scratch\CallingGenericMethod\Program.cs @ 25:

003d02c5 b9d0382900      mov     ecx,2938D0h (MT: CallingGenericMethod.Point)

003d02ca e8511debff      call    00282020 (JitHelp: CORINFO_HELP_NEWSFAST)

003d02cf 8945d4          mov     dword ptr [ebp-2Ch],eax

003d02d2 8d45f0          lea     eax,[ebp-10h]

003d02d5 8945d0          mov     dword ptr [ebp-30h],eax

003d02d8 8b7dd4          mov     edi,dword ptr [ebp-2Ch]

003d02db 83c704          add     edi,4

003d02de 8d7508          lea     esi,[ebp+8]

003d02e1 f30f7e06        movq    xmm0,mmword ptr [esi]

003d02e5 660fd607        movq    mmword ptr [edi],xmm0

003d02e9 8b45d4          mov     eax,dword ptr [ebp-2Ch]

003d02ec 8945cc          mov     dword ptr [ebp-34h],eax

003d02ef 8b4dd0          mov     ecx,dword ptr [ebp-30h]

003d02f2 8b55cc          mov     edx,dword ptr [ebp-34h]

003d02f5 ff15a4382900    call    dword ptr ds:[2938A4h] (CallingGenericMethod.Point.Equals(System.Object), mdToken: 06000004)

003d02fb 8945e0          mov     dword ptr [ebp-20h],eax

003d02fe 837de000        cmp     dword ptr [ebp-20h],0

003d0302 0f94c0          sete    al

003d0305 0fb6c0          movzx   eax,al

003d0308 8945e4          mov     dword ptr [ebp-1Ch],eax

Note the boxing operation in the first two lines, which is also reflected in the method’s IL (from Reflector):

L_001c: ldloca.s inst

L_001e: ldarg.1

L_001f: box !T

L_0024: constrained !T

L_002a: callvirt instance bool [mscorlib]System.Object::Equals(object)

Also note that the method is not dispatched virtually, because the JIT can convince itself that the value type is sealed.

So what, you may ask. Well, unfortunately, to call the virtual Point.Equals method the parameter must be boxed, incurring a memory allocation for each iteration of the loop. This will cost us dearly.

What can we do, then? We could use the IEquatable<T> interface as a generic constraint on T, and try using the Equals method from that interface. In other words, the Point struct should now implement the IEquatable<Point> interface and the Collection<T> class should have a constraint “where T : IEquatable<T>” on its generic type parameter. Now, the IL code does not contain a “box” instruction, and the JITted code changes accordingly to this:

D:\Scratch\CallingGenericMethod\Program.cs @ 25:

003d02c2 8d4508          lea     eax,[ebp+8]

003d02c5 83ec08          sub     esp,8

003d02c8 f30f7e00        movq    xmm0,mmword ptr [eax]

003d02cc 660fd60424      movq    mmword ptr [esp],xmm0

003d02d1 8d4df0          lea     ecx,[ebp-10h]

003d02d4 ff15b8382b00    call    dword ptr ds:[2B38B8h] (CallingGenericMethod.Point.Equals(CallingGenericMethod.Point), mdToken: 06000005)

003d02da 8945e0          mov     dword ptr [ebp-20h],eax

003d02dd 837de000        cmp     dword ptr [ebp-20h],0

003d02e1 0f94c0          sete    al

003d02e4 0fb6c0          movzx   eax,al

003d02e7 8945e4          mov     dword ptr [ebp-1Ch],eax

Now there’s no boxing—the value type is copied onto the stack (using movq) and the method is invoked directly. It is also the “right” method—the Equals(Point) overload and not the Equals(Object) override.

Does it really matter, performance-wise? Indeed it does. I just ran a quick test calling the Contains method a 10,000 times in a row on a collection with 10,000 points, looking for an element that isn’t there (in other words, invoking the Equals method for each element). With the IEquatable<T> constraint, it took 97ms. Without the constraint, it took 941ms.

While these results should be taken with a grain of salt, there’s an order of magnitude difference here. Not negligible at all.

Add comment
facebook linkedin twitter email

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>