问题 涉及sin()的两个非常相似的函数表现出截然不同的性能 - 为什么?


考虑以下两个以两种不同方式执行相同计算的程序:

// v1.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x;
   for (j = 0; j < nbr_values; j++) {
      x = 1;
      for (i = 0; i < n_iter; i++)
         x = sin(x);
   }
   printf("%f\n", x);
   return 0;
}

// v2.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x[nbr_values];
   for (i = 0; i < nbr_values; ++i) {
      x[i] = 1;
   }
   for (i = 0; i < n_iter; i++) {
      for (j = 0; j < nbr_values; ++j) {
         x[j] = sin(x[j]);
      }
   }
   printf("%f\n", x[0]);
   return 0;
}

当我使用gcc 4.7.2编译它们时 -O3 -ffast-math 并且在Sandy Bridge盒子上运行,第二个程序的速度是第一个程序的两倍。

这是为什么?

一个可疑的是连续迭代之间的数据依赖性 i 循环进来 v1。但是,我不太明白完整的解释是什么。

(问题的灵感来自 为什么我的python / numpy示例比纯C实现更快?

编辑:

这是生成的程序集 v1

        movl    $8192, %ebp
        pushq   %rbx
LCFI1:
        subq    $8, %rsp
LCFI2:
        .align 4
L2:
        movl    $100000, %ebx
        movss   LC0(%rip), %xmm0
        jmp     L5
        .align 4
L3:
        call    _sinf
L5:
        subl    $1, %ebx
        jne     L3
        subl    $1, %ebp
        .p2align 4,,2
        jne     L2

并为 v2

        movl    $100000, %r14d
        .align 4
L8:
        xorl    %ebx, %ebx
        .align 4
L9:
        movss   (%r12,%rbx), %xmm0
        call    _sinf
        movss   %xmm0, (%r12,%rbx)
        addq    $4, %rbx
        cmpq    $32768, %rbx
        jne     L9
        subl    $1, %r14d
        jne     L8

12243
2018-01-22 21:49


起源

尝试使用 double 代替 float - Basile Starynkevitch
@BasileStarynkevitch: double 没有区别。 - NPE
在第二个代码中,可能是因为对于所有j> = 1的所有x [j] = sin(x [j])将与初始sin-calc?之后的x [0]相同,从而整个内部循环可以被抛出并替换为单个sin-calc和fill? (只是在这里猜测)。第一个循环用每个内循环迭代计算一个依赖于值的sin,第二个代码段没有这样的限制。 - WhozCraig
@NPE我认为数据依赖可能是完整的解释。是什么让你觉得还有另一个原因?由于第二个版本中的数据“独立性”,处理器可以在计算前一个数据时预加载下一个计算值,等等。我不是CPU架构的专家,但是由于今天的处理器管道很长,我会考虑这实际上可以解释这种性能差异,这似乎是合理的。 - us2012
@NPE我相信斯蒂芬佳能本人 是 x86架构专家。 - Mysticial


答案:


一起忽略循环结构,只考虑调用的顺序 sinv1 执行以下操作:

x <-- sin(x)
x <-- sin(x)
x <-- sin(x)
...

也就是说,每次计算 sin( ) 在前一次通话的结果可用之前无法开始;它必须等待以前的整个计算。这意味着对于N次调用 sin,所需的总时间是单个延迟的819200000倍 sin 评价。

v2相比之下,您执行以下操作:

x[0] <-- sin(x[0])
x[1] <-- sin(x[1])
x[2] <-- sin(x[2])
...

注意每次打电话 sin 不依赖于之前的通话。有效地,呼吁 sin 一旦所需的寄存器和ALU资源可用,处理器就可以在每个处理器上开始(无需等待先前的计算完成)。因此,所需的时间是该函数的函数 吞吐量 sin函数,而不是延迟,等等 v2 可以在很短的时间内完成。


我还应该注意到DeadMG是对的 v1 和 v2 在形式上是等价的,在完美的世界中,编译器会将它们优化为100000的单个链 sin 评估(或简单地在编译时评估结果)。可悲的是,我们生活在一个不完美的世界。


15
2018-01-22 21:51



@DeadMG:当然可以。的价值 x 是v1中的循环携带依赖项。 - Stephen Canon
@StephenCanon:OSX Libm还在使用我的 sin 实施? - Eric Postpischil
@EricPostpischil:确实如此。 - Stephen Canon
更重要的是,FSIN总体上给出了错误的结果。它不能做减少参数。 - R..
@R ..:是的,那也是;我把“使用FSIN”简写为“使用FPREM1 + FSIN”(它没有做无限pi减少,但至少做了一些事情)。 - Stephen Canon


在第一个例子中,它运行100000个sin循环,8192次。

在第二个例子中,它运行8192个sin循环,100000次。

除此之外,以不同方式存储结果,我没有看到任何差异。

但是,有所不同的是,在第二种情况下,每个循环的输入都在改变。所以我怀疑发生的事情是,在循环中的某些时间,sin值变得更容易计算。这可以产生很大的不同。计算sin并不是完全无关紧要的,它是一个循环计算,直到退出条件被击中。


0
2018-01-22 22:02



啊,我会编辑我的答案...... - Mats Petersson
为什么downvote - 当我没有评论downvotes时我真的不喜欢它 - 我想知道什么是错的... - Mats Petersson
我没有投票,但值得注意的是两个程序计算完全一样 sin 价值,只是以不同的顺序。 - NPE