Czy ten algorytm wymiany wartości XOR jest nadal w użyciu lub przydatny

25

Kiedy zacząłem pracować, programista asemblera na komputerze mainframe pokazał mi, jak zamieniają się na wartości bez korzystania z tradycyjnego algorytmu:

a = 0xBABE
b = 0xFADE

temp = a
a = b
b = temp

To, czego używali do zamiany dwóch wartości - z nieco na duży bufor - to:

a = 0xBABE
b = 0xFADE

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

teraz

b == 0xBABE
a == 0xFADE

co zamieniło zawartość 2 obiektów bez potrzeby utrzymywania trzeciej temperatury.

Moje pytanie brzmi: czy ten algorytm wymiany XOR jest nadal w użyciu i gdzie nadal ma zastosowanie?

algorithms

— Quinton Bernhardt
źródło

50

Nadal jest szeroko stosowany do popisywania się i złych pytań podczas wywiadu; o to chodzi.

— Michael Borgwardt

4

Czy to coś w stylu sztuczki: a = a + b, b = ab, a = ab?

— Pieter B

4

@ PieterB tak, oba są przypadkami tego stackoverflow.com/questions/1826159/…

— jk.

Więc ... Zapisujesz rejestr, ale płacisz 3 dodatkowymi instrukcjami. Myślę, że wersja tymczasowa i tak byłaby szybsza.

— Billy ONeal

1

Wymiana wartości @MSalters od samego początku nie była problemem w x86 dzięki instrukcji xchg. Wymiana OTOH 2 lokalizacji pamięci wymaga 3 xchgs :)

— Netch

41

Podczas używania xorswapistnieje niebezpieczeństwo podania tej samej zmiennej jako obu argumentów do funkcji, która zeruje wymienioną zmienną, ponieważ jest ona xorze sobą, co powoduje, że wszystkie bity zostają wyzerowane. Oczywiście samo to spowodowałoby niepożądane zachowanie niezależnie od zastosowanego algorytmu, ale zachowanie może być zaskakujące i nieoczywiste na pierwszy rzut oka.

Tradycyjnie xorswapbył stosowany w implementacjach niskiego poziomu do wymiany danych między rejestrami. W praktyce istnieją lepsze alternatywy dla zamiany zmiennych w rejestrach. Na przykład Intel x86 ma XCHGinstrukcję, która zamienia zawartość dwóch rejestrów. Wiele razy kompilator obliczy semantykę takiej funkcji (zamienia zawartość przekazywanych do niej wartości) i może w razie potrzeby dokonywać własnych optymalizacji, więc próba zoptymalizowania czegoś tak trywialnego jak funkcja zamiany tak naprawdę nic nie kupuje w praktyce. Najlepiej jest zastosować oczywistą metodę, chyba że istnieje udowodniony powód, dla którego gorsze byłoby powiedzenie xorswap w obrębie problematycznej dziedziny.

— zxcdw
źródło

18

Jeśli obie wartości są takie same, nadal otrzymujesz poprawny wynik. a: 0101 ^ 0101 = 0000; b: 0101 ^ 0000 = 0101; a: 0101 ^ 0000 = 0101;

— Bobson,

1

Co powiedział @ GlenH7. -1-> +1.

— Bobson,

1

Nadal wydaje się, że masz wiersz o tym: „Podczas używania xorswap istnieje niebezpieczeństwo podania tej samej zmiennej jako obu argumentów funkcji, która zeruje wymienioną zmienną, ponieważ jest ona xor'd ze sobą, co powoduje, że wszystkie bity zostają wyzerowane.”. .. Czy to nie miało być usunięte?

— Chris

9

@Chris Nie, na początku napisałem, że jeśli wartości byłyby identyczne, jak gdyby a=10, b=10, a jeśli to zrobisz xorswap(a,b), zadziałałoby i nie wyzerowało zmiennych, które są fałszywe, a teraz usunięte. Ale jeśli nie xorswap(a, a)wtedy adostanie wyzerowany które pierwotnie oznaczało, ale głupi. :)

— zxcdw

3

Jest to dość istotne w niektórych językach - takie małe małe niebezpieczeństwa utrudniają znalezienie błędów w przyszłości, gdy mamy do czynienia z dwoma wskaźnikami, które w jakiś sposób zostały ustawione tak, aby wskazywały ten sam adres ponad 100 linii, których nie widzisz.

— Drake Clarris

14

Kluczem do odpowiedzi jest pytanie - „praca programisty asemblera na komputerach mainframe” - na kilka dni przed kompilatorem. Kiedy ludzie skulili się z instrukcjami montażu i ręcznie opracowali dokładne rozwiązania dla konkretnego elementu sprzętu (który może, ale nie musi działać na innym modelu tego samego komputera - problemy, takie jak synchronizacja dysków twardych i pamięci bębna, miały wpływ na sposób kodowania napisane - przeczytaj Historię Mela, jeśli czujesz potrzebę nostalgii).

W dawnych czasach rejestrów i pamięci brakowało, a każda sztuczka polegająca na tym, że nie trzeba było prosić o kolejny bajt lub słowo pamięci od głównego architekta, oszczędzała czas - zarówno przy pisaniu kodu, jak i czasu wykonania.

Te dni minęły. Sztuczka polegająca na zamianie dwóch rzeczy bez użycia trzeciej jest sztuczką. Pamięć i rejestry są obfite we współczesnym środowisku komputerowym, a ludzie nie piszą już asemblera. Nauczyliśmy wszystkich naszych sztuczek naszych kompilatorów i robią to lepiej niż my. Możliwe, że kompilator zrobił coś jeszcze lepszego niż to, co byśmy zrobili. W większości przypadków czasem z jakiegoś powodu musimy napisać asembler w wewnętrznej pętli ... ale to nie jest zapisanie rejestru ani słowa pamięci.

Może się to przydać ponownie, jeśli pracujesz w szczególnie ograniczonym mikrokontrolerze, ale optymalizacja zamiany nie jest prawdopodobnie źródłem problemu - próbowanie bycia zbyt sprytnym jest bardziej prawdopodobne.

2

Rejestry nie są tak obfite w wielu kontekstach. Nawet jeśli procesor ma wystarczającą liczbę rejestrów, każdy rejestr wykorzystywany w ISR jest rejestrem, który należy wcześniej zapisać i przywrócić. Jeśli ISR zajmuje dwadzieścia cykli i ma działać co czterdzieści cykli, każdy dodatkowy cykl dodany do ISR obniży wydajność systemu o pięć punktów procentowych.

— supercat

8

Czy to zadziała? Tak.

Czy powinieneś go użyć? Nie.

Tego rodzaju mikrooptymalizacja miałaby sens, gdyby:

spojrzałeś na kod generowany przez kompilator, aby w prosty sposób to zrobić (przypisanie i tymczasowe) i zdecydowałeś, że podejście XOR generuje szybszy kod
Twoja aplikacja została sprofilowana i okazało się, że koszt prostego podejścia przeważa nad przejrzystością kodu (i skutkuje oszczędnościami w utrzymaniu)

Do pierwszego punktu, chyba że wykonałeś ten pomiar, powinieneś zaufać kompilatorowi. Kiedy semantyka tego, co próbujesz zrobić, jest jasna, kompilator może wykonać wiele sztuczek, w tym zmienić porządek dostępu do zmiennych, aby zmiana nie była wcale potrzebna, lub wstawienie instrukcji na poziomie maszyny zapewniających najszybsze zamień dla danego typu danych. „Sztuczki”, takie jak zamiana XOR, utrudniają kompilatorowi zobaczenie, co próbujesz zrobić, a tym samym zmniejszają możliwości zastosowania takich optymalizacji.

Do drugiego punktu, co zyskujesz na dodatkową złożoność? Nawet jeśli zmierzyłeś i znalazłeś podejście XOR szybciej, czy ma to wystarczający wpływ, aby uzasadnić mniej jasne podejście? Skąd wiesz?

Na koniec powinieneś sprawdzić, czy istnieje standardowa funkcja zamiany dla twojej platformy / języka - na przykład C ++ STL zapewnia funkcję zamiany szablonów, która będzie wysoce zoptymalizowana dla twojego kompilatora / platformy.

— jimwise
źródło

2

Mój kolega powiedział, że jest to podstawowa sztuczka, której nauczył na studiach uniwersyteckich dla programisty systemów automatycznych. Wiele takich systemów jest wbudowanych z ograniczonymi zasobami i mogą brakować bezpłatnego rejestru, aby zachować tymczasową wartość; w takim przypadku taka trudna wymiana (lub jej analog z dodawaniem i odejmowaniem) staje się niezbędna, więc nadal jest używana.

Należy jednak dbać o to, aby te dwie lokalizacje nie mogły być identyczne, ponieważ w tym drugim przypadku skutecznie wyzeruje obie wartości. Zwykle ogranicza się to do oczywistych przypadków, takich jak wymiana rejestru i lokalizacja pamięci.

W przypadku x86 instrukcje xchg i cmpxchg w większości przypadków spełniają tę potrzebę, ale RISC na ogół nie są nimi objęte (z wyjątkiem Sparc).

— Netch
źródło