Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Swapping two Numbers without Temporary Variables

garrit.xyz

Post reply on HN
Print view View original

81–90 of 93 posts

Re: Swapping two Numbers without Temporary Variables

#81

Post by tialaramex »

layer8 wrote: post #43
a_e_k wrote: post #38

Behold!, 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’…

Idiom recognition has been a thing in compilers for decades, so certainly don't rule it out.

Re: Swapping two Numbers without Temporary Variables

#83

Post by tialaramex »

lanna wrote: post #13
paxys wrote: post #6

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.

And on a modern CPU the machine code does not map 1-to-1 to what actually happens when this is executed, the phrase "out-of-order execution" ought to give away that even though your machine code says A, then B, then C, the CPU may decide it was better to do A, then C, then B instead.

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.

Re: Swapping two Numbers without Temporary Variables

#85

Post by Khoth »

happytoexplain wrote: post #18
wolpoli wrote: post #15

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?

A modern CPU makes heavy use of out of order execution to do things quickly. Having the results of one operation depend on another makes it harder for the CPU to do this.

If you have this:

  a = a + b
  b = a - b
  a = a - b
  // use a for something
  c = a + 7
then the final value of 'a' depends on both 'a' and 'b', so execution of the final line can't happen until the original 'a' and 'b' have both been fetched from memory/calculated/whatever.

However, if you have this:

  temp = b
  b = a
  a = temp
  // use a for something
  c = a + 7
then the final value of 'a' depends only on 'b', so the final line can be executed even if the original 'a' isn't yet available.

Re: Swapping two Numbers without Temporary Variables

#87

Post by KMag »

mangamadaiyan wrote: post #66
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…

> 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.

Oops. You're right. "The Garbage Collection Handbook: The Art of Automatic Memory Management" by Richard Jones, et al., CRC Press, 2012.

Re: Swapping two Numbers without Temporary Variables

#89

Post by KMag »

KMag wrote: post #37
Jerrrry wrote: post #9

Earlier 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…

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 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...

Re: Swapping two Numbers without Temporary Variables

#90

Post by madars »

groby_b wrote: post #54
makeset wrote: post #45

Earlier quoted context omitted.

XNOR is the (only) other binary operator that also works.

That'd be because they are the only bitwise operations under which integers form an Abelian group. Specifically, AND and OR lack an inverse operation.

By the way, while one indeed needs the ability to "cancel out"/invert, we can derive similar swaps in weaker algebraic structures (and don't need full Abelian groups). For example, non-zero rationals can be divide-swapped: a = a / b; b = a / (1 / b); a = b / a; or similar for subtraction-swap. In general, a quasigroup seems to suffice: a = a * b; b = a / b; a = b \ a (where * is the group operation and / and \ are the right and left divisions, respectively).
Post reply on HN