具有下限溢位的炭衬底

Question

有没有办法计算：

/** clipped(a - b) **/
unsigned char clipped_substract(unsigned char a, unsigned char b)
{
    return a > b ? a - b : 0;
}

使用一些二进制操作而不是测试？

Answer 1

/** clipped(a - b) **/
unsigned char clipped_substract(unsigned char a, unsigned char b)
{
    return a - (a+b) / 2 + getAbs(a-b) / 2;
}

unsigned int getAbs(int n)
{
    int const mask = n >> (sizeof(int) * 8 - 1);

    return ((n + mask) ^ mask);
}

Answer 2

使用clang 11.0，启用编译器优化

unsigned char clipped_substract(unsigned char a, unsigned char b)
{   
    long c = b - a;
    return ((unsigned long)c >> (sizeof(c)*8-1)) * c;
}

虽然任何替代方案所花费的时间都有显著不同，但当执行10000000迭代时，其他方法在我的机器上大约需要0.300秒<，而此解决方案大约需要0.200秒。

但这仅在使用大小大于< code>char的类型时有效，例如这里我使用< code>long。我不记得< code>char或< code>long的确切定义，但我知道在我的机器上< code>long比< code>char更宽。所以要相应调整。

基本上，我只是将减法的结果存储在更大的宽度变量中。如果结果为负数，则最高有效位将为 1 else 0。

Answer 3

原始函数编译为条件移动，不受性能问题的影响。您试图在此处执行过早的优化，这对您绝对没有好处。编写可读代码，然后对其进行分析，然后识别和优化性能瓶颈。

你说“考试会降低表现”。如果你想做这样的微优化，你应该致力于理解这些经验法则背后的原因，而不是把它们当作无条件的真理。

降低“测试”性能的是（预测失误的）控制流分支。现代CPU大量使用指令流水线，控制流分支意味着不清楚下一条指令是什么。常见的方法是CPU猜测（使用分支预测硬件/算法）分支的走向。如果它弄错了，它必须冲洗整个管道并重新填充，这会浪费循环。

好吧，有问题的代码没有这样的问题。它编译成有条件的移动:

https://godbolt.org/z/upkgok

clipped_substract(unsigned char, unsigned char):
    mov     eax, edi
    mov     edx, 0
    sub     eax, esi
    cmp     dil, sil
    cmovbe  eax, edx
    ret

您可以看到这里没有控制流分支。了解为什么条件移动不易受到分支预测失败的影响？为什么不受制于上述性能问题。

我重复一遍:编写可读的代码，然后对其进行分析，然后识别并优化性能瓶颈。您在这里尝试的是修复一个根本不存在的性能问题代码(更不用说您没有证明这个代码的性能甚至与您的程序性能相关)。