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#?
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://docs.microsoft.com/en-us/dotnet/csharp/language-reference/operators/bitwise-and-shift-operators
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 |
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);
}