Swapping two Numbers without Temporary Variables • Hacker News Board

Re: Swapping two Numbers without Temporary Variables

#91

Post by rurban » Sat, Mar 26, 2022, 8:08 AM UTC

KMag wrote: post #89

KMag wrote: post #37

Earlier quoted context omitted.

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…

Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1] 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 numbe…

yes, you keep the 3 colors in each object. conveniently 2 bits of a pointer.

Re: Swapping two Numbers without Temporary Variables

#92

Post by rurban » Sat, Mar 26, 2022, 8:10 AM UTC

ncmncm wrote: post #60

mkdirp wrote: post #58

Earlier quoted context omitted.

Doesn't this create a new (temporary) array of value `[b,a]`?

If it does, that was optimal. If it doesn't, that was optimal. Outsmarting your optimizer is harder than that nowadays.

if optimizers would be smart. they are not.

they do bad things, and occasionally even wrong things. and usually compiler writers blame the user, not themselves then.

Re: Swapping two Numbers without Temporary Variables

#93

Post by KMag » Sat, Mar 26, 2022, 4:16 PM UTC

rurban wrote: post #91

KMag wrote: post #89

Earlier quoted context omitted.

Aha... it seems I've been lied to! It seems the proof of correctness is for a binary graph (each node has an out-degree of at most 2, but cycles are allowed in the graph) and needs 2 extra bits of state per node. [0][1] 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 numbe…

yes, you keep the 3 colors in each object. conveniently 2 bits of a pointer.

That's not quite what I'm talking about. If you look at Gries's 2006 paper (the less formal one, not his formal proof of the algorithm), each node has 2 bits for state and two child pointers.

  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

To generalize this algorithm to nodes with k children, you need to either pack ceil(log2(k+1)) bits into object header and tag bits in the first few fields of the object, or else have a white/not-white bit in the object header and have one tag bit in each object field, indicating which pointer has been reversed to point to the parent node. The latter is less complex, but results in O(k^2) time complexity in the repeated scanning of the object to find the currently reversed pointer each time you recurse back up to the node while traversing the graph. To really maximize speed, I suspect the O(k^2) algorithm is used in practice for small k, and the more complex counter spread across tag bits of multiple pointers is used for nodes with larger k.