c - 单个 sqrt() 的运行速度如何比放入 for 循环时慢两倍

Question

我正在做一个实验来分析用 C 代码计算单个 sqrt 所花费的时间。我有两个策略。

一种是直接测量单个sqrt调用，另一种是在for循环中多次执行sqrt，然后计算平均值。 C代码非常简单，如下所示:

long long readTSC(void);

int main(int argc, char** argv)
{
    int    n = atoi(argv[1]);
    //v is input of sqrt() making sure compiler won't 
    //precompute the result of sqrt(v) if v is constant
    double v = atof(argv[2]);. 
    long long tm;            //track CPU clock cycles
    double x;                //result of sqrt()
    //-- strategy I ---
    tm = readTSC();     //A function that uses rdtsc instruction to get the number of clock cycles from Intel CPU
    x  = sqrt(v);
    tm = readTSC() - tm;
    printf("x=%15.6\n",x);   //make sure compiler won't optimize out the above sqrt()
    printf("%lld clocks\n",tm);
    double sum = 0.0;
    int i;

    //-- strategy II --
    tm = readTSC();
    for ( i = 0; i < n; i++ )
        sum += sqrt((double) i);
    tm = readTSC() - tm;

    printf("%lld clocks\n",tm);
    printf("%15.6e\n",sum);
    return 0;
}

long long readTSC(void)
{
 /* read the time stamp counter on Intel x86 chips */
  union { long long complete; unsigned int part[2]; } ticks;
  __asm__ ("rdtsc; mov %%eax,%0;mov %%edx,%1"
        : "=mr" (ticks.part[0]),
          "=mr" (ticks.part[1])
        : /* no inputs */
        : "eax", "edx");
  return ticks.complete;
}

在运行代码之前，我预计策略一的计时结果可能会比策略二的计时结果略小，因为策略二还计算了for循环和求和所产生的开销。

我在没有 O3 优化的情况下使用以下命令在 Intel Xeon E5-2680 2.7GHz 机器上编译我的代码。

gcc -o timing -lm timing.c

然而，结果显示策略I大约需要40个时钟周期，而策略II平均需要21.8个时钟周期，几乎是前者的一半。

为了方便大家引用，我也把相关的汇编代码贴在了下面，并附上了一些注释。根据计时结果，我想到每个 for 迭代执行两个 sqrt()。但是我很难从汇编代码中看出 CPU 是如何并行执行两个 sqrt() 的调用的？

call    atof
cvtsi2ss    %eax, %xmm0
movss   %xmm0, -36(%rbp)

//-- timing single sqrt ---
call    readTSC
movq    %rax, -32(%rbp)
movss   -36(%rbp), %xmm1
cvtps2pd    %xmm1, %xmm1
//--- sqrtsd instruction
sqrtsd  %xmm1, %xmm0
ucomisd %xmm0, %xmm0
jp  .L8
je  .L4
.L8:
movapd  %xmm1, %xmm0
//--- C function call sqrt()
call    sqrt
.L4:
movsd   %xmm0, -72(%rbp)
movq    -72(%rbp), %rax
movq    %rax, -24(%rbp)
call    readTSC
//-- end of timing single sqrt ---

subq    -32(%rbp), %rax
movq    %rax, -32(%rbp)
movl    $.LC0, %eax
movsd   -24(%rbp), %xmm0
movq    %rax, %rdi
movl    $1, %eax
call    printf
movl    $.LC1, %eax
movq    -32(%rbp), %rdx
movq    %rdx, %rsi
movq    %rax, %rdi
movl    $0, %eax
call    printf
movl    $0, %eax
movq    %rax, -16(%rbp)

call    readTSC
//-- start of for loop----
movq    %rax, -32(%rbp)
movl    $0, -4(%rbp)
jmp .L5
.L6:
//(double) i
cvtsi2sd    -4(%rbp), %xmm0
//-- C function call sqrt()
call    sqrt
movsd   -16(%rbp), %xmm1
//add sqrt(i) to sum (%xmm0)
addsd   %xmm1, %xmm0
movsd   %xmm0, -16(%rbp)
//i++
addl    $1, -4(%rbp)
.L5:
movl    -4(%rbp), %eax
//check i<n
cmpl    -40(%rbp), %eax
jl  .L6
//-- end of for loop--
//you can skip the rest of the part.
call    readTSC
subq    -32(%rbp), %rax
movq    %rax, -32(%rbp)
movl    $.LC1, %eax
movq    -32(%rbp), %rdx
movq    %rdx, %rsi
movq    %rax, %rdi
movl    $0, %eax
call    printf
movl    $.LC3, %eax
movsd   -16(%rbp), %xmm0
movq    %rax, %rdi
movl    $1, %eax
call    printf

Answer 1

E5-2680 是一款 Sandy Bridge CPU，SQRTSD 的延迟和倒数吞吐量均为 10 到 21 个周期/指令。因此无论是否循环，您都应该测量接近观察到的 21.8 个循环的值。 GLIBC 中的 sqrt 函数只是检查参数的符号，并安排非负分支通过分支预测推测性地执行，这反过来又是对 __ieee754_sqrt 的调用，它本身是简单的内联汇编例程，在 x86-64 系统上发出 sqrtsd %xmm0, %xmm0。

CPU 使用寄存器重命名来处理数据相关性。因此它可以在管道的不同执行阶段拥有 sqrtsd %xmm0, %xmm0 的两个副本。由于 sqrt 的结果不是立即需要的，因此可以在处理 sqrt 的同时执行其他指令，这就是为什么平均只测量 21.8 个周期。

对于第一种情况下较大的值，RDTSC不具备单周期分辨率。它有一定的延迟，因此您基本上是在测量 T_code_block + T_rdtsc_latency。在第二种情况下，对迭代进行平均得到:

(T_code_block * n_iters + T_rdtsc_latency) / n_iters =
= T_code_block + (T_rdtsc_latency / n_iters)

对于较大的 n_iters，第二项消失，您可以非常准确地测量单次迭代。

---

在使用 RDTSC 进行基准测试时必须非常小心。 TSC 本身以引用时钟速度在现代 CPU 上运行。如果循环运行足够长的时间，它可以触发核心时钟提升模式，CPU 将运行得更快，因此一个核心时钟周期将对应少于一个引用时钟周期。因此，在提升区域中执行的指令似乎比在标称时钟频率区域中执行的指令花费更少的周期。

此外，在执行周期精确测量时，始终将进程固定到单个 CPU 内核，使用 taskset 实用程序或 sched_setaffinity(2) 系统调用。操作系统调度程序通常会围绕不同的内核移动进程，以保持它们的负载均等，这是一个昂贵的过程。在执行几条指令的一小部分过程中发生这种情况的可能性非常低，但对于长循环来说，这种可能性要高得多。对多次迭代进行平均可以降低迁移的严重性，但仍然会得到有偏差的结果。将进程固定到单个核心可以完全防止这种情况。