Gapotchenko.FX.Runtime.CompilerServices.Intrinsics 2022.1.4

Overview

Gapotchenko.FX.Runtime.CompilerServices.Intrinsics module allows to define and compile intrinsic functions. They can be used in hardware-accelerated implementations of algorithms.

Example

Suppose we are trying to fix the performance bottleneck in the following algorithm:

class BitOperations
{
    // Returns the base 2 logarithm of a specified number.
    public static int Log2_Trivial(uint value)
    {
        int r = 0;
        while ((value >>= 1) != 0)
            ++r;
        return r;
    }
}

log₂ seems to be a trivial operation but it often becomes a serious bottleneck in path-finding or cryptographic algorithms. We can do better here if we switch to a table lookup:

class BitOperations
{
    // "Bit Twiddling Hacks" by Sean Eron Anderson:
    // http://graphics.stanford.edu/~seander/bithacks.html

    static readonly int[] m_Log2DeBruijn32 =
    {
         0,  9,  1, 10, 13, 21,  2, 29,
        11, 14, 16, 18, 22, 25,  3, 30,
         8, 12, 20, 28, 15, 17, 24,  7,
        19, 27, 23,  6, 26,  5,  4, 31
    };

    public static int Log2_DeBruijn(uint value)
    {
        // Round down to one less than a power of 2.
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        value |= value >> 16;

        var index = (value * 0x07C4ACDDU) >> 27;
        return m_Log2DeBruijn32[index];
    }
}

This is a vast improvement over previous version but we can do even better.

Meet the Intel 80386, a 32-bit microprocessor introduced in 1985. It brought the Bit Scan Reverse (BSR) instruction that does exactly what we want to achieve with Log2 using just a small fraction of cycles.

Chances are your machine runs on a descendant of that influential CPU, be it AMD Ryzen or Intel Core. So how can we use the BSR instruction from .NET?

This is why Gapotchenko.FX.Runtime.CompilerServices.Intrinsics class exists. It provides an ability to define intrinsic implementation of a method with MachineCodeIntrinsicAttribute. Let's see how:

using Gapotchenko.FX.Runtime.CompilerServices;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;

class BitOperations
{
    // Use static constructor to ensure that intrinsic methods are initialized (compiled) before they can be used
    static BitOperations() => Intrinsics.InitializeType(typeof(BitOperations));

    static readonly int[] m_Log2DeBruijn32 =
    {
         0,  9,  1, 10, 13, 21,  2, 29,
        11, 14, 16, 18, 22, 25,  3, 30,
         8, 12, 20, 28, 15, 17, 24,  7,
        19, 27, 23,  6, 26,  5,  4, 31
    };

    // Define machine code intrinsic for the method
    [MachineCodeIntrinsic(Architecture.X64, 0x0f, 0xbd, 0xc1)]  // BSR EAX, ECX
    [MethodImpl(MethodImplOptions.NoInlining)]
    public static int Log2_Intrinsic(uint value)
    {
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        value |= value >> 16;

        var index = (value * 0x07C4ACDDU) >> 27;
        return m_Log2DeBruijn32[index];
    }
}

Log2_Intrinsic method defines a custom attribute that provides a machine code for BSR EAX, ECX instruction. Machine code is tied to CPU architecture and this is reflected in the attribute as well.

Please note that besides using MachineCodeIntrinsicAttribute to define method intrinsic implementations, BitOperations class should use a static constructor to ensure that corresponding methods are initialized (compiled) before they are called.

Here are the execution times of all three implementations (lower is better):

Log2_Intrinsic is a clear winner.

Intrinsic compiler may or may not apply machine code to a method depending on current app host environment. When intrinsic is not applied, the original method implementation is used, thus providing a graceful, albeit less performant, fallback.