4 ms·
There’s a well-known in-place implementation of swap of the form: a ^= b b ^= a a ^= b (Here ^ denotes bitwise XOR) Allowing for the mask, one could do
by kevinventullo 2y ago
There’s a well-known in-place implementation of swap of the form:
a ^= b
b ^= a
a ^= b
(Here ^ denotes bitwise XOR)
Allowing for the mask, one could do an in-place version of swap_if via
a ^= (b & mask)
b ^= (a & mask)
a ^= (b & mask)
The in-place version of swap is generally discouraged because compilers are smart (https://stackoverflow.com/questions/36906/what-is-the-fastest-way-to-swap-values-in-c https://stackoverflow.com/questions/36906/what-is-the-fastes...) but I do wonder whether the masking in swap_if obscures intent to the compiler enough to close the gap.
Assuming the mask is passed in, Godbolt puts OP’s swap_if at 26 instructions, versus the above swap_if at 17 instructions: https://godbolt.org/z/Wedco5hPv https://godbolt.org/z/Wedco5hPv
- ack_complete 2y agoYou have the optimizer disabled and the functions are no-ops. Additionally, masking that way makes the XOR no longer a no-op, so only one masking operation is necessary -- but it seems that GCC already knows this trick: https://godbolt.org/z/qxMvcbrc8 https://godbolt.org/z/qxMvcbrc8
- kevinventullo 2y agoOof, thank you for the correction.
- Someone 2y ago> The in-place version of swap is generally discouraged because compilers are smart Isn’t that more because CPUs slow down when there are dependencies between instructions? Compilers could (and may even do) fairly easily detect that pattern (like they do with some versions of popcnt. See for example https://langdev.stackexchange.com/questions/3942/what-are-the-ways-compilers-recognize-complex-patterns https://langdev.stackexchange.com/questions/3942/what-are-th..., discussed here in https://news.ycombinator.com/item?id=40987123 https://news.ycombinator.com/item?id=40987123) and compile it to whatever is fastest on the target CPU/in the given context (in some contexts, it can be compiled to nothing, just changing the mapping between local variables and the registers they’re stored in)
- gpderetta 2y ago> Isn’t that more because CPUs slow down when there are dependencies between instructions? Indeed, while reg-reg moves can be resolved at the rename stage and are effectively free latency-wise.
- Almondsetat 2y agoCPUs have shortcuts in the pipeline to provide the results to the dependent operation in time