Re: Java left shift and right shift operators.
On 4/26/2011 10:40 PM, Travers Naran wrote:
....
;; if (b > 0) return a << b else return a >> -b
compare b to 0
jump-less-than to L1
a := a << b
jump L2
L1:
b := -b
a := a >> b
L2:
return ;; result in a
....
It's the jump that's adding the time. But on an x86, that kind of
instruction can be entirely cached and the Intel/AMD processors can
perform predictive branching to speed up this bit of code.
The only way you should be getting 20-50 times longer is if you
aren't using any sort of optimizing run-time. Example: running always
as byte code without compiling.
But usually this kind of if-checking and bit-twiddling is so fast
that it's not worth optimizing beyond a single statement. What are
you coding that makes this the most expensive calculation in your
program?
....
The obvious possibility is a random mix of left and right shifts, with
the two directions equally probable. In that case, the hardware branch
prediction would mis-predict, on average, half the time.
When the hardware branch prediction gets it wrong, the result is a
complete pipeline flush. With deep pipelines and multiple instructions
in each pipeline stage, a pipeline flush costs the equivalent of dozens
of simple arithmetic operations.
My question is whether the measurement was from the actual program, or
from a benchmark that may differ from the real program in ways that
affect branch prediction.
If branching is "20-50 times longer" than any of the operations
(negation or shifting), how could you re-write this assembly to use a
single branch statement?
Why bother? Your sample code only has one conditional branch,
"jump-less-than to L1". Unconditional jumps to a fixed target, such as
"jump L2" are always correctly predicted, and take about the same time
as a simple arithmetic operation. The method is short enough that the
JVM will in-line it anywhere it is frequently called so we don't have to
worry about the return.
Patricia