i ++ menos eficiente que ++ i, ¿cómo mostrar esto?

Question

Estoy tratando de mostrar con el ejemplo que el incremento de prefijo es más eficiente que el incremento de postfijo.

En teoría, esto tiene sentido: i ++ necesita poder devolver el valor original no aumentado y, por lo tanto, almacenarlo, mientras que ++ i puede devolver el valor incrementado sin almacenar el valor anterior.

¿Pero hay un buen ejemplo para mostrar esto en la práctica?

He probado el siguiente código:

int array[100]; 

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

He compilado usando GCC 4.4.0 de esta manera:

gcc -Wa,-adhls -O0 myfile.cpp 

lo hice de nuevo, con el incremento de sufijo cambia a un incremento de prefijo:

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

El resultado es un código de ensamblaje idéntico en ambos casos.

Esto fue algo inesperado. Parecía que al desactivar las optimizaciones (con -O0) debería ver una diferencia para mostrar el concepto. ¿Qué me estoy perdiendo? ¿Hay un mejor ejemplo para mostrar esto?

Answer 1

En el caso general, el incremento posterior dará como resultado una copia en la que no se realizará un incremento previo. Por supuesto, esto se optimizará en un gran número de casos y en los casos en que no lo sea, la operación de copia será insignificante (es decir, para los tipos incorporados).

Aquí hay un pequeño ejemplo que muestra la posible ineficacia del incremento posterior.

#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++; 
} 

Los resultados de una estructura optimizada (que en realidad elimina una segunda operación de copia en el caso de incremento posterior debido a OVR):

construct foo() 

preinc example: 
preincrement foo 

postinc example: 
postincrement foo 
copy foo() 

En general, si usted no necesita la semántica del incremento posterior, ¿por qué correr el riesgo de que se produzca una copia innecesaria?

Por supuesto, es bueno tener en cuenta que un operador personalizado ++() - ya sea la variante previa o posterior - es libre de devolver lo que quiera (o incluso hacer lo que quiera), y me imagino que hay son bastantes los que no siguen las reglas habituales. De vez en cuando me he encontrado con implementaciones que devuelven "void", lo que hace que la diferencia semántica habitual desaparezca.

Answer 2

Trate de usar tiempo o hacer algo con valor devuelto, por ejemplo .:

#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; 
} 

compilado con VS 2005 utilizando/o O2/buey, trató en mi escritorio y en la computadora portátil.

de manera estable en torno conseguir algo en la computadora portátil, el número de escritorio son un poco diferentes (pero la tasa es aproximadamente la misma):

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

xx significa que los números son diferentes, por ejemplo, 813 vs 640 - aún alrededor del 20% de aceleración.

Y un punto más - si se reemplaza "d + =" con "d =" verá la optimización buen truco:

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

Sin embargo, es bastante específica. Pero después de todo, no veo ninguna razón para cambiar de opinión y creo que no hay diferencia :)

Answer 3

Ok, todo este prefijo/postfix "optimización" es simplemente ... algún gran malentendido.

La idea principal de que i ++ devuelve su copia original y por lo tanto requiere copiar el valor.

Esto puede ser correcto para algunas implementaciones ineficientes de iteradores. Sin embargo, en el 99% de los casos, incluso con los iteradores STL no hay diferencia porque el compilador sabe cómo optimizarlo y los iteradores reales son solo punteros que se parecen a la clase. Y, por supuesto, no hay diferencia para los tipos primitivos como los enteros en los punteros.

Así que ... olvídalo.

EDIT: clearification

Como ya había mencionado, la mayor parte de clases STL iterador son sólo punteros envueltos con las clases, que tienen todas las funciones miembro inlined permitiendo a cabo la optimización de dicha copia irrelevante.

Y sí, si tiene sus propios iteradores sin funciones miembro integradas, entonces puede trabajar más despacio. Pero, debes entender qué hace el compilador y qué no.

Como una pequeña probar, tomar este código:

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 para el montaje y comparar sum1 y SUM2, sum3 y sum4 ...

yo sólo puedo decir ... gcc dar exactamente el mismo código con -02.

Answer 4

No verá ninguna diferencia con enteros. Necesita usar iteradores o algo donde la publicación y el prefijo realmente hacen algo diferente. Y debe activar todas las optimizaciones en, ¡no apagado!

Answer 5

Me gusta seguir la regla de "di lo que quieres decir".

++i simplemente incrementa. i++ incrementos y tiene un resultado de evaluación especial, no intuitivo. Solo uso i++ si explícitamente quiero ese comportamiento, y uso ++i en todos los demás casos. Si sigues esta práctica, cuando ves i++ en el código, es obvio que el comportamiento posterior al incremento fue realmente intencionado.

Answer 6

Este código y sus comentarios deben demostrar las diferencias entre los dos.

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; 
} 

Se puede ver que el Postfix tiene un paso adicional (paso 1), que implica la creación de una copia del objeto. Esto tiene implicaciones tanto para el consumo de memoria como para el tiempo de ejecución. Eso es por qué el prefijo es más eficiente que el postfix para tipos no básicos de.

Según lo que haga con el resultado del incremento, podrá ver la diferencia con o sin optimizaciones.

Answer 7

varios puntos:

• En primer lugar, es poco probable que vea una gran diferencia de rendimiento en modo alguno
• segundo lugar, su evaluación comparativa es inútil si usted tiene optimizaciones desactivadas. Lo que queremos saber es si este cambio nos da un código más o menos eficiente, lo que significa que tenemos que usarlo con el código más eficiente que el compilador pueda producir. No nos importa si es más rápido en compilaciones no optimizadas, necesitamos saber si es más rápido en las optimizadas.
• Para tipos de datos integrados como enteros, el compilador generalmente puede optimizar la diferencia.El problema ocurre principalmente para tipos más complejos con iteradores de incremento sobrecargados, donde el compilador no puede ver trivialmente que las dos operaciones serían equivalentes en el contexto.
• Debe usar el código que más claramente expresa su intención. ¿Desea "agregar uno al valor" o "agregar uno al valor, pero seguir trabajando en el valor original un poco más"? Por lo general, el primero es el caso, y luego un pre-incremento expresa mejor su intención.

Si desea mostrar la diferencia, la opción más simple es simplemente imponer a ambos operadores, y señalar que uno requiere una copia adicional, el otro no.

Answer 8

En respuesta a Mihail, esta es una versión portátil de su código de algo más:

#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; 
} 

Los bucles externos son los que permiten que yo que jugar los tiempos para conseguir algo adecuado en mi plataforma.

No consumo VC++ más, así que compilé (en Windows) con:

g++ -O3 t.cpp 

Entonces me encontré con él por la alternancia:

a.exe 

y

a.exe 1 

Mis resultados de sincronización fueron aproximadamente los mismos para ambos casos. Algunas veces, una versión sería más rápida hasta en un 20% y, a veces, la otra. Esto, supongo, se debe a otros procesos que se ejecutan en mi sistema.

Answer 9

¿Quizás podría mostrar la diferencia teórica escribiendo ambas versiones con las instrucciones de ensamblaje x86? Como mucha gente ha señalado anteriormente, el compilador siempre tomará sus propias decisiones sobre la mejor manera de compilar/ensamblar el programa.

Si el ejemplo está destinado a estudiantes que no están familiarizados con el conjunto de instrucciones x86, podría considerar usar el conjunto de instrucciones MIPS32; por alguna extraña razón, parece que muchas personas lo entienden más fácilmente que el ensamblaje x86.