4 ms·
> Back in time it was known for being a fast way to multiply and divide by powers of 2. This hasn't been true for a long time now, and in the rare cases it is,
by jcranmer 5y ago
> Back in time it was known for being a fast way to multiply and divide by powers of 2. This hasn't been true for a long time now, and in the rare cases it is, most optimizing compilers will bitwise shift where in your source code you divide or multiply.
Shifting is still faster than multiplication--a shift is a 1-cycle operation, multiplication typically 3 cycles. Division is somewhere in the region of a dozen cycles or more. (Also, division is one of the assembly operations whose time is data-dependent). So it's faster to replace a multiplication with a single shift (but not multiple shifts), and to replace division with shifts or even multiplies--there's a fast division replacement that replaces a division by a small constant with a multiply-hi and shift.
Will compilers replace multiplies and divides with shifts? Kind of. If you multiply a value with a constant (after inlining/constant propagation/etc.) that's a power of two, or if you multiply it with an expression 1 << var, then that will be converted to a shift.
For division, it's even more complicated because shifts and division by power of 2 are not equivalent if the type is signed: -1 / 2 is 0 but -1 >> 1 is -1, so the transform is not legal unless the compiler can find out either a) the value is never negative or b) the division is exact.
- NwtnsMthd 5y agoWith a DSP core it often gets even better, the bit shift might be free. Say you have the instruction ACC = ACC + P << PM, that could compile to a single instruction, if you're not writing assembly directly. Additionally if you're ever working directly with hardware, writing drivers, or firmware, bit-shift operations are often the best (and most common) way to get stuff done.
- rasz 5y agoSame on first ARM chips http://www.csbio.unc.edu/mcmillan/Comp411F18/Lecture07.pdf http://www.csbio.unc.edu/mcmillan/Comp411F18/Lecture07.pdf
- BulgarianIdiot 5y agoI wouldn't call it better because CPUs have a similar "sum and multiply" instruction, and GPUs are pretty much made of such units. The problem with bitshifting is that it's just a special case of multiplication and division. So if you want your hardware utilized, you don't scale bitshifts, that'd be largely useless. You scale multiplication and division, and this is what modern hardware does. Bitshifting is very simple in terms of hardware, but scale beats simplicity.