5 ms·

YMMV on this because different models of chips differ, but I found years ago just playing around that many of the more obscure x86 opcodes are actually very slo

by api 15y ago

YMMV on this because different models of chips differ, but I found years ago just playing around that many of the more obscure x86 opcodes are actually very slow to execute. My hypothesis is that because they are obscure and rarely used by compilers, 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. So if you think about using obscure x86 opcodes, benchmark them first. They might be slower than just implementing the algorithm using standard mainstream opcodes.

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).
InclinedPlane 15y ago
Since the Pentium-Pro / P6 era there has no longer been such a beast as a "CISC" processor or even an "x86" processor per se. Modern IA32 processors have a RISC core that executes x86 instructions via opcode translation. So you are exactly right, the more obscure x86 opcodes are likely to be implemented inefficiently.

by api 15y ago

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).

InclinedPlane 15y ago

Since the Pentium-Pro / P6 era there has no longer been such a beast as a "CISC" processor or even an "x86" processor per se. Modern IA32 processors have a RISC core that executes x86 instructions via opcode translation. So you are exactly right, the more obscure x86 opcodes are likely to be implemented inefficiently.