Quanto è veloce std :: swap per i tipi interi?

Question

STL implementa una funzione generica std::swap per scambiare 2 valori. Può essere presentata nel modo seguente:

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

Tuttavia, c'è un algoritmo XOR di swap per scambiare 2 numeri interi (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; 
} 

Le mie domande:

1. È un'ottimizzazione al giorno d'oggi (su x86 o arm)?
2. Lo standard C++ favorisce questo tipo di ottimizzazione?
3. Esistono implementazioni STL reali in natura che hanno la specializzazione std::swap per i numeri interi?

Answer 1

Nella maggior parte delle situazioni, lo scambio XOR non è un'ottimizzazione.

Vedere questo wiki entry.

Nella maggior parte degli scenari pratici, l'algoritmo di scambio banale che utilizza un registro temporaneo è più efficiente. situazioni limitate in cui XOR swap può essere pratico includono:

• su un processore in cui la codifica del set di istruzioni permette lo scambio XOR essere codificato in un numero minore di byte;
• In una regione con pressione di registro elevata, può consentire all'allocatore di registro di evitare di versare un registro.
• Nei microcontrollori in cui la RAM disponibile è molto limitata.

Poiché queste situazioni sono rare, la maggior parte dei compilatori di ottimizzazione non genera il codice di scambio XOR.

Si noti inoltre che l'implementazione dello scambio XOR è interrotta. È necessario innanzitutto verificare che x e y non siano alias. Questo controllo renderà sicuramente lo scambio XOR più lento.

Non sono a conoscenza di alcuna implementazione di libreria standard che utilizza lo scambio XOR.

Si noti che, indipendentemente da ciò che implementa la libreria standard, se lo scambio XOR fosse davvero più veloce del normale swap, l'ottimizzazione dei compilatori farebbe uno peephole optimization per trasformarlo in uno scambio XOR. Questo è davvero il caso di lasciare che sia il compilatore a scegliere per te.

Answer 2

Lo scambio XOR è in realtà solo un espediente e può non riuscire in alcuni casi (ad esempio, entrambe le variabili sono riferimenti allo stesso oggetto).

Lo scambio XOR non è particolarmente efficiente in quanto ha dipendenze seriali, pertanto richiederà sempre almeno tre cicli di istruzioni. Utilizzare uno scambio diretto con un temporaneo ha meno dipendenze, consentendo un certo parallelismo sulle moderne CPU superscalari: su alcune CPU può anche essere implementato in un'unica istruzione, ma anche senza istruzioni speciali può essere eseguito in due cicli.

Answer 3

Su X86, un triplo scambio XOR tra posizioni di memoria (non registri CPU) richiede gli stessi cicli del processore di una copia tripla. Possono essere anche meno se il temporaneo è un registro.