c++ - que - ¿Qué tan rápido es std:: swap para tipos enteros?

swap en c

Question

STL implementa una función genérica std::swap para intercambiar 2 valores. Se puede presentar de la siguiente manera:

template <class T> void swap (T& a, T& b)
{
T c(std::move(a));
a=std::move(b);
b=std::move(c);
}

Sin embargo, hay un algoritmo de intercambio XOR para intercambiar 2 enteros ( http://en.wikipedia.org/wiki/XOR_swap_algorithm ):

void swap_u( size_t& x, size_t& y )
{
x = x^y;
y = x^y;
x = x^y;
}

Mis preguntas:

1. ¿Es una optimización hoy en día (en x86 o arm )?
2. ¿El estándar de C ++ favorece este tipo de optimización?
3. ¿Existe alguna implementación real de STL en la naturaleza que tenga la especialización std::swap para enteros?

Answer 1

El intercambio XOR es realmente solo un truco y puede fallar en ciertos casos (por ejemplo, ambas variables son referencias al mismo objeto).

El intercambio XOR tampoco es particularmente eficiente ya que tiene dependencias en serie, por lo que siempre tomará al menos tres ciclos de instrucción. El uso de un intercambio directo con un temporal tiene menos dependencias, lo que permite cierto paralelismo en las CPU superescalares modernas. En algunas CPU puede incluso implementarse en una instrucción, pero incluso sin instrucciones especiales, puede ejecutarse en dos ciclos.

Answer 2

En X86, un intercambio de XOR triple entre ubicaciones de memoria (no registros de CPU) toma los mismos ciclos de procesador que una copia triple. Pueden ser incluso menos si lo temporal es un registro.

Answer 3

En la gran mayoría de las situaciones, el intercambio XOR no es una optimización.

Ver esta entrada de wiki .

En la mayoría de los escenarios prácticos, el algoritmo de intercambio trivial que usa un registro temporal es más eficiente. Las situaciones limitadas en las que el intercambio XOR puede ser práctico incluyen:

• En un procesador en el que la codificación del conjunto de instrucciones permite que el intercambio XOR se codifique en un número menor de bytes;
• En una región con alta presión de registro, puede permitir que el asignador de registros evite derramar un registro.
• En microcontroladores donde la memoria RAM disponible es muy limitada.

Debido a que estas situaciones son poco frecuentes, la mayoría de los compiladores de optimización no generan código de intercambio XOR.

También tenga en cuenta que su implementación de swap XOR está rota. Primero debes comprobar que xey no tienen alias. Esta verificación definitivamente hará que el cambio de XOR sea más lento.

No tengo conocimiento de ninguna implementación de biblioteca estándar que utilice el intercambio XOR.

Tenga en cuenta que, independientemente de lo que implemente la biblioteca estándar, si el intercambio XOR fuera realmente más rápido que el intercambio normal, la optimización de los compiladores haría una optimización de mirilla para convertirlo en un intercambio XOR. Esto realmente es un caso de simplemente dejar que el compilador elija por ti.