Ottimizzazione GCC: come rallentare le operazioni?

Question

Durante il tentativo di confrontare alcune opzioni per il mio codice (usando interi a 128 bit o meno) ho osservato un comportamento che non riesco a capire. Qualcuno potrebbe far luce su questo?

#include <stdio.h> 
#include <stdint.h> 
#include <time.h> 

int main(int a, char** b) 
{ 
    printf("Running tests\n"); 

    clock_t start = clock(); 
    unsigned __int128 t = 13; 
    for(unsigned long i = 0; i < (1UL<<30); i++) 
     t += 23442*t + 25; 
    if(t == 0) printf("0\n"); 
    printf("u128, +25, took %fs\n", double(clock() - start)/CLOCKS_PER_SEC); 

    start = clock(); 
    t = 13; 
    for(unsigned long i = 0; i < (1UL<<30); i++) 
     t += 23442*t; 
    if(t == 0) printf("0\n"); 
    printf("u128, no+, took %fs\n", double(clock() - start)/CLOCKS_PER_SEC); 

    start = clock(); 
    unsigned long u = 13; 
    for(unsigned long i = 0; i < (1UL<<30); i++) 
     u += 23442*u + 25; 
    if(u == 0) printf("0\n"); 
    printf("u64 , +25, took %fs\n", double(clock() - start)/CLOCKS_PER_SEC); 

    start = clock(); 
    u = 13; 
    for(unsigned long i = 0; i < (1UL<<30); i++) 
     u += 23442*u; 
    if(u == 0) printf("0\n"); 
    printf("u64 , no+, took %fs\n", double(clock() - start)/CLOCKS_PER_SEC); 

    return 0; 
} 

(Si noti che il printf sono qui in modo che gcc non ottimizza il ciclo for) Sul mio sistema, questo produce in modo affidabile il seguente output:

u128, +25, took 2.411922s 
u128, no+, took 1.799805s 
u64 , +25, took 1.797960s 
u64 , no+, took 2.454104s 

Mentre il comportamento intero a 128 bit ha senso, non riesco a vedere come il ciclo a 64 bit con meno operazioni si comporta in modo significativo (30%) più lento.

È un comportamento noto? Quale sarebbe la regola generale quando si cerca di beneficiare di questa ottimizzazione quando si scrivono loop di questo tipo?

Modifica: il comportamento viene osservato solo durante la compilazione con l'opzione -O3.

gcc -lstdc++ -O3 -o a main.cpp 

u128, +25, took 2.413949s 
u128, no+, took 1.799469s 
u64 , +25, took 1.798278s 
u64 , no+, took 2.453414s 

gcc -lstdc++ -O2 -o a main.cpp 

u128, +25, took 2.415244s 
u128, no+, took 1.800499s 
u64 , +25, took 1.798699s 
u64 , no+, took 1.348133s 

Answer 1

Il loop è così stretto che lo stallo di dipendenza, l'ALU occupato ecc. Arriva a giocare e domina i tempi. Il risultato non è quindi affidabile e più sensibile ad altri fattori rispetto all'esecuzione effettiva delle istruzioni.

Nota che +25 può essere calcolato in parallelo insieme al moltiplicare.

---

PS. Il mio risultato sul 4970K:

gcc version 5.2.1 20151010 
gcc -lstdc++ -O2 -o a a.cpp 

u128, +25, took 1.346360s 
u128, no+, took 1.022965s 
u64 , +25, took 1.020189s 
u64 , no+, took 0.765725s 

---

EDIT: Dopo sguardo al smontare il -O2 e -O3, la differenza principale è quel momento in poi la generazione del codice. (Sopra ragione ancora tenere -O2 su differenti macchine di prova/ambiente ottenendo risultati leggermente diversi)

-O2:

400618:  48 69 d2 93 5b 00 00 imul $0x5b93,%rdx,%rdx 
40061f:  48 83 e8 01    sub $0x1,%rax 
400623:  75 f3     jne 400618 <_Z4testv+0x18> 

-O3:

400628:  66 0f 6f d9    movdqa %xmm1,%xmm3 
40062c:  83 c0 01    add $0x1,%eax 
40062f:  66 0f 6f c1    movdqa %xmm1,%xmm0 
400633:  66 0f f4 cc    pmuludq %xmm4,%xmm1 
400637:  3d 00 00 00 20   cmp $0x20000000,%eax 
40063c:  66 0f f4 da    pmuludq %xmm2,%xmm3 
400640:  66 0f 73 d0 20   psrlq $0x20,%xmm0 
.... 

O3 generare vettorializzare codice mentre il ciclo ha una dipendenza pesante che non può ottenere valore dalla vettorizzazione. In realtà ha generato un codice molto più complesso e quindi ha un tempismo molto più lungo.

Answer 2

Sarà necessario misurare ciò che effettivamente accade in fase di esecuzione per sapere con certezza. Come Calvin menziona in his answer, ci sono molte cose che succedono all'interno del processore, che influenzeranno il tempo finale del ciclo.

È possibile utilizzare PAPI o Intel's brilliant tools per eseguire le misurazioni. Gli strumenti di Intel sono costosi, ma puoi provarli gratuitamente per 30 giorni. Sono molto più facili da usare rispetto a PAPI.