7 ms·
Question from a perf noob: it seems like this in principle only shows that there's no difference for a Pixel 3 because other Android machines could have process
by lgessler 6y ago
Question from a perf noob: it seems like this in principle only shows that there's no difference for a Pixel 3 because other Android machines could have processors that have/lack an optimization for shift or divide. Couldn't a different Android phone have different performance characteristics?
- __s 6y agoYou're correct
- toxicFork 6y agoEven in the same model different regions can have different performance characteristics, or even functionality. While I was working at Unity Technologies (the game engine company) I have seen many horror stories when it comes to Android. Everything looked the same from the software, and also the name and versions of the hardware components, but for the components made in different countries, it behaved slightly differently.
- anyfoo 6y agoIn theory, yes. In practice, shifting is usually a very simple operation, while general multiplication (and especially division) is not. There have been (and there might still be, on the lowest end) many processors that have shift, but no multiplication or division.
- edoceo 6y agoLike the 386 w/a math coprocessor?
- anyfoo 6y agoNo, the math coprocessor was for floating point, all integer operations (or at least all the basic ones) were on-die.
- 0x0 6y agoFor integers, x86 has had mul and div all the way back to at least the 8086. If you are looking for a cpu with no mul or div then look at the classic 6502/6510 as known from c64, nes, and many more contemporary machines.
- fortran77 6y agoThe co-processor was for floating point operations. Integer MUL and DIV were in the 386 (and the 8086/8088)
- duskwuff 6y agoA lot of microcontrollers fall into that category. The Cortex-M0 ARM core doesn't have integer multiply or divide, for instance, and it's almost always absent on 8-bit cores like AVR and PIC.
- lgg 6y agoIt 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.
- blihp 6y agoIt's more of a language/compiler thing than a hardware one. Hardware support for bit shifting exists on every processor I've ever used. The only real question from a performance standpoint is whether the language you are using will automatically generate optimal code for the x*2 and x/2 cases. Most of the time, it's not worth worrying about: you do it in the clearest way possible (i.e. as a math expression, not a bit shift) and only look at forcing the optimization if you have a performance problem.
- orangecat 6y agoYes: https://community.arm.com/developer/ip-products/processors/b/processors-ip-blog/posts/divide-and-conquer https://community.arm.com/developer/ip-products/processors/b.... I ran into this several years ago when one of my devices was surprisingly slow with code like "x = (x + 1) % limit". Turns out it didn't do integer division in hardware (the mod operator requires a divide) and was using a runtime library. Replacing the code with "x++; if (x == limit) x = 0;" made it much faster.
- benibela 6y agoI just benchmarked a bunch of hashmaps, and the fastest maps were using a power of 2 as size. So they could do "x = (x + 1) & (limit - 1)". No division and branch free.