3 ms·

I would expect eliminating branches in a busy inner loop to matter. The interesting part is how that was done: > A New Primitive, swap_if > How can we use th

I would expect eliminating branches in a busy inner loop to matter. The interesting part is how that was done: > A New Primitive, swap_if > How can we use this method in our sort? First, let us make a swap_if: inline bool swap_if(bool c, int& a, int& b) { int ta = a, mask = -c; // false -> 0, true -> 111..111 a = (b & mask) | (ta & ~mask); b = (ta & mask) | (b & ~mask); return c; } > In our partition function, then, we can transform if (*right <= pivot) { int tmp = *left; *left = *right, *right = tmp; ++left; } > into just left += swap_if(*right <= pivot, *left, *right);

magicalhippo 2y ago
Will we see x86 or similar CPUs replace hot instruction blocks with current-processor-specific optimized code during runtime, similar to how certain JIT VMs do? What I mean is, say you have a similar simple "x = (cond) ? a : b;" which the compiler has not translated to a CMOV. If this is in a hot loop then the CPU could, in theory, notice that "it's just doing a conditional move, I can do the CMOV faster" and then translate those code bytes at that memory location to a CMOV instead (ie during decoding or something like that). Not worth the complexity? I imagine it would slow down the decoder or wherever they insert this replacement logic. Or am I hopelessly out of date and they're already doing this?
- akira2501 2y ago
  I think it could only do that in spans of code where interrupts are disabled and purely between values already in registers. CPU state feels like it's in your control, but it's not at all in your control, and even if it was, multiple processes might exist and memory is never in your control.
- saagarjha 2y ago
  Whether to use a branch or a conditional move isn’t really dependent on what the source is doing but how likely the branch is and its dependencies. Simplifying a bit, an explicit cmov is basically telling the computer that the condition is not easy to predict and to not bother. Modern processors will typically do the same analysis themselves and perform similarly on a branch with a slight overhead.
- jeffbee 2y ago
  > Will we see x86 or similar CPUs replace hot instruction blocks with current-processor-specific optimized code during runtime, similar to how certain JIT VMs do? Wasn't that one of Transmeta's things?
  - magicalhippo 2y ago
    Kinda, though Transmeta was built to translate everything. I must admit though I had forgotten some details, and you're right in that my idea is not unlike bolting the Code Morphing stuff to a regular x86 core.
- gpderetta 2y ago
  Look for "idiom detection". Macro uop fusion is a limited form of this. As a relevant example, POWER CPUs can convert some non diverging branches into conditional execution if not well predictable. Many RISC CPUs can convert well known LL/SC code patterns into locked atomic operations to guarantee forward progress.
  - magicalhippo 2y ago
    Thanks, keyword helped. Yeah I was thinking about macro uop fusion but taken to another level.
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 ago
  You 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 ago
    Oof, 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)
a_e_k 2y ago
This sort of use of turning conditionals into bitmasks and then shuffling masked values around was fairly common back in the day when writing code for SSE intrinsics. You wouldn't want to have to check each lane individually since that would spoil the point of using SSE. So you'd write masking ops like this and keep things parallel, tThen judiciously use any() and all() type intrinsics to check whether the lanes could agree to skip certain blocks conditionally. (This was before ISPC and before autovectorization to handle it for you.)
- djmips 2y ago
  Does ISPC + auto vectorization truly remove the need to attend to these details in the most optimized code?
  - a_e_k 2y ago
    They can, yes. For example, here's a simple Compiler Explorer link with a simple loop conditionally copying from one of two values: https://godbolt.org/z/TbeK99sx1 https://godbolt.org/z/TbeK99sx1. If you look at the assembly code produced, you'll see in lines 9-11, it's doing a similar thing as the swap_if() function: ANDing one value with the mask, ANDing the other with the negation of the mask, and then ORing them together. And it produced that automatically from the ternary in the loop. They can also do things like automatically generate epilogues with a serial loop to handle the leftover items if the loop count isn't an even multiple of the SIMD width. That's something else that I remember writing by hand before autovectorizers. That said, coaxing an autovectorizer to actually vectorize a loop can be an art in itself. They're notoriously finicky. My favorite used to be the one in the old ("classic") ICC compiler where you use compiler flags to get a nice optimization report which would explain exactly why it chose what it did for each loop. You could also set #pragma's which would noisily warn or error out if the associated loop failed to vectorize for some reason. (And of course, a lot of this stuff you might just use GPU compute for now.)
    - mgaunard 2y ago
      normally there is an instruction for this called blend (since SSE4.1). There shouldn't be a need to do any bitwise magic.

magicalhippo 2y ago

Will we see x86 or similar CPUs replace hot instruction blocks with current-processor-specific optimized code during runtime, similar to how certain JIT VMs do? What I mean is, say you have a similar simple "x = (cond) ? a : b;" which the compiler has not translated to a CMOV. If this is in a hot loop then the CPU could, in theory, notice that "it's just doing a conditional move, I can do the CMOV faster" and then translate those code bytes at that memory location to a CMOV instead (ie during decoding or something like that). Not worth the complexity? I imagine it would slow down the decoder or wherever they insert this replacement logic. Or am I hopelessly out of date and they're already doing this?

akira2501 2y ago
I think it could only do that in spans of code where interrupts are disabled and purely between values already in registers. CPU state feels like it's in your control, but it's not at all in your control, and even if it was, multiple processes might exist and memory is never in your control.
saagarjha 2y ago
Whether to use a branch or a conditional move isn’t really dependent on what the source is doing but how likely the branch is and its dependencies. Simplifying a bit, an explicit cmov is basically telling the computer that the condition is not easy to predict and to not bother. Modern processors will typically do the same analysis themselves and perform similarly on a branch with a slight overhead.
jeffbee 2y ago
> Will we see x86 or similar CPUs replace hot instruction blocks with current-processor-specific optimized code during runtime, similar to how certain JIT VMs do? Wasn't that one of Transmeta's things?
- magicalhippo 2y ago
  Kinda, though Transmeta was built to translate everything. I must admit though I had forgotten some details, and you're right in that my idea is not unlike bolting the Code Morphing stuff to a regular x86 core.
gpderetta 2y ago
Look for "idiom detection". Macro uop fusion is a limited form of this. As a relevant example, POWER CPUs can convert some non diverging branches into conditional execution if not well predictable. Many RISC CPUs can convert well known LL/SC code patterns into locked atomic operations to guarantee forward progress.
- magicalhippo 2y ago
  Thanks, keyword helped. Yeah I was thinking about macro uop fusion but taken to another level.

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 ago
You 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 ago
  Oof, 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)

a_e_k 2y ago

This sort of use of turning conditionals into bitmasks and then shuffling masked values around was fairly common back in the day when writing code for SSE intrinsics. You wouldn't want to have to check each lane individually since that would spoil the point of using SSE. So you'd write masking ops like this and keep things parallel, tThen judiciously use any() and all() type intrinsics to check whether the lanes could agree to skip certain blocks conditionally. (This was before ISPC and before autovectorization to handle it for you.)

djmips 2y ago
Does ISPC + auto vectorization truly remove the need to attend to these details in the most optimized code?
- a_e_k 2y ago
  They can, yes. For example, here's a simple Compiler Explorer link with a simple loop conditionally copying from one of two values: https://godbolt.org/z/TbeK99sx1 https://godbolt.org/z/TbeK99sx1. If you look at the assembly code produced, you'll see in lines 9-11, it's doing a similar thing as the swap_if() function: ANDing one value with the mask, ANDing the other with the negation of the mask, and then ORing them together. And it produced that automatically from the ternary in the loop. They can also do things like automatically generate epilogues with a serial loop to handle the leftover items if the loop count isn't an even multiple of the SIMD width. That's something else that I remember writing by hand before autovectorizers. That said, coaxing an autovectorizer to actually vectorize a loop can be an art in itself. They're notoriously finicky. My favorite used to be the one in the old ("classic") ICC compiler where you use compiler flags to get a nice optimization report which would explain exactly why it chose what it did for each loop. You could also set #pragma's which would noisily warn or error out if the associated loop failed to vectorize for some reason. (And of course, a lot of this stuff you might just use GPU compute for now.)
  - mgaunard 2y ago
    normally there is an instruction for this called blend (since SSE4.1). There shouldn't be a need to do any bitwise magic.