performance - 通过提前计算条件来避免停顿管道

Question

在谈论 ifs 的性能时，我们通常会谈论错误预测如何使管道停滞。我看到的推荐解决方案是:

对于通常只有一个结果的条件，请相信分支预测器；或

如果合理可能，避免使用一点点魔法进行分支；或

在可能的情况下进行有条件的移动。

我找不到的是我们是否可以尽早计算条件以在可能的情况下提供帮助。所以，而不是:

... work
if (a > b) {
    ... more work
}

做这样的事情:

bool aGreaterThanB = a > b;
... work
if (aGreaterThanB) {
    ... more work
}

像这样的事情是否可以完全避免这种条件下的停顿(取决于管道的长度以及我们可以在 bool 和 if 之间放置的工作量)？它不必像我写的那样，但是 有没有办法尽早评估条件，这样 CPU 就不必尝试和预测分支 ?

另外，如果这有帮助，编译器可能会做些什么吗？

Answer 1

是 ，让分支条件尽可能早地计算可能是有益的，这样任何错误预测都可以提前解决，管道的前端部分可以提前开始重新填充。在最好的情况下，如果已经有足够的工作在进行中以完全隐藏前端气泡，则可以避免错误预测。

不幸的是，在乱序的 CPU 上， early 有一个有点微妙的定义，因此让分支尽早解决并不像在源代码中移动行那么简单 - 您可能必须对方式进行更改条件计算。

什么不起作用

不幸的是，更早的不是指条件/分支在源文件中的位置，也不是指与比较或分支对应的汇编指令的位置。因此，从根本上讲，它主要 7 不像您的示例那样工作。

即使源级定位很重要，它也可能在您的示例中不起作用，因为:

您已将条件的评估向上移动并将其分配给 bool ，但不是测试(< 操作符)可以预测错误，而是后续的条件分支:毕竟，这是分支预测错误。在你的例子中，分支在两个地方都在同一个地方:它的形式只是从 if (a > b) 改变了。至 if (aGreaterThanB) .

除此之外，您转换代码的方式不太可能欺骗大多数编译器。优化编译器不会按照您编写的顺序逐行生成代码，而是根据源代码级别的依赖关系安排他们认为合适的事情。提早提出条件可能会被忽略，因为编译器希望将检查放在它自然去的地方:大约在具有标志寄存器的体系结构上的分支之前。

例如，请考虑以下两个简单函数的实现，它们遵循您建议的模式。第二个函数将条件移动到函数的顶部。

int test1(int a, int b) {
    int result = a * b;
    result *= result;
    if (a > b) {
        return result + a;
    }
    return result + b * 3;
}

int test2(int a, int b) {
    bool aGreaterThanB = a > b;
    int result = a * b;
    result *= result;
    if (aGreaterThanB) {
        return result + a;
    }
    return result + b * 3;
}

我检查了 gcc、clang2 和 MSVC，并且都编译了这两个函数 identically (不同编译器的输出不同，但对于每个编译器，两个函数的输出相同)。例如编译 test2与 gcc导致:

test2(int, int):
  mov eax, edi
  imul eax, esi
  imul eax, eax
  cmp edi, esi
  jg .L4
  lea edi, [rsi+rsi*2]
.L4:
  add eax, edi
  ret

cmp指令对应于 a > b条件，并且 gcc 已将其移回所有“工作”并将其放在 jg 旁边这是条件分支。

什么工作

因此，如果我们知道在源代码中对操作顺序的简单操作不起作用，那么什么起作用呢？事实证明，您可以在数据流图中“向上”移动分支条件的任何操作都可以通过允许更早地解决错误预测来提高性能。我不会深入研究现代 CPU 如何依赖数据流，但您可以找到 brief overview here最后附有进一步阅读的提示。

遍历链表

这是一个涉及链表遍历的真实示例。

考虑将所有值相加到一个以空字符结尾的链表的任务，该链表还将其 length1 存储为链表头结构的成员。链表实现为一个 list_head对象和零个或多个列表节点(具有单个 int value 有效负载)，定义如下:

struct list_node {
    int value;
    list_node* next;
};

struct list_head {
    int size;
    list_node *first;
};

规范搜索循环将使用 node->next == nullptr sentinel 在最后一个节点判断是否已经到达链表的末尾，像这样:

long sum_sentinel(list_head list) {
    int sum = 0;
    for (list_node* cur = list.first; cur; cur = cur->next) {
        sum += cur->value;
    }
    return sum;
}

这就像你得到的一样简单。

但是，这会将结束求和的分支(第一个 cur == null )放在节点到节点指针追逐的末尾，这是数据流图中最长的依赖项。如果此分支预测错误，则错误预测的解决将发生“晚”，并且前端气泡将直接添加到运行时。

另一方面，您可以通过显式计算节点来进行求和，如下所示:

long sum_counter(list_head list) {
    int sum = 0;
    list_node* cur = list.first;
    for (int i = 0; i < list.size; cur = cur->next, i++) {
        sum += cur->value;
    }
    return sum;
}

将此与哨兵解决方案进行比较，似乎我们增加了额外的工作:我们现在需要初始化、跟踪和递减 count4。然而，关键是这个递减依赖链非常短，所以它会“跑在”指针追逐工作之前，并且错误预测会提前发生，而仍然有有效的剩余指针追逐工作要做，可能有一个运行时的巨大改进。

让我们实际试试这个。首先，我们检查两个解决方案的程序集，因此我们可以验证没有任何意外发生:

<sum_sentinel(list_head)>:
test   rsi,rsi
je     1fe <sum_sentinel(list_head)+0x1e>
xor    eax,eax
loop:
add    eax,DWORD PTR [rsi]
mov    rsi,QWORD PTR [rsi+0x8]
test   rsi,rsi
jne    loop
cdqe   
ret    


<sum_counter(list_head)>:
test   edi,edi
jle    1d0 <sum_counter(list_head)+0x20>
xor    edx,edx
xor    eax,eax
loop:
add    edx,0x1
add    eax,DWORD PTR [rsi]
mov    rsi,QWORD PTR [rsi+0x8]
cmp    edi,edx
jne    loop:
cdqe   
ret    

正如预期的那样，哨兵方法稍微简单一些:在设置期间少一条指令，在循环中少一条指令.

事实上，当预测影响可以忽略不计时，在对短列表或长列表求和时，循环的性能几乎相同。对于长列表，分支预测影响自动很小，因为到达列表末尾时的单个错误预测会在许多节点上分摊，并且对于 L1 中包含的列表，每个节点的运行时间几乎恰好达到 4 个周期，这就是我们期望英特尔的最佳情况下 4 周期加载到使用延迟。

对于短列表，如果列表的模式是可预测的，则分支错误预测可以忽略不计:要么始终相同，要么循环一段时间(如果预测良好，可以是 1000 或更多!)。在这种情况下，当对许多短列表求和时，每个节点的时间可以少于 4 个周期，因为多个列表可以同时运行(例如，如果汇总一个列表数组)。在任何情况下，两种实现的性能几乎相同。例如，当列表总是有 5 个节点时，使用任一实现对一个列表求和的时间约为 12 个周期:

** Running benchmark group Tests written in C++ **
                     Benchmark   Cycles   BR_MIS
       Linked-list w/ Sentinel    12.19     0.00
          Linked-list w/ count    12.40     0.00

让我们通过更改 list generation code 将分支预测添加到组合中创建平均长度为 5，但实际长度均匀分布在 [0, 10] 中的列表.求和代码不变:只有输入不同。随机列表长度的结果:

** Running benchmark group Tests written in C++ **
                     Benchmark   Cycles   BR_MIS
       Linked-list w/ Sentinel    43.87     0.88
          Linked-list w/ count    27.48     0.89

BR_MIS列显示，正如预期的那样，我们每个 list6 都会得到近一个分支预测错误，因为循环导出是不可预测的。

然而，哨兵算法现在需要约 44 个周期，而计数算法需要约 27.5 个周期。计数算法大约快 16.5 个周期。您可以使用列表长度和其他因素，并更改绝对时间，但增量几乎总是在 16-17 个周期左右，这与最近 Intel 的分支预测错误惩罚大致相同并非巧合!通过及早解决分支条件，我们避免了前端泡沫，在那里什么也不会发生。

提前计算迭代次数

另一个例子是类似于计算浮点值的循环，比如泰勒级数近似，其中终止条件取决于计算值的某个函数。这与上面的效果相同:终止条件取决于慢循环携带的依赖关系，因此它与值本身的计算一样慢。如果导出是不可预测的，您将在导出时遭遇失速。

如果您可以更改它以预先计算迭代计数，您可以使用解耦整数计数器作为终止条件，避免气泡。即使预先计算增加了一些时间，它仍然可以提供整体加速(无论如何，计算可以与循环的第一次迭代并行运行，因此通过查看您所期望的成本可能要低得多在其延迟)。

1 MIPS 是一个有趣的异常(exception)，这里没有标志寄存器 - 测试结果直接存储到通用寄存器中。

2 Clang 以无分支的方式编译了这个和许多其他变体，但它仍然很有趣，因为您仍然拥有相同的测试指令和条件移动(代替分支)的结构。

3 像 C++11 std::list .

4 事实证明，在 x86 上，由于 dec 的方式，两种方法之间的每个节点工作实际上非常相似。隐式设置零标志，所以我们不需要额外的 test指令，而 mov在指针追逐中使用没有，所以计数器方法有一个额外的 dec而哨兵方法有一个额外的测试，使它成为一个洗涤。

5 虽然这部分只是因为 gcc 没有设法将递增的 for 循环转换为递减的循环以利用 dec设置零标志，避免 cmp .也许较新的 gcc 版本做得更好。另见脚注 4。

6 我猜这比 1.0 更接近 0.9，因为也许分支预测器仍然得到长度 = 10 大小写正确，因为一旦循环 9 次，下一次迭代将始终退出。不太合成/精确的分布不会表现出这一点。

7 我之所以这么说，主要是因为在某些情况下，您可能会通过此类源代码或程序集级别的重新排序来节省一两个周期，因为此类事情可能会对乱序处理器中的执行顺序产生轻微影响，因此执行顺序也是受装配顺序的影响，但仅在数据流图的约束范围内。另见 this comment .