Esse algoritmo de troca de valor XOR ainda está em uso ou é útil

Quando comecei a trabalhar, um programador de assembler de mainframe me mostrou como eles trocam para valores sem usar o algoritmo tradicional de:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

O que eles usaram para trocar dois valores - de um pouco para um buffer grande - foi:

a = 0xBABE
b = 0xFADE

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

agora

b == 0xBABE
a == 0xFADE

que trocou o conteúdo de 2 objetos sem a necessidade de um terceiro espaço de retenção temporário.

Minha pergunta é: esse algoritmo de troca XOR ainda está em uso e onde ainda é aplicável.

Ao usar, xorswapexiste o perigo de fornecer a mesma variável que os dois argumentos para a função que zera a referida variável devido ao fato de estar xorcom ela mesma, que transforma todos os bits em zero. É claro que isso por si só resultaria em comportamento indesejado, independentemente do algoritmo usado, mas o comportamento pode ser surpreendente e não óbvio à primeira vista.

Tradicionalmente, xorswaptem sido usado para implementações de baixo nível para troca de dados entre registradores. Na prática, existem melhores alternativas para trocar variáveis ​​nos registradores. Por exemplo, o x86 da Intel possui uma XCHGinstrução que troca o conteúdo de dois registros. Muitas vezes, um compilador descobre a semântica de uma função (troca o conteúdo dos valores passados) e pode fazer suas próprias otimizações, se necessário, portanto, tentar otimizar algo tão trivial quanto uma função de troca não comprará nada para você na prática. É melhor usar o método óbvio, a menos que haja uma razão comprovada pela qual seria inferior dizer xorswap no domínio do problema.

A chave da resposta está na pergunta - "trabalhando com um programador de assembler de mainframe" - nos dias anteriores ao compilador. Quando os seres humanos se acocoraram com as instruções de montagem e criaram soluções exatas para uma determinada peça de hardware (que pode ou não funcionar em outro modelo do mesmo computador - questões como o tempo dos discos rígidos e da memória do tambor tiveram impacto sobre como o código era escrito - leia A História de Mel, se alguém sentir necessidade de ser nostálgico).

Naqueles dias passados, os registros e a memória eram escassos e qualquer truque para não precisar implantar outro byte ou palavra de memória do arquiteto principal era economizado - tanto na escrita do código quanto no tempo de execução.

Esses dias se foram. O truque de trocar duas coisas sem usar uma terceira é um truque. A memória e os registros são abundantes na computação moderna e os humanos não escrevem mais montagem. Ensinamos todos os nossos truques aos nossos compiladores, e eles fazem um trabalho melhor do que nós. Provavelmente, o compilador fez algo ainda melhor do que o que teríamos feito. Na maioria dos casos, às vezes precisamos escrever assembly em algum trecho interno de um loop apertado por algum motivo ... mas não é para salvar um registro ou uma palavra de memória.

Pode ser útil novamente se alguém estiver trabalhando em um microcontrolador particularmente limitado, mas otimizar uma troca provavelmente não é a fonte do seu problema - tentar ser inteligente demais é mais um problema.

será que vai dar certo? Sim.

Você deveria usá-lo? Não.

Esse tipo de micro-otimização faria sentido se:

• você examinou o código que o compilador gera para a maneira direta de fazer isso (atribuição e temporária) e decidiu que a abordagem XOR gera código mais rápido

• você definiu o perfil do seu aplicativo e descobriu que o custo da abordagem direta supera a clareza do código (e a economia resultante em manutenção)

Para o primeiro ponto, a menos que você tenha feito essa medição, deve confiar no compilador. Quando a semântica do que você está tentando fazer é clara, existem muitos truques que o compilador pode fazer, incluindo reorganizar o acesso variável para que a troca não seja necessária, ou alinhar as instruções no nível da máquina que forneçam o mais rápido trocar por um determinado tipo de dados. "Truques", como a troca XOR, tornam mais difícil para o compilador ver o que você está tentando fazer e, portanto, tornam menos capaz de aplicar essas otimizações.

Para o segundo ponto, o que você está ganhando pela complexidade adicional? Mesmo se você mediu e encontrou a abordagem XOR mais rapidamente, isso tem impacto suficiente para justificar uma abordagem menos clara? Como você sabe?

Finalmente, você deve verificar se existe uma função de troca padrão para sua plataforma / linguagem - o C ++ STL, por exemplo, fornece uma função de troca de modelo que tenderá a ser altamente otimizada para seu compilador / plataforma.

Meu colega relatou que esse é um truque básico que ele ensinou na universidade estudando para um programador de sistemas automatizados. Muitos desses sistemas são embarcados com recursos limitados e podem não ter um registro gratuito para manter o valor temporário; nesse caso, essa troca complicada (ou seu análogo à adição e subtração) está se tornando vital e ainda sendo usada.

Mas devemos nos preocupar em usá-lo para que esses dois locais não possam ser idênticos porque, no último caso, efetivamente zerará ambos os valores. Geralmente, isso se limita a casos óbvios, como a troca de um registro e um local de memória.

Com o x86, as instruções xchg e cmpxchg atendem à necessidade na maioria dos casos, mas os RISCs geralmente não são cobertos por elas (exceto Sparc).