C - 海湾合作委员会分支预测

Question

这是我的演示程序：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int cmp(const void *d1, const void *d2)
{
    int a, b;
    a = *(int const *) d1;
    b = *(int const *) d2;
    if (a > b)
        return 1;
    else if (a == b)
        return 0;
    return -1;
}
int main()
{
    int seed = time(NULL);
    srandom(seed);
    int i, n, max = 32768, a[max];
    for (n=0; n < max; n++) {
        int r = random() % 256;
        a[n] = r;
    }
    qsort(a, max, sizeof(int), cmp);
    clock_t beg = clock();
    long long int sum = 0;
    for (i=0; i < 20000; i++) 
    {
        for (n=0; n < max; n++) {
            if (a[n] >= 128)
                sum += a[n];
        }
    }
    clock_t end = clock();
    double sec = (end - beg) / CLOCKS_PER_SEC;
    printf("sec: %fn", sec);
    printf("sum: %lldn", sum);
    return 0;
}

unsorted
sec: 5.000000
sum: 63043880000
sorted
sec: 1.000000
sum: 62925420000

这是该程序的两个版本的程序集差异，一个带有qsort，一个没有：

--- unsorted.s  
+++ sorted.s    
@@ -58,7 +58,7 @@
    shrl    $4, %eax
    sall    $4, %eax
    subl    %eax, %esp
-   leal    4(%esp), %eax
+   leal    16(%esp), %eax
    addl    $15, %eax
    shrl    $4, %eax
    sall    $4, %eax
@@ -83,6 +83,13 @@
    movl    -16(%ebp), %eax
    cmpl    -24(%ebp), %eax
    jl  .L7
+   movl    -24(%ebp), %eax
+   movl    $cmp, 12(%esp)
+   movl    $4, 8(%esp)
+   movl    %eax, 4(%esp)
+   movl    -32(%ebp), %eax
+   movl    %eax, (%esp)
+   call    qsort
    movl    $0, -48(%ebp)
    movl    $0, -44(%ebp)
    movl    $0, -12(%ebp)

据我了解程序集输出，由于将值传递给qsort，排序版本只是有更多的代码，但我没有看到任何分支优化/预测/任何东西。也许我看错了方向？

Answer 1

分支预测不是你在汇编代码级别看到的东西;它是由CPU本身完成的。

Answer 2

内置功能：长__builtin_expect (long exp, long c)

您可以使用__builtin_expect为编译器提供分支预测信息。一般来说，你应该更喜欢使用实际的 配置文件反馈（-fprofile-arcs），因为程序员是 出了名的不善于预测他们的程序的实际表现。 但是，在某些应用程序中，很难收集此数据。

返回值是 exp 的值，它应该是一个积分表达式。内置的语义是，预期 exp == c .例如：

if (__builtin_expect (x, 0))
  foo ();

表示我们不希望调用foo，因为我们希望x为零。由于您仅限于 exp 的积分表达式，因此 应使用诸如

if (__builtin_expect (ptr != NULL, 1))
  foo (*ptr);

测试指针或浮点值时。

否则，分支预测由处理器确定...

分支预测

预测分支目标并启用 处理器在分支 true 之前很久就开始执行指令 执行路径已知。所有分支都利用分支预测 用于预测的单位 （BPU）。此单位预测目标地址不 仅基于分支的EIP，也基于执行 执行到达此 EIP 的路径。BPU可以 有效预测以下分支类型：

• 条件分支。

•直接呼叫和跳转。

• 间接呼叫和跳转。

•返回。

---

微架构试图通过将最可能的分支馈送到管道中并以推测方式执行来克服这个问题。

。使用各种分支预测方法。