performance - valores - swap lenguaje c

¿Hay algún punto para intercambiar dos variables sin usar un tercero? (6)

Sé que no debo usarlos, pero hay técnicas para intercambiar dos variables sin usar un tercero, como

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

x = x + y y = x - y x = x - y

En clase, el profesor mencionó que estos eran populares hace 20 años cuando la memoria era muy limitada y todavía se usan en aplicaciones de alto rendimiento en la actualidad. ¿Es esto cierto? Mi comprensión de por qué no tiene sentido utilizar tales técnicas es que:

Nunca puede ser el cuello de botella usando la tercera variable.
El optimizador hace esto de todos modos.

Entonces, ¿hay alguna vez un buen momento para no intercambiar con una tercera variable? ¿Es siempre más rápido?

Comparado entre sí, ¿el método que usa XOR es el método que usa +/- más rápido? La mayoría de las arquitecturas tienen una unidad para sumar / restar y XOR, ¿no significaría que todas tienen la misma velocidad? ¿O solo porque una CPU tiene una unidad para la operación no significa que tengan la misma velocidad?

Estas técnicas aún son importantes de saber para los programadores que escriben el firmware de una lavadora promedio o más. Muchos de esos tipos de hardware todavía se ejecutan en CPU Z80 o similares, a menudo con no más de 4K de memoria más o menos. Fuera de esa escena, conocer estos tipos de "trucos" algorítmicos tiene, como dices, tan buena como ningún uso práctico real.

(Sin embargo, quiero señalar que, sin embargo, los programadores que recuerdan y conocen este tipo de cosas a menudo resultan ser mejores programadores incluso para aplicaciones "regulares" que sus "pares" que no se molestan. Precisamente porque estos últimos a menudo toman esa actitud de "memoria es lo suficientemente grande de todos modos" demasiado lejos.)

Estos trucos no son muy útiles si quieres intercambiar dos palabras completas en la memoria o dos registros completos. Aún así, podría aprovecharlas si no tiene registros gratuitos (o solo un registro gratuito para intercambio de memoria a memoria) y no hay instrucciones de "intercambio" disponibles (como cuando se intercambian dos registros SSE en x86) o "intercambio". la instrucción es demasiado costosa (como la memoria de registro xchg en x86) y no es posible evitar el intercambio o la menor presión de registro.

Pero si sus variables son dos campos de bits en una sola palabra, una modificación del enfoque 3-XOR puede ser una buena idea:

y = (x ^ (x >> d)) & mask x = x ^ y ^ (y << d)

Este fragmento es del "El arte de la programación de computadoras" de Knuth vol. 4a. segundo. 7.1.3. Aquí y es solo una variable temporal. Ambos campos de bit a cambiar están en x . mask se usa para seleccionar un campo de bits, d es la distancia entre los campos de bit.

También podría usar trucos como este en pruebas de dureza (para preservar la planaridad). Consulte, por ejemplo, el gadget de cruce de esta diapositiva (página 7). Esto es de recientes conferencias en "Algorithmic Lower Bounds" por el prof. Erik Demaine.

No tiene sentido en absoluto. Es un intento de demostrar inteligencia. Teniendo en cuenta que no funciona en muchos casos (punto flotante, punteros, estructuras), es unreadabe y utiliza tres operaciones dependientes que serán mucho más lentas que el simple intercambio de valores, es absolutamente inútil y demuestra que no se es realmente inteligente.

Tienes razón, si fue más rápido, entonces la optimización de compiladores detectaría el patrón cuando se intercambian dos números, y lo reemplazará. Es bastante fácil de hacer. Pero los compiladores realmente notan cuando intercambias dos variables y no pueden producir ningún código, pero luego comienzas a usar las diferentes variables después de eso. Por ejemplo, si intercambias x e y, escribe a + = x; b + = y; el compilador puede simplemente cambiar esto a a + = y; b + = x; . Por otro lado, el patrón xor o add / resta no se reconocerá porque es muy raro y no se mejorará.

Por supuesto, todavía es útil saber. ¿Cuál es la alternativa?

c = a a = b b = c

tres operaciones con tres recursos en lugar de tres operaciones con dos recursos?

Claro que el conjunto de instrucciones puede tener un intercambio, pero eso solo entra en juego si estás 1) escribiendo un ensamblaje o 2) el optimizador lo interpreta como un intercambio y luego codifica esa instrucción. O podría hacer el ensamblaje en línea, pero eso no es portátil y un problema que mantener, si llamó a una función de asm, entonces el compilador tiene que configurar la llamada para grabar un montón de recursos e instrucciones. Aunque se puede hacer, no es probable que explote la función de conjuntos de instrucciones a menos que el lenguaje tenga una operación de intercambio.

Ahora, el programador promedio NO NECESITA saber esto ahora más que en el pasado, la gente recurrirá a este tipo de optimización prematura, ya menos que conozca el truco y lo use a menudo si el código no está documentado, entonces no es obvio, por lo que es mala programación porque es ilegible e imposible de mantener.

sigue siendo una educación y un ejercicio de programación de valor, por ejemplo, hacer que uno invente una prueba para demostrar que realmente cambia para todas las combinaciones de patrones de bits. Y al igual que hacer un registro xor, registrar un x86 para poner a cero un registro, tiene un impulso de rendimiento pequeño pero real para un código altamente optimizado.

Sí, lo hay, especialmente en el código de ensamblaje.

Los procesadores tienen solo un número limitado de registros. Cuando los registros están bastante llenos, este truco puede evitar el derrame de un registro a otra ubicación de memoria (posiblemente en una línea de caché no recuperada).

De hecho, he usado el xor 3 vías para intercambiar un registro con la ubicación de la memoria en la ruta crítica de las rutinas de bloqueo codificadas a mano de alto rendimiento para x86 donde la presión de registro era alta y no había lugar (¡seguro!) Para poner la temperatura (En el X86, es útil saber que la instrucción XCHG a la memoria tiene un alto costo asociado, porque incluye su propio bloqueo, cuyo efecto no quería. Dado que el x86 tiene el código de operación del prefijo LOCK, esto fue realmente errores innecesarios, pero históricos son solo eso).

Moral: cada solución, sin importar qué tan fea se vea cuando se está aislado, es probable que tenga algunos usos. Es bueno conocerlos; no siempre puedes usarlos si no es apropiado. Y donde son útiles, pueden ser muy efectivos.

Tal construcción puede ser útil en muchos miembros de la serie PIC de microcontroladores que requieren que casi todas las operaciones pasen por un único acumulador ("registro de trabajo") [tenga en cuenta que aunque a veces esto puede ser un obstáculo, el hecho de que solo es necesario para cada instrucción para codificar una dirección de registro y un bit de destino, en lugar de dos direcciones de registro, hace posible que el PIC tenga un conjunto de trabajo mucho más grande que otros microcontroladores].

Si el registro activo tiene un valor y es necesario intercambiar sus contenidos con los de RAM, la alternativa a:

xorwf other,w ; w=(w ^ other) xorwf other,f ; other=(w ^ other) xorwf other,w ; w=(w ^ other)

sería

movwf temp1 ; temp1 = w movf other,w ; w = other movwf temp2 ; temp2 = w movf temp1,w ; w = temp1 [old w] movwf other ; other = w movf temp2,w ; w = temp2 [old other]

Tres instrucciones y ningún almacenamiento adicional, en comparación con seis instrucciones y dos registros adicionales.

Por cierto, otro truco que puede ser útil en los casos en los que uno desea hacer otro registro contiene el máximo de su valor presente o W, y el valor de W no será necesario luego

subwf other,w ; w = other-w btfss STATUS,C ; Skip next instruction if carry set (other >= W) subwf other,f ; other = other-w [i.e. other-(other-oldW), i.e. old W]

No estoy seguro de cuántos otros procesadores tienen una instrucción de resta, pero ninguna comparación no destructiva, pero en esos procesadores ese truco puede ser bueno para saber.