gcc простая производительность петли арифметики

Question

Проблема: одна, очевидно, дополнительная строка кода ускоряет программу почти в два раза.

Это довольно сложно сформулировать исходную проблему, она исходит из алгоритма устранения ограничений границ. Итак, просто какой-то простой тест, который я не могу понять.

Очевидно, что дополнительная строка кода приводит к ускорению программы почти в два раза.

Существует следующий источник:

#include <stdlib.h> 
#include <stdio.h> 

int main(void) 
{ 
    long i = 0, a = 0, x = 0; 
    int up = 200000000; 

    int *values = malloc(sizeof(int)*up); 

    for (i = 0; i < up ; ++i) 
    { 
     values[i]=i % 2; 
    } 
    for (i = 0; i < up ; ++i) 
    { 
     x = (a & i); 
#ifdef FAST 
     x = 0; 
#endif 
     a += values[x]; 
    } 
    printf ("a=%ld\n", a); 
    return 0; 
}/*main*/ 

В этом примере значение «а» всегда равен 0. Линия х = 0; - дополнительно.

Но, (смотрите - НЕТ НИКАКИХ оптимизаций)
$ НКУ -O0 -o короткие short.c & & время ./short
а = 0
реальные 0m2.808s
0m2.196s пользователей
SYS 0m0.596s

$ НКУ -O0 -DFAST -o короткие short.c & & время ./short
а = 0
реальные 0m1.869s
пользователь 0m1.260s
SYS 0m0.608s

И это воспроизводимый на многих компиляторов/вариантов оптимизации и вариаций программы.

Кроме того, они действительно приводят к тому же самому ассемблерному кодексу, за исключением того, что он помещает этот глупый дополнительный 0 в какой-нибудь регистр! Например:

НКУ -S -O0 -DFAST short.c & & мв short.s shortFAST.s
НКУ -S -O0 short.c & & мв short.s shortSLOW.s
дифференциалов shortFAST.s shortSLOW.s
55d54
< MOVQ $ 0, -24 (% РСП)

И немного после - тот же эффект на некоторые (все, что я был в состоянии проверить) другие компиляторы/языки (в том числе Java JIT). Единственная вещь была разделена - архитектура x86-64. Был протестирован как на процессорах Intel, так и на AMD ...

Answer 1

Короткий ответ: Сохранение 0 исключает зависимость чтения после записи в одном из циклов.

Детали:

Я подумал, что это интересный вопрос, и хотя вы сосредоточены на уровне оптимизации O0, то же убыстрение видно на О3, а также. Но, глядя на O0, проще сосредоточиться на том, что делает процессор для оптимизации кода, а не компилятора, потому что, как вы заметили, полученный код сборки отличается только 1 инструкцией.

Сборку код цикла интереса показан ниже

movq $0, -32(%rbp) 
    jmp .L4 
.L5:  
    movq -32(%rbp), %rax 
    movq -24(%rbp), %rdx 
    andq %rdx, %rax  
    movq %rax, -16(%rbp) 
    movq $0, -16(%rbp)  ;; This instruction in FAST but not SLOW 
    movq -16(%rbp), %rax 
    leaq 0(,%rax,4), %rdx 
    movq -8(%rbp), %rax 
    addq %rdx, %rax  
    movl (%rax), %eax  
    cltq     
    addq %rax, -24(%rbp) 
    addq $1, -32(%rbp) 
.L4:      
    movl -36(%rbp), %eax 
    cltq     
    cmpq -32(%rbp), %rax 
    jg .L5  

Бега с perf stat на моей системе я получаю следующие результаты:

Результатов для медленного кода

Performance counter stats for './slow_o0': 

    1827.438670 task-clock    # 0.999 CPUs utilized   
      155 context-switches   # 0.085 K/sec     
      1 CPU-migrations   # 0.001 K/sec     
     195,448 page-faults    # 0.107 M/sec     
6,675,246,466 cycles     # 3.653 GHz      
4,391,690,661 stalled-cycles-frontend # 65.79% frontend cycles idle 
1,609,321,845 stalled-cycles-backend # 24.11% backend cycles idle 
7,157,837,211 instructions    # 1.07 insns per cycle   
             # 0.61 stalled cycles per insn 
    490,110,757 branches     # 268.195 M/sec     
     178,287 branch-misses    # 0.04% of all branches   

    1.829712061 seconds time elapsed 

Результаты для быстрого кода

Performance counter stats for './fast_o0': 

    1109.451910 task-clock    # 0.998 CPUs utilized   
      95 context-switches   # 0.086 K/sec     
      1 CPU-migrations   # 0.001 K/sec     
     195,448 page-faults    # 0.176 M/sec     
4,067,613,078 cycles     # 3.666 GHz      
1,784,131,209 stalled-cycles-frontend # 43.86% frontend cycles idle 
    438,447,105 stalled-cycles-backend # 10.78% backend cycles idle 
7,356,892,998 instructions    # 1.81 insns per cycle   
             # 0.24 stalled cycles per insn 
    489,945,197 branches     # 441.610 M/sec     
     176,136 branch-misses    # 0.04% of all branches   

    1.111398442 seconds time elapsed 

Таким образом, вы можете видеть, что даже при том, что «быстрый» код выполняет больше инструкций, он имеет меньше киосков. Когда процессор вне порядка (как и большинство архитектур x64) выполняет код, он отслеживает зависимости между инструкциями. Команда ожидания может быть обойдена другой командой, если операнды готовы.

В этом примере критическая точка, скорее всего, эта последовательность команд:

andq %rdx, %rax 
    movq %rax, -16(%rbp) 
    movq $0, -16(%rbp)  ;; This instruction in FAST but not SLOW 
    movq -16(%rbp), %rax 
    leaq 0(,%rax,4), %rdx 
    movq -8(%rbp), %rax  

В быстром коде movq -8(%rbp), %rax инструкции получит результат от movq $0, -16(%rbp) пересылаемых к нему, и он будет в состоянии выполнить раньше. В то время как более медленная версия должна будет ждать movq %rax, -16(%rbp), которая имеет больше зависимостей между итерациями цикла.

Обратите внимание, что, не зная больше о конкретной микроархитектуре, этот анализ, вероятно, слишком упрощен. Но я подозреваю, что основной причиной является эта зависимость, и что выполнение хранилища 0 (инструкция movq $0, -16(%rbp)) позволяет ЦП выполнять более агрессивную спекуляцию при выполнении кодовой последовательности.