21–30 of 93 posts
To deal with overflow the size of variable a needs to be doubled. This trick, if applied correctly, uses the same amounts of memory. Now you may wonder whether we can mathematically prove swapping two variavles requires memory of three variables in digital computer...
I'd still be curious about any theories of storage.
Earlier quoted context omitted.
These aren't algorithms. The language is still doing something under the hood to do the swap.
Some people seem to forget that in high-level programming languages, lines of code seldom map 1-to-1 to processor instructions.
The person that developed this trick is obviously familiar with the Mathematical properties of numbers. But this is the wrong approach from many prospective, including the impact to performance, the potential of under/overflow, and the lack of readability.
The author explicitly states that it should never be used due to readability. I'm interested in your point about performance, though - as a layman in this area, I would have thought that the additional operations were cheaper than whatever the overhead of a variable is, even for a primitive value type. Is that definitely not the case?
Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);
import dis
def swap(a, b):
a, b = b, a
return a
dis.dis(swap)
4 0 LOAD_FAST 1 (b)
2 LOAD_FAST 0 (a)
4 ROT_TWO
6 STORE_FAST 0 (a)
8 STORE_FAST 1 (b)
5 10 LOAD_FAST 0 (a)
12 RETURN_VALUE
I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.
Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);
I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.
Edit: I am hard pressed to think of an Assembly that doesn't have exchange (swap) between registers - e.g. 6502, but has a xor instead.
To deal with overflow the size of variable a needs to be doubled. This trick, if applied correctly, uses the same amounts of memory. Now you may wonder whether we can mathematically prove swapping two variavles requires memory of three variables in digital computer...
You could use unsigned ints, whose arithmetic wraps, to deal with the overflow. I'd still be curious about any theories of storage.
I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.
The only weird thing is that the article has managed to reach the front page. I was under the impression all number (and pointer) swap methods are very well known - with xor being the most applicable. Edit: I am hard pressed to think of an Assembly that doesn't have exchange (swap) between registers - e.g. 6502, but has a xor instead.
I think the more accepted way for a long time has been to use xor. https://en.wikipedia.org/wiki/XOR_swap_algorithm Its better in a number of ways, and since each bit is independent, it could actually be faster on really low end/old processors. Although these days just about any modern OoO processor will just detect swaps (even if there isn't an actual instruction) and the renamer makes it zero cost.
The only weird thing is that the article has managed to reach the front page. I was under the impression all number (and pointer) swap methods are very well known - with xor being the most applicable. Edit: I am hard pressed to think of an Assembly that doesn't have exchange (swap) between registers - e.g. 6502, but has a xor instead.