valores - como cambiar el valor de una variable en c++

¿Cuál es la forma más rápida de intercambiar valores en C? (21)

Quiero intercambiar dos enteros, y quiero saber cuál de estas dos implementaciones será más rápida: La forma más obvia con una variable de temperatura:

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

O la versión xor que estoy seguro que la mayoría de la gente ha visto:

void swap(int* a, int* b) { *a ^= *b; *b ^= *a; *a ^= *b; }

Parece que el primero usa un registro extra, pero el segundo está haciendo tres cargas y almacena, mientras que el primero solo hace dos de cada uno. ¿Puede alguien decirme qué es más rápido y por qué? El por qué ser más importante.

@Harry: Ve a pararte en la esquina y piensa en lo que has sugerido. Vuelve cuando te hayas dado cuenta del error de tus caminos.

Nunca implemente funciones como macros por los siguientes motivos:

Escriba seguridad. No hay ninguno. Lo siguiente solo genera una advertencia al compilar pero falla en tiempo de ejecución:
float a=1.5f,b=4.2f; swap (a,b);
Una función de plantilla siempre será del tipo correcto (¿y por qué no estás tratando las advertencias como errores?).
EDITAR: Como no hay plantillas en C, necesita escribir un intercambio por separado para cada tipo o usar algún acceso de memoria hacky.
Es una sustitución de texto. Lo siguiente falla en tiempo de ejecución (esta vez, sin advertencias del compilador):
int a=1,temp=3; swap (a,temp);
No es una función. Por lo tanto, no se puede usar como argumento para algo como qsort.
Los compiladores son inteligentes. Quiero decir realmente inteligente. Hecho por personas realmente inteligentes. Pueden hacer funciones de alineación. Incluso en tiempo de enlace (que es aún más inteligente). No olvides que el aumento del tamaño del código aumenta. El código grande significa más posibilidades de error de caché cuando se buscan instrucciones, lo que significa que el código es más lento.
Efectos secundarios. ¡Las macros tienen efectos secundarios! Considerar:
int &f1 (); int &f2 (); void func () { swap (f1 (), f2 ()); }
Aquí, f1 y f2 se llamarán dos veces.
EDITAR: versión de CA con efectos secundarios desagradables:
int a[10], b[10], i=0, j=0; swap (a[i++], b[j++]);

Macros: ¡ solo di que no!

EDITAR: Esta es la razón por la que prefiero definir nombres de macros en MAYÚSCULAS para que se destaquen en el código como una advertencia para usar con cuidado.

EDIT2: Para responder el comentario de Leahn Novash:

Supongamos que tenemos una función no en línea, f, que el compilador convierte en una secuencia de bytes, entonces podemos definir el número de bytes así:

bytes = C(p) + C(f)

donde C () da el número de bytes producidos, C (f) son los bytes para la función y C (p) son los bytes para el código de "limpieza", el preámbulo y el postámbulo que el compilador agrega a la función (creando y destruir el marco de pila de la función, etc.). Ahora, llamar a la función f requiere C (c) bytes. Si la función se llama n veces, el tamaño total del código es:

size = C(p) + C(f) + n.C(c)

Ahora enlineemos la función. C (p), el "mantenimiento" de la función se convierte en cero, ya que la función puede usar el marco de pila de la persona que llama. C (c) también es cero ya que ahora no hay código de operación de llamada. Pero, f se replica donde sea que haya una llamada. Entonces, el tamaño total del código ahora es:

size = n.C(f)

Ahora, si C (f) es menor que C (c), entonces se reducirá el tamaño general del ejecutable. Pero, si C (f) es mayor que C (c), entonces el tamaño del código va a aumentar. Si C (f) y C (c) son similares, entonces debes considerar C (p) también.

Entonces, ¿cuántos bytes producen C (f) y C (c)? Bueno, la función C ++ más simple sería un getter:

void GetValue () { return m_value; }

que probablemente generaría la instrucción de cuatro bytes:

mov eax,[ecx + offsetof (m_value)]

que es cuatro bytes. Una instrucción de llamada es de cinco bytes. Entonces, hay un ahorro general de tamaño. Si la función es más compleja, digamos un indexador ("return m_value [index];") o un cálculo ("return m_value_a + m_value_b;") entonces el código será más grande.

Acabo de colocar ambos swaps (como macros) en el quicksort escrito a mano con el que he estado jugando. La versión XOR fue mucho más rápida (0.1seg) luego la que tenía la variable temporal (0.6seg). Sin embargo, el XOR corrompió los datos en la matriz (probablemente la misma dirección que Ant mencionó).

Como era un quicksort de pivote graso, la velocidad de la versión XOR probablemente sea la misma para hacer grandes porciones de la matriz. Probé una tercera versión de swap que fue la más fácil de entender y tuvo el mismo tiempo que la versión temporal única.

acopy=a; bcopy=b; a=bcopy; b=acopy;

[Acabo de poner una instrucción if en cada intercambio, por lo que no intentaré intercambiarla, y el XOR ahora toma el mismo tiempo que los demás (0,6 segundos)]

El método XOR falla si a y b apuntan a la misma dirección. El primer XOR borrará todos los bits en la dirección de memoria señalada por ambas variables, por lo que una vez que la función retorna (* a == * b == 0), independientemente del valor inicial.

Más información en la página Wiki: Algoritmo de intercambio XOR

Aunque no es probable que surja este problema, siempre preferiría usar el método que garantiza que funciona, no el método inteligente que falla en momentos inesperados.

El número 2 se cita a menudo como la forma "inteligente" de hacerlo. De hecho, es más probable que sea más lento ya que oscurece el objetivo explícito del programador, intercambiando dos variables. Esto significa que un compilador no puede optimizarlo para usar las operaciones reales del ensamblador para intercambiar. También asume la capacidad de hacer un xor bit a bit en los objetos.

Se adhiere al número 1, es el intercambio más genérico y más comprensible, y puede ser fácilmente convertido en plantilla / genérico.

Esta sección de la wikipedia explica los problemas bastante bien: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice

El primero es más rápido porque las operaciones en modo bit como xor suelen ser muy difíciles de visualizar para el lector.

Más rápido de entender, por supuesto, que es la parte más importante;)

En mi opinión, las optimizaciones locales como esta solo deberían considerarse estrechamente relacionadas con la plataforma. Hace una gran diferencia si está compilando esto en un compilador uC de 16 bits o en gcc con x64 como destino.

Si tiene un objetivo específico en mente, intente con ambos y mire el código asm generado o el perfil de su aplicación con ambos métodos y vea cuál es realmente más rápido en su plataforma.

En un procesador moderno, puede usar lo siguiente al ordenar arreglos grandes y no ver diferencias en la velocidad:

void swap (int *a, int *b) { for (int i = 1 ; i ; i <<= 1) { if ((*a & i) != (*b & i)) { *a ^= i; *b ^= i; } } }

La parte realmente importante de su pregunta es el ''¿por qué?'' parte. Ahora, al remontar 20 años a los 8086 días, lo anterior hubiera sido un verdadero asesino de rendimiento, pero en el último Pentium sería una velocidad de coincidencia para los dos que publicaste.

El motivo es puramente de memoria y no tiene nada que ver con la CPU.

Las velocidades de CPU en comparación con las velocidades de memoria han aumentado astronómicamente. El acceso a la memoria se ha convertido en el principal cuello de botella en el rendimiento de las aplicaciones. Todos los algoritmos de intercambio pasarán la mayor parte de su tiempo esperando a que los datos se obtengan de la memoria. Los sistemas operativos modernos pueden tener hasta 5 niveles de memoria:

Nivel de caché 1: funciona a la misma velocidad que la CPU, tiene un tiempo de acceso insignificante, pero es pequeño
Nivel de caché 2: se ejecuta un poco más lento que L1, pero es más grande y tiene una sobrecarga mayor para acceder (por lo general, los datos deben moverse primero a L1)
Nivel de caché 3 - (no siempre presente) A menudo externo a la CPU, más lento y más grande que L2
RAM: la memoria principal del sistema, por lo general implementa una tubería para que haya latencia en las solicitudes de lectura (datos de solicitudes de CPU, mensajes enviados a la RAM, RAM obtiene datos, RAM envía datos a la CPU)
Disco Duro: cuando no hay suficiente RAM, los datos se paginan a HD, que es realmente lento, no realmente bajo el control de la CPU como tal.

Los algoritmos de clasificación empeorarán el acceso a la memoria, ya que generalmente acceden a la memoria de una manera muy desordenada, lo que genera una carga ineficiente para obtener datos de L2, RAM o HD.

Por lo tanto, optimizar el método de intercambio es realmente inútil: si solo se llama un par de veces, se oculta cualquier ineficiencia debido a la poca cantidad de llamadas, si se llama mucho, se oculta cualquier ineficiencia debido a la cantidad de errores de caché (donde La CPU necesita obtener datos de L2 (1 de ciclos), L3 (10 de ciclos), RAM (100 de ciclos), HD (!)).

Lo que realmente necesita hacer es mirar el algoritmo que llama al método de intercambio. Este no es un ejercicio trivial. Aunque la notación Big-O es útil, una O (n) puede ser significativamente más rápida que una O (log n) para n pequeña. (Estoy seguro de que hay un artículo de CodingHorror sobre esto.) Además, muchos algoritmos tienen casos degenerados en los que el código hace más de lo necesario (usar qsort en datos casi ordenados podría ser más lento que un tipo de burbuja con una verificación temprana). Entonces, necesitas analizar tu algoritmo y la información que está usando.

Lo que lleva a cómo analizar el código. Los perfiladores son útiles pero es necesario que sepa cómo interpretar los resultados. Nunca use una sola ejecución para obtener resultados, siempre promedie los resultados en muchas ejecuciones, ya que el sistema operativo pudo haber localizado su aplicación de prueba en el disco duro a la mitad. Siempre el lanzamiento de perfil, las compilaciones optimizadas, el código de depuración de perfiles no tiene sentido.

En cuanto a la pregunta original, ¿qué es más rápido? - Es como tratar de descubrir si un Ferrari es más rápido que un Lambourgini mirando el tamaño y la forma del espejo retrovisor.

Está optimizando lo incorrecto, ambos deben ser tan rápidos que tendrá que ejecutarlos miles de millones de veces solo para obtener una diferencia medible.

Y casi cualquier cosa tendrá un efecto mucho mayor en su rendimiento, por ejemplo, si los valores que está intercambiando están próximos en la memoria al último valor que tocó, estarán en el caché del procesador, de lo contrario tendrá que acceder al memoria - y eso es varios órdenes de magnitud más lento que cualquier operación que haga dentro del procesador.

De todos modos, es más probable que su cuello de botella sea un algoritmo ineficiente o una estructura de datos inapropiada (o sobrecarga de comunicación) y luego cómo intercambia números.

La única manera de saber realmente es probarlo, y la respuesta puede variar incluso según el compilador y la plataforma en la que se encuentre. Los compiladores modernos son realmente buenos para optimizar el código en estos días, y nunca debes tratar de ser más astuto que el compilador a menos que puedas demostrar que tu camino es realmente más rápido.

Dicho esto, será mejor que tengas una muy buena razón para elegir # 2 sobre # 1. El código en # 1 es mucho más legible y por eso siempre se debe elegir primero. Solo cambie al # 2 si puede probar que necesita hacer ese cambio, y si lo hace, coméntelo para explicar lo que está sucediendo y por qué lo hizo de la manera no obvia.

Como anécdota, trabajo con un par de personas a las que les encanta optimizar de forma prematura y crea un código realmente horrible e inmanejable. También estoy dispuesto a apostar que la mayoría de las veces se están pegando un tiro en el pie porque han limitado la capacidad del compilador de optimizar el código escribiéndolo de una manera no directa.

La pieza debajo del código hará lo mismo. Este fragmento es una forma de programación optimizada ya que no usa ninguna tercera variable.

x = x ^ y; y = x ^ y; x = x ^ y;

No lo haría con punteros a menos que sea necesario. El compilador no puede optimizarlos muy bien debido a la posibilidad de alias de punteros (aunque si puede GARANTIZAR que los punteros apuntan a ubicaciones no superpuestas, GCC al menos tiene extensiones para optimizar esto).

Y no lo haría con las funciones en absoluto, ya que es una operación muy simple y la sobrecarga de llamada de función es significativa.

La mejor manera de hacerlo es con macros si la velocidad bruta y la posibilidad de optimización es lo que necesita. En GCC, puede usar el tipo de typeof() incorporado para crear una versión flexible que funcione con cualquier tipo de typeof() incorporada.

Algo como esto:

#define swap(a,b) / do { / typeof(a) temp; / temp = a; / a = b; / b = temp; / } while (0) ... { int a, b; swap(a, b); unsigned char x, y; swap(x, y); /* works with any type */ }

Con otros compiladores, o si requiere un cumplimiento estricto de la norma C89 / 99, debería crear una macro por separado para cada tipo.

Un buen compilador optimizará esto tan agresivamente como sea posible, dado el contexto, si se llama con variables locales / globales como argumentos.

Nunca entendí el odio por las macros. Cuando se usan correctamente, pueden hacer que el código sea más compacto y legible. Creo que la mayoría de los programadores saben que las macros se deben usar con cuidado, lo que es importante es dejar claro que una llamada en particular es una macro y no una llamada a función (todo en mayúsculas). Si SWAP(a++, b++); es una fuente constante de problemas, tal vez la programación no es para ti.

Es cierto que el truco de xor está limpio las primeras 5000 veces que lo ves, pero lo único que hace es ahorrar uno temporalmente a expensas de la confiabilidad. Al observar el conjunto generado anteriormente, guarda un registro pero crea dependencias. Tampoco recomendaría xchg ya que tiene un prefijo de bloqueo implícito.

Eventualmente, todos llegamos al mismo lugar, después de que se desperdiciaran incontables horas en optimización y depuración improductivas causadas por nuestro código más inteligente. Manténgalo simple.

#define SWAP(type, a, b) / do { type t=(a);(a)=(b);(b)=t; } while (0) void swap(size_t esize, void* a, void* b) { char* x = (char*) a; char* y = (char*) b; char* z = x + esize; for ( ; x < z; x++, y++ ) SWAP(char, *x, *y); }

Otra hermosa forma.

#define Swap( a, b ) (a)^=(b)^=(a)^=(b)

Ventaja

No es necesario llamar a la función y es útil.

Retirarse:

Esto falla cuando ambas entradas son la misma variable. Se puede usar solo en variables enteras.

Para aquellos que tropiezan con esta pregunta y deciden usar el método XOR. Debería considerar incluir su función o usar una macro para evitar la sobrecarga de una llamada de función:

#define swap(a, b) / do { / int temp = a; / a = b; / b = temp; / } while(0)

Para responder a su pregunta tal como se indica, sería necesario profundizar en los tiempos de instrucción de la CPU particular en la que se ejecutará este código, por lo que me obligaría a hacer una serie de suposiciones sobre el estado de las cachés en el sistema y el código ensamblado emitido por la compilador. Sería un ejercicio interesante y útil desde la perspectiva de entender cómo funciona realmente el procesador de su elección, pero en el mundo real la diferencia será insignificante.

Si puede usar un ensamblador en línea y hacer lo siguiente (ensamblador psuedo):

PUSH A A=B POP B

Ahorrará mucho tiempo de paso de parámetros y código de arreglo de pila, etc.

Si su compilador es compatible con el ensamblador en línea y su objetivo es de 32 bits x86, entonces la instrucción XCHG es probablemente la mejor manera de hacerlo ... si realmente le importa mucho el rendimiento.

Aquí hay un método que funciona con MSVC ++:

#include <stdio.h> #define exchange(a,b) __asm mov eax, a / __asm xchg eax, b / __asm mov a, eax int main(int arg, char** argv) { int a = 1, b = 2; printf("%d %d --> ", a, b); exchange(a,b) printf("%d %d/r/n", a, b); return 0; }

Todas las respuestas mejor calificadas no son realmente "hechos" definitivos ... ¡son personas que están especulando!

Definitivamente, puede saber por qué código necesita menos instrucciones de ensamblaje para ejecutarse, ya que puede ver el ensamblaje de salida generado por el compilador y ver qué se ejecuta en menos instrucciones de ensamblaje.

Aquí está el código c que compilé con los indicadores "gcc -std = c99 -S -O3 lookingAtAsmOutput.c":

#include <stdio.h> #include <stdlib.h> void swap_traditional(int * restrict a, int * restrict b) { int temp = *a; *a = *b; *b = temp; } void swap_xor(int * restrict a, int * restrict b) { *a ^= *b; *b ^= *a; *a ^= *b; } int main() { int a = 5; int b = 6; swap_traditional(&a,&b); swap_xor(&a,&b); }

La salida ASM para swap_traditional () toma >>> 11 <<< instrucciones (sin incluir "leave", "ret", "size"):

.globl swap_traditional .type swap_traditional, @function swap_traditional: pushl %ebp movl %esp, %ebp movl 8(%ebp), %edx movl 12(%ebp), %ecx pushl %ebx movl (%edx), %ebx movl (%ecx), %eax movl %ebx, (%ecx) movl %eax, (%edx) popl %ebx popl %ebp ret .size swap_traditional, .-swap_traditional .p2align 4,,15

La salida ASM para swap_xor () toma >>> 11 <<< instrucciones sin incluir "leave" y "ret":

.globl swap_xor .type swap_xor, @function swap_xor: pushl %ebp movl %esp, %ebp movl 8(%ebp), %ecx movl 12(%ebp), %edx movl (%ecx), %eax xorl (%edx), %eax movl %eax, (%ecx) xorl (%edx), %eax xorl %eax, (%ecx) movl %eax, (%edx) popl %ebp ret .size swap_xor, .-swap_xor .p2align 4,,15

Resumen del resultado de la asamblea:
swap_traditional () toma 11 instrucciones
swap_xor () toma 11 instrucciones

Conclusión:
Ambos métodos usan la misma cantidad de instrucciones para ejecutar y, por lo tanto, tienen aproximadamente la misma velocidad en esta plataforma de hardware.

Lección aprendida:
Cuando tiene pequeños fragmentos de código, es útil mirar el resultado del asm para iterar rápidamente su código y obtener el código más rápido (es decir, menos instrucciones). Y puede ahorrar tiempo incluso porque no tiene que ejecutar el programa para cada cambio de código. Solo necesita ejecutar el cambio de código al final con un generador de perfiles para mostrar que los cambios de su código son más rápidos.

Utilizo mucho este método para código DSP pesado que necesita velocidad.

x = x + y- (y = x);

float x; cout << "X:"; cin >> x; float y; cout << "Y:" ; cin >> y; cout << "---------------------" << endl; cout << "X=" << x << ", Y=" << y << endl; x=x+y-(y=x); cout << "X=" << x << ", Y=" << y << endl;

Para las arquitecturas de CPU modernas, el método 1 será más rápido, también con mayor legibilidad que el método 2.

En las arquitecturas de CPU modernas, la técnica XOR es considerablemente más lenta que el uso de una variable temporal para realizar el intercambio. Una razón es que las CPU modernas se esfuerzan por ejecutar instrucciones en paralelo a través de tuberías de instrucciones. En la técnica XOR, las entradas de cada operación dependen de los resultados de la operación anterior, por lo que deben ejecutarse en un orden estrictamente secuencial. Si la eficiencia es una gran preocupación, se aconseja probar las velocidades de la técnica XOR y el intercambio temporal de variables en la arquitectura de destino. Consulte http://en.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice para más información.

Editar: El Método 2 es una forma de intercambio in situ (es decir, sin usar variables adicionales). Para completar esta pregunta, agregaré otro intercambio local usando +/- .

void swap(int* a, int* b) { if (a != b) // important to handle a/b share the same reference { *a = *a+*b; *b = *a-*b; *a = *a-*b; } }

void swap(int* a, int* b) { *a = (*b - *a) + (*b = *a); }

// Mi C está un poco oxidado, así que espero tener el * derecho :)