Swapping two Numbers without Temporary Variables
garrit.xyz
garrit.xyz
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 compilers excel at, so write the code clearly, leave that job to them, and worry about the high-level stuff that the compiler can't do for you.
Convert into SSA:
c = a + b;
d = c - b;
e = c - d;
b’ = d;
a’ = e;
d = a + b - b;
e = a + b - d;
b’ = d;
a’ = e;
d = a;
e = a + b - d;
b’ = d;
a’ = e;
d = a;
e = a + b - a;
b’ = d;
a’ = e;
d = a;
e = b;
b’ = d;
a’ = e;
e = b;
b’ = a;
a’ = e;
[0] https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
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.
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).
Hmm, Arm v1 - that's something I don't know. The earliest Assembly I know is the v6.
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.
Specifically, AND and OR lack an inverse operation.
Think of NaNs, infinities, operands that are vastly different in magnitude (e.g. try calculating (1e10 + 1e-10 - 1e10)) and so on.
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 colors: black, white, and grey. It must maintain the invariant that black objects never have pointers to white objects. A (full) GC cycle begins with all objects marked white, then the GC roots are marked grey. Then the collector repeatedly removes an object from the grey set, marks all of the white objects it points to as grey, and then marks the just removed grey object black. The GC cycle ends when there are no more grey objects, at which point all white objects are garbage and can be reclaimed.
This is often implemented by using a single bit in the object header to keep track of white/black, and a stack to keep track of the set of grey objects. In this setup, a white object is marked grey by setting the color bit in the object header to whichever color indicates black, and putting it in the grey set. That is, grey objects are really marked black, but in the grey set. In other words, the color bit in the object header is really a "white"/"not white" bit. This is the easiest way to ensure a white object never gets added twice to the grey set without having to explicitly mark the object as grey. (Some systems actually invert the sense of the color bit in the object header between major GC collections. In one major collection 0 means white, and the next major collection 0 means black. This avoids having to scan the heap marking all objects white at the beginning of the GC cycle.)
One way to implement the logical stack of grey objects is to use a singly-linked list. If you want to implement a linked list of objects without adding an extra pointer to every object's header, and you don't want to allocate any extra space in the middle of a garbage collection, then you need to figure out some kind of clever hack to re-purpose some existing space. I forget the exact details, but (1) if an object doesn't have any pointers in it, you can immediately mark it black without first adding it to the grey set ... and that's where I lose track of the details about how you keep track of which object pointer you've borrowed to reverse in order to use a linked list to implement your grey object stack.
So, I'm missing the key detail that makes the whole trick work, but at a high level, you have extra storage space of one pointer to point at the top of the grey stack. The object at the bottom of the grey stack has its pointer nulled out, and off to the side you keep track of that last final pointer to restore when you empty the grey stack (which ends the GC cycle). When you pop an object off of the grey stack, you point its pointer to the previous object popped off of the grey stack (thus restoring (re-reversing) its reversed pointer).
However, I can't for the life of me remember how you keep track of which pointer you've reversed in each object without using any extra space. I don't think you can always just use the first pointer in an object, because that could trap you in a cyclic sub-graph.
EDIT: I've found a few different sets of very vague lecture notes online that are super vague... just saying you reverse pointers in order to make a linked list of grey objects. However, if you reverse all of the pointers, you don't get a linked list, but a general graph. You need to have exactly one pointer per object in order to have a singly linked list. If you have some rule of always using the first (or last) non-null pointer in an object, you might still wind up in a situation where you're reversing a cycle of pointers. I found a nice slide deck showing the steps, but the example was acyclic, and there was no explanatory text.
I thought maybe there's a trick with using two bits for color in the object header, and using that to mark which pointer has been reversed by also marking the target object, but that breaks if there are multiple pointers to the specially marked object.
Maybe the unmentioned trick is to use tagged pointers to keep track of the one pointer in each grey object that has been reversed. I really hope that's not it. That just feels... less brilliant.
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.
Now, one can represent any higher-degree graph as a binary graph by simply replacing any higher-degree nodes with a binary tree with the required number of out-nodes, but then that increases the number of extra bits required.
Gries's 2006 less formal writeup [1] is simple to extend to higher-degree nodes. Instead of his 2-bit counter, one can use a counter that goes from 0 to the number of out-links. My guess is that real implementations use tagged pointers to indicate which pointer has been reversed instead of using a counter in Gries's write-up.
I feel so lied to! No wonder I couldn't figure out how to do it without tagged pointers! Though, please correct me if you find a pointer reversal algorithm that doesn't use tagged pointers and is guaranteed to terminate in the case of arbitrary graph cycles.
[0] https://xlinux.nist.gov/dads//HTML/SchorrWaiteGraphMarking.h...
[1] https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec...
State 0: Node is white
State 1: Node is grey and child[0] points to parent
State 2: Node is grey and child[1] points to parent
State 3: Node is black and both child pointers are restored
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 been a good thing.
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"?
let a = 9007199254740992;
let b = 1;
a = a + b
b = a - b
a = a - b
a // 1
b // 9007199254740991 a = -0.0
b = 0.0"Please never use this in any production code. The less we have to think about a piece of code, the better it is. It's a fun thought experiment nevertheless!"
a, b = b, a
(a, b) = (b, a);Express your actual intent, if your chosen language has a "swap" intrinsic, use it, if not write the swap in a natural and idiomatic way, and let other people do the lifting.
And then the cpu is doing something under the hood to do whatever the assembly code thought it said.
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
std::tie(a, b) = std::tuple(b, a); std::swap(a, b);If you have this:
a = a + b
b = a - b
a = a - b
// use a for something
c = a + 7
However, if you have this:
temp = b
b = a
a = temp
// use a for something
c = a + 7
Bear in mind this is a place building relatively simple web apps... standard line of business stuff. The test was questions like "how many words can you unscramble from these letters" etc.
A majority of the engineers felt the test meant you "knew you were working with smart people". A majority of the code was unmaintainable sludge. (though a few people were extremely talented)
I no longer work there.
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.
let a = 5;
let b = 10;
[a,b] = [b,a];
console.log(a,b) // 10, 5
Outsmarting your optimizer is harder than that nowadays.
they do bad things, and occasionally even wrong things. and usually compiler writers blame the user, not themselves then.
[0] https://gist.github.com/siraben/d2ad58914166d5f6139b03b1b503...
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.
It works for integers (and pointers)
[1] Actually multiple of sizeof(char), where sizeof(char) is defined as 1. And that's technically not 1 byte everywhere, but most of the time nowadays it is.
Telling someone who doesn't know what widening a variable means that they meant widening a variable without explaining what widening a variable means helps no one.
(Plus adding 1 bit to the "bit size" of a variable _does_ double the base 10 size of the variable if you want to be really pedantic)
This is consistent with other uses: The size of an array, the size of a data structure in general, the size of a file... In all of those you are concerned about how much memory or disk space is taken.
So I think calling the range "size" is counterintuitive and gives the wrong idea, and I do not agree that the "base 10 size" of a variable is equivalent to its range. (What does "base 10" have to do with it anyway? The range is doubled no matter what base we're operating in.)