6 ms·

I’ve read that some vector instruction sets use masking instructions to avoid branching. You execute both arms of the conditional and discard the unwanted compu

I’ve read that some vector instruction sets use masking instructions to avoid branching. You execute both arms of the conditional and discard the unwanted computation, which can be cheaper than an X% chance of a branch misprediction. Should CPUs include more masking instructions for regular, non-vectorized code as well?

banachtarski 6y ago
I’m unconvinced because the instruction set sizes are already becoming fairly bloated (increasing microcode translation cost and i-cache pressure) but also because CPUs already do speculative execution which has a nearly equivalent effect to the idiom you’re referring to. *edit: wording
- MauranKilom 6y ago
  To be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation https://en.wikipedia.org/wiki/Eager_evaluation) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case. The problem in question is due to predictive execution in which the CPU has to flush the pipeline on misprediction. This is dominant in desktop PC CPUs. I have no knowledge on what is prevalent in e.g. server or mobile CPUs. Both are (according to https://en.wikipedia.org/wiki/Speculative_execution https://en.wikipedia.org/wiki/Speculative_execution) forms of speculative execution.
  - banachtarski 6y ago
    I'm speaking broadly about desktop/console CPUs which I have low-level familiarity with. I don't know of any CPUs in this class that don't perform some form of speculative execution. I'm not sure if eager evaluation is related to the topic at hand and was speaking specifically about speculative execution. Eager evaluation is just what pretty much every language except Haskell (or Haskell-like) does.
    - MauranKilom 6y ago
      Sorry, that first link was nonsense. I just copied the wiki link under "Eager execution" in the Speculative Execution page, but that is of course far from the same as "eager evaluation" (which is what the link goes to). I apologized for the confusion. The point is that there are at least two ways CPUs can speculatively execute a conditional: Either predict which branch is taken and flush the pipeline if the prediction was wrong, or execute both arms of the conditional and discard the one that was not actually taken. The top-level SIMD comment is about the latter, but most optimization around speculative execution is for the former. Yes, CPUs do speculative execution. The "flush pipeline on mispredict" kind ("predictive execution"). That is not the same as the "execute both and discard the untaken one" kind ("eager execution"). Your first reply suggests you consider them equivalent when they are not. I just wanted to clear that up.
      - banachtarski 6y ago
        Ah OK I understand now thanks for clearing that up. I meant that the end effect was similar but not so much that the mechanism was identical.
tom_mellior 6y ago
32-bit ARM assembly language provided conditional execution for most instructions. This was dropped in the 64-bit instruction set. (https://en.wikipedia.org/wiki/Predication_(computer_architecture) https://en.wikipedia.org/wiki/Predication_(computer_architec..., https://en.wikipedia.org/wiki/ARM_architecture#64-bit https://en.wikipedia.org/wiki/ARM_architecture#64-bit) I imagine the architects had a clear picture of the advantages and disadvantages, and made a very well-informed decision. I guess that part of the reason might have been that it's not clear when compilers should emit predicated code instead of branches. Also, you can get something very similar even for scalar code as long as your machine has a conditional move operation, which they all have: /* true path */ a = ... b = ... true_result = ... /* false path */ x = ... y = ... false_result = ... /* final result */ result = (condition ? true_result : false_result) This works if the two "branches" have no side effects (memory writes, function calls) and cannot raise exceptions. Again, it's very difficult to estimate for compilers (and humans) if it will pay off to run both computations rather than branch. The trade-offs for vectorization are different from scalar code since vectorizing a loop by a factor N gives a huge win, and even if you waste some time doing some redundant computations, you still have a reasonable chance of being faster than scalar.
- ncmncm 6y ago
  You can get close to the performance of a cmov instruction by generating a pair of all-1s and all-0s values: a=c, b=c-1, and a result z=a&x|b&y. Gcc will not under any circumstances produce two cmov instructions in a basic block, so that is your only alternative without dropping to asm. Clang is happy to produce two adjacent cmov instructions. Usually your ALUs are not otherwise so engaged as to make the number of operations involved costly.
  - ncmncm 6y ago
    I should add that Clang is happy to turn c&x|(c-1)&y into cmov.
  - deleted 6y ago
    [deleted]
  - 6y ago

banachtarski 6y ago

I’m unconvinced because the instruction set sizes are already becoming fairly bloated (increasing microcode translation cost and i-cache pressure) but also because CPUs already do speculative execution which has a nearly equivalent effect to the idiom you’re referring to. *edit: wording

MauranKilom 6y ago
To be more precise, some CPUs do the "both sides of the conditional" execution (EDIT This link is incorrect! Refer to "Eager execution" in the last link below. /EDIT https://en.wikipedia.org/wiki/Eager_evaluation https://en.wikipedia.org/wiki/Eager_evaluation) - years ago I heard that mobile processors do so for power reasons. No idea if that's still the case. The problem in question is due to predictive execution in which the CPU has to flush the pipeline on misprediction. This is dominant in desktop PC CPUs. I have no knowledge on what is prevalent in e.g. server or mobile CPUs. Both are (according to https://en.wikipedia.org/wiki/Speculative_execution https://en.wikipedia.org/wiki/Speculative_execution) forms of speculative execution.
- banachtarski 6y ago
  I'm speaking broadly about desktop/console CPUs which I have low-level familiarity with. I don't know of any CPUs in this class that don't perform some form of speculative execution. I'm not sure if eager evaluation is related to the topic at hand and was speaking specifically about speculative execution. Eager evaluation is just what pretty much every language except Haskell (or Haskell-like) does.
  - MauranKilom 6y ago
    Sorry, that first link was nonsense. I just copied the wiki link under "Eager execution" in the Speculative Execution page, but that is of course far from the same as "eager evaluation" (which is what the link goes to). I apologized for the confusion. The point is that there are at least two ways CPUs can speculatively execute a conditional: Either predict which branch is taken and flush the pipeline if the prediction was wrong, or execute both arms of the conditional and discard the one that was not actually taken. The top-level SIMD comment is about the latter, but most optimization around speculative execution is for the former. Yes, CPUs do speculative execution. The "flush pipeline on mispredict" kind ("predictive execution"). That is not the same as the "execute both and discard the untaken one" kind ("eager execution"). Your first reply suggests you consider them equivalent when they are not. I just wanted to clear that up.
    - banachtarski 6y ago
      Ah OK I understand now thanks for clearing that up. I meant that the end effect was similar but not so much that the mechanism was identical.

tom_mellior 6y ago

32-bit ARM assembly language provided conditional execution for most instructions. This was dropped in the 64-bit instruction set. (https://en.wikipedia.org/wiki/Predication_(computer_architecture) https://en.wikipedia.org/wiki/Predication_(computer_architec..., https://en.wikipedia.org/wiki/ARM_architecture#64-bit https://en.wikipedia.org/wiki/ARM_architecture#64-bit) I imagine the architects had a clear picture of the advantages and disadvantages, and made a very well-informed decision. I guess that part of the reason might have been that it's not clear when compilers should emit predicated code instead of branches. Also, you can get something very similar even for scalar code as long as your machine has a conditional move operation, which they all have: /* true path */ a = ... b = ... true_result = ... /* false path */ x = ... y = ... false_result = ... /* final result */ result = (condition ? true_result : false_result) This works if the two "branches" have no side effects (memory writes, function calls) and cannot raise exceptions. Again, it's very difficult to estimate for compilers (and humans) if it will pay off to run both computations rather than branch. The trade-offs for vectorization are different from scalar code since vectorizing a loop by a factor N gives a huge win, and even if you waste some time doing some redundant computations, you still have a reasonable chance of being faster than scalar.

ncmncm 6y ago
You can get close to the performance of a cmov instruction by generating a pair of all-1s and all-0s values: a=c, b=c-1, and a result z=a&x|b&y. Gcc will not under any circumstances produce two cmov instructions in a basic block, so that is your only alternative without dropping to asm. Clang is happy to produce two adjacent cmov instructions. Usually your ALUs are not otherwise so engaged as to make the number of operations involved costly.
- ncmncm 6y ago
  I should add that Clang is happy to turn c&x|(c-1)&y into cmov.
- deleted 6y ago
  [deleted]
- 6y ago