4 ms·

Another fast way to double a number is to add it to itself.

by remcob 6y ago

fyp 6y ago
Isn't that the wrong direction for the optimization? I would assume you would want to compile adding two numbers into shifting by one, not the other way around. (I know nothing about hardware, it just intuitively seems like moving a bunch of bits over by 1 should be faster than dealing with xor and carries)
- mhh__ 6y ago
  Realistically when you get into real world questions about performance the only way to be sure is to measure it. In this case I imagine you're right. Although also worth pointing out that due to the way modern CPUs are basically frontends to generate uOps that it could actually perform the optimization by itself anyway. Time to break out PAPI (very cool tool for anyone unaware, you can get instruction level profiling in your program with basically 4 function calls and a header file).
- jcranmer 6y ago
  In hardware terms, adders are simpler than shifters. You can usually do both in a single cycle, but it's going to be lower power to do the add instead of the shift. To put this in more concrete terms: an N-bit adder involves N 1-bit stages to add each bit, and then a 1-bit carry network on top of that, which has N stages in it. So overall, it's O(N) in terms of hardware. An N-bit shift unit is going to use lg N N-bit muxes--or O(N lg N) in terms of hardware. Total gate delay in both cases is O(lg N), but adders have O(N) hardware (and thus energy consumption) while shifters have O(N lg N). A secondary consequence of being larger area is that a superscalar architecture may choose to have one execution unit that has an adder and a shifter and a second that only has the adder. So an addition may schedule better than a shift, since there are more things it can execute on.
  - deleted 6y ago
    [deleted]
  - Tuna-Fish 6y ago
    > To put this in more concrete terms: an N-bit adder involves N 1-bit stages to add each bit, and then a 1-bit carry network on top of that, which has N stages in it. So overall, it's O(N) in terms of hardware. O(N) adders cannot meet the latency demands of modern high-frequency CPUs. The actual complexity of adders in real CPUs is usually O(N²).
- magicalhippo 6y ago
  > it just intuitively seems like moving a bunch of bits over by 1 should be faster than dealing with xor and carries Yes, a fixed shift-by-one unit would be much simpler than an adder. But many (most?) CPUs that supports shifting have generic shift units, where the number of bits to shift varies, and that makes them much more complex.
  - kevin_thibedeau 6y ago
    Barrel shifters are still frequently omitted from microcontrollers. Primarily because of their size.
    - magicalhippo 6y ago
      Right, I was thinking mostly of "application-level" CPUs capable of running Android.
- simcop2387 6y ago
  There's some hardware that surprisingly doesn't have a real shift but instead has rotate operations. These will take the bits that get dropped off and put them on the other side, in those cases the addition can be a much better choice than doing a bitmask and then rotate operation. These types of hardware are usually embedded devices that also have high cost multiplication instructions too so unrolling to a smaller number of fixed additions can actually perform better sometimes.
pwg 6y ago
This very much depends upon the CPU upon which the code is running. The 'shift' vs 'multiply' (or add to self) for doubling came about because in the past, it was very common that shifts were faster than multiplies (if your CPU even had a multiply instruction) and often faster than adds as well. Example, from the 8086 (yes, very long time ago, but this is the environment where the differences often massively mattered): https://www.oocities.org/mc_introtocomputers/Instruction_Timing.PDF https://www.oocities.org/mc_introtocomputers/Instruction_Tim... Add reg->reg: 3 clock cycles Mul: 70-133 depending on 8 vs. 16 bit size Shift: Reg with shift of 1 (which is a *2): 2 clock cycles. Now, for divide by 2 the issue is even larger (as you can't 'subtract from itself' to achieve divide by 2): Idiv: 101-184 clocks, depending on 8 vs. 16 bit size Shift: 2 clock cycles. So, on the 8086, for times 2, a shift was 33% faster than an add to self (and so much faster than a Mul that no one should use Mul for times 2). And for divide by 2, a shift was massively faster than an Idiv (2 cycles vs minimum of 101 cycles). Now, these relative values change as one moves up the x86 CPU line to newer CPU's. Intel built faster adders, faster multipliers, faster dividers, so one really has to check the specific CPU to see which instruction is faster. But the one item that will remain fairly constant is that presuming that using a shift for powers of two multiply or divide is generally close to the 'fastest' method is a good ball-park estimate that is more often right than it is wrong.
- remcob 6y ago
  In the article, there's a whole path from source to JVM bytecode to ARM assembly. With auxiliary goals like bytecode size. This makes it interesting to include add-double because it has a simple bytecode encoding ('DUP ADD' compared to 'PUSH 2 MUL') and it is interesting to see what the several compilers do with it along the way in terms of optimization. Interesting info on 8086. Another approach that doesn't apply to OP's article, but does to x86 assembly is (ab)using LEA for small multiplications. At 2 clock cycles it looks competitive with shift for doubling, but can also be used for multiples like 3 and 5.
  - spc476 6y ago
    SHL/SAL/SHR/SAR (the shifts) affect the condition codes so one could check for overflow (or use it as part of multibyte arithmetic) while LEA does not affect the conditions code (so overflow goes undetected). It's something else to keep in mind.

Another fast way to double a number is to add it to itself.

by remcob 6y ago

Another fast way to double a number is to add it to itself.

fyp 6y ago

Isn't that the wrong direction for the optimization? I would assume you would want to compile adding two numbers into shifting by one, not the other way around. (I know nothing about hardware, it just intuitively seems like moving a bunch of bits over by 1 should be faster than dealing with xor and carries)

mhh__ 6y ago
Realistically when you get into real world questions about performance the only way to be sure is to measure it. In this case I imagine you're right. Although also worth pointing out that due to the way modern CPUs are basically frontends to generate uOps that it could actually perform the optimization by itself anyway. Time to break out PAPI (very cool tool for anyone unaware, you can get instruction level profiling in your program with basically 4 function calls and a header file).
jcranmer 6y ago
In hardware terms, adders are simpler than shifters. You can usually do both in a single cycle, but it's going to be lower power to do the add instead of the shift. To put this in more concrete terms: an N-bit adder involves N 1-bit stages to add each bit, and then a 1-bit carry network on top of that, which has N stages in it. So overall, it's O(N) in terms of hardware. An N-bit shift unit is going to use lg N N-bit muxes--or O(N lg N) in terms of hardware. Total gate delay in both cases is O(lg N), but adders have O(N) hardware (and thus energy consumption) while shifters have O(N lg N). A secondary consequence of being larger area is that a superscalar architecture may choose to have one execution unit that has an adder and a shifter and a second that only has the adder. So an addition may schedule better than a shift, since there are more things it can execute on.
- deleted 6y ago
  [deleted]
- Tuna-Fish 6y ago
  > To put this in more concrete terms: an N-bit adder involves N 1-bit stages to add each bit, and then a 1-bit carry network on top of that, which has N stages in it. So overall, it's O(N) in terms of hardware. O(N) adders cannot meet the latency demands of modern high-frequency CPUs. The actual complexity of adders in real CPUs is usually O(N²).
magicalhippo 6y ago
> it just intuitively seems like moving a bunch of bits over by 1 should be faster than dealing with xor and carries Yes, a fixed shift-by-one unit would be much simpler than an adder. But many (most?) CPUs that supports shifting have generic shift units, where the number of bits to shift varies, and that makes them much more complex.
- kevin_thibedeau 6y ago
  Barrel shifters are still frequently omitted from microcontrollers. Primarily because of their size.
  - magicalhippo 6y ago
    Right, I was thinking mostly of "application-level" CPUs capable of running Android.
simcop2387 6y ago
There's some hardware that surprisingly doesn't have a real shift but instead has rotate operations. These will take the bits that get dropped off and put them on the other side, in those cases the addition can be a much better choice than doing a bitmask and then rotate operation. These types of hardware are usually embedded devices that also have high cost multiplication instructions too so unrolling to a smaller number of fixed additions can actually perform better sometimes.

pwg 6y ago

This very much depends upon the CPU upon which the code is running. The 'shift' vs 'multiply' (or add to self) for doubling came about because in the past, it was very common that shifts were faster than multiplies (if your CPU even had a multiply instruction) and often faster than adds as well. Example, from the 8086 (yes, very long time ago, but this is the environment where the differences often massively mattered): https://www.oocities.org/mc_introtocomputers/Instruction_Timing.PDF https://www.oocities.org/mc_introtocomputers/Instruction_Tim... Add reg->reg: 3 clock cycles Mul: 70-133 depending on 8 vs. 16 bit size Shift: Reg with shift of 1 (which is a *2): 2 clock cycles. Now, for divide by 2 the issue is even larger (as you can't 'subtract from itself' to achieve divide by 2): Idiv: 101-184 clocks, depending on 8 vs. 16 bit size Shift: 2 clock cycles. So, on the 8086, for times 2, a shift was 33% faster than an add to self (and so much faster than a Mul that no one should use Mul for times 2). And for divide by 2, a shift was massively faster than an Idiv (2 cycles vs minimum of 101 cycles). Now, these relative values change as one moves up the x86 CPU line to newer CPU's. Intel built faster adders, faster multipliers, faster dividers, so one really has to check the specific CPU to see which instruction is faster. But the one item that will remain fairly constant is that presuming that using a shift for powers of two multiply or divide is generally close to the 'fastest' method is a good ball-park estimate that is more often right than it is wrong.

remcob 6y ago
In the article, there's a whole path from source to JVM bytecode to ARM assembly. With auxiliary goals like bytecode size. This makes it interesting to include add-double because it has a simple bytecode encoding ('DUP ADD' compared to 'PUSH 2 MUL') and it is interesting to see what the several compilers do with it along the way in terms of optimization. Interesting info on 8086. Another approach that doesn't apply to OP's article, but does to x86 assembly is (ab)using LEA for small multiplications. At 2 clock cycles it looks competitive with shift for doubling, but can also be used for multiples like 3 and 5.
- spc476 6y ago
  SHL/SAL/SHR/SAR (the shifts) affect the condition codes so one could check for overflow (or use it as part of multibyte arithmetic) while LEA does not affect the conditions code (so overflow goes undetected). It's something else to keep in mind.