关于减少分支未命中预测

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