7 ms·
Xor swap trick and add/sub swap trick (2010)
- threatofrain 5y agohttps://graphics.stanford.edu/~seander/bithacks.html https://graphics.stanford.edu/~seander/bithacks.html
- xnorswap 5y agoApparently you can do it with xnor too, which I didn't actually realise when I made this username.
- hansvm 5y agoYep, and all the solutions that treat bits independently are some combination of xor/xnor/not/identity. They can't get very long (certainly no more than 23 operations) without repeating some pair of numbers, hence being trivially reducible. The two shortest solutions are pure xor or pure xnor, so in some sense any not operations are also extraneous.
- tweakimp 5y agoWhy dont all languages have the inplace swap built in like python has? In python you can just do: y, x = x, y
- xxs 5y agoIt only makes sense to swap elements of an arrays (lists). Swapping variable is super rare. I can't recall the same time I had to swap two integers/floats or even object references.
- eesmith 5y agoYou're right! I was surprised. I did: ag '(^|[^a-zA-Z0-9=])([a-zA-Z_][a-zA-Z0-9_]*), ?([a-zA-Z_][a-zA-Z0-9_]*) ?= ?\3, ?\2' across several Python code bases I've worked on, and indeed found very few examples. Here's one from Python's statistics.py: X, Y = self, other if (Y._sigma, Y._mu) < (X._sigma, X._mu): # sort to assure commutativity X, Y = Y, X NumPy has only one match that isn't in test code, in numpy/core/numeric.py:convolve if (len(v) > len(a)): a, v = v, a It's a bit more common in SciPy, like scipy/linalg/blas.py:_get_funcs which has: if prefer_fortran: module1, module2 = module2, module1 but even then, there are only 26 relevant matches across 421KLoC.
- dotancohen 5y ago> ag '(^|[^a-zA-Z0-9=])([a-zA-Z_][a-zA-Z0-9_]*), ?([a-zA-Z_][a-zA-Z0-9_]*) ?= ?\3, ?\2' Why are you checking `(^|[^a-zA-Z0-9=])` before the first variable? Why are you storing it? Wouldn't `^\s*` (beginning of line, then 0 or more whitespace, not stored) be simpler? I ask to learn, not critically.
- eesmith 5y agoThe exclusion test is to reduce false positives like: return open(filename, mode, encoding=encoding, errors=errors) ^^^^^^^^^^^^^^^^^^^^^^^ This case matches because of the under-caret'ed e, encoding=encoding, e You are right that requiring only leading whitespace would be clearer. I didn't think of it. I only wanted to eliminate those false positives I was seeing with my original test, which only had \2, \1. In thinking more about it, your whitespace-only gives a false negative for constructs like: progressbar/widgets.py:306: if not self.fill_left: rpad, lpad = lpad, rpad matplotlib/lib/matplotlib/widgets.py:1093: if vmin>vmax: vmin, vmax = vmax, vmin The reason I stored \1 was simply to get the grouping. I didn't recall the syntax for non-capturing groups, and it wasn't worthwhile to look up.
- dotancohen 5y agoI see, thank you. Targeting the if statements, but not the open() methods, is an interesting corner case that I would not have though about.
- eesmith 5y agoI did mine because I thought some people might write it: (a, b) = (b, a) so the grouping stands out better. Turns out I didn't find any examples of that.
- jasonhansel 5y agoIt's a bit more common in C when swapping pointers, since it can help you ensure that there's only one pointer to a given structure at any time, and it can simplify memory management in certain cases by letting you repurpose an existing allocation.
- forgotpwd16 5y agoInterestingly checking the implementation of this[0], it uses two temporary variables rather the commonly one. [0]:https://stackoverflow.com/a/62038590/1308965 https://stackoverflow.com/a/62038590/1308965
- Sebb767 5y agoBecause few languages have the ability to create a tuple with syntactic sugar on the fly that Python has. In PHP, you can similarly do the following: > list($a, $b) = [$b, $a]; Which is a bit more verbose than what Python does, but it's the same thing under the hood - you create a list/tuple, create a new list with swapped items at specific indices and then dissolve that list back to local variables. In the end, this is more expensive than the swap you'd do in C++^W other languages (EDIT: apparently C++ can also do this now), since it involves tuple creation. Although the compiler/JIT/interpreter will most likely recognize this pattern and optimize it to a `swap` call.
- adastra22 5y agoC++ can do multiple assignment now, fyi.
- tored 5y agoSince PHP 7.1 you can write [$a, $b] = [$b, $a];
- Koiwai 5y agoLots of newer languages can, like go and rust. BTW it's not "creating a tuple with syntactic sugar on the fly", I mean, if you think that's creating a tuple, obviously in lots of languages, that tuple is created by passing x/y's value, assigning to that anonymous tuple won't affect original x/y. The correct term should be destructuring assignment.
- Koiwai 5y agoIt's called destructuring assignment, it's not just for "in-place swap", and more over, it's about syntax, not performance. That article is talking about performance, and as many have pointed out, it's better just use a 3rd variable(when there's no destructuring assignment) to swap and let compiler do its work. I'm not saying syntax sugar is a bad thing.
- tialaramex 5y agoOr, express directly what you intended and let the compiler and library do it: e.g. https://doc.rust-lang.org/core/mem/fn.swap.html https://doc.rust-lang.org/core/mem/fn.swap.html
- mjg59 5y agoArticle is from 2010 so not going to quibble about there having been a lot of history since then, but from the end: > especially since floating point operations are generally compiled to use the x87 fpu (so the floats will be moved back into gprs, and end up being slower than a regular swap) gcc, at least, will use SSE rather than x87 by default on 64-bit x86. Looking at godbolt there's still a bunch of conversions that come out to about the same number of instructions, although I suspect doing it with SSE is probably faster than doing it with x87. Doing it with a temporary variable instead rather than coercing through a series of casts is probably even faster, though.
- stncls 5y agoAlso probably excusable because 2010, but from that same part of the article: void swap(int& x, int& y); void swap(float& x, float& y) { swap((int&)x, (int&)y); } This is UB and may explode. Probably the only portable way to do it is a memcpy() [1]. [1] https://blog.regehr.org/archives/959 https://blog.regehr.org/archives/959
- CyberRabbi 5y agoC compilers should really refuse to compile code that does blatant type punning like this. Is there a book out there that is teaching people this is okay? Everything I’ve ever learned about C/C++ has explicitly warned against type punning.
- hrydgard 5y agoThis is old, cute, but simply slow and a really bad idea on modern hardware.
- mi_lk 5y ago> slow and a really bad idea on modern hardware. say more?
- bruce343434 5y agocare to elaborate? It's just 3 instructions.
- jleahy 5y agoOn a modern x86 cpu the ‘xchg’ instruction performs a swap and can do so entirely in the front-end via register renaming. It doesn’t even require a micro-op. This ‘trick’ actually requires executing micro-ops and creates an unnecessary data dependency (which is actually worse than the micro-ops themselves). Better to just use more variables and let the register allocator in the compiler decide what to do. If it’s a loop then unrolling it once could remove the need for any swapping at all, for example.
- animal531 5y agoI'd also hazard that throwing in an if statement in place of a temporary variable is a bad idea.
- zwegner 5y ago> On a modern x86 cpu the ‘xchg’ instruction performs a swap and can do so entirely in the front-end via register renaming. It doesn’t even require a micro-op. This is only true for AMD cpus, on Intel xchg is 3 uops. Still better than the xor trick, though. Source: https://www.uops.info/html-instr/XCHG_R64_R64.html https://www.uops.info/html-instr/XCHG_R64_R64.html
- marginalia_nu 5y agoWhat if you want to swap two large memory blocks? Should be doable in a maximally cache-fridendly way with SIMD XORs I think.
- jacquesm 5y agoThe better way to deal with having to swap two items is to ensure they end up in the right spot in the first place. Seeing a 'swap' is usually a sign of something being wrong a bit upstream.
- wheybags 5y agoWhat about inside the implementation of a sorting routine? Or the move assign operator of a smart pointer? There are plenty of legitimate reasons to swap variables, not everyone is making a crud app.
- jacquesm 5y agoWhen implementing a sorting routine the typical 'swap' operation is two loads and stores from memory, and the order of the loads and stores is what effects the swap, you don't typically do swap-in-place with memory.
- xanathar 5y ago99.9% of the time swaps are done for a reason, usually when sorting or manipulating linked lists pointers, but - for example - comes into play also when you want to transpose a matrix in place, or other similar algorithms. I guess you can make an argument that the best way to get an array sorted is to have the array already sorted, but that sounds as "the best way to calculate the length of the hypotenuse is to just measure the hypotenuse, and Pythagoras never realized it was a problem upstream".
- jacquesm 5y agoOf course swaps are done 'for a reason'. But this is an implementation detail for a swap, one where the xor trick is used to be able to swap 'in place' without using a third variable to perform the swap, and that screams 'register constraints'. To get into that situation is the mistake, not to get clever to use an xor swap to get you back out of it. In any other situation that realistically speaking would occur such constraints would not normally exist.
- deleted 5y ago[deleted]
- notorandit 5y agoThat's an old trick that, IMHO, makes no practical sense at all. Unless you are in tight long running loop that needs to swaps several pair of values, the advantage of the trick is rather tiny with the extra disadvantage of portability and readability. Watch your steps! The swap with floats relies on sizeof( float ) == sizeof( int ) which could not always be the case. Yes, you can create a set of macros and conditional compilation stanzas to cope with that and cover also char, short, long, long long, double and long double. Finally, the explanation on why it works would be a great supplement to the article.
- Brian_K_White 5y agoAnd as far as I can see the assert() should have been if(x==y) return(0).
- tzs 5y agoA similar old trick that both swaps x with y and negates y: x -= y // x-y, y y += x // x-y, x x -= y // -y, x If (x, y) represents a 2d vector this operation rotates the vector counterclockwise 90°.
- xxs 5y agodoesn't work with floats, due to NaN, infinity
- praptak 5y agoOne of the Underhanded C contestants used this trick, obviously intentionally admitting &x == &y. Hitting this edge case triggered the desired "underhanded" behavior of the program. Here: http://www.underhanded-c.org/_page_id_16.html http://www.underhanded-c.org/_page_id_16.html
- deleted 5y ago[deleted]
- billpg 5y agoUse the temporary variable swap and let the compiler detect what you're doing and optimize it away if it can.
- Brian_K_White 5y agoWhy treat x == y as an error instead of just returning success immediately without doing any other work?