Or, in Python a, b = b, a Or Rust: (a, b) = (b, a);
Even in C++ std::tie(a, b) = std::tuple(b, a);
Or, you know,
std::swap(a, b);Swapping two Numbers without Temporary Variables
61–70 of 93 posts
Re: Swapping two Numbers without Temporary Variables
#62Earlier quoted context omitted.
Yah, or just store both the forward and backwards links in a single variable by xoring the forward and backward links together and storing it. Then the list traversal direction is picked by selecting either the head or tail and starting the operation. Halves the cost of a doubly linked list, while allowing the same function to be used for forward and backwards traversal.
Halves the cost provided that touching that many cache lines is free. Even after you rewrite them back to how they were, the cache doesn't know, so has to write back every line. If it's a balanced tree, you need only log(n) stack entries you can statically provision, and then other threads can traverse the tree at the same time. Most of the traditional optimizations turned into pessimizations decades back. That has b…
> Even after you rewrite them back to how they were
Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?
Re: Swapping two Numbers without Temporary Variables
#63Behold!, as it all becomes the same thing in C++ with optimizations on: https://godbolt.org/z/joh1jhdhq Good production compilers recognize all these swap idioms and will compile them down (i.e., canonicalize them) to the same thing. In the case of things like swapping by adding and xoring, they'll often undo the cleverness and just use temporary registers anyway. These are the kinds of micro-optimizations that compi…
I don’t think the compilers recognize the specific idiom here, but instead (what you also say) perform normalizations (e.g. into static single assignment form), expression analysis and elimination, yielding the same result. For the present case, I’d imagine a sequence of transformations like this: Convert into SSA: c = a + b; d = c - b; e = c - d; b’ = d; a’ = e; Eliminate c : d = a + b - b; e = a + b - d; b’ = d; a’…
This is fascinating.
Re: Swapping two Numbers without Temporary Variables
#64Sorry to be that guy, but this doesn't work in languages that use floats: let a = 9007199254740992; let b = 1; a = a + b b = a - b a = a - b a // 1 b // 9007199254740991
By the same logic, you could argue that `x++` doesn't work work for floats. As long as your intermediate values stay between `Number.MAX_SAFE_INTEGER` and `Number.MIN_SAFE_INTEGER`, you'll be fine.
Again, not trying to be that guy, but technically it still breaks:
a = -0.0
b = 0.0Re: Swapping two Numbers without Temporary Variables
#65I 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.
6502's xor is not efficient (IIRC) for swapping because the result is always stored in A, and the second operation is either immediate or memory. AKA it is to much an accumulator machine, similarly for 6800 even though the xor can target multiple registers the source still has to be memory, so while its possible to create an xor swap, the alternatives are going to be more efficient. Z80+/8080/etc have an exchange..
I suspect it might be useful on ArmV1 because xor can operate between registers and it doesn't (IIRC) have an xchng. Although Arm wasn't nearly register starved enough, nor does it have special register uses (index vs accumulator, etc) for a trick like this to be really useful.
PS: The fastest way to swap a register pair on 6502 is probably storing the first register into the instruction stream for an immediate load, then a register, register transfer, followed by the immediate load. Bonus if the code is running in the zero page, saving a cycle on the store. (3+2+2=7 cycles).
Re: Swapping two Numbers without Temporary Variables
#66Earlier quoted context omitted.
can you explain this please (your comments are lovely btw)
If you're interested in this sort of thing "The Art of Garbage Collection" is the standard go-to text these days. It's been a little while, but as I remember, the main reason for pointer reversing is to be able to not use any extra space to keep track of the list of grey (currently being processed) objects in a standard three-color collector. As you'll recall, a basic tracing collector marks each object as one of 3 c…
> The Art of Garbage Collection
By any chance, were you referring instead to Richard Jones' "The Garbage Collection Handbook: The Art of Automatic Memory Management"?
Garbage Collection interests me greatly, and I was looking forward to exploring a new reference - as it turned out, I couldn't find anything titled "The Art of Garbage Collection", so I thought I'd ask.
Re: Swapping two Numbers without Temporary Variables
#67I remember just after college I applied for a .net job, when I came in for the interview they gave me a paper exam with a bunch of questions on how to do silly little tricks including that one specifically. I didn't take that job.
I can't comment on the rest of the interview, but this question in particular wouldn't necessarily be bad for some positions if so many people hadn't memorized a few solutions. A large part of some jobs is applying first-principles reasoning to a set of arbitrary requirements, and predicated on the assumption that a reasonable interviewer thought this was a good question or that they explicitly asked you to do your best to reason through the problem you'd be pretty safe starting with what you know and seeing how far that got you.
A sample chain of reasoning might go as follows:
- We have to take some first step transforming (X,Y) into (f(X,Y),Y) or (X,f(X,Y)). If one has a solution the other must as well, so assume (X,f(X,Y)).
- The function f can't destroy any information since swapping two variables twice ends up where we started.
- That immediately requires that f(X,Y) must properly depend on Y or else some information would be destroyed. Moreover, it has to properly depend on X if we're to ever make forward progress in swapping the information content of the two variables.
- The problem doesn't specify how big the numbers are, so as a first pass at the problem there should probably exist a solution that works with 1-bit numbers.
- There are only 16 two-input functions on bits. Only 2 of them (XOR and XNOR) properly depend on both variables and don't destroy information.
- Applying XOR or XNOR a few times you'll easily find a small number of operations that swap two variables.
For an alternative formulation you might not bother with or notice the 1-bit simplification. You'll go on to the second operation yielding (g(X,f(X,Y)), f(X,Y)). Again looking for something that makes your life easier you assume g is some kind of partial inverse of f so that you've actually almost completed the swap (i.e., that your partial solution at this point is (Y, f(X,Y))). That suggests some kind of a group-structure and lends itself to the XOR/XNOR we previously discovered, the ADD/SUB people commonly attempt as well (and we live in the real-world, say something to the interviewer about wraparound arithmetic or needing an extra bit if you go that route), and all sorts of other methods.
And so on. If you have reason to actually try to _solve_ this problem instead of regurgitating answers you'll find a half-dozen easy methods which should still leave plenty of time for the rest of the interview.
Side-note: I recall needing silly tricks like that more in .NET than other platforms. They didn't have an optimized popcount even as recently as the beginning of Covid for God's sake.
Re: Swapping two Numbers without Temporary Variables
#68XOR swap, as others have noted, is another very common way of implementing a swap without temporary variables. It's also a good exercise for formal verification, here's a proof in Coq of XOR swap's correctness in C.[0]
[0] https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503...
Re: Swapping two Numbers without Temporary Variables
#69I 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.
> The only weird thing is that the article has managed to reach the front page.
This is the kind of detail not surfaced in a Boot Camp.
This isn’t to harsh on BCs. They have a specific goal and a short fuse, and the kind of things they cover use languages that are so high level you tend to have no visibility into the actual machine.
Re: Swapping two Numbers without Temporary Variables
#70Earlier quoted context omitted.
Halves the cost provided that touching that many cache lines is free. Even after you rewrite them back to how they were, the cache doesn't know, so has to write back every line. If it's a balanced tree, you need only log(n) stack entries you can statically provision, and then other threads can traverse the tree at the same time. Most of the traditional optimizations turned into pessimizations decades back. That has b…
> Even after you rewrite them back to how they were Why would you do that? I was under the impression that the trick with the "XOR-ly linked list" is to keep these in RAM strictly in the XOR'd form. What exactly did you mean by "has to write back every line"?
I misremembered the trick. Yes, it does save on storage without appreciable overhead.