0

这是我的演示程序：

#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: %f\n", sec);
    printf("sum: %lld\n", 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，但我没有看到任何分支优化/预测/任何东西。也许我看错了方向？

4

2 回答 2

5

分支预测不是您在汇编代码级别看到的；它是由 CPU 自己完成的。

于 2012-07-01T14:52:29.340 回答
0

内置函数：long__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);

在测试指针或浮点值时。

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

分支预测预测分支目标并使处理器能够在知道分支真实执行路径之前很久就开始执行指令。所有分支都使用分支预测单元 (BPU) 进行预测。该单元不仅根据分支的 EIP，还根据执行到达该 EIP 的执行路径来预测目标地址。BPU 可以有效地预测以下分支类型：

• 条件分支。

• 直接呼叫和跳转。

• 间接调用和跳转。

• 退货。

微架构试图通过将最可能的分支输入管道并推测性地执行它来克服这个问题。

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

于 2017-07-24T20:52:57.873 回答