5 ms·

This could just be the general slowness of bitwise operations kicking in. I remember reading in Intel's optimisation documents that shift instructions take arou

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.
    - psykotic 15y ago
      > They're hardly modern CPUs They're annoying to program but why aren't they modern? You're just redefining terms to try to win an argument. They were intentionally scraped down to lower power consumption and manufacturing costs. That doesn't make them not modern.
      - maximilianburke 15y ago
        Both the Cell and the Xenon are around 7 years old now and the POWER4-based PowerPC 970, their direct ancestor, is over 9 years old. They're not ancient in the sense of a Z80 being ancient but since the PPC970's inception IBM has itself iterated the Power architecture 3 more times (the current generation is POWER7), not to mention the strides that AMD and Intel have both made in processor architectures since that time.
    - luu 15y ago
      What's your definition of modern? The latest and greatest ARM processor (Cortex-A9) has a penalty for shifting. Their shifts are a bit strange, because any alu op can shift one of the operands. For standard alu ops, shifting by an immediate costs one extra cycle, and shifting by a register costs two extra cycles. Mov, i.e, a pure shift, only costs an extra cycle in the register case, but it’s still more expensive than, say, an add. I haven't done any Itanium assembly since McKinley (Itanium 2), but their shifts had 3 extra cycles of latency. Making a fast shifter has only become a harder problem since then, because the ratio of wire:gate delay has grown; they could have a single cycle shifter in the current implementation, but it would cost them even more than it did back then. x86 is unique among modern architectures because it has so much legacy baggage. Shifts are only fast on x86 because when Intel implanted slow shifts on the P4, it killed performance in a lot of apps that were compiled with compilers that were accustomed to having fast shifts, so that they would substitute shifts for multiplies whenever possible.

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.
  - psykotic 15y ago
    > They're hardly modern CPUs They're annoying to program but why aren't they modern? You're just redefining terms to try to win an argument. They were intentionally scraped down to lower power consumption and manufacturing costs. That doesn't make them not modern.
    - maximilianburke 15y ago
      Both the Cell and the Xenon are around 7 years old now and the POWER4-based PowerPC 970, their direct ancestor, is over 9 years old. They're not ancient in the sense of a Z80 being ancient but since the PPC970's inception IBM has itself iterated the Power architecture 3 more times (the current generation is POWER7), not to mention the strides that AMD and Intel have both made in processor architectures since that time.
  - luu 15y ago
    What's your definition of modern? The latest and greatest ARM processor (Cortex-A9) has a penalty for shifting. Their shifts are a bit strange, because any alu op can shift one of the operands. For standard alu ops, shifting by an immediate costs one extra cycle, and shifting by a register costs two extra cycles. Mov, i.e, a pure shift, only costs an extra cycle in the register case, but it’s still more expensive than, say, an add. I haven't done any Itanium assembly since McKinley (Itanium 2), but their shifts had 3 extra cycles of latency. Making a fast shifter has only become a harder problem since then, because the ratio of wire:gate delay has grown; they could have a single cycle shifter in the current implementation, but it would cost them even more than it did back then. x86 is unique among modern architectures because it has so much legacy baggage. Shifts are only fast on x86 because when Intel implanted slow shifts on the P4, it killed performance in a lot of apps that were compiled with compilers that were accustomed to having fast shifts, so that they would substitute shifts for multiplies whenever possible.