5 ms·

they are implemented via some kind of alternate "cruft path" using micro-ops that requires extra decode steps, pipeline flush, etc. that slows the processor dow

by adgar 15y ago

they are implemented via some kind of alternate "cruft path" using micro-ops that requires extra decode steps, pipeline flush, etc. that slows the processor down. This is exactly the case. Just a few minutes ago I was implementing a parse tree data structure my thesis advisor commonly uses. It encodes the number of types of children of each node as a pair of bits, ordered from least-significant to most-significant. If the nth child is a leaf node, it's encoded as `10`, and if it's an internal node, it's `11`. I implement the "number of children" function as a loop, shifting this pattern right by 2 until the value is zero. Naturally, x86 has a useful opcode for this: BSR, bit-scan right. It tells you the index of the first set (1) bit scanning from most-significant to least-significant. It returns the index from 0=LSB, 31=MSB. In theory, this takes my O(n) solution and makes it O(1). I just BSR the pattern, shift right 1, add 1. I know it's a micro-optimization anyway, but I want to have some fun on labor day, so I give it a shot. In practice, since the number of children is always 8 or fewer (this is for Ruby's grammar), the loop is always very short. Even while running 10,000,000 iterations to get the total time up to a few seconds, and even while using `rand` to try to trick the branch predictor (to make the looping case less predictable), I couldn't get a discernable difference to show up between O(1) and O(n). The O(n) case was definitely executing at least 3-4 times as many instructions in the test I was running, so I can only conclude BSR is deoptimized. Edit: DarkShikari says that the deoptimization may be because I'm on an Athlon 64 processor and that this is not the case on intel processors.

andrewf 15y ago
POPCNT sounds like a more suitable instruction, and it's modern (ie not likely to be slow-pathed; although pre-Core iX processors won't support it at all!)
- adgar 15y ago
  Not for my particular encoding, as I have "10" to indicate a terminal node and "11" to indicate a non-terminal. Essentially it's a 3-valued encoding of 'empty', 'terminal', 'nonterminal' for a variable number of children.
  - andrewf 15y ago
    AND your input with 0xAAAAAAAA (ie 101010...10 binary) to turn all the "11" values into "10".
    - adgar 15y ago
      How does help me use popcnt to find how many bit pairs are used and how many are empty? Edit: whoops, I gotcha. I'll profile this. Edit 2: no I won't profile it, because I don't have the instruction. Damn.
      - acqq 15y ago
        You don't need to have POPCNT to implement much faster bit counting: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel http://graphics.stanford.edu/~seander/bithacks.html#CountBit...
DarkShikari 15y ago
Naturally, x86 has a useful opcode for this: BSR, bit-scan right. It tells you the index of the first set (1) bit scanning from most-significant to least-significant. It returns the index from 0=LSB, 31=MSB. BSR/BSF are the equivalents of CLZ/CTZ on ARM and other CPUs; it isn't a "crufty" or "redundant" instruction in the same way as LOOP, etc. Most modern x86 CPUs implement it in 1 or 2 cycles, with the exception of Athlon 64 and Atom. Check Agner's list of instruction latencies; don't guess. BSF/BSR are extraordinarily useful instructions for a wide variety of uses, the most common being integer log2 (useful for parsing variable-length codes).
- adgar 15y ago
  I never said it was crufty, just that it wasn't successful for me in improving my use-case despite requiring noticeably fewer instructions (not cycles). I am, however, on Athlon 64. That may explain why I found it to be indistinguishable to the short loop in profiling. I didn't guess anything, I even explicitly explained my profiling methodology.
- arto 15y ago
  Here's a link to Agner's optimization manuals, for the benefit of those who may not be familiar with them: http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals In short they contain what is probably the best x86 instruction latency reference, based on actual empirical measurements on various Intel/AMD/VIA chips.
pmjordan 15y ago
This could just be the general slowness of bitwise operations kicking in. I remember reading in Intel's optimisation documents that shift instructions take around 3 times as long as an add, so for multiplying by 4 you're better off with 2 adds than shifting up by 2. (In reality, the compiler would probably use lea)
- adgar 15y ago
  The compiler did use `lea` - I used inline asm for the `BSR` instruction and then did the shift and increment in C, figuring the compiler would be smarter than me.
- DarkShikari 15y ago
  remember reading in Intel's optimisation documents that shift instructions take around 3 times as long as an add Shift and add are both one cycle on all modern CPUs. I think this might be different on the Pentium 4, but we x86 programmers pretend that the Pentium 4 didn't exist. With regard to the other bitwise operations (and, or, xor), I don't know any CPU in existence where these are slower than add.* *Except for the Pentium 4, where the add/sub unit is double-pumped and nothing else on the chip is, but that's a bizarre exception.
  - psykotic 15y ago
    > Shift and add are both one cycle on all modern CPUs. It's common for variable-length shifts to be slow on modern CPUs once you move outside of the x86 space. On the PS3's PPU and the Xbox 360's PowerPC cores they are very slow and to be avoided. > I think this might be different on the Pentium 4 What was particularly slow on the P4 were variable-length shifts and rotates. With an immediate operand they still had 1 cycle throughput. That sounds good until you realize that the P4 had a double-pumped ALU design (as you also mentioned) and it had two ALUs. Whereas shifts and rotates could only execute on the general integer unit.
    - DarkShikari 15y ago
      It's common for variable-length shifts to be slow on modern CPUs once you move outside of the x86 space. On the PS3's PPU and the Xbox 360's PowerPC cores they are very slow and to be avoided. They're hardly modern CPUs -- even outside the x86 space, slow variable-shifts are pretty rare. They're horrifically crippled, with the PS3's PPU not being intended to be used for any serious processing (supplemented by the SPEs), and the Xbox 360's CPU just being plain bad. Fast variable-shifts are critical for bitstream reading -- the end result of this crippling is that despite having 3 highly-clocked cores, and being supplemented by GPU processing, the Xbox 360 still can't play Blu-ray video.
vilya 15y ago
Are you compiling with any optimisations on? If so, did you check the asm output for your looping version? It's possible that the compiler detects this pattern and replaces it with a BSR instruction in the binary. Even if it doesn't do that, it's quite likely that the compiler is vectorising the loop for you. Which might explain why you're not seeing a speedup from BSR: not because BSR is slow, but because the compiler is making your other code fast.

by adgar 15y ago

andrewf 15y ago

POPCNT sounds like a more suitable instruction, and it's modern (ie not likely to be slow-pathed; although pre-Core iX processors won't support it at all!)

adgar 15y ago
Not for my particular encoding, as I have "10" to indicate a terminal node and "11" to indicate a non-terminal. Essentially it's a 3-valued encoding of 'empty', 'terminal', 'nonterminal' for a variable number of children.
- andrewf 15y ago
  AND your input with 0xAAAAAAAA (ie 101010...10 binary) to turn all the "11" values into "10".
  - adgar 15y ago
    How does help me use popcnt to find how many bit pairs are used and how many are empty? Edit: whoops, I gotcha. I'll profile this. Edit 2: no I won't profile it, because I don't have the instruction. Damn.
    - acqq 15y ago
      You don't need to have POPCNT to implement much faster bit counting: http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel http://graphics.stanford.edu/~seander/bithacks.html#CountBit...

DarkShikari 15y ago

Naturally, x86 has a useful opcode for this: BSR, bit-scan right. It tells you the index of the first set (1) bit scanning from most-significant to least-significant. It returns the index from 0=LSB, 31=MSB. BSR/BSF are the equivalents of CLZ/CTZ on ARM and other CPUs; it isn't a "crufty" or "redundant" instruction in the same way as LOOP, etc. Most modern x86 CPUs implement it in 1 or 2 cycles, with the exception of Athlon 64 and Atom. Check Agner's list of instruction latencies; don't guess. BSF/BSR are extraordinarily useful instructions for a wide variety of uses, the most common being integer log2 (useful for parsing variable-length codes).

adgar 15y ago
I never said it was crufty, just that it wasn't successful for me in improving my use-case despite requiring noticeably fewer instructions (not cycles). I am, however, on Athlon 64. That may explain why I found it to be indistinguishable to the short loop in profiling. I didn't guess anything, I even explicitly explained my profiling methodology.
arto 15y ago
Here's a link to Agner's optimization manuals, for the benefit of those who may not be familiar with them: http://www.agner.org/optimize/#manuals http://www.agner.org/optimize/#manuals In short they contain what is probably the best x86 instruction latency reference, based on actual empirical measurements on various Intel/AMD/VIA chips.

pmjordan 15y ago

This could just be the general slowness of bitwise operations kicking in. I remember reading in Intel's optimisation documents that shift instructions take around 3 times as long as an add, so for multiplying by 4 you're better off with 2 adds than shifting up by 2. (In reality, the compiler would probably use lea)

adgar 15y ago
The compiler did use `lea` - I used inline asm for the `BSR` instruction and then did the shift and increment in C, figuring the compiler would be smarter than me.
DarkShikari 15y ago
remember reading in Intel's optimisation documents that shift instructions take around 3 times as long as an add Shift and add are both one cycle on all modern CPUs. I think this might be different on the Pentium 4, but we x86 programmers pretend that the Pentium 4 didn't exist. With regard to the other bitwise operations (and, or, xor), I don't know any CPU in existence where these are slower than add.* *Except for the Pentium 4, where the add/sub unit is double-pumped and nothing else on the chip is, but that's a bizarre exception.
- psykotic 15y ago
  > Shift and add are both one cycle on all modern CPUs. It's common for variable-length shifts to be slow on modern CPUs once you move outside of the x86 space. On the PS3's PPU and the Xbox 360's PowerPC cores they are very slow and to be avoided. > I think this might be different on the Pentium 4 What was particularly slow on the P4 were variable-length shifts and rotates. With an immediate operand they still had 1 cycle throughput. That sounds good until you realize that the P4 had a double-pumped ALU design (as you also mentioned) and it had two ALUs. Whereas shifts and rotates could only execute on the general integer unit.
  - DarkShikari 15y ago
    It's common for variable-length shifts to be slow on modern CPUs once you move outside of the x86 space. On the PS3's PPU and the Xbox 360's PowerPC cores they are very slow and to be avoided. They're hardly modern CPUs -- even outside the x86 space, slow variable-shifts are pretty rare. They're horrifically crippled, with the PS3's PPU not being intended to be used for any serious processing (supplemented by the SPEs), and the Xbox 360's CPU just being plain bad. Fast variable-shifts are critical for bitstream reading -- the end result of this crippling is that despite having 3 highly-clocked cores, and being supplemented by GPU processing, the Xbox 360 still can't play Blu-ray video.

vilya 15y ago

Are you compiling with any optimisations on? If so, did you check the asm output for your looping version? It's possible that the compiler detects this pattern and replaces it with a BSR instruction in the binary. Even if it doesn't do that, it's quite likely that the compiler is vectorising the loop for you. Which might explain why you're not seeing a speedup from BSR: not because BSR is slow, but because the compiler is making your other code fast.