Branchless min/max methods in c#

Question

I've recently learned about branchless programming. I found example of branchless min method. In pesudocode it's something like this

function Max(a, b)
{
    return a * (a > b) + b * (a <= b);
}

This code works only under condition that in used language true can be casted to 1 and false to 0. In c# however it doesn't seem to work, since true and false aren't just aliases for 1 and 0, but actual logical values. Can min and max methods be implemented branchless in any other way in C#?

Answer 1

Just an FYI for anyone thinking of implementing some "speedhack" like this... The runtime and compiler are obviously already aware of optimizations like this and have already applied them for you. You don't need to reinvent the wheel. Quick benchmarks show only miniscule differences between the "fast" branchless method, naive x > y ? x : y, and Math.Max().

BenchmarkDotNet=v0.13.1, OS=Windows 10.0.22000
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET SDK=6.0.300
  [Host]     : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT
  Job-RVHKGU : .NET 6.0.5 (6.0.522.21309), X64 RyuJIT

Method	Mean	Error	StdDev	Median	Allocated
SimpleTernaryMax	96.41 ms	1.126 ms	3.025 ms	95.21 ms	480 B
BranchlessMax	98.34 ms	1.428 ms	3.884 ms	97.23 ms	480 B
BuiltInMathMax	97.14 ms	0.860 ms	2.280 ms	96.60 ms	768 B

Answer 2

Using @GuruStron's hint, here is an extension method:

public static class BoolExt {
    [StructLayout(LayoutKind.Explicit)]
    struct TBoolInt32 {
        [FieldOffset(0)]
        public bool Bool;
        [FieldOffset(0)]
        public int Int;
    }

    public static int ToInt32(this bool value) => Unsafe.As<bool, TBoolInt32>(ref value).Int;
}

Then you can use it:

public int Min(int a, int b) => a * (a < b).ToInt32() + b * (a >= b).ToInt32();

However, even with AgressiveInlining in IL this causes two calls to ToInt32 so isn't really more efficient.

Another possibility is to use the implementation of Math.Sign (not sure if it inlines so I reimplemented) to create tests that return 0 or 1:

public static class TestExt {
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    static int IntSign(int value) => (value >> 31) | (int)((uint)(-value) >> 31);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int GreaterEqual(this int a, int b) => IntSign(IntSign(a - b) + 1);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int LessThan(this int a, int b) => 1 - a.GreaterEqual(b);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int LesserEqual(this int a, int b) => IntSign(IntSign(b - a) + 1);

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int GreaterThan(this int a, int b) => 1 - a.LesserEqual(b);
}

Answer 3

You can use bitwise and shift operators like this:

int FastMax(int a, int b) {
  int diff = a - b;
  int dsgn = diff >> 31;
  return a - (diff & dsgn);
}

The >> operator is right shift and I use 31 for Int you can use 63 for long numbers.

FYI: see this link https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/operators/bitwise-and-shift-operators

Answer 4

You can use the following approach. It requires some unsafe code to cast the bool to a byte (0 or 1) which we use as an offset to choose which argument to return.

static int Min(int a, int b) => If(a < b, a, b);

static int Max(int a, int b) => If(a < b, b, a);

static T If<T>(bool condition, T then, T @else)
{
    return Unsafe.Add(ref @else, Unsafe.As<bool, byte>(ref condition));
}

You can see that it doesn't produce any branching instructions: SharpLab link.

If you're using the upcoming .NET 7, you can make Min and Max generic like this:

static T Min<T>(T a, T b) where T : IComparisonOperators<T, T, bool> =>
    If(a < b, a, b);

static T Max<T>(T a, T b) where T : IComparisonOperators<T, T, bool> =>
    If(a < b, b, a);