[Code Index] by Mike Marynowski

programming for work and fun

Generic Math at Raw Operator Speed

Let's start off with a simple example - let's say you need to increment a value, but only up to its maximum possible value. If you were writing a method for a particular type like int, you might do it like this:

public static int IncrementToMax(int value)
{
    return value < int.MaxValue ? value + 1 : value;
}

With that out of the way...if you need the absolute fastest way to do this in a generic version of that method that supports all discrete number types and nullable discrete number types then this monstrosity, unfortunately, is the way you need to do it (explanation will follow, I promise):

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T IncrementToMax(T value)
{
    if (typeof(T) == typeof(char))
        return (char)(object)value! < char.MaxValue ? (T)(object)(char)((char)(object)value + 1) : value;

    if (typeof(T) == typeof(byte))
        return (byte)(object)value! < byte.MaxValue ? (T)(object)(byte)((byte)(object)value + 1) : value;

    if (typeof(T) == typeof(sbyte))
        return (sbyte)(object)value! < sbyte.MaxValue ? (T)(object)(sbyte)((sbyte)(object)value + 1) : value;

    if (typeof(T) == typeof(short))
        return (short)(object)value! < short.MaxValue ? (T)(object)(short)((short)(object)value + 1) : value;

    if (typeof(T) == typeof(ushort))
        return (ushort)(object)value! < ushort.MaxValue ? (T)(object)(ushort)((ushort)(object)value + 1) : value;

    return IncrementToMax2(value);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static T IncrementToMax2(T value)
    {
        if (typeof(T) == typeof(int))
            return (int)(object)value! < int.MaxValue ? (T)(object)((int)(object)value + 1) : value;

        if (typeof(T) == typeof(uint))
            return (uint)(object)value! < uint.MaxValue ? (T)(object)((uint)(object)value + 1) : value;

        if (typeof(T) == typeof(long))
            return (long)(object)value! < long.MaxValue ? (T)(object)((long)(object)value + 1) : value;

        if (typeof(T) == typeof(ulong))
            return (ulong)(object)value! < ulong.MaxValue ? (T)(object)((ulong)(object)value + 1) : value;

        if (typeof(T) == typeof(BigInteger))
            return (T)(object)((BigInteger)(object)value! + 1);

        return IncrementToMax3(value);
    }

    // Nullables:

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static T IncrementToMax3(T value)
    {
        if (typeof(T) == typeof(char?))
            return (char?)(object)value < char.MaxValue ? (T)(object)(char?)((char?)(object)value + 1) : value;

        if (typeof(T) == typeof(byte?))
            return (byte?)(object)value < byte.MaxValue ? (T)(object)(byte?)((byte?)(object)value + 1) : value;

        if (typeof(T) == typeof(sbyte?))
            return (sbyte?)(object)value < sbyte.MaxValue ? (T)(object)(sbyte?)((sbyte?)(object)value + 1) : value;

        if (typeof(T) == typeof(short?))
            return (short?)(object)value < short.MaxValue ? (T)(object)(short?)((short?)(object)value + 1) : value;

        if (typeof(T) == typeof(ushort?))
            return (ushort?)(object)value < ushort.MaxValue ? (T)(object)(ushort?)((ushort?)(object)value + 1) : value;

        return IncrementToMax4(value);
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static T IncrementToMax4(T value)
    {
        if (typeof(T) == typeof(int?))
            return (int?)(object)value < int.MaxValue ? (T)(object)((int?)(object)value + 1) : value;

        if (typeof(T) == typeof(uint?))
            return (uint?)(object)value < uint.MaxValue ? (T)(object)((uint?)(object)value + 1) : value;

        if (typeof(T) == typeof(long?))
            return (long?)(object)value < long.MaxValue ? (T)(object)((long?)(object)value + 1) : value;

        if (typeof(T) == typeof(ulong?))
            return (ulong?)(object)value < ulong.MaxValue ? (T)(object)((ulong?)(object)value + 1) : value;

        if (typeof(T) == typeof(BigInteger?))
            return (T)(object)((BigInteger?)(object)value + 1)!;

        throw new NotSupportedException($"'{typeof(T)}' is not a supported discrete value type.");
    }
}

It may not be pretty, and while it may not look like it, it is actually maximally optimized the way it is written. When the JIT compiler processes this method for a particular type <T>, there are a number of clever optimizations that happen which allow it to run at raw operator speed (*see appendix at the end). Other cleaner looking approaches all tend to suffer from large performance impacts that are unacceptable for number crunching, like delegate call or virtual method call overhead. Furthermore, IL emit based methods don't work on AOT (i.e. Xamarin.iOS) and compiled Expression based methods will run extremely slowly on AOT since they are interpreted and not really compiled on those platforms. This approach does not suffer from any of those problems.

The following details the JIT magic that optimizes this beast of a method into something that executes at raw operator speed:

The Explanation

1. Inlining all the methods into a single method

The [MethodImpl(MethodImplOptions.AggressiveInlining] attribute signals to the JIT that you always want the method to be inlined. Inlining is a process where the method body is moved directly into the call-sites (the places method is called) in order to avoid the overhead of calling a method. As you can see, IncrementToMax is divided into 4 pieces, but that's okay since all the pieces will be inlined together anyway. We need to do this to address a current shortcoming in the JIT (which will hopefully be addressed soon - see here) which causes it to ignore inlining requests for methods that contain too many IL instructions (even if they will ultimately compile down to only a few machine instructions) so we can't pack too much into each method. I just split up the method with trial and error and some benchmarking until it was apparent that it was actually getting inlined.

2. Conditional branch elimination

The JIT is smart enough to eliminate all the if blocks that won't execute and eliminate the if test for the one that always will. If we consider IncrementToMax<int> for example, that means that the optimizations up to this point result in something like this:

public static T IncrementToMax(T value)
{
    return (int)(object)value! < int.MaxValue ? (T)(object)((int)(object)value + 1) : value;
}

3. Cast elimination

The next clever thing the JIT does is eliminate all the redundant casts because it knows T is an int and value is an int. That leaves us with:

public static T IncrementToMax(T value)
{
    return value < int.MaxValue ? value + 1 : value;
}

4. Inlining the method into the call-site

The final thing the JIT does is inline the body of that method directly into any code that calls that method, again thanks to the AggressiveInlining request.

Appendix

Raw operator speed

This claim is true for all non-nullable value types. In runtime versions prior to .NET 5, the JIT codegen for generic nullable value types was slightly suboptimal, so there is a small performance difference between raw operators and the inlined generic method. On .NET 5+ the method runs at full operator speed for nullable types as well.

Additional .NET 5 only optimizations

If you are using .NET 5+ there are additional JIT improvements that allow it to better optimize code that is formatted in the following way without sacrificing performance, which cleans up some of the casts a little bit:

public static T IncrementToMax(T value)
{
    if (value is char charValue)
        return charValue < char.MaxValue ? (T)(object)(char)(charValue + 1) : value;

    // rest of the type operations...
}



 

 Hi, I am Mike, Owner / Technical Lead at Singulink :)

This is where I post (mostly) software development related stuff I think might be useful and interesting.

We are currently accepting software development project contracts so drop me a line if you want to chat or head over to our GitHub page to check out our open-source projects.

Posts by Date