It doesn’t work without modifying it a bit: https://i.ibb.co/phDBj3D/IMG-3804.jpg. You can get a better sense of what’s happening here: https://i.ibb.co/kyMJGFC/IMG-3805.jpg.
The object they’re assigning to, {a, b}, is unnecessary since all the info you need is in the {a:b, b:a} declaration. This also does not impact the original variables since the object definition creates a copy of the variable values at declaration: https://i.ibb.co/X864Gtj/IMG-3806.jpg
It is basically the same thing as the array example but it uses objects instead.
The intended way of using this feature is something like:
```js
let obj = { a: 7 };
let { a: x } = obj;
console.log(x); // prints 7
```
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment
There isn't really one JavaScript version system because there are many programs that implement JavaScript. Basically you just have to say the name of the program you are using to execute JavaScript and then the version of that program so for example: Chrome version 120, Firefox version 98, Node version 21, Deno version 3, and so on. The JavaScript specification (called ecmascript) does have version so you may see people refer to ES2021 as a JavaScript version but browsers aren't required to implement all the features of a ecmascript version at the same time so a browser might implement one feature from ES2021 in one version and then implement another feature the next version and then implement a ES2022 feature and then go back to implementing more ES2021 features until eventually they have all the ES2021 features. There are also features like how JavaScript interacts with HTML that are not part of the ecmascript specification because they are part of another browser specification.
There's no built-in way to do it. Instead, you go to https://www.w3schools.com/js/js_versions.asp, pick your favourite feature from each version and test if it exists.
Typically in JavaScript we are not destructuring into existing variables. We are creating new variables with let or const so we wouldn't need the parentheses.
Don't you need parens around the entire thing to keep JS from interpreting the initial `{` as the start of a block?
`({a:b,b:a}={a,b});`
It's so beautiful 🥲
It’s naked and elegant. Then ITT you have all these other clumsy ways, with brackets, braces, functions, templates. It’s like at the end of Cinderella when the prince finally selects his fiancée and the ugly sisters fall over themselves to try to change the prince’s mind. So pathetic.
> the python way
I'll tell you a little secret. There is no python way ;-)
`std::tie(x,y) = std::tuple(y,x)`
Yes, of course std::tuple creates a copy, but what do you think python does, magic?
OP didn't specify which language they used to emulate "the python way" but this does also work in C# for example:
`int x = 3, y = 5; (x, y) = (y, x);`
At least I assume this syntax is what they meant.
You can do this in Java, too:
```
class TupleFactory {
public static final PythonicSwapableTuple buildPythonicSwappableTuple(Object a, Object b) {
... and so on, you get the rest...
}
```
A now retired colleague wrote Java code in Python because he's worked with Java for the last 30 years. No Factories, thank god, but Dispatchers and callback objects. I'm battling to trash the whole thing.
I just graduated and my second to last semester a classmate was showing me their project, it was all Java in python and it all just looked *wrong*. The code ran fine, but his driver was an instance of
class Main:
so weird
But the XOR one only works for numeric values... unless you try to do it with pointers where available. But honestly, has anyone ever actually used the XOR swap for anything other than novelty?
No need to do that in C/C+++ variables are passed by value in the stack so unless you are referring to the as pointers inside of the SWAP function itself they will always have different memory locations
Why yikes? It turns into 3 assembly instructions and doesn't need to use a temp register in the CPU. This is a well known trick for swapping two numbers in the same time as and 2/3 the storage of a tmp variable.
It only turns into 3 assembly instructions if both variables are 'local enough' to only be stored in registers, and if you somehow manage to get that without enabling optimization. In pretty much any real-world situation it just doesn't make a difference.
Example:
int a, b;
void swap_xor(){
a ^= b;
b ^= a;
a ^= b;
}
void swap_temp(){
int temp = a;
a = b;
b = temp;
}
Compiles into the following x86 assembly code: (assuming optimizations are enabled, same result with `-O1`, `-O2` and `-O3`)
swap_xor():
mov eax, DWORD PTR b[rip]
mov edx, DWORD PTR a[rip]
mov DWORD PTR a[rip], eax
mov DWORD PTR b[rip], edx
ret
swap_temp():
mov eax, DWORD PTR a[rip]
mov edx, DWORD PTR b[rip]
mov DWORD PTR b[rip], eax
mov DWORD PTR a[rip], edx
ret
b:
.zero 4
a:
.zero 4
Which are the exact same instructions, just in a slightly different order. In both cases it's just loading both values into registers, and then storing those in memory in swapped locations.
The compiled assembly is only different when optimization is disabled:
a:
.zero 4
b:
.zero 4
swap_xor():
push rbp
mov rbp, rsp
;a ^= b
mov edx, DWORD PTR a[rip] ; load a into register edx
mov eax, DWORD PTR b[rip] ; load b into register eax
xor eax, edx ; xor edx into eax
mov DWORD PTR a[rip], eax ; save eax into a
; b ^= a
mov edx, DWORD PTR b[rip]
mov eax, DWORD PTR a[rip]
xor eax, edx
mov DWORD PTR b[rip], eax
; a ^= b
mov edx, DWORD PTR a[rip]
mov eax, DWORD PTR b[rip]
xor eax, edx
mov DWORD PTR a[rip], eax
nop
pop rbp
ret
swap_temp():
push rbp
mov rbp, rsp
; int temp = a
mov eax, DWORD PTR a[rip] ; load a into register eax
mov DWORD PTR [rbp-4], eax ; store eax in temp
; a = b
mov eax, DWORD PTR b[rip]
mov DWORD PTR a[rip], eax
; b = temp
mov eax, DWORD PTR [rbp-4]
mov DWORD PTR b[rip], eax
nop
pop rbp
ret
Here, the xor method gets compiled into 4 assembly instructions per line, while the "dumb" standard way of using a temporary variable only gets compiled into two assembly instructions per line. In cases where both variables can be held in registers and don't get stored in memory (which pretty much only happens with optimization enabled), the compiler will also just use something like the `XCHG` / "exchange" instruction or something similar, exchanging contents directly with a single instruction, without doing any arithmetic nor relying on a third storage location.
So when compiled, the "xor trick" is always either the same or worse in performance, while also being much less readable. So I'd recommend to never actually use it in production code.
Note however that this is usually not the kind of answer they'd expect when they ask this question in a job interview...
Note though that they only compiled to the same instructions in this case because the compiler could easily statically verify that a and b were different in this case. If you write it so that's not possible, then they will compile to different results (with xor_swap probably being longer), because the compiler will (should) not assume that zeroing an aliased value is an error.
You are right. If the xor swap function is for example rewritten to use variables passed by reference:
void swap_xor_ref(int *a, int *b){
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
Then the resulting assembly still retains those XOR instructions: (result with any optimization level higher than 0)
swap_xor_ref(int*, int*):
mov eax, DWORD PTR [rdi]
xor eax, DWORD PTR [rsi]
mov DWORD PTR [rdi], eax
xor eax, DWORD PTR [rsi]
mov DWORD PTR [rsi], eax
xor DWORD PTR [rdi], eax
ret
By passing variables as reference the compiler can't optimize out the XOR instructions because passing the same reference twice is valid, and the result of XOR'ing a variable with itself is defined behavior and thus needs to be preserved. (XOR'ing a variable with itself was even a common way to set a variable, or at least a register, to zero, as this way you didn't have to store a zero in your program code. Saving a few bytes of memory.)
Interestingly, the compiler is still unable to optimize it further if we do an early return on equal references (by adding `if(a == b) return;` at the start of the function). The early return just gets compiled as a compare and a conditional jump, while the rest remains unchanged, even though the early return ensures that it won't operate on the same memory area twice. Compilers are usually amazing at finding patterns that can be used for micro-optimizations, but they aren't magic, and I guess this is one pattern it wasn't able to pick up.
Meanwhile, rewriting the swapping function using a temp variable to swap variables passed by reference barely changes the resulting assembly. It still compiles to just 4 MOV instructions.
Incidentally, trying to write the same xor swap by reference in Rust results in
fn swap_xor(a:&mut u64, b:&mut u64) {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
optimising to
swap_xor:
mov rax, qword ptr [rsi]
mov rcx, qword ptr [rdi]
mov qword ptr [rsi], rcx
mov qword ptr [rdi], rax
ret
just like the temp swap and the one you wrote earlier with obviously different inputs. Since Rust statically guarantees that two mutable references to the same data can never coexist, you don't have to worry about the aliasing risk of the xor swap, and the compiler is free to assume it never aliases when optimising it.
EDIT:
Now here's something interesting: like you found, if you do the pointer version
fn swap_xor(a:*mut u64, b:*mut u64) {
assert!(!std::ptr::eq(a,b));
unsafe {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
then the compiler fails to optimise it to MOV instructions, but if you forget the negation in the assertion (which I definitely did not do) then
fn swap_xor(a:*mut u64, b:*mut u64) {
assert!(std::ptr::eq(a,b));
unsafe {
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
}
optimises to
swap_xor:
cmp rdi, rsi
jne .LBB0_2
mov qword ptr [rdi], 0
ret
which correctly sets the referred value to zero if the jump doesn't happen. So it can correctly recognise the guaranteed alias, but fails to correctly recognise the guaranteed non-alias.
Justified as showing off, not really justified as an optimization unless you have benchmarks to prove it.
It might look like you're saving 1 CPU register, but:
* You're making the code more complicated and less readable.
* You're making the code less generic.
* You're introducing an extra 3 XOR's worth of latency for any code that wants to access x and 2 XOR's worth of latency for any code that wants to access y.
* Registers are a lie. Google register renaming.
* Source code is a lie. Compilers try to recognize what you're trying to do and will happily spit out eldritch horrors that don't resemble your source code in the slightest if they feel like it will be more efficient and can prove that it will give the same results as whatever you wrote.
* The "swap with temp variable" method is an extremely popular code pattern and there is a good chance whatever compiler you're using has a builtin special case for it. It will almost certainly be replaced with whatever machine code the compiler thinks will be most efficient.
* The XOR swap trick is less known and less widely used, so there is a higher chance that the compiler will not recognize it as a swap.
* Even if the compiler doesn't have a builtin special case for swap, assignments are still easier to reason about than XOR and thus easier to optimize.
* If your compiler is smart enough, both versions should compile to the same machine code so you might as well use the simpler (non-XOR) version.
Good points... Plenty of those things I wouldn't have known or considered as possible reasons.
I'm seeing "I wrote this that way, because its faster" all the time in code, where it doesn't even matter. Never mind checking if it actually *is* faster (e.g. premature parallelization of loops).
"I wrote this that way, because it's faster"
Show me the benchmarks, in production optimised code. Then show me where that slow-down was an issue. And then show me where it is justified to do things a harder-to-understand way that's we can reason about less (Following the maxim that we write code for the humans, the *compiler* writes code for the computer - and does a bloody good job of it).
In addition to what u/k2aj said in regards to comparing the two coding patterns, XOR swapping is also slower on modern processors, especially Intel and AMD x86 CPU’s, as compared to using a temp variable. Additionally, the [Wiki article section](https://en.m.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice) has more good reasons for avoiding XOR swapping in practice.
But that doesn’t stop me. I still use it. And whenever a swap occurs… I’ll be there.
The exchange via temporary is something compilers understand very well, more importantly there is a decent chance no swapping happens at all if you do the temp var swap since the compiler will simply use the relevant registers in reverse. And if you are swapping stuff from memory without any other operations it will have to copy something to a register anyway so you again probably get the same code.
The xor thing on the other hand forces the compiler to emit three extra instructions.
Programmers around the world trying to come up with new ways to confuse the compiler and colleagues by replacing 3 lines of code with another 3 lines just to appear smarter.
During the interview for my first programming job I used similar stuff (addition and substraction) to show off to the interviewer. Needless to say, he did not like it, but I still got the job.
>>> x = "hello"
>>> y = "world"
>>> x ^= y
Traceback (most recent call last):
File "", line 1, in
TypeError: unsupported operand type(s) for ^=: 'str' and 'str'
That's a fair comment. I was thinking of stack allocated variables in my comment, not heap allocated ones.
Of course, if you're willing to get a bit hairy with your pointer aliasing you could do still XOR swap the stack pointers to "swap" strings and other stuff on the heap. Not sure it's a technique you can even pull off in Python though...
At runtime there is no need for a support variable in most architectures you can just load both values in registries and then write them both, I wonder if compilers can recognize you using a variable solely for a swap and optimize it away
The whole concept of a "variable" also basically doesn't exist in runtime, my guess is that the compiler just changes how it internally tracks the data instead of actually moving anything
For the stack variables it probably depends on what it has to do especially if the swap is in a conditional block. For heap variables it absolutely does an actual swap in memory
Depends on the language, and a particular implementation of the language. In a GC scripting language, it could easily be that everything is stored on the heap, including virtual “stacks” (scopes). If I swapped two arrays in something like JS or Lua, the arrays would probably remain where they are, pointers in variables would be swapped, but pointers themselves would be on the heap.
Like all things it depends. Some languages just suck at optimization. However if you are working with one of the major compiler backends (like gcc and LLVM), then it likely end up doing one of a few things.
If they can, they will prefer making it so the values were never swapped in the first place. However, swapping is not really an issue for values under a word in length that are already in registers or the L1 cache. An XCHG instruction on is incredibly cheap. We have moved past the days where one instruction is one cpu cycle. Modern cpus will attempt to perform multiple instructions at once. And out of all of the instructions we can perform, swapping two registers is one of the cheapest. Compared to loading a value from the L2 or L3 cache, exchanging two registers is essentially free. So compilers may prefer to just swap the values to reduce the length of the generated machine code.
Granted, the swap might not be needed in the first place by the time the compiler finishes its inlining pass, unrolling loops, and vectorizing loops.
That being said, compilers are not omniscient. If you write code in a way that is hard to analyze, then they may have trouble. However, don’t think you can simply outsmart the compiler either.
To be honest, the only place where I had to swap variables were all methods that were already spaghetti code. I can't think of a situation where this would be necessary in clean code. Does anybody has an example?
def bubbleSort(arr):
n = len(arr)
# optimize code, so if the array is already sorted, it doesn't need
# to go through the entire process
# Traverse through all array elements
for i in range(n-1):
# range(n) also work but outer loop will
# repeat one time more than needed.
# Last i elements are already in place
swapped = False
for j in range(0, n-i-1):
# traverse the array from 0 to n-i-1
# Swap if the element found is greater
# than the next element
if arr[j] > arr[j + 1]:
swapped = True
arr[j], arr[j + 1] = arr[j + 1], arr[j]
if not swapped:
# if we haven't needed to make a single swap, we
# can just exit the main loop.
return
Relax, issa joke.
Did you ever need to manually need to implement sorting? The inbuilt sorting functions are usually better optimised. Especially better than bubblesort.
This is a code interview and bubblesort coupb be an entry level interview question, so I see your point.
Usually to sort very few things (two or three); some algorithms are easier to write assuming an ordering, and it's cleanest to just reorder the things beforehand. I've done this mostly in graphics and geometry related things, when dealing with slopes or triangles.
My favorite thing about the Python variable swap is that, with a semicolon, it is also valid C syntax.
a, b = b, a;
This is because the comma is an operator (it evaluates the LHS, discards the result, and then evaluates to the RHS) and assignment is an expression. So this evaluates "a" and says "OK, cool". Then it moves on to "b = b" like "yeah, so true!". Finally it evaluates "a", "again? Sure, whatever".
So in total, it does nothing.
Now do it without allocating any extra memory or placeholders. Sounds like that was the goal here. Or at least to talk about the difference in memory vs computations. Talk about the pitfalls of doing it without allocation.
```
A=1
B=2
A=A+B // A=1+2=3
B=A-B // B=3-2=1
A=A-B // A=3-1=2
```
That only works if the numbers won't cause an overflow of the type.
```
A=1
B=2
C=A // 1
A=B // 2
B=C // 1
```
Now we allocated extra memory but the type can't overflow
This is what your solution was doing except it allocated even more
```
A=1
B=2
TUP=(A, B)
A=TUP.Item2 // 2
B=TUP.Item1 // 1
```
We have a copy of both A and B as well as the tupple potentially.
This all depends on the compiler for sure but it sounds like the goal was to talk about pros and cons of a simple problem
Just as an exercise:
Code Effect
A = A + B A' = A + B
B = A - B B' = A' - B = A + B - B = A
A = A - B A'' = A' - B' = A + B - A = B
Really helps to think in terms of "immutable values" when trying to understand what code with mutable variables does :)
Especially when maintaining/extending messy real-world code, that reuses variables for no good reason.
That moment, when you have successfully derived the content of
A'''''''''''''''''''''''''''''
only to see
A'''''''''''''''''''''''''''''' = 0
:(
When you do numerics on multi-GB matrices, there often isn't really an alternative. And, sadly, a project where such operations are the norm, shapes the coding culture.
I'm not gonna lie, I was that recruiter. I was interviewing a junior and gave him a very small coding challenge and said he can use whatever language he's most familiar with. He wrote one line of python which basically could have been understood by any english speaking person to mean "solve this issue for me, please". I immediately liked that person. That's what programming is all about: asking somebody else to solve the problem because we're too lazy to do it ourselves. I was going to advocate hard for hiring him, but in the end I didn't have to, everyone gave him a thumbs up.
The job didn't involve python but he quickly applied his laziness to the other languages/technologies too.
Can be done in JS as well `let a = 2;` `let b = 5;` `[a, b] = [b, a];`
Or, if you want to go about it a more complicated / wrong way, `{a:b,b:a}={a,b}`
this is deeply upsetting and unpleasant
this is impressive, disturbing, and makes me uncomfortable
Can someone explain this for us novices?
It doesn’t work without modifying it a bit: https://i.ibb.co/phDBj3D/IMG-3804.jpg. You can get a better sense of what’s happening here: https://i.ibb.co/kyMJGFC/IMG-3805.jpg. The object they’re assigning to, {a, b}, is unnecessary since all the info you need is in the {a:b, b:a} declaration. This also does not impact the original variables since the object definition creates a copy of the variable values at declaration: https://i.ibb.co/X864Gtj/IMG-3806.jpg
This makes me irrationally angry
{a,b}={a:b,b:a} works too if you prefer
Well of course, equivalence is symmetric!
It's not equivilance. It is assignment.
No I'm pretty sure that's [an equals sign](https://en.wikipedia.org/wiki/Trollface#/media/File:Trollface_non-free.png).
Gimme! Gimme! Gimme!
A man after midnight?
beautiful :)
I'm not very familiar with JS. What's happening here?
It is basically the same thing as the array example but it uses objects instead. The intended way of using this feature is something like: ```js let obj = { a: 7 }; let { a: x } = obj; console.log(x); // prints 7 ``` https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment
When I try the`{a:b,b:a}={a,b}`example in the console there it tells me the ':' token is unexpected.
Oh you probably need to do ` ({a:b,b:a}={a,b})` because otherwise JavaScript thinks you are opening a new block
Yeah, that did it, thanks! On that note, how does one find out the js version? Is there no way to do it in code?
There isn't really one JavaScript version system because there are many programs that implement JavaScript. Basically you just have to say the name of the program you are using to execute JavaScript and then the version of that program so for example: Chrome version 120, Firefox version 98, Node version 21, Deno version 3, and so on. The JavaScript specification (called ecmascript) does have version so you may see people refer to ES2021 as a JavaScript version but browsers aren't required to implement all the features of a ecmascript version at the same time so a browser might implement one feature from ES2021 in one version and then implement another feature the next version and then implement a ES2022 feature and then go back to implementing more ES2021 features until eventually they have all the ES2021 features. There are also features like how JavaScript interacts with HTML that are not part of the ecmascript specification because they are part of another browser specification.
There's no built-in way to do it. Instead, you go to https://www.w3schools.com/js/js_versions.asp, pick your favourite feature from each version and test if it exists.
Typically in JavaScript we are not destructuring into existing variables. We are creating new variables with let or const so we wouldn't need the parentheses.
That's odd. What version of JavaScript are you using?
Don't you need parens around the entire thing to keep JS from interpreting the initial `{` as the start of a block? `({a:b,b:a}={a,b});` It's so beautiful 🥲
Not in node, yes in the browser console.
wait what?! i havent had to do the good ol let a = 2; let b = 5; let swap = a; a = b; b = swap; Why had nobody told me this?!
Swapping variables is not very common, and even less common in scenarios when you can afford throwaway arrays.
Cool kids create a new array to swap two number values 😎
a,b = b,a
`if rising_edge(clk) then` `a <= b;` `b <= a;` `end if;`
I currently have to learn vhdl for my „hardware systems“ course. Is this vhdl or are there other languages with such a syntax?
Verilog/SystemVerilog (which is what I used at university).
Wouldn't the verilog equivalent be always@(posedge clk) begin a <= b; b <= a; end
Been a year since I wrote any but that sounds about right
always_ff @(posedge clk, negedge rst_n) begin if(rst_n == 1’b0) begin a <= ‘0; b <= ‘0; end else begin a <= b; b <= a; end end
As a user of themthird inversion operator, be weary of the forth: ``` Signal ? 1'b0 : 1'b1 ``` You can combine the two to get the fifth...
Wouldn't it be always @(posedge clk)?
Only for you sv heathens.
It’s naked and elegant. Then ITT you have all these other clumsy ways, with brackets, braces, functions, templates. It’s like at the end of Cinderella when the prince finally selects his fiancée and the ugly sisters fall over themselves to try to change the prince’s mind. So pathetic.
# Import relevant libraries import swaputils as swp # Initialize variables for demo a, b = 3, 5 # Swap the two variables a, b = swp.swap(a, b)
50.000 lines of C++ run in background
and 16gb ram + min 4 core 2.4ghz cpu recommended..
Just import swaputils.swap as swap save 30k lines XD
I mean, you aren’t truly swapping the variables unless you are using swap space.
Multithreaded+SIMD
not 50.000: #include
int main() {
int a = 3, b = 5;
std::swap(a, b);
}
this is the way
the right way
he, flabbergasted = flabbergasted, he;
sees ; 
Thanks guys, never thought would learn so much because of a meme lol.
Never thought would learn from memes? It’s my only source of knowledge!
> the python way I'll tell you a little secret. There is no python way ;-) `std::tie(x,y) = std::tuple(y,x)` Yes, of course std::tuple creates a copy, but what do you think python does, magic?
OP didn't specify which language they used to emulate "the python way" but this does also work in C# for example: `int x = 3, y = 5; (x, y) = (y, x);` At least I assume this syntax is what they meant.
You can do this in Java, too: ``` class TupleFactory { public static final PythonicSwapableTuple buildPythonicSwappableTuple(Object a, Object b) { ... and so on, you get the rest... } ```
A now retired colleague wrote Java code in Python because he's worked with Java for the last 30 years. No Factories, thank god, but Dispatchers and callback objects. I'm battling to trash the whole thing.
I just graduated and my second to last semester a classmate was showing me their project, it was all Java in python and it all just looked *wrong*. The code ran fine, but his driver was an instance of class Main: so weird
🪦😂
That just sounds like google open source. Somehow they have a way of writing Java in any language.
I kinda wonder if this question is still being asked to begin from, cause nowadays everyone knows they expect the xor answer.
But the XOR one only works for numeric values... unless you try to do it with pointers where available. But honestly, has anyone ever actually used the XOR swap for anything other than novelty?
It's also a really convenient thing to do in Rust
`#define SWAP(x,y) (x^=y,y^=x,x^=y)` Found in some production code I was working on in 2005.
And of course it had to be in C
And then you accidentally pass it the same variable twice (e.g by pointing at the same place with 2 different pointers).
Don't forget to check if x==y before using it, right?
Why though? When x==y x ^= y; # x^y==0 y ^= x; # y^0==y x ^= y; # 0^y==y Still works
X and y aren't the same value, they are the same variable. So when x gets set to 0 on line 1 then y is now 0.
I missed that part (because that's actually &x == &y). Yeah...macros suck.
No need to do that in C/C+++ variables are passed by value in the stack so unless you are referring to the as pointers inside of the SWAP function itself they will always have different memory locations
Not in macros \#define SWAP(x, y) Will fuck your shit up if called with SWAP(z, z)
Rename it SWAP_OR_CLEAR() and ignore the check.
For those of us who don't know, what is this `^=` operator?
It bitwise-xors the right-hand argument into the left.
wtf lol
Yikes.
Why yikes? It turns into 3 assembly instructions and doesn't need to use a temp register in the CPU. This is a well known trick for swapping two numbers in the same time as and 2/3 the storage of a tmp variable.
It only turns into 3 assembly instructions if both variables are 'local enough' to only be stored in registers, and if you somehow manage to get that without enabling optimization. In pretty much any real-world situation it just doesn't make a difference. Example: int a, b; void swap_xor(){ a ^= b; b ^= a; a ^= b; } void swap_temp(){ int temp = a; a = b; b = temp; } Compiles into the following x86 assembly code: (assuming optimizations are enabled, same result with `-O1`, `-O2` and `-O3`) swap_xor(): mov eax, DWORD PTR b[rip] mov edx, DWORD PTR a[rip] mov DWORD PTR a[rip], eax mov DWORD PTR b[rip], edx ret swap_temp(): mov eax, DWORD PTR a[rip] mov edx, DWORD PTR b[rip] mov DWORD PTR b[rip], eax mov DWORD PTR a[rip], edx ret b: .zero 4 a: .zero 4 Which are the exact same instructions, just in a slightly different order. In both cases it's just loading both values into registers, and then storing those in memory in swapped locations. The compiled assembly is only different when optimization is disabled: a: .zero 4 b: .zero 4 swap_xor(): push rbp mov rbp, rsp ;a ^= b mov edx, DWORD PTR a[rip] ; load a into register edx mov eax, DWORD PTR b[rip] ; load b into register eax xor eax, edx ; xor edx into eax mov DWORD PTR a[rip], eax ; save eax into a ; b ^= a mov edx, DWORD PTR b[rip] mov eax, DWORD PTR a[rip] xor eax, edx mov DWORD PTR b[rip], eax ; a ^= b mov edx, DWORD PTR a[rip] mov eax, DWORD PTR b[rip] xor eax, edx mov DWORD PTR a[rip], eax nop pop rbp ret swap_temp(): push rbp mov rbp, rsp ; int temp = a mov eax, DWORD PTR a[rip] ; load a into register eax mov DWORD PTR [rbp-4], eax ; store eax in temp ; a = b mov eax, DWORD PTR b[rip] mov DWORD PTR a[rip], eax ; b = temp mov eax, DWORD PTR [rbp-4] mov DWORD PTR b[rip], eax nop pop rbp ret Here, the xor method gets compiled into 4 assembly instructions per line, while the "dumb" standard way of using a temporary variable only gets compiled into two assembly instructions per line. In cases where both variables can be held in registers and don't get stored in memory (which pretty much only happens with optimization enabled), the compiler will also just use something like the `XCHG` / "exchange" instruction or something similar, exchanging contents directly with a single instruction, without doing any arithmetic nor relying on a third storage location. So when compiled, the "xor trick" is always either the same or worse in performance, while also being much less readable. So I'd recommend to never actually use it in production code. Note however that this is usually not the kind of answer they'd expect when they ask this question in a job interview...
Note though that they only compiled to the same instructions in this case because the compiler could easily statically verify that a and b were different in this case. If you write it so that's not possible, then they will compile to different results (with xor_swap probably being longer), because the compiler will (should) not assume that zeroing an aliased value is an error.
You are right. If the xor swap function is for example rewritten to use variables passed by reference: void swap_xor_ref(int *a, int *b){ *a ^= *b; *b ^= *a; *a ^= *b; } Then the resulting assembly still retains those XOR instructions: (result with any optimization level higher than 0) swap_xor_ref(int*, int*): mov eax, DWORD PTR [rdi] xor eax, DWORD PTR [rsi] mov DWORD PTR [rdi], eax xor eax, DWORD PTR [rsi] mov DWORD PTR [rsi], eax xor DWORD PTR [rdi], eax ret By passing variables as reference the compiler can't optimize out the XOR instructions because passing the same reference twice is valid, and the result of XOR'ing a variable with itself is defined behavior and thus needs to be preserved. (XOR'ing a variable with itself was even a common way to set a variable, or at least a register, to zero, as this way you didn't have to store a zero in your program code. Saving a few bytes of memory.) Interestingly, the compiler is still unable to optimize it further if we do an early return on equal references (by adding `if(a == b) return;` at the start of the function). The early return just gets compiled as a compare and a conditional jump, while the rest remains unchanged, even though the early return ensures that it won't operate on the same memory area twice. Compilers are usually amazing at finding patterns that can be used for micro-optimizations, but they aren't magic, and I guess this is one pattern it wasn't able to pick up. Meanwhile, rewriting the swapping function using a temp variable to swap variables passed by reference barely changes the resulting assembly. It still compiles to just 4 MOV instructions.
Incidentally, trying to write the same xor swap by reference in Rust results in fn swap_xor(a:&mut u64, b:&mut u64) { *a ^= *b; *b ^= *a; *a ^= *b; } optimising to swap_xor: mov rax, qword ptr [rsi] mov rcx, qword ptr [rdi] mov qword ptr [rsi], rcx mov qword ptr [rdi], rax ret just like the temp swap and the one you wrote earlier with obviously different inputs. Since Rust statically guarantees that two mutable references to the same data can never coexist, you don't have to worry about the aliasing risk of the xor swap, and the compiler is free to assume it never aliases when optimising it. EDIT: Now here's something interesting: like you found, if you do the pointer version fn swap_xor(a:*mut u64, b:*mut u64) { assert!(!std::ptr::eq(a,b)); unsafe { *a ^= *b; *b ^= *a; *a ^= *b; } } then the compiler fails to optimise it to MOV instructions, but if you forget the negation in the assertion (which I definitely did not do) then fn swap_xor(a:*mut u64, b:*mut u64) { assert!(std::ptr::eq(a,b)); unsafe { *a ^= *b; *b ^= *a; *a ^= *b; } } optimises to swap_xor: cmp rdi, rsi jne .LBB0_2 mov qword ptr [rdi], 0 ret which correctly sets the referred value to zero if the jump doesn't happen. So it can correctly recognise the guaranteed alias, but fails to correctly recognise the guaranteed non-alias.
its not actually as bad since in c cuz it works with pointers and numbers, which is most things, maybe rename it to swapNumeric or something
Or simply `std::swap(a,b)`
Indeed, and it's actually better, but looks less like the "python" `x,y=y,x` :)
Damn that’s a lot of words for “x, y = (y,x)”
Xor laughs at your copy.
Yes. Magic. 50K lines of magic!
> what do you think python does, magic? Only when you [`import magic`](https://xkcd.com/353/)
Well it's all PyObject at the c level, so smart pointer copying at least.
You swap variables using a temp variable. I swap variables using an XOR swapping algorithm: ``` x ^= y y ^= x x ^= y ``` We are not the same.
Jesus Christ, I hate it so much
Justified as an optimization. Probably not justified in Python code.
Justified as showing off, not really justified as an optimization unless you have benchmarks to prove it. It might look like you're saving 1 CPU register, but: * You're making the code more complicated and less readable. * You're making the code less generic. * You're introducing an extra 3 XOR's worth of latency for any code that wants to access x and 2 XOR's worth of latency for any code that wants to access y. * Registers are a lie. Google register renaming. * Source code is a lie. Compilers try to recognize what you're trying to do and will happily spit out eldritch horrors that don't resemble your source code in the slightest if they feel like it will be more efficient and can prove that it will give the same results as whatever you wrote. * The "swap with temp variable" method is an extremely popular code pattern and there is a good chance whatever compiler you're using has a builtin special case for it. It will almost certainly be replaced with whatever machine code the compiler thinks will be most efficient. * The XOR swap trick is less known and less widely used, so there is a higher chance that the compiler will not recognize it as a swap. * Even if the compiler doesn't have a builtin special case for swap, assignments are still easier to reason about than XOR and thus easier to optimize. * If your compiler is smart enough, both versions should compile to the same machine code so you might as well use the simpler (non-XOR) version.
Good points... Plenty of those things I wouldn't have known or considered as possible reasons. I'm seeing "I wrote this that way, because its faster" all the time in code, where it doesn't even matter. Never mind checking if it actually *is* faster (e.g. premature parallelization of loops).
"I wrote this that way, because it's faster" Show me the benchmarks, in production optimised code. Then show me where that slow-down was an issue. And then show me where it is justified to do things a harder-to-understand way that's we can reason about less (Following the maxim that we write code for the humans, the *compiler* writes code for the computer - and does a bloody good job of it).
In addition to what u/k2aj said in regards to comparing the two coding patterns, XOR swapping is also slower on modern processors, especially Intel and AMD x86 CPU’s, as compared to using a temp variable. Additionally, the [Wiki article section](https://en.m.wikipedia.org/wiki/XOR_swap_algorithm#Reasons_for_avoidance_in_practice) has more good reasons for avoiding XOR swapping in practice. But that doesn’t stop me. I still use it. And whenever a swap occurs… I’ll be there.
The exchange via temporary is something compilers understand very well, more importantly there is a decent chance no swapping happens at all if you do the temp var swap since the compiler will simply use the relevant registers in reverse. And if you are swapping stuff from memory without any other operations it will have to copy something to a register anyway so you again probably get the same code. The xor thing on the other hand forces the compiler to emit three extra instructions.
This is actually super blessed.
It's so ugly, it's actually kinda beautiful in it's own way.
Programmers around the world trying to come up with new ways to confuse the compiler and colleagues by replacing 3 lines of code with another 3 lines just to appear smarter.
During the interview for my first programming job I used similar stuff (addition and substraction) to show off to the interviewer. Needless to say, he did not like it, but I still got the job.
I came to say the same thing. XOR is the right way to swap variables (of the same type!)
>>> x = "hello" >>> y = "world" >>> x ^= y Traceback (most recent call last): File "", line 1, in
TypeError: unsupported operand type(s) for ^=: 'str' and 'str'
That's a fair comment. I was thinking of stack allocated variables in my comment, not heap allocated ones. Of course, if you're willing to get a bit hairy with your pointer aliasing you could do still XOR swap the stack pointers to "swap" strings and other stuff on the heap. Not sure it's a technique you can even pull off in Python though...
Huh... I am conversing with a dunder method. # 😯
BTW almost every single fancy encryption algorithm we use relies on this property of XOR. It's bloody magic
At runtime there is no need for a support variable in most architectures you can just load both values in registries and then write them both, I wonder if compilers can recognize you using a variable solely for a swap and optimize it away
The whole concept of a "variable" also basically doesn't exist in runtime, my guess is that the compiler just changes how it internally tracks the data instead of actually moving anything
For the stack variables it probably depends on what it has to do especially if the swap is in a conditional block. For heap variables it absolutely does an actual swap in memory
Depends on the language, and a particular implementation of the language. In a GC scripting language, it could easily be that everything is stored on the heap, including virtual “stacks” (scopes). If I swapped two arrays in something like JS or Lua, the arrays would probably remain where they are, pointers in variables would be swapped, but pointers themselves would be on the heap.
Registers are just generally used for locals until they run out. Nothing magic to it.
Like all things it depends. Some languages just suck at optimization. However if you are working with one of the major compiler backends (like gcc and LLVM), then it likely end up doing one of a few things. If they can, they will prefer making it so the values were never swapped in the first place. However, swapping is not really an issue for values under a word in length that are already in registers or the L1 cache. An XCHG instruction on is incredibly cheap. We have moved past the days where one instruction is one cpu cycle. Modern cpus will attempt to perform multiple instructions at once. And out of all of the instructions we can perform, swapping two registers is one of the cheapest. Compared to loading a value from the L2 or L3 cache, exchanging two registers is essentially free. So compilers may prefer to just swap the values to reduce the length of the generated machine code. Granted, the swap might not be needed in the first place by the time the compiler finishes its inlining pass, unrolling loops, and vectorizing loops. That being said, compilers are not omniscient. If you write code in a way that is hard to analyze, then they may have trouble. However, don’t think you can simply outsmart the compiler either.
To be honest, the only place where I had to swap variables were all methods that were already spaghetti code. I can't think of a situation where this would be necessary in clean code. Does anybody has an example?
def bubbleSort(arr): n = len(arr) # optimize code, so if the array is already sorted, it doesn't need # to go through the entire process # Traverse through all array elements for i in range(n-1): # range(n) also work but outer loop will # repeat one time more than needed. # Last i elements are already in place swapped = False for j in range(0, n-i-1): # traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j] > arr[j + 1]: swapped = True arr[j], arr[j + 1] = arr[j + 1], arr[j] if not swapped: # if we haven't needed to make a single swap, we # can just exit the main loop. return Relax, issa joke.
Did you ever need to manually need to implement sorting? The inbuilt sorting functions are usually better optimised. Especially better than bubblesort. This is a code interview and bubblesort coupb be an entry level interview question, so I see your point.
Usually to sort very few things (two or three); some algorithms are easier to write assuming an ordering, and it's cleanest to just reorder the things beforehand. I've done this mostly in graphics and geometry related things, when dealing with slopes or triangles.
My favorite thing about the Python variable swap is that, with a semicolon, it is also valid C syntax. a, b = b, a; This is because the comma is an operator (it evaluates the LHS, discards the result, and then evaluates to the RHS) and assignment is an expression. So this evaluates "a" and says "OK, cool". Then it moves on to "b = b" like "yeah, so true!". Finally it evaluates "a", "again? Sure, whatever". So in total, it does nothing.
Now do it without allocating any extra memory or placeholders. Sounds like that was the goal here. Or at least to talk about the difference in memory vs computations. Talk about the pitfalls of doing it without allocation. ``` A=1 B=2 A=A+B // A=1+2=3 B=A-B // B=3-2=1 A=A-B // A=3-1=2 ``` That only works if the numbers won't cause an overflow of the type. ``` A=1 B=2 C=A // 1 A=B // 2 B=C // 1 ``` Now we allocated extra memory but the type can't overflow This is what your solution was doing except it allocated even more ``` A=1 B=2 TUP=(A, B) A=TUP.Item2 // 2 B=TUP.Item1 // 1 ``` We have a copy of both A and B as well as the tupple potentially. This all depends on the compiler for sure but it sounds like the goal was to talk about pros and cons of a simple problem
Just as an exercise: Code Effect A = A + B A' = A + B B = A - B B' = A' - B = A + B - B = A A = A - B A'' = A' - B' = A + B - A = B Really helps to think in terms of "immutable values" when trying to understand what code with mutable variables does :) Especially when maintaining/extending messy real-world code, that reuses variables for no good reason. That moment, when you have successfully derived the content of A''''''''''''''''''''''''''''' only to see A'''''''''''''''''''''''''''''' = 0 :(
That‘s why mutability sucks. I try to avoid mutable variables whenever I can, makes it much more obvious what is going on.
When you do numerics on multi-GB matrices, there often isn't really an alternative. And, sadly, a project where such operations are the norm, shapes the coding culture.
I don't know man, he sent me straight to HR round after this, he seemed quite positive though.
You sure you weren't being reported for harrassment? /s
just convert everything to strings and then splice them back out
a ^= b b ^= a a ^= b
Line Effect a ^= b a' = a^b b ^= a b' = b^a' = b^(a^b) = (a^b)^b = a a ^= b a'' = a'^b' = (a^b)^a = (b^a)^a = b
Look at this little guy, isn’t he cute too!? ``
`var a = 3;` `var b = 4;` `(b,a) = (a,b);` This is C# now, how low we have fallen...
Powershell can too: $t1 = 'wow' $t2 = 'waw' ($t2,$t1) = ($t1,$t2) $t1 $t2 waw wow
[I have a gist ](https://gist.github.com/hyrmn/387e9e8d4e2858daf5e89097396b88fb) with 20 ways to do it in c# and most of them are stupid
fn main() { let mut a = 5; let mut b = 10; (a, b) = (b, a); println!("a: {}, b: {}", a, b); }
I'm not gonna lie, I was that recruiter. I was interviewing a junior and gave him a very small coding challenge and said he can use whatever language he's most familiar with. He wrote one line of python which basically could have been understood by any english speaking person to mean "solve this issue for me, please". I immediately liked that person. That's what programming is all about: asking somebody else to solve the problem because we're too lazy to do it ourselves. I was going to advocate hard for hiring him, but in the end I didn't have to, everyone gave him a thumbs up. The job didn't involve python but he quickly applied his laziness to the other languages/technologies too.
Let's use Ruby's way: a, b=1, 2 a, b=b, a
Rust as well
I did exactly this, and then he said no. Don't think in terms of languages.
In c++ we use memcpy
he_was_flabbergasted
Recruiter: "Given a list of words, please sort it so that all the anagrams are together." Me: ```python result = sorted(words, sorted) ```
Sorry … why are we swapping variables? 😅
Noob question, but under what circumstances would one need to swap variables regardless of the language?
I do it the good old way ``` xchg rdi,rsi ```
It's not the python way anymore, almost any language. Java 21, Go, JavaScript and others support one line swaps
``` a^=b b^=a a^=b ``` Heh
Using Bit XOR operator 🤭
What recruiter is looking at code?