关于减少分支误预测

Question

我在一篇论文中看到一句话“将分支转化为数据依赖，以避免分支预测错误”。 （第6页）

我想知道如何将代码从分支更改为数据依赖。

这是论文：http://www.adms-conf.org/p1-SCHLEGEL.pdf

更新：如何变换二分查找中的分支？

Answer 1

基本想法（我认为）是改变以下内容：

if (a>b)
    return "A is greater than B";
else
    return "A is less than or equal to B";

进入：

static char const *strings[] = {
    "A is less than or equal to B", 
    "A is greater than B"
};

return strings[a>b];

对于二分搜索中的分支，让我们考虑“正常”二分搜索的基本思想，它通常看起来（至少模糊地）像这样：

while (left < right) {
    middle = (left + right)/2;
    if (search_for < array[middle])
        right = middle;
    else
        left = middle;
}

我们可以用几乎相同的方式摆脱这里的大部分分支：

size_t positions[] = {left, right};

while (left < right) {
    size_t middle = (left + right)/2;

    positions[search_for >= array[middle]] = middle;
}

[对于通用代码，请使用

left + (right-left)/2

而不是

(left+right)/2

。]

当然，我们仍然有循环本身的分支，但我们通常不太关心这一点——该分支非常容易预测，所以即使我们确实消除了它，这样做也不会获得什么好处一条规则。

Answer 2

删除分支并不总是最佳的，即使（尤其是）像这样的简单二元条件也是如此。我之前曾考虑过在各种情况下以类似的方式删除分支。在遇到循环中带有条件分支的代码比等效的无分支代码运行得更快的实例后，我对处理器执行策略进行了一些研究。

我知道 ARM 指令集有条件指令，这可以使条件分支比论文中的无分支代码更快，但我正在研究 intel（并且该分支不是 cmove 可以处理的）的）。事实证明，包括英特尔在内的现代 CPU 有时会将普通指令转换为条件指令：如果分支的两个端点足够短，它们就会使用急切执行。也就是说，CPU 会将两条可能的路径放入管道中并执行它们，并且只有在已知条件后才保留正确的结果。这避免了在不必索引数组的情况下错误预测的可能性。请参阅 https://en.wikipedia.org/wiki/Speculative_execution#Variants 了解更多信息。

即使在汇编中，也需要对处理器有大量详细的了解才能为其编写最佳代码。这使得“原始”实现有时比忽略某些 CPU 特性的手工优化实现更快。优化编译器也会发生同样的事情：有时编写更复杂的“优化”代码会破坏编译器的一些优化，并导致可执行文件比编译器可以完全优化的简单实现慢。

当有疑问且性能至关重要且有时间时，通常最好尝试两种方法，看看哪种更快！