Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!news.dougwise.org!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!74.125.46.80.MISMATCH!postnews.google.com!news2.google.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: Thu, 28 Apr 2011 18:01:57 -0500 Date: Thu, 28 Apr 2011 16:02:04 -0700 From: Patricia Shanahan User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.2; 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> <201104280037257944-angrybaldguy@gmailcom> In-Reply-To: <201104280037257944-angrybaldguy@gmailcom> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <1POdnXxPDIx7bCTQnZ2dnUVZ_gOdnZ2d@earthlink.com> Lines: 26 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 75.8.126.96 X-Trace: sv3-irIjCQlRLj1f+xhS770dGS/YNcTikOd3qe2oWymexCxfdBEzbfkZvsOsIeRbGS6d6RfqEUfuzbOsEx5!fL95VnnUGD1ulNpDhFH0qiLsAemcZ/SsOCw1ZJViw/ScMoutq+6gpKiPeedIqHEf8EMwuwcxlxfv!LFwoGWo6ABSPGLWl8ksxDW/pE+qr7rfGFzCwraUaHY0= 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: 2681 Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:3345 On 4/27/2011 9:37 PM, Owen Jacobson wrote: > On 2011-04-27 08:34:32 -0400, Patricia Shanahan said: ... >> 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. > > There are worse distributions. Consider a program that alternates > between the two possible branch outcomes, assuming a four-bit branch > prediction counter like those found in several generations of Intel > chips: it's possible that the sequence will start by acting opposite to > the prediction and flipping the predicted direction for the next branch > (from b01 to b10 or vice versa). A strictly alternating sequence of > branches would then be mis-predicted *every time*. ... I agree that, depending on the branch predictor implementation, it is possible to get worse than 50% mis-prediction for a single conditional branch. However, the right patterns are relatively unlikely. On the other hand, someone who does not understand branch prediction would be quite likely write a conditional branch benchmark that gets 50% mis-prediction. Patricia