prosta pętla arytmetyczna gcc wydajność

Question

Problem: jedna ewidentnie dodatkowa linia kodu przyspiesza program prawie dwukrotnie.

To raczej trudne do sformułowania oryginalny problem, pochodzi z algorytmu eliminacji sprawdzania ograniczeń. A więc po prostu prosty test, którego nie rozumiem.

Jedna ewidentnie dodatkowa linia kodu prowadzi do przyspieszenia programu prawie dwukrotnie.

znajduje się następujące źródła:

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

W tym przypadku wartość 'a' jest zawsze 0. Linia x = 0; jest ekstra.

Ale (wygląd - Nie Obojętnie optymalizacje)
$ gcc -o -O0 krótki short.c & & czas ./short
a = 0
prawdziwe 0m2.808s
0m2.196s użytkowników
SYS 0m0.596s

$ gcc -o -O0 -DFAST krótkie short.c & & czas ./short
a = 0
prawdziwe 0m1.869s
użytkownik 0m1.260s
sys 0m0.608s

I to jest powtarzalne w wielu kompilatorów/opcji optymalizacji i wariantów programowych.

Co więcej, naprawdę dają ten sam kod assemblera, z wyjątkiem umieszczenia tego głupiego dodatkowego 0 w jakimś rejestrze! Np

gcc -S -O0 -DFAST short.c & & mv short.s shortFAST.s
gcc -S -O0 short.c & & mv short.s shortSLOW.s
diff shortFAST.s shortSLOW.s
55d54
< MOVQ $ 0, -24 (% RBP)

A nieco później - tym samym wpływ na niektóre (wszystko udało mi się przetestować) inne kompilatory/języki (w tym Java JIT). Została udostępniona tylko architektura x86-64. Przetestowano na procesorach Intel i AMD ...

Answer 1

Krótka odpowiedź: Przechowywanie wartości 0 eliminuje zależność odczytu po zapisie w jednej z pętli.

Szczegóły:

Myślałem, że to interesujące pytanie, i choć koncentruje się na poziomie optymalizacji O0, tym samym przyspieszenie jest widoczne na O3 również. Ale patrząc na O0 łatwiej jest skupić się na tym, co robi procesor, aby zoptymalizować kod, a nie kompilator, ponieważ jak zauważyłeś, wynikowy kod zespołu różni się tylko o 1 instrukcję.

Kod montaż na pętli zainteresowania przedstawiono poniżej

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  

Biegając z perf stat na moim systemie otrzymuję następujące wyniki:

wyników dla powolnego kodu

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 

Wyniki dla szybkiego kodu

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 

Widać więc, że chociaż "szybki" kod wykonuje więcej instrukcji, ma mniej stoisk. Kiedy wykonywany kod jest poza procesorem (jak większość architektur x64), śledzi zależności między instrukcjami. Instrukcja oczekiwania może zostać ominięta przez inną instrukcję, jeśli operandy są gotowe.

W tym przykładzie punkt krytyczny jest prawdopodobne, to sekwencja instrukcji:

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  

W szybkim kodzie instrukcja movq -8(%rbp), %rax będzie uzyskać wynik od movq $0, -16(%rbp) przekazanych mu i będzie w stanie wykonać szybciej. Podczas gdy wolniejsza wersja będzie musiała poczekać na movq %rax, -16(%rbp), która ma więcej zależności między iteracjami pętli.

Należy pamiętać, że bez wiedzy na temat konkretnej mikroarchitektury taka analiza jest prawdopodobnie zbyt uproszczona. Ale podejrzewam, że podstawową przyczyną jest ta zależność i że wykonanie zapisu 0 (instrukcja movq $0, -16(%rbp)) umożliwia procesorowi wykonywanie bardziej agresywnych spekulacji podczas wykonywania sekwencji kodu.