Path: csiph.com!x330-a1.tempe.blueboxinc.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Wed, 27 Apr 2011 07:34:39 -0500
Date: Wed, 27 Apr 2011 05:34:32 -0700
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.15) Gecko/20110303 Thunderbird/3.1.9
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Java left shift and right shift operators.
References: <295e16b3-2ed8-4529-bfb0-1cc26ed93ad6@d26g2000prn.googlegroups.com> <188cz6ta97kkm$.dlg@kimmeringer.de> <ip6igu$j0g$2@news.albasani.net> <aecb4896-0502-4d79-bc7d-c6ef2219ed94@r35g2000prj.googlegroups.com> <ip8a8m$iul$1@dont-email.me>
In-Reply-To: <ip8a8m$iul$1@dont-email.me>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <wKqdnZYsRd7CkCXQnZ2dnUVZ_gGdnZ2d@earthlink.com>
Lines: 53
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 75.8.126.96
X-Trace: sv3-6RyA+PRFeQgpvgk0bNQy8De9eMqrhdrd4tOYCx8xZQOxEDKYEptVVnpDG7kJJGNzcb/0ioRFVVgK8qi!KFNqJGyKYeagJ4xHlSBLXObvFUqcRgrEVtv8PtWDvPug4RdCw69bRJX+HBVfSjUkn0tWpsQVRW21!tZItw8pGoO6jLCmTlHcfeuVjLLjHiU5jL0e2ZGNZn+k=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3421
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3300

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