6

看到一篇论文《将分支转化为数据依赖，避免误判分支》中的一句话。（第 6 页）

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

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

更新：如何在二分搜索中转换分支？

4

2 回答 2

13

基本想法（我想）是改变如下：

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.]

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

于 2012-07-05T17:19:26.793 回答
1

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

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

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

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

于 2016-11-03T17:58:29.880 回答