Gapotchenko.FX.Runtime.CompilerServices.Intrinsics 2022.2.7 The ID prefix of this package has been reserved for one of the owners of this package by NuGet.org. Prefix Reserved

.NET 5.0 .NET Core 2.0 .NET Standard 2.0 .NET Framework 4.6
Install-Package Gapotchenko.FX.Runtime.CompilerServices.Intrinsics -Version 2022.2.7
dotnet add package Gapotchenko.FX.Runtime.CompilerServices.Intrinsics --version 2022.2.7
<PackageReference Include="Gapotchenko.FX.Runtime.CompilerServices.Intrinsics" Version="2022.2.7" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add Gapotchenko.FX.Runtime.CompilerServices.Intrinsics --version 2022.2.7
The NuGet Team does not provide support for this client. Please contact its maintainers for support.
#r "nuget: Gapotchenko.FX.Runtime.CompilerServices.Intrinsics, 2022.2.7"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. Copy this into the interactive tool or source code of the script to reference the package.
// Install Gapotchenko.FX.Runtime.CompilerServices.Intrinsics as a Cake Addin
#addin nuget:?package=Gapotchenko.FX.Runtime.CompilerServices.Intrinsics&version=2022.2.7

// Install Gapotchenko.FX.Runtime.CompilerServices.Intrinsics as a Cake Tool
#tool nuget:?package=Gapotchenko.FX.Runtime.CompilerServices.Intrinsics&version=2022.2.7
The NuGet Team does not provide support for this client. Please contact its maintainers for support.

Overview

The module allows to define and compile intrinsic functions. They can be used in hardware-accelerated implementations of various performance-sensitive 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<sub>2</sub> 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];
    }
}

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

Method Mean Error StdDev
Log2_Trivial 4.587 ns 0.0325 ns 0.0288 ns
Log2_DeBruijn 1.256 ns 0.0068 ns 0.0063 ns

This is a vast improvement over the 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 the same what we want to achieve by Log2 using just a small fraction of CPU cycles.

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

This is why Gapotchenko.FX.Runtime.CompilerServices.Intrinsics class exists. It provides the ability to define an 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 the corresponding methods are initialized (compiled) before they are called.

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

Method Mean Error StdDev
Log2_Trivial 4.587 ns 0.0325 ns 0.0288 ns
Log2_DeBruijn 1.256 ns 0.0068 ns 0.0063 ns
Log2_Intrinsic 1.038 ns 0.0660 ns 0.0947 ns

Log2_Intrinsic is a clear winner.

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

Commonly Used Types

  • Gapotchenko.FX.Runtime.CompilerServices.IntrinsicServices
  • Gapotchenko.FX.Runtime.CompilerServices.MachineCodeIntrinsicAttribute

Other Modules

Let's continue with a look at some other modules provided by Gapotchenko.FX:

Symbol ✱ denotes an advanced module.
Symbol ✱✱ denotes an expert module.

Or take a look at the full list of modules.

Product Versions
.NET net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows net7.0
.NET Core netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1
.NET Standard netstandard2.0 netstandard2.1
.NET Framework net46 net461 net462 net463 net47 net471 net472 net48
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen40 tizen60
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.

NuGet packages (1)

Showing the top 1 NuGet packages that depend on Gapotchenko.FX.Runtime.CompilerServices.Intrinsics:

Package Downloads
Gapotchenko.FX.Numerics The ID prefix of this package has been reserved for one of the owners of this package by NuGet.org.

The module provides hardware-accelerated operations for numeric data types.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
2022.2.7 132 5/1/2022
2022.2.5 81 5/1/2022
2022.1.4 117 4/6/2022
2021.2.21 102 1/21/2022
2021.2.20 92 1/17/2022
2021.1.5 284 7/6/2021
2020.2.2-beta 291 11/21/2020
2020.1.15 422 11/5/2020
2020.1.9-beta 278 7/14/2020
2020.1.8-beta 291 7/14/2020
2020.1.7-beta 308 7/14/2020
2020.1.1-beta 448 2/11/2020
2019.3.7 450 11/4/2019
2019.2.20 495 8/13/2019