Hacker News Reader

Comment by remcob | Hacker News Reader

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

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

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.

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.

Indeed! And this is not necessarily a downside, sometimes you want to preserve the flags.

Intell added the MULX instruction that is similar to MUL, except that it doesn't touch the flags. It's very useful in bignum math.

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)

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.

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

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.

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

Barrel shifters are still frequently omitted from microcontrollers. Primarily because of their size.

Right, I was thinking mostly of "application-level" CPUs capable of running Android.

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

Reply on news.ycombinator.com