c Две очень похожие функции, связанные с sin(), демонстрируют значительно отличающуюся производительность-почему?




performance gcc (2)

Рассмотрим следующие две программы, которые выполняют одни и те же вычисления двумя способами:

// 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

В первом примере он запускает 100000 циклов греха, 8192 раз.

Во втором примере он запускает 8192 цикла греха, 100000 раз.

Помимо этого и сохранения результата по-разному, я не вижу никакой разницы.

Однако имеет значение то, что ввод изменяется для каждого цикла во втором случае. Поэтому я подозреваю, что происходит то, что значение sin в определенные моменты цикла становится намного проще вычислять. И это может иметь большое значение. Вычисление греха не является полностью тривиальным, и это серия вычислений, которая петляет до тех пор, пока не будет достигнуто условие выхода.


Игнорируйте структуру цикла все вместе и думайте только о последовательности вызовов sin . v1 выполняет следующие действия:

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 (или просто оценивает результат во время компиляции). К сожалению, мы живем в несовершенном мире.





x86