Questo algoritmo di scambio di valori XOR è ancora in uso o utile

25

Quando ho iniziato a lavorare su un programmatore assemblatore di mainframe mi ha mostrato come si scambiano i valori senza utilizzare l'algoritmo tradizionale di:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

Quello che usavano per scambiare due valori - da un bit a un buffer di grandi dimensioni - era:

a = 0xBABE
b = 0xFADE

a = a XOR b
b = b XOR a
a = a XOR b

Ora

b == 0xBABE
a == 0xFADE

che scambiava il contenuto di 2 oggetti senza la necessità di un terzo spazio di trattenimento temporaneo.

La mia domanda è: questo algoritmo di scambio XOR è ancora in uso e dove è ancora applicabile.

    
posta Quinton Bernhardt 09.01.2013 - 15:27
fonte

4 risposte

41

Quando si usa xorswap c'è il pericolo di fornire la stessa variabile di entrambi gli argomenti alla funzione che azzera la suddetta variabile a causa del fatto che è xor 'd con se stessa che trasforma tutti i bit a zero. Naturalmente questo stesso risultato comporterebbe un comportamento indesiderato indipendentemente dall'algoritmo utilizzato, ma il comportamento potrebbe essere sorprendente e non ovvio a prima vista.

Tradizionalmente xorswap è stato utilizzato per implementazioni di basso livello per lo scambio di dati tra registri. In pratica esistono alternative migliori per lo scambio di variabili nei registri. Ad esempio, Intel x86 ha un'istruzione XCHG che scambia il contenuto di due registri. Molte volte un compilatore capirà la semantica di una tale funzione (scambia i contenuti dei valori passati ad essa) e può apportare le proprie ottimizzazioni se necessario, quindi provare a ottimizzare qualcosa di così banale come una funzione di swap in realtà non ti compra nulla in pratica. È meglio usare il metodo ovvio a meno che non ci sia una ragione comprovata perché sarebbe inferiore a dire xorswap all'interno del dominio del problema.

    
risposta data 09.01.2013 - 15:35
fonte
14

La chiave per la risposta è nella domanda - "working a mainframe assembler programmer" - nei giorni precedenti al compilatore. Quando gli umani si accovacciavano con le istruzioni di assemblaggio e le soluzioni esatte create a mano per un particolare componente hardware (che potrebbe funzionare o meno su un altro modello dello stesso computer), problemi come il tempo dei dischi rigidi e la memoria del tamburo avevano un impatto sul modo in cui il codice era scritto - leggi La storia di Mel se senti il bisogno di essere nostalgico.

Tornati in questi giorni passati, i registri e la memoria erano entrambi scarsi e qualsiasi trucco per non dover elemosinare un altro byte o parola di memoria dall'architetto principale era tempo risparmiato - sia nella scrittura del codice che nel tempo di esecuzione.

Quei giorni sono finiti. Il trucco di scambiare due cose senza usare un terzo è un trucco. La memoria e i registri sono entrambi abbondanti nell'informatica moderna e gli umani non scrivono più assemblaggi. Abbiamo insegnato tutti i nostri trucchi ai nostri compilatori, e ci fanno un lavoro migliore di quello che facciamo noi. È probabile che il compilatore abbia fatto qualcosa di meglio di quello che avremmo fatto. Nella maggior parte dei casi, a volte abbiamo bisogno di scrivere assembly in qualche bit interno di un loop chiuso per qualche motivo ... ma non è quello di salvare un registro o una parola di memoria.

Potrebbe tornare utile se si sta lavorando in un microcontrollore particolarmente limitato, ma l'ottimizzazione di uno swap non è probabilmente la fonte del problema, quindi provare a essere troppo intelligente è più probabilmente un problema.

    
risposta data 09.01.2013 - 15:59
fonte
8

Funzionerà? Sì.

Dovresti usarlo? No.

Questo tipo di micro-ottimizzazione avrebbe senso se:

  • hai guardato il codice che il compilatore genera per il modo diretto di farlo (assegnazione e temporanea) e ha deciso che l'approccio XOR genera codice più veloce

  • hai profilato la tua app e hai scoperto che il costo dell'approccio diretto supera la chiarezza del codice (e il conseguente risparmio in termini di manutenibilità)

Al primo punto, a meno che tu non abbia fatto questa misurazione, dovresti fidarti del compilatore. Quando la semantica di ciò che stai cercando di fare è chiara, ci sono molti trucchi che il compilatore può fare, incluso riorganizzare l'accesso alle variabili in modo che lo swap non sia affatto necessario, o in-lining qualsiasi istruzione a livello macchina fornisca il più veloce scambia per un determinato tipo di dati. I "trucchi" come lo scambio XOR rendono più difficile per il compilatore vedere cosa si sta tentando di fare, e quindi rendere meno in grado di applicare tali ottimizzazioni.

Al secondo punto, cosa stai guadagnando per la complessità aggiunta? Anche se hai misurato e trovato l'approccio XOR più veloce, questo ha un impatto sufficiente a giustificare un approccio meno chiaro? Come lo sai?

Infine, dovresti esaminare se esiste una funzione di swap standard per la tua piattaforma / lingua - il C ++ STL, ad esempio, fornisce una funzione di scambio di template che tenderà ad essere altamente ottimizzata per il tuo compilatore / piattaforma.

    
risposta data 09.01.2013 - 16:07
fonte
2

Il mio collega ha riferito che questo è un trucco di base che ha insegnato negli studi universitari per un programmatore di sistemi automatizzati. Molti di questi sistemi sono integrati con risorse limitate e potrebbero mancare di un registro gratuito per mantenere il valore temporaneo; in tal caso, uno scambio così delicato (o il suo analogo con l'aggiunta e la sottrazione) sta diventando vitale, quindi è ancora in uso.

Ma ci si deve preoccupare di usare queste due posizioni non possono essere identiche perché in quest'ultimo caso effettivamente azzererà entrambi i valori. Quindi di solito è limitato a casi ovvi come lo scambio di un registro e una posizione di memoria.

Con x86, le istruzioni xchg e cmpxchg soddisfano la necessità nella maggior parte dei casi, ma in genere i RISC non ne sono coperti (eccetto Sparc).

    
risposta data 19.12.2013 - 11:47
fonte

Leggi altre domande sui tag