Ottimizzazione della divisione in gcc

Question

Ecco un po 'di codice (programma completo segue più avanti nella questione):

template <typename T> 
T fizzbuzz(T n) { 
    T count(0); 
    #if CONST 
     const T div(3); 
    #else 
     T div(3); 
    #endif 
    for (T i(0); i <= n; ++i) { 
     if (i % div == T(0)) count += i; 
    } 
    return count; 
} 

Ora, se io chiamo questa funzione modello con int, tanto sono un fattore di differenza 6 prestazioni in base alle se definisco cONST o meno:

$ gcc --version 
gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125) 

$ make -B wrappedint CPPFLAGS="-O3 -Wall -Werror -DWRAP=0 -DCONST=0" && 
time ./wrappedint 
g++ -O3 -Wall -Werror -DWRAP=0 -DCONST=0 wrappedint.cpp -o wrappedi 
nt 
484573652 

real 0m2.543s 
user 0m2.059s 
sys  0m0.046s 

$ make -B wrappedint CPPFLAGS="-O3 -Wall -Werror -DWRAP=0 -DCONST=1" && 
time ./wrappedint 
g++ -O3 -Wall -Werror -DWRAP=0 -DCONST=1 wrappedint.cpp -o wrappedi 
nt 
484573652 

real 0m0.655s 
user 0m0.327s 
sys  0m0.046s 

Esaminando lo smontaggio risulta che, nel caso veloce (const), il modulo è stato trasformato in una cosa moltiplicazione e spostamento tipo, mentre nel caso lenta (non-const) sta usando idivl.

Ancora peggio, se provo a racchiudere il mio intero in una classe, l'ottimizzazione non avviene se utilizzo const o no. Il codice utilizza sempre idivl e scorre lenta:

#include <iostream> 

struct WrappedInt { 
    int v; 
    explicit WrappedInt(const int &val) : v(val) {} 
    bool operator<=(const WrappedInt &rhs) const { return v <= rhs.v; } 
    bool operator==(const WrappedInt &rhs) const { return v == rhs.v; } 
    WrappedInt &operator++() { ++v; return *this; } 
    WrappedInt &operator+=(const WrappedInt &rhs) { v += rhs.v; return *this; } 
    WrappedInt operator%(const WrappedInt &rhs) const 
     { return WrappedInt(v%rhs.v); } 
}; 

std::ostream &operator<<(std::ostream &s, WrappedInt w) { 
    return s << w.v; 
} 

template <typename T> 
T fizzbuzz(T n) { 
    T count(0); 
    #if CONST 
     const T div(3); 
    #else 
     T div(3); 
    #endif 
    for (T i(0); i <= n; ++i) { 
     if (i % div == T(0)) count += i; 
    } 
    return count; 
} 

int main() { 
    #if WRAP 
     WrappedInt w(123456789); 
     std::cout << fizzbuzz(w) << "\n"; 
    #else 
     std::cout << fizzbuzz<int>(123456789) << "\n"; 
    #endif 
} 

Le mie domande sono:

1) Esiste un semplice principio di C++ per sé, o di ottimizzazione di gcc, il che spiega il motivo per cui questo accade, o è solo un caso di "varie corse euristiche, questo è il codice che ottieni"?

2) Esiste un modo per far sì che il compilatore si renda conto che il mio const WrappedInt localmente dichiarato e mai referenziato può essere trattato come un valore const di compilazione? Voglio che questa cosa sia una sostituzione diretta per int nei template.

3) Esiste un modo noto di eseguire il wrapping di un int tale che il compilatore possa scartare il wrapping durante l'ottimizzazione? L'obiettivo è che WrappedInt sarà un modello basato su criteri. Ma se una politica del "do-nothing" si traduce in penalità di velocità 6x essenzialmente arbitrarie rispetto a int, io sto meglio a svantaggiare questa situazione e usare direttamente int.

Answer 1

Sto indovinando la sua versione GCC severamente vecchia che stai utilizzando. Il più vecchio compilatore che ho sulla mia macchina - gcc-4.1.2, esegue il modo veloce con entrambe le versioni non-const e wrap (e lo fa solo a -O1).

Answer 2

Provare a combinare const int v nella classe WrappedInt con const T nella funzione fizzbuzz e verificare se il compilatore può ottimizzarlo.

Dichiarando const int hai creato un caso speciale - una costante di tempo di compilazione. Il compilatore sa qual è il valore e può ottimizzarlo più pesantemente di un valore che potrebbe cambiare durante l'esecuzione del programma.

Answer 3

Esiste un modo noto di eseguire il wrapping di un int tale che il compilatore possa scartare il wrapping durante l'ottimizzazione?

Provare a passare WrappedInt in base al valore. Quindi è possibile passare WrappedInt s nei registri. Pass-by-const-reference a volte costringe gcc a ricadere nello stack per il passaggio degli argomenti.

Informazioni sul rallentamento int vs const int, posso solo ipotizzare che GCC stia cercando di giocare sul sicuro di fronte all'aliasing. Fondamentalmente, se non può dimostrare che div non è un alias per un'altra variabile più accessibile, non può trasformarla in una costante. Se lo dichiari const, GCC presume che non sia alias e compia la conversione in una costante. A parte lo idivl, dovresti anche vedere un recupero di memoria, una volta, quando inserisci la funzione, al contrario dei valori immediati usati per il caso const.

Answer 4

La differenza di velocità è dovuta al fatto che il compilatore non sa se "div" cambierà valore. Quando è non-const, lo considera come una variabile passata. Potrebbe essere qualsiasi cosa, e quindi il compilatore userà un'istruzione che divide due variabili - idivl. Quando si dice che è const, il compilatore è libero di trattare esattamente come se avessi scelto:

 
if (i % 3 == 0) 

Sono un po 'sorpreso che non ha utilizzato AND bit a bit (&).

WrappedInt non viene ottimizzato perché, beh, non è un int. È una classe.

Qualcosa che potresti fare è incorporare fizzbuzz in WrappedInt.