
Which is better on Android: divide by 2 or shift by 1? - zdw
https://jakewharton.com/which-is-better-on-android-divide-by-two-or-shift-by-one/
======
anyfoo
Thorough 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
I 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.

~~~
slavik81
That 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
That'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.

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

~~~
bsder
I 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
What exactly do you miss in Java? It's possible to treat int as unsigned for
all the necessary operations.

~~~
blibble
plus Java's had various unsigned integer operations on Integer for years

------
lgessler
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?

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

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

~~~
reitzensteinm
Since it's what I'm typing this on, let's look at Skylake.

Multiply: Latency 3, Throughput 1 Shift: Latency 1, Throughput 2

If the ALU contained an early out or fast path for simpler multiplies, the
latency would read 1-3. You can verify this by looking at div, which does
early out and has a latency of 35-88.

Any compiler that doesn't swap a multiply to a shift when it can is negligent.

[https://www.agner.org/optimize/instruction_tables.pdf](https://www.agner.org/optimize/instruction_tables.pdf)

------
necovek
I 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
It'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.

~~~
bonzini
It's not small integer division that is being benchmarked, the JIT compiler
has reduced it to an addition, a conditional move and a right shift. This
sequence is then benchmarked against the right shift.

~~~
saagarjha
ART is an AOT complier, is it not?

~~~
monocasa
It's both AOT and JIT.

[https://source.android.com/devices/tech/dalvik/jit-
compiler](https://source.android.com/devices/tech/dalvik/jit-compiler)

~~~
pjmlp
With a PGO cache updated across execution runs and devices (since Android 10
PGO data is shared across the Play Store).

~~~
ignoramous
For anyone like me wondering what a PGO is:
[https://source.android.com/devices/tech/perf/pgo](https://source.android.com/devices/tech/perf/pgo)

------
MithrilTuxedo
Now 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
For scalar instructions, most of the energy is consumed in scheduling not
executing them. This means that cycles is a good proxy for total energy.

------
saurik
Everyone 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-
pathologic...](https://pvk.ca/Blog/2012/07/30/binary-search-is-a-pathological-
case-for-caches/)

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

~~~
chrisseaton
> 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
Right: 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.

~~~
uluyol
These 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.

~~~
sambe
I think that's a point which is bordering on religious - many people would
debate trusting the compiler, especially over time and more complex
situations.

I'd certainly tend to agree with you in general but more for the reason that
the compiler can abstract over hardware changes across time. I'd take that
benefit over the risk of the optimisation not being applied for most code I
write - non-optimisations would be considered bugs and probably/eventually
fixed.

I'd strongly disagree the code is more complex (in this case).

~~~
merlincorey
It especially seems religious to me because it's saying that somehow "/ 2" is
simpler than ">> 1" because it has one less character for the symbol, and
because division is a more commonly known operator to most people than bitwise
shifting.

It seems to me that they are equally simple if we assume that programmers
dealing with low level or performance intensive code know what a bitwise shift
is and ignore the extra character, then they are literally equivalently
complicated expressions with 1 symbol and 1 value applied to the symbol.

~~~
kadoban
Code does not happen in a vacuum. Which is more understandable/simple depends
on the domain of the code in question. Usually that's going to be the multiply
or the divide.

~~~
merlincorey
Right, but my statement was that the domain would be low level or performance
intensive code -- do you disagree that in that domain they are equally simple?

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

~~~
fyp
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)

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

~~~
Tuna-Fish
> 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²).

------
Animats
He 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
Java 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.

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

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

------
pacman83
Apart 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
Yes, followed by some Intel and MIPS survivors.

------
jejones3141
If 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
Can't you do an arithmetic shift-right? That takes the sign into account.

~~~
jcranmer
No. 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.

------
Too
I thought this discussion was settled 30 years ago?

Write what you want to do, not how to do it. There is no difference.

------
nicetryguy
...So the Dalvik VM sucks?

~~~
pjmlp
Yes it sucks, that is why it was replaced by ART on Android 5.0.

~~~
nicetryguy
Ah, 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
ART 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
Awesome 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
Android Studio is the official IDE, it is a merge of InteliJ with Clion and
Google specific plugins.

------
madhato
Is there an advantage of using multiply by .5 versus divide by 2?

~~~
fox8091
Multiply by 0.5 would be slower, as it's a floating point operation rather
than simple arithmetic.

------
nipxx
if these kinds of optimizations make a difference for your applications write
it in native code, dammitl

~~~
pjmlp
Which 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.

------
temac
TLDR: 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
lol... if you care about optimizing, you should care about all possible
optimizations... (even if most of today's platforms don't)

~~~
temac
Yeah 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.

------
drivebycomment
News at 11 - someone learned strength reduction exists, which have been in use
for the past 4 decades.

~~~
anyfoo
Had 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.

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

~~~
anyfoo
All things directly addressed by the article.

------
devit
Honestly, 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
While 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.

