单个 sqrt() 的运行速度如何比放入 for 循环时慢两倍
How can a single sqrt() runs twice slower than when it was put in a for loop
我正在做一个实验，分析用 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
但是结果显示，策略一大约需要40个时钟周期，而策略二平均需要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 , %eax
call printf
movl $.LC1, %eax
movq -32(%rbp), %rdx
movq %rdx, %rsi
movq %rax, %rdi
movl [=12=], %eax
call printf
movl [=12=], %eax
movq %rax, -16(%rbp)
call readTSC
//-- start of for loop----
movq %rax, -32(%rbp)
movl [=12=], -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 , -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 [=12=], %eax
call printf
movl $.LC3, %eax
movsd -16(%rbp), %xmm0
movq %rax, %rdi
movl , %eax
call printf
在我看来，策略 I 使用了 sqrtsd 指令。这是因为ucomisd指令没有设置校验标志，代码直接跳转到L4。
for 循环，策略 II 使用 call sqrt 来计算平方根。这可能是 sqrt 的优化版本，通过近似实现，因此比调用 sqrtsd 更快。某些编译器可能会进行此优化。
即使 call sqrt 在后面使用 sqrtsd 指令，也没有理由 运行 更快 在 之外循环。
请注意，测量仅执行一次的单个指令的延迟是不确定的。 rdtsc 指令有它自己的延迟，因为现在的 CPU 是超标量的并且乱序你无法知道 rdtsc sqrtsd rdtsc 完全按程序顺序执行。它们肯定不会在同一端口上执行，因此不能保证 sqrtsd 在第二个 rdtsc 完成时完成。
另一个需要考虑的重要事项是，当您在循环中执行 sqrt 时，您减少了指令的平均延迟。这是因为 您可以在流水线的不同阶段 并行执行多条指令。 Agner Fog 的 instruction tables 表明 Ivy Bridge 的 sqrtsd 指令可以具有每周期 1/8 到 1/14 条指令的吞吐量。 for 循环增加了平均吞吐量，而单个独立指令将具有最高延迟。
因此，由于流水线并行执行，循环中的指令平均 运行 比 运行 隔离时更快。
问题出在 'readTSC()' 函数上。为了确保您可以将 'strategy I' 与 'strategy II' 互换。现在您会看到 'Strategy II' 花费了更多时间。我认为 readTSC() 函数在第一次运行时需要更多时间。
E5-2680 是一个 Sandy Bridge CPU，SQRTSD 的延迟和相互吞吐量都是 10 到 21 cycles/instr。因此无论是否循环，您都应该测量接近观察到的 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 本身以参考时钟速度在现代 CPUs 上滴答作响。如果循环 运行s 足够长，它可以触发核心时钟提升模式并且 CPU 将 运行 更快，因此一个核心时钟周期将对应少于一个参考时钟周期.结果，看起来在提升区域中执行的指令比在标称时钟频率区域中执行的指令花费更少的周期。
此外，在执行周期精确测量时，始终将进程固定到单个 CPU 核心，使用 taskset 实用程序或 sched_setaffinity(2) 系统调用。 OS 调度程序通常在不同的核心周围移动进程，以保持它们的平均负载，这是一个昂贵的过程。在执行几条指令的一小部分过程中发生这种情况的可能性非常低，但对于长循环来说，这种可能性要高得多。对多次迭代进行平均可以降低迁移的严重性，但仍然会得到有偏差的结果。将进程固定到单个内核可以完全防止这种情况。
我正在做一个实验，分析用 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
但是结果显示，策略一大约需要40个时钟周期，而策略二平均需要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 , %eax
call printf
movl $.LC1, %eax
movq -32(%rbp), %rdx
movq %rdx, %rsi
movq %rax, %rdi
movl [=12=], %eax
call printf
movl [=12=], %eax
movq %rax, -16(%rbp)
call readTSC
//-- start of for loop----
movq %rax, -32(%rbp)
movl [=12=], -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 , -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 [=12=], %eax
call printf
movl $.LC3, %eax
movsd -16(%rbp), %xmm0
movq %rax, %rdi
movl , %eax
call printf
在我看来，策略 I 使用了 sqrtsd 指令。这是因为ucomisd指令没有设置校验标志，代码直接跳转到L4。
for 循环，策略 II 使用 call sqrt 来计算平方根。这可能是 sqrt 的优化版本，通过近似实现，因此比调用 sqrtsd 更快。某些编译器可能会进行此优化。
即使 call sqrt 在后面使用 sqrtsd 指令，也没有理由 运行 更快 在 之外循环。
请注意，测量仅执行一次的单个指令的延迟是不确定的。 rdtsc 指令有它自己的延迟，因为现在的 CPU 是超标量的并且乱序你无法知道 rdtsc sqrtsd rdtsc 完全按程序顺序执行。它们肯定不会在同一端口上执行，因此不能保证 sqrtsd 在第二个 rdtsc 完成时完成。
另一个需要考虑的重要事项是，当您在循环中执行 sqrt 时，您减少了指令的平均延迟。这是因为 您可以在流水线的不同阶段 并行执行多条指令。 Agner Fog 的 instruction tables 表明 Ivy Bridge 的 sqrtsd 指令可以具有每周期 1/8 到 1/14 条指令的吞吐量。 for 循环增加了平均吞吐量，而单个独立指令将具有最高延迟。
因此，由于流水线并行执行，循环中的指令平均 运行 比 运行 隔离时更快。
问题出在 'readTSC()' 函数上。为了确保您可以将 'strategy I' 与 'strategy II' 互换。现在您会看到 'Strategy II' 花费了更多时间。我认为 readTSC() 函数在第一次运行时需要更多时间。
E5-2680 是一个 Sandy Bridge CPU，SQRTSD 的延迟和相互吞吐量都是 10 到 21 cycles/instr。因此无论是否循环，您都应该测量接近观察到的 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 本身以参考时钟速度在现代 CPUs 上滴答作响。如果循环 运行s 足够长，它可以触发核心时钟提升模式并且 CPU 将 运行 更快，因此一个核心时钟周期将对应少于一个参考时钟周期.结果，看起来在提升区域中执行的指令比在标称时钟频率区域中执行的指令花费更少的周期。
此外，在执行周期精确测量时，始终将进程固定到单个 CPU 核心，使用 taskset 实用程序或 sched_setaffinity(2) 系统调用。 OS 调度程序通常在不同的核心周围移动进程，以保持它们的平均负载，这是一个昂贵的过程。在执行几条指令的一小部分过程中发生这种情况的可能性非常低，但对于长循环来说，这种可能性要高得多。对多次迭代进行平均可以降低迁移的严重性，但仍然会得到有偏差的结果。将进程固定到单个内核可以完全防止这种情况。