There is an old bit twiddling trick that uses XOR to swap two integer values. Theoretically, this optimization saves one register, and on older compil

Search code, repositories, users, issues, pull requests...

submited by
Style Pass
2024-11-23 12:30:07

There is an old bit twiddling trick that uses XOR to swap two integer values. Theoretically, this optimization saves one register, and on older compilers with worse register allocators, a whole stack allocation.

However, is this trick still relevant today? Modern processors make use of Tomasulo's algorithm to rename registers on the fly and avoid stalls from write after read or write after write hazards.

To test the performance of the xor trick, we use a swap-heavy algorithm like bubble-sort. Unfortunately, clang is too smart on my machine and compiles both variants of the code to efficiently use the stp (store pair of registers) instruction. The solution is to write inline assembly for this functionality.

Gross. For the uninitiated, %0 and %1 refer to the output operands that are specified after the colon. +Kr (x) means we want a register (r) that we can read and write to (+), be used with 32-bit logical instructions (K), and is where the variable x is stored.

Anyways, we can now run the algorithm on different length random number arrays to get a result. For random number generation, we read from /dev/urandom. This may be slower than reading a small seed for a pseudo random number generator (PRNG), but it works.

Leave a Comment