不分支实现 f(x) := 若 x == 0 则为 0，否则为 (x * log(x))

Question

我有这个C函数：

double f(int x)
{
    if (x <= 0)
        return 0.0;
    else
        return x * log(x);
}

我正在一个紧密循环中调用它，并希望消除分支以查看是否可以提高性能。

我不能使用这个：

double f(int x)
{
    return x * log(x);
}

因为当 x == 0 时它会返回 NaN （这种情况大约占总数的25%）。有没有另一种实现方式，可以使其在 x == 0 时返回 0，但仍然能够消除分支？（我不太关心负数输入，因为这些是错误，而零不是。）

- finnw

---

你确实有一个分段函数。很难想象在没有对这些部分的条件进行评估的情况下如何进行评估。但是请检查您的汇编代码，它可能会用条件移动替换分支。 - Kerrek SB

这个计算的性能将完全受到“对数”函数的支配。因此，你希望在其中加上这个分支，因为如果你打算丢弃答案，就不想调用“对数”函数。 - zwol

对于x86-64，对数被实现为一个函数。不分支但总是调用昂贵的函数可能比分支并偶尔不调用它带来更多的开销。 - fuz

为了测试性能，只需将该函数替换为return x * log(x)。这肯定会给出错误的答案，但它不会比您可能想出的无分支代码更慢。因此，除非比您拥有的代码快得多，否则可以停止了。没有必要实际想出无分支代码，因为您已经确定它对提高性能没有帮助。 - Steve Jessop

@meagar：小值（≤20）比较大的值更常见，所以如果我无论如何都要使用分支，将它们保存在表中可能是值得的。这是你考虑的吗？ - finnw

Answer 1

首先需要注意log(1) = 0。然后你可以将问题写成x * log(y)，其中如果x <= 0，y = 1，否则y等于x；如果y = 1，则x无关紧要，因为log(y)=0。

类似于y = (x > 0)*x + (x <= 0)即可解决此问题，然后：

double f(int x) {
    return x * log((x > 0)*x + (x <= 0));
}

这只取决于log(1)和四个整数运算是否比分支更糟糕。

- Hodapp

---

可以。正如你所说，它可能比分支慢得多。但是它确实为OP的问题提供了完美的答案，所以+1。 - Tim

我很好奇log(1)是否是一个特殊情况，可以提前退出。即使如此，两个比较、加法和乘法的操作可能比分支语句更耗时。 - Hodapp

当然，这取决于编译器是否实际上是无分支代码，但它具有看起来可能是的好特性;-) - Steve Jessop

但编译器从哪里获取这个分支呢？从比较运算符吗？ - Hodapp

@Hodapp：正确。x86有setle和setg条件指令，ARM允许所有指令都可以是条件的，但并非每种架构都支持。 - Steve Jessop

一个小变体是缓存比较结果：double f(int x) { int b = x > 0; return x * log(b*x + (1-b)); }。在这里几乎肯定没有区别，但在条件 b 更复杂的其他情况下可能会有所帮助。 - wren romano

Answer 2

编译器扩展可以在这方面提供帮助。在GCC中，您可以执行以下操作：

if(__builtin_expect(x > 0, 1)) {
    return x * log(x);
}
return 0.0;

GCC将生成有利于x > 0 == 1分支的机器代码。

如果您不关心负数，则可以将x == 0视为不太可能的分支：

if(__builtin_expect(x == 0, 0)) {
    return 0.0;
}
return x * log(x);

如果您不使用GCC，您应该查看编译器文档并查看它是否提供类似的功能。

请注意，这仍然不是无分支的。只是可能分支所需的时间更少。

- Nikos C.

---

当 x 为0时，“大约25%的时间为真”，我认为偏向于 x > 0 是没有帮助的。 - Pascal Cuoq

@PascalCuoq 如果 x 小于等于0的概率为25％，那么大于0的概率为75％。所以这就是偏爱的情况。至少这就是我理解问题的方式。 - Nikos C.

这将消除更频繁情况下的跳转，但不会消除分支，因为我理解该术语。这可能仍有助于OP，所以我会点赞。 - user4815162342

Answer 3

任何无分支代码都必须包含对“正常”情况的 x * log(x) 计算。

因此，在尝试设计无分支代码之前，先测量 x * log(x) 的速度。除非它比您已有的代码快得多，否则在这里没有什么显著的收益。我怀疑它不会比现有代码更快。

- Steve Jessop