C# 中的无分支最小/最大方法

Question

我最近了解了无分支编程。我找到了无分支最小方法的示例。在伪代码中它是这样的

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

此代码仅在使用的语言中 true 可以转换为 1 和 false 转换为 0 的条件下才有效。但在 c# 中，它似乎不起作用，因为 true 和 false 不仅仅是 1 和 0 的别名，而是实际的逻辑值。min 和 max 方法可以在 C# 中以任何其他方式实现无分支吗？

Answer 1

对于任何想要实现这样的“speedhack”的人来说，仅供参考...运行时和编译器显然已经意识到这样的优化，并且已经为您应用了它们。您不需要重新发明轮子。快速基准测试仅显示“快速”无分支方法、naivex > y ? x : y和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

方法	意思是	错误	标准差	中位数	已分配
简单三元最大	96.41 毫秒	1.126 毫秒	3.025毫秒	95.21 毫秒	480乙
无分支最大	98.34 毫秒	1.428 毫秒	3.884 毫秒	97.23 毫秒	480乙
内置MathMax	97.14 毫秒	0.860 毫秒	2.280 毫秒	96.60 毫秒	768乙

Answer 2

使用@GuruStron的提示，这里是一个扩展方法：

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;
}

然后你就可以使用它：

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

然而，即使AgressiveInlining在 IL 中，这也会导致两次调用ToInt32so 并不是真正更有效。

另一种可能性是使用Math.Sign（不确定它是否内联，所以我重新实现）的实现来创建返回 0 或 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);
}