i ++ meno efficiente di ++ i, come mostrare questo?

Question

Sto cercando di mostrare con l'esempio che l'incremento del prefisso è più efficiente dell'incremento postfisso.

In teoria questo ha senso: i ++ deve essere in grado di restituire il valore originale non integrato e quindi memorizzarlo, mentre ++ i può restituire il valore incrementato senza memorizzare il valore precedente.

Ma c'è un buon esempio per mostrare questo in pratica?

ho provato il seguente codice:

int array[100]; 

int main() 
{ 
    for(int i = 0; i < sizeof(array)/sizeof(*array); i++) 
    array[i] = 1; 
} 

ho compilato utilizzando 4.4.0 gcc come questo:

gcc -Wa,-adhls -O0 myfile.cpp 

ho fatto ancora una volta, con l'incremento suffisso cambiato in un incremento prefisso:

for(int i = 0; i < sizeof(array)/sizeof(*array); ++i) 

Il risultato è codice di assemblaggio identico in entrambi i casi.

Questo era un po 'inaspettato. Sembrava che disattivando le ottimizzazioni (con -O0) dovrei vedere una differenza per mostrare il concetto. Cosa mi manca? C'è un esempio migliore per mostrare questo?

Answer 1

Nel caso generale, l'incremento del post restituirà una copia in cui non verrà eseguito un pre-incremento. Ovviamente questo verrà ottimizzato in un numero elevato di casi e nei casi in cui non è l'operazione di copia sarà trascurabile (ad esempio, per i tipi incorporati).

Ecco un piccolo esempio che mostra la potenziale inefficienza del post-incremento.

#include <stdio.h> 

class foo 
{ 

public: 
    int x; 

    foo() : x(0) { 
     printf("construct foo()\n"); 
    }; 

    foo(foo const& other) { 
     printf("copy foo()\n"); 
     x = other.x; 
    }; 

    foo& operator=(foo const& rhs) { 
     printf("assign foo()\n"); 
     x = rhs.x; 
     return *this; 
    }; 

    foo& operator++() { 
     printf("preincrement foo\n"); 
     ++x; 
     return *this; 
    }; 

    foo operator++(int) { 
     printf("postincrement foo\n"); 
     foo temp(*this); 
     ++x; 
     return temp; 
    }; 

}; 


int main() 
{ 
    foo bar; 

    printf("\n" "preinc example: \n"); 
    ++bar; 

    printf("\n" "postinc example: \n"); 
    bar++; 
} 

I risultati di una build ottimizzata (che rimuove in realtà una seconda operazione di copia nel caso di post-incremento a causa di RVO):

construct foo() 

preinc example: 
preincrement foo 

postinc example: 
postincrement foo 
copy foo() 

In generale, se non avete bisogno la semantica del post-incremento, perché correre il rischio che si verifichi una copia non necessaria?

Naturalmente, è bene tenere presente che un operatore personalizzato ++() - sia la versione pre o post - è libero di restituire ciò che vuole (o anche fare quello che vuole), e immagino che lì sono alcuni che non seguono le solite regole. Occasionalmente mi sono imbattuto in implementazioni che restituiscono "void", il che fa andare via la solita differenza semantica.

Answer 2

Provare a usare po 'o fare qualcosa con valore restituito, ad es .:

#define SOME_BIG_CONSTANT 1000000000 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int i = 1; 
    int d = 0; 

    DWORD d1 = GetTickCount(); 
    while(i < SOME_BIG_CONSTANT + 1) 
    { 
     d += i++; 
    } 
    DWORD t1 = GetTickCount() - d1; 

    printf("%d", d); 
    printf("\ni++ > %d <\n", t1); 

    i = 0; 
    d = 0; 

    d1 = GetTickCount(); 
    while(i < SOME_BIG_CONSTANT) 
    { 
     d += ++i; 

    } 
    t1 = GetTickCount() - d1; 

    printf("%d", d); 
    printf("\n++i > %d <\n", t1); 

    return 0; 
} 

compilato con VS 2005 utilizzando/O2 o/Ox, ha provato sul mio desktop e sul computer portatile.

stabilmente ottenere qualcosa in giro sul computer portatile, sui numeri desktop sono un po 'diverso (ma il tasso è circa lo stesso):

i++ > 8xx < 
++i > 6xx < 

xx significa che i numeri sono diversi per esempio 813 vs 640 - ancora più veloce del 20%.

E un punto in più - se si sostituisce "D + =" con "d =" vedrete bel trucco ottimizzazione:

i++ > 935 < 
++i > 0 < 

Tuttavia, è abbastanza specifico. Dopotutto, non vedo alcun motivo per cambiare idea e penso che non ci siano differenze :)

Answer 3

Ok, tutto questo prefisso/postfix "ottimizzazione" è solo ... un grosso equivoco.

L'idea principale che i ++ restituisca la sua copia originale e quindi richiede la copia del valore.

Questo potrebbe essere corretto per alcune implementazioni non efficienti degli iteratori. Tuttavia nel 99% dei casi, anche con gli iteratori STL, non vi è alcuna differenza perché il compilatore sa come ottimizzarlo e gli iteratori effettivi sono solo indicatori che assomigliano alla classe. E naturalmente non c'è alcuna differenza per i tipi primitivi come gli interi sui puntatori.

Quindi ... lascia perdere.

EDIT: Clearification

Come avevo detto, la maggior parte di classi STL iteratori sono solo puntatori avvolto con le classi, che hanno tutte le funzioni membro inline permettendo out-ottimizzazione di tale copia irrilevante.

E sì, se si hanno i propri iteratori senza funzioni membro inline, allora è possibile che lavori più lentamente. Ma dovresti solo capire cosa fa il compilatore e cosa no.

Come una piccola dimostrare, prendere questo codice:

int sum1(vector<int> const &v) 
{ 
    int n; 
    for(auto x=v.begin();x!=v.end();x++) 
      n+=*x; 
    return n; 
} 

int sum2(vector<int> const &v) 
{ 
    int n; 
    for(auto x=v.begin();x!=v.end();++x) 
      n+=*x; 
    return n; 
} 

int sum3(set<int> const &v) 
{ 
    int n; 
    for(auto x=v.begin();x!=v.end();x++) 
      n+=*x; 
    return n; 
} 

int sum4(set<int> const &v) 
{ 
    int n; 
    for(auto x=v.begin();x!=v.end();++x) 
      n+=*x; 
    return n; 
} 

compilarlo al montaggio e confrontare sum1 e sum2, sum3 e sum4 ...

Ho appena posso dire ... gcc dare esattamente lo stesso codice con -02.

Answer 4

Non vedrete alcuna differenza con numeri interi. Devi usare iteratori o qualcosa in cui post e prefisso fanno davvero qualcosa di diverso. E devi attivare tutte le ottimizzazioni su, non disattivare!

Answer 5

Mi piace seguire la regola "dì cosa intendi".

++i incrementi semplicemente. Gli incrementi i++e hanno un risultato di valutazione speciale e non intuitivo. Io uso solo i++ se desidero esplicitamente tale comportamento e utilizzo ++i in tutti gli altri casi. Se segui questa procedura, quando vedi il codice i++, è ovvio che il comportamento post-incremento era realmente previsto.

Answer 6

Questo codice e i relativi commenti dovrebbero dimostrare le differenze tra i due.

class a { 
    int index; 
    some_ridiculously_big_type big; 

    //etc... 

}; 

// prefix ++a 
void operator++ (a& _a) { 
    ++_a.index 
} 

// postfix a++ 
void operator++ (a& _a, int b) { 
    _a.index++; 
} 

// now the program 
int main (void) { 
    a my_a; 

    // prefix: 
    // 1. updates my_a.index 
    // 2. copies my_a.index to b 
    int b = (++my_a).index; 

    // postfix 
    // 1. creates a copy of my_a, including the *big* member. 
    // 2. updates my_a.index 
    // 3. copies index out of the **copy** of my_a that was created in step 1 
    int c = (my_a++).index; 
} 

Si può vedere che il suffisso ha un passo in più (fase 1), che prevede la creazione di una copia dell'oggetto. Ciò ha implicazioni sia per il consumo di memoria che per il runtime. Che è il motivo per cui il prefisso è più efficace di postfix per i tipi non di base.

A seconda del some_ridiculously_big_type e anche su qualsiasi cosa tu faccia con il risultato dell'incrememt, sarai in grado di vedere la differenza con o senza ottimizzazioni.

Answer 7

diversi punti:

• In primo luogo, è improbabile vedere una grande differenza di prestazioni in alcun modo
• In secondo luogo, la vostra analisi comparativa è inutile se si dispone di ottimizzazioni disabilitate. Quello che vogliamo sapere è se questo cambiamento ci dà codice più o meno efficiente, il che significa che dobbiamo usarlo con il codice più efficiente che il compilatore è in grado di produrre. Non ci importa se è più veloce nelle build non ottimizzate, abbiamo bisogno di sapere se è più veloce in quelle ottimizzate.
• Per i tipi di dati incorporati come gli interi, il compilatore è generalmente in grado di ottimizzare la differenza.Il problema si verifica principalmente per tipi più complessi con iteratori incrementali sovraccaricati, in cui il compilatore non può banalmente vedere che le due operazioni sarebbero equivalenti nel contesto.
• È necessario utilizzare il codice che esprime in modo più chiaro le proprie intenzioni. Vuoi "aggiungere uno al valore" o "aggiungerne uno al valore, ma continuare a lavorare sul valore originale un po 'più a lungo"? Di solito, il primo è il caso, e quindi un pre-incremento esprime meglio il tuo intento.

Se si vuole mostrare la differenza, l'opzione più semplice è semplicemente quella di impementare entrambi gli operatori, e sottolineare che uno richiede una copia aggiuntiva, l'altro no.

Answer 8

In risposta a Mihail, questa è una versione portatile il suo codice un po 'di più:

#include <cstdio> 
#include <ctime> 
using namespace std; 

#define SOME_BIG_CONSTANT 100000000 
#define OUTER 40 
int main(int argc, char * argv[]) { 

    int d = 0; 
    time_t now = time(0); 
    if (argc == 1) { 
     for (int n = 0; n < OUTER; n++) { 
      int i = 0; 
      while(i < SOME_BIG_CONSTANT) { 
       d += i++; 
      } 
     } 
    } 
    else { 
     for (int n = 0; n < OUTER; n++) { 
      int i = 0; 
      while(i < SOME_BIG_CONSTANT) { 
       d += ++i; 
      } 
     } 
    } 
    int t = time(0) - now; 
    printf("%d\n", t); 
    return d % 2; 
} 

I loop esterni sono lì per permettermi di violino i tempi per ottenere qualcosa di adatto sulla mia piattaforma.

Non faccio uso di VC++ più, così ho compilato (su Windows) con:

g++ -O3 t.cpp 

Ho poi fatto funzionare alternando:

a.exe 

e

a.exe 1 

I miei risultati di temporizzazione erano approssimativamente uguali per entrambi i casi. A volte una versione sarebbe più veloce fino al 20% e talvolta l'altra. Ciò che suppongo sia dovuto ad altri processi in esecuzione sul mio sistema.

Answer 9

Forse potresti semplicemente mostrare la differenza teorica scrivendo entrambe le versioni con le istruzioni di assemblaggio x86? Come molti hanno già sottolineato, il compilatore prenderà sempre le proprie decisioni su come compilare/assemblare il programma al meglio.

Se l'esempio è destinato agli studenti che non hanno familiarità con il set di istruzioni x86, si potrebbe prendere in considerazione l'utilizzo del set di istruzioni MIPS32 - per qualche strana ragione molte persone sembrano trovarlo più facile da comprendere rispetto all'assembly x86.