7 ms·
Which is better on Android: divide by 2 or shift by 1?
- anyfoo 7y agoThorough work. Going back to the premise, I want to offer an alternative viewpoint by asking whether, in the case of binary trees implemented by arrays, “integer division by 2” of the array index is necessarily the best interpretation of what you are trying to do here? Instead, you can also see the array index as a bit string, where every bit tells you which path to go down, left or right. In that case, “shifting right by one bit” moves you up to the parent. “Shifting left” moves you down to the left child. Flipping one bit flips you over to the other child. Bit wise operations indeed seem more natural with that interpretation. A lot of “power of 2” multiplication/division has similar interpretations. For example, when walking page tables, you could see walking down the levels as “dividing by the size of the granule”, or simply as “shifting right to select the index on that level”. No contest on anything where the power of 2 is coincidence, i.e. for non “computery” things where there is no such underlying structure.
- yiyus 7y agoI had a slightly similar experience at work. We deal a lot with angles and binary angles are often the most efficient representation. Many colleagues find it annoying because they insist on converting every binary angle to radian or degrees, but if you actually interpret the bits as successive divisions of a circumference, I actually find the binary representation way more intuitive than a floating point number.
- a1369209993 7y ago> they insist on converting every binary angle to [] degrees Bit of hypocrisy there, since degrees are literally the same thing, just with 360 sectors rather than (say) 256. Though the extra factors of 3 and 5 are sometimes useful.
- yiyus 7y agoThe point is to not think of the bits as the representation of a decimal number. For example, if I need to know in which quadrant an angle is, I just need to look at the first two bits, independently of the precision (which we change just shifting and truncating). But I do not mind if 90 degrees are equal to 64 or 1073741824 "sectors". I think this is another good example where a binary representation (and a shift) can be a more natural way to approach the problem.
- pdehaan 7y agoNot just more natural, it also lends itself to better accuracy and/or efficiency in some cases too. As a quick example, if you're writing a numerical approximation or even just a LUT for sin(x), you can get away with only approximating/storing values for a reduced range by using some bit twiddling. The top bit becomes sign of output if you XOR it out first, the next bit lets you take advantage of sin(pi/2-x) = sin(x+pi/2) to half the input range again, eek out symmetry for the next bit and you can nearly approximate sin(x) as a linear function for some use cases.
- slavik81 7y agoThat method is exactly equivalent to using revolutions as the unit with a fixed-point numeric representation. Maybe your skeptical colleagues would find that perspective more palatable?
- yiyus 7y agoThat's some good advice. Unfortunately, most of the people I work with do not have a computer science background (they are materials scientists and mechanical engineers), so they are not familiarized with fixed-point arithmetic neither.
- lgessler 7y agoQuestion 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 7y agoYou're correct
- toxicFork 7y 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 7y 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 7y agoLike the 386 w/a math coprocessor?
- anyfoo 7y agoNo, the math coprocessor was for floating point, all integer operations (or at least all the basic ones) were on-die.
- 0x0 7y 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.
- remcob 7y agoAnother fast way to double a number is to add it to itself.
- fyp 7y agoIsn'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__ 7y agoRealistically 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 7y agoIn 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 7y ago[deleted]
- twoodfin 7y agoI appreciate the thorough exploration and resulting detail in this article. Still, I find it a little sad that either the state of our toolchains or the perception thereof prevent it from being self-evident that basic strength reduction will always happen, and developers need not worry about the cost of expressing simple arithmetic operations in the clearest way.
- deleted 7y ago[deleted]
- bsder 7y agoI would go further in that many programmers don't understand the difference between logical and arithmetic operations and why they exist. I have had to puzzle over far too much code doing adds/subtracts/multiplies/divides instead of and/or/xor/shift FAR too often. I blame Java not having an unsigned type. There are apparently some weird tricks you can do with arithmetic in Java that operate on things like an unsigned type without having to go up to the next higher integer width.
- vbezhenar 7y agoWhat exactly do you miss in Java? It's possible to treat int as unsigned for all the necessary operations.
- blibble 7y agoplus Java's had various unsigned integer operations on Integer for years
- pjmlp 7y agoBlame it on developers that think they know unsigned math. > One of the little experiments I tried was asking people about the rules for unsigned arithmetic in C. It turns out nobody understands how unsigned arithmetic in C works. There are a few obvious things that people understand, but many people don't understand it. https://www.artima.com/intv/gosling3.html https://www.artima.com/intv/gosling3.html Since 2014 that Java now has support for unsigned math via methods on its boxed types since Java 8. And depending on how Valhalla goes, it might gain inline classes for unsigned types, which is pretty much the same thing as having an uint.
- pacman83 7y agoApart from the fact that compilers are really good and generally will choose the best option for you, it seems like it boils down to what processor is used. On Android aren't ARM processors the most common?
- pjmlp 7y agoYes, followed by some Intel and MIPS survivors.
- MithrilTuxedo 7y agoNow I'm wondering if there's a power usage difference between the two. It stands to reason that if two operations take the same amount of time, but one requires more transistors to compute, power usage should diverge.
- wmf 7y agoFor scalar instructions, most of the energy is consumed in scheduling not executing them. This means that cycles is a good proxy for total energy.
- jejones3141 7y agoIf it's signed int, unless you know the value is positive you can't just shift right 1--if the result of the shift is negative, you have to add 1.
- chrisseaton 7y agoCan't you do an arithmetic shift-right? That takes the sign into account.
- xxpor 7y agoYep, ASR is the ARM64 instruction.
- jcranmer 7y agoNo. An arithmetic shift right does a division that rounds down; an integer division operation instead truncates (rounds to zero). The easiest example is -1 / 2: -1 / 2 is 0, but -1 ashr 1 is -1. To replace a signed division with ashr, you have to know that for all negative inputs, the value of the bits shifted out are all 0.
- sambe 7y agoAm I mis-reading this? The article keeps claiming there is no difference but the way I read it the compiler(s) are transforming mul/div to shifts. i.e. it very likely is faster on the hardware but it won't matter for this particular toolchain because of the conversion.
- wmf 7y agoThe point is that from the perspective of the programmer there is no performance difference between / 2 and >> 1.
- chrisseaton 7y ago> Am I mis-reading this? The article keeps claiming there is no difference but the way I read it the compiler(s) are transforming mul/div to shifts. i.e. it very likely is faster on the hardware but it won't matter for this particular toolchain because of the conversion. There is no difference... because of the conversion.
- sambe 7y agoRight: for now, in certain situations, on the tested toolchain. Even ignoring those caveats, several commentators seem to have got the impression that this applies to the CPU.
- wk_end 7y agoI wonder: do any microarchitectures detect and redirect multiplications/divisions by powers of two to the shifter?
- uluyol 7y agoThese types of transformations are simple to detect, well known, and applied by ~every compiler. Unless you have evidence otherwise (ASM differences or benchmarks), there is no use in manually transforming your arithmetic into something more complex but faster. The compiler will do it for you.
- necovek 7y agoI am really struggling to understand the benchmark output quoted. Can anyone elaborate what does benchmark=3/4 ns mean, and the count? Is the set-up part of the benchmark (test structure suggest not, but just to make sure)? The only way I can read it is that 4000 divisions takes 4ns, and 4000 shift-rights takes 3ns, but that only has 1 digit of precision, which makes it unusable for comparison, but even then suggests a 25%/33% difference, which is not insignificant. Also, the VM seems to optimise multiply out, so it must be doing it for a reason.
- thechao 7y agoIt's definitely not 4000 divisions per 4ns — that'd imply a terahertz computer. I think it's saying that the amortized cost of 4000 divisions is 4ns per division. Small integer division is an "easy win" for a dedicated HW path, so it doesn't surprise me that it's only a little slower than a shift-right. Variable length right shifts aren't that fast.
- drivebycomment 7y agoNews at 11 - someone learned strength reduction exists, which have been in use for the past 4 decades.
- anyfoo 7y agoHad you read the article, you would have known that the question answered here was whether, and where in the process, strength reduction was actually applied.
- dingo_bat 7y agoWhy wouldn't it be? Even the simplest compilers do it. You can bet that the world's leading mobile OS is doing all such obvious optimizations.
- fefe23 7y agoA few points. 1. Looking at the Java bytecode is practically meaningless, you would have to look at the machine code the JIT is creating. 2. A division by 2 is identical to a shift right by 1 only if the integer is unsigned. Java integers are signed. Try this program in C to see for yourself: int foo(int a) { return a/2; } int bar(int a) { return a>>1; } Run gcc -S -O2 to get assembly output in text form. Basically, the problem is this: 5/2 -> 2 (ok, rounds down) 5>>1 -> 2 (ok, same) -5/2 -> -2 (ok, rounds down) -5>>1 -> -3 (oops!) 3. The question is really about the JIT backend for the target platform, which means CPU platform, not OS platform. So "on Android" does not make much sense here, as Android exists for x86 and ARM and those JIT backends might behave differently.
- lgessler 7y agoIn defense of the author re: 2, since the application domain seems to be manipulating indices for a binary tree represented in an array, the integer will always be non-negative.
- anyfoo 7y agoAll things directly addressed by the article.
- ryenus 7y ago-5/2 -> -2 (ok, rounds down) Actually this is rounding up, to zero, as -2.5 < -2 < 0
- maxwindiff 7y agoThe article did investigate the assembly.
- pjmlp 7y agoYet another one that didn't bother to actually read the article.
- renewiltord 7y agoOne addition: You can't just divide by 2 and expect that to be equivalent to shifting right by 1. That only works if the integer is unsigned. For signed integers, that won't yield the right result. This is trivial to verify.
- devit 7y agoHonestly, it's hard to read this article and not question the author's mental state or intelligence. He literally presents x86 and ARM assembly dumps where shift right generates one instruction, and divide generates that same instruction plus several others. Then, he feels the need to run an unnecessary benchmark (most likely screwing it up somehow) and concludes there is no difference! But how can there possibly be no performance difference, in general, between the CPU running an ALU instruction and running that same instruction plus several other ALU instructions?!? It's almost unbelievable. As to how he screwed up the benchmark, my guesses are that either he failed to inline the function (and the CPU is really bad), or failed to prevent the optimizer from optimizing the whole loop, or didn't run enough iterations, or perhaps he ran the benchmark on a different VM than what produced the assembly (or maybe somehow the CPU can extract instruction level parallelism in this microbenchmark, but obviously that doesn't generalize to arbitrary code).
- brianyu8 7y agoWhile I think that there is merit to your argument, I feel like it could have been presented without questioning the author's intelligence or mental state.
- ken 7y agoThe "asrs" mnemonics are the same, but the opcodes use different addressing modes. The 4th instruction in the longer sequence is a register-to-register move, which might be a simple register rename. It's not obvious to me that the shorter sequence is necessarily faster than the longer one. OK, the "adds" is probably slower, and introduces a register dependency. But the whole exercise here is to test and see, not trust that some simple operation performs like how it looks. Indeed, if you discount the "bx lr" (that's just the return, right?), the 1-instruction version takes 3ns, and the 4-instruction version takes 4ns. Clearly, 4 times as many instructions is not taking anywhere near 4 times as long to execute.
- nipxx 7y agoif these kinds of optimizations make a difference for your applications write it in native code, dammitl
- pjmlp 7y agoWhich pretty much means Assembly, given that Java and Koltin go through JVM and DEX bytecodes to machine code, and C and C++ on Android go through LLVM bitcode to machine code.
- madhato 7y agoIs there an advantage of using multiply by .5 versus divide by 2?
- fox8091 7y agoMultiply by 0.5 would be slower, as it's a floating point operation rather than simple arithmetic.
- renewiltord 7y agoHow come the division is almost the same as the shifting? Is the CPU pipelining the operations between iterations of the loop or something? There is a direct data-dependency in those operations but not between iterations so perhaps that's it? AFAIK there's no fused add-shift op that could be used.
- temac 7y agoTLDR: it is the same, like it should. We are in 2020. Don't shift by 1 instead of /2 if you mean to /2.
- OrgNet 7y agolol... if you care about optimizing, you should care about all possible optimizations... (even if most of today's platforms don't)
- temac 7y agoYeah but you should also then understand what will yield real results, and >>1 instead of /2 has become useless to write manually a long time ago, whereas e.g. continuous memory is more important than ever. You will not optimize a lot by attempting micro techniques from 30 years ago. Other random example: in some edge cases, integer division replacement by a multiplication can still be relevant today (depends on if its a constant, the compiler, and if nothing optimized also on the exact processor, though, because last models are already ultra-fast with the real integer divide instructions), but I suspect in 15 years (maybe even 10) this will be completely irrelevant, at least for high perf targets.
- Animats 7y agoHe did this in Java? In one case, running on an emulator? That's removed too far from the hardware for this kind of benchmarking. Try in a hard-compiled language. Using shifts for constant divide has been a compiler code generator optimization for decades. This is not something programmers have needed to worry about in source code for a long time, unless targeting some small microcontroller that lacks fast divide hardware.
- pjmlp 7y agoJava is a hard-compiled language on Android since version 5.0. ART, which replaced Dalvik on 5.0 (available as experimental on 4.4), was AOT only up to version 7.0. As it was proven that Android users lack the patience of a C++ developer when updating their apps, Google adopted another approach with version 7.0. A multi-tier compiler infrastructure, composed by a very fast interpreter hand written in Assembly for fast startup, a JIT compiler for the first optimization level, with gathering of PGO data, then the AOT compiler runs in the background and when the device is idle gets that PGO data and just like a C++ compiler with PGO data, outputs a clean AOT compiled binary for the usual user workflow. In case of an update or changes in the workflow that trigger the execution of code that wasn't AOT compiled, the process restarts. As means to reduce this kind of de-optimizations, since Android 10 those PGO files are uploaded into the Play Store and when a user installs an application that already has PGO data available, it is downloaded alongside the APK and the AOT compiler can do its job right from the start. In any case, he used dex2aot which is the AOT compiler daemon on Android. Microsoft has gone through similar process with .NET for UWP, with the main difference that the AOT compiler lives on the Microsoft store and what gets downloaded is already straight binary code. Apparently mixing language capabilities with toolchains keeps being an issue.
- esnellman 7y agoGiven the number of execution loops. The profiler applied an optimization. Don't expect this optimization during initial executions or seldom used code or cases where properties of the method do not allow it to be optimized; be it on Android VMs or JVMs.
- nicetryguy 7y ago...So the Dalvik VM sucks?
- pjmlp 7y agoYes it sucks, that is why it was replaced by ART on Android 5.0.
- nicetryguy 7y agoAh, i haven't kept up. Anyway, a right bit shift should absolutely be quicker than floating point or even integer division. If it isn't, that is an implementation problem.
- pjmlp 7y agoART as of Android 10, combines an hand written interpreter in Assembly, a JIT compiler that generates PGO data as well, and an AOT PGO based optimizing compiler capable of doing bounds check elision, de-virtualization, auto-vectorization, escape analysis and a couple of other traditional optimizations. The PGO metadata files also get shared across devices via the Play Store as means to steer the AOT compiler into the optimal level of optimization across all users of the application. I assume that at the current level of ongoing ART optimizations, the team would consider that a compiler bug.
- nicetryguy 7y agoAwesome info! Thanks! What would you recommend for an IDE? I used Eclipse some years ago. Is that still common? I may want to experiment with some Android flavored Java again.
- pjmlp 7y agoAndroid Studio is the official IDE, it is a merge of InteliJ with Clion and Google specific plugins.
- Too 7y agoI thought this discussion was settled 30 years ago? Write what you want to do, not how to do it. There is no difference.
- Ragib_Zaman 7y agoThis will never be settled. I know professional developers who regard the recursion section of their algorithms classes as academic masturbation and a waste of time because you should write an iterative version in the "real world" for performance reasons. I can't even get them to agree in the case of tail-recursion because "why trust the compiler to optimise that?".
- saurik 7y agoEveryone is talking about this microoptimization on the math of the access but all I can think about is how the data structure you are building using this is probably memory bandwidth limited and powers-of-two storage is almost definitely going to cause some kind of cache line aliasing, so maybe you should try something non-obvious like "division by 3" (after doing three key comparisons instead of one) and see if it makes your algorithm much much faster than messing around with a division by 2; there was even some good analysis of this effect a while back I can reference. https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-case-for-caches/ https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathologic...