5 ms·
It is not that the processor that contains an optimization per se. The thing to understand is that shift is fundamentally a simpler operation than multiply... a
by lgg 6y ago
It is not that the processor that contains an optimization per se. The thing to understand is that shift is fundamentally a simpler operation than multiply... a shift can be implemented with a few transistors per bit and done in a single cycle trivially. A multiply unit takes tons of transistors, and often takes multiple cycles (this is a trade off you make when you design a multiply unit, you can save space by making it work on smaller integers and reusing it multiple times over several cycles to do multiplies of larger integers, just you like you iteratively multiply digits one you do it on paper by hand). Even on processors that have single cycle multipliers it takes a lot more power to do a multiply than a shift because of all the extra hardware you need to engage.
Since shifts are fundamentally simpler than multiplies it always makes sense to do this transform. This is one of a number of transforms that are generally called "strength reductions" <https://en.wikipedia.org/wiki/Strength_reduction> https://en.wikipedia.org/wiki/Strength_reduction>, converting for a more general expensive operation into a more constrained cheaper operation. In this case it is the equivalent to knowing that if you want to multiply a number by 10 you can just add a 0 at the beginning instead of having to write all the work by hand.
The only reason not to do this transform would be if you had a CPU that literally does not have a shift operation, but I cannot think of any such part. Even if you did have such a part, the odds are you could emulate a shift using other other instructions and still outperform the multiply.
This has been a standard optimization for half a century. The original C compiler for the PDP-11 did these transforms even when you turned off optimizations <http://c-faq.com/misc/shifts.html> http://c-faq.com/misc/shifts.html>.
- Aachen 6y agoSmall note that I'll delete again: your links are broken, the <> doesn't work here, this isn't proper markdown
- lgg 6y agoThanks for the heads up, unfortunately I got distracted with work, and I am no longer able to edit the post.
- MithrilTuxedo 6y agoGiven that performance is so close to the same, my only question now is whether there's a measurable difference in power usage between shift and multiply.
- cogman10 6y agoDepends on the processor, but no. Most processors will decode an instruction into micro-ops and guess what that decode phase can do? It can say "Is this a power of 2? Great, engage the shifting operator". Only on super simple processors (think embedded systems) would this ever actually make a difference. Anything else, this is an optimization that your processor is going to do for you automatically.
- lern_too_spel 6y agoAre there any processors that do this? I am not aware of any.
- ynik 6y agoThe decode phase can't do that, because it runs before the input values for the instruction are available.
- KMag 6y agoPresumably the GP was talking about multiplying by an immediate value embedded in the instruction. That would be possible, but I doubt there are any current processors that do so.
- lgg 6y agoYou can do it in decode if the relevant operand is encoded as an immediate. I'm not aware of any processors that do any of the strength reductions discussed here in that way.
- jdsully 6y agoBarrel shifters use n log n transistors, which isn't quite as bad as a multiplier but is still very significant. The Pentium 4 was notable for excluding it making shifts very slow.
- cogman10 6y ago> This has been a standard optimization for half a century. The original C compiler for the PDP-11 did these transforms even when you turned off optimizations Consider this, a common easily applied optimization that compilers have been doing for half a century MAY have made it's way into modern CPUs. Transistors aren't nearly as power hungry as you paint them and CPUs aren't nearly as bad at optimization. There is no reason to switch a multiply or divide for a shift. The ONLY reason to make that switch is if you are dealing with the simplest of processors (Such as a microwave processors). If you are using anything developed in the last 10 years that consumes more than 1W of power, chances are really high that the you aren't saving any power by using shifts instead of multiples. It is the sort of micro-optimization that fundamentally misunderstands how modern CPUs actually work and over estimates how much power or space transistors actually need.
- anyfoo 6y agoValid points, but in this case (and many others where you encounter power-of-2 mult/div), I'd consider that a shift might actually semantically be the more natural operation in the first place, instead of an "optimization" of the mult/div operation. (With their equivalence being obvious to any reader, it might not matter.)
- lgg 6y agoI was not arguing the people writing code should perform strength reductions manually, I was explaining what they were and then stating that even ancient compilers do them automatically. While I did not explicitly state it, the logical follow on is that programmers should almost never explicitly strength reduce in their code, they should write the semantically clear version and let the compiler handle it for them. You are correct, that on modern CPUs there are often specifically recognized idioms where the processor can implicitly perform an instruction transform such as a strength reduction from a multiply to a shift. Having said that, it still makes sense a compiler to perform strength reductions rather than depending on the CPU frontend, at least if your compiler has a relatively decent scheduling model for the CPU. I don't know of any modern production quality compiler that would omit a simple strength reduction like this and leave it to the CPU.
- 6y ago
- SlowRobotAhead 6y ago> The thing to understand is that shift is fundamentally a simpler operation than multipl ... well... If you have hardware multiply that is guaranteed to take one click cycle and a shift that will take the same... does fundamental complexity of how that happens even matter?
- rasz 6y agodepends, shift might be fusable. First ARM chips had free shifts taking zero cycles http://www.csbio.unc.edu/mcmillan/Comp411F18/Lecture07.pdf http://www.csbio.unc.edu/mcmillan/Comp411F18/Lecture07.pdf