Groups > comp.lang.java.programmer > #3345

Re: Java left shift and right shift operators.

Date	2011-04-28 16:02 -0700
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.lang.java.programmer
Subject	Re: Java left shift and right shift operators.
References	(2 earlier) <ip6igu$j0g$2@news.albasani.net> <aecb4896-0502-4d79-bc7d-c6ef2219ed94@r35g2000prj.googlegroups.com> <ip8a8m$iul$1@dont-email.me> <wKqdnZYsRd7CkCXQnZ2dnUVZ_gGdnZ2d@earthlink.com> <201104280037257944-angrybaldguy@gmailcom>
Message-ID	<1POdnXxPDIx7bCTQnZ2dnUVZ_gOdnZ2d@earthlink.com> (permalink)

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Java left shift and right shift operators. Sanny <softtanks22@hotmail.com> - 2011-04-26 00:38 -0700
  Re: Java left shift and right shift operators. Lothar Kimmeringer <news200709@kimmeringer.de> - 2011-04-26 09:55 +0200
    Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-26 03:16 -0700
    Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 09:49 -0400
      Re: Java left shift and right shift operators. Travers Naran <tnaran@gmail.com> - 2011-04-26 07:09 -0700
        Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 11:21 -0400
        Re: Java left shift and right shift operators. Martin Gregorie <martin@address-in-sig.invalid> - 2011-04-26 15:37 +0000
      Re: Java left shift and right shift operators. Sanny <softtanks22@hotmail.com> - 2011-04-26 09:32 -0700
        Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-26 11:09 -0700
          Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-26 13:09 -0700
        Re: Java left shift and right shift operators. Travers Naran <tnaran@gmail.com> - 2011-04-26 22:40 -0700
          Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-27 05:34 -0700
            Re: Java left shift and right shift operators. Owen Jacobson <angrybaldguy@gmail.com> - 2011-04-28 00:37 -0400
              Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-28 16:02 -0700
              Re: Java left shift and right shift operators. Michael Wojcik <mwojcik@newsguy.com> - 2011-04-28 19:22 -0400
          Re: Java left shift and right shift operators. bugbear <bugbear@trim_papermule.co.uk_trim> - 2011-04-27 14:28 +0100
          Re: Java left shift and right shift operators. Thomas Richter <thor@math.tu-berlin.de> - 2011-04-30 00:02 +0200
      Re: Java left shift and right shift operators. Roedy Green <see_website@mindprod.com.invalid> - 2011-04-27 19:25 -0700
        Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 23:08 -0400
  Re: Java left shift and right shift operators. Sanny <softtanks22@hotmail.com> - 2011-04-26 02:04 -0700
    Re: Java left shift and right shift operators. Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-04-26 07:34 -0400
      Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 09:47 -0400
        Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-27 09:23 -0700
          Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 14:49 -0400
            Re: Java left shift and right shift operators. Paul Cager <paul.cager@googlemail.com> - 2011-04-27 17:28 -0700
              Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 22:06 -0400
      Re: Java left shift and right shift operators. Sanny <softtanks22@hotmail.com> - 2011-04-26 09:39 -0700
        Re: Java left shift and right shift operators. Patricia Shanahan <pats@acm.org> - 2011-04-26 11:17 -0700
        Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 14:55 -0400
          Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 14:57 -0400
          Re: Java left shift and right shift operators. Daniele Futtorovic <da.futt.news@laposte-dot-net.invalid> - 2011-04-26 21:38 +0200
          Re: Java left shift and right shift operators. Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-04-26 23:32 +0000
            Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 00:08 -0400
              Re: Java left shift and right shift operators. Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-04-27 06:57 +0000
                Re: Java left shift and right shift operators. Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-04-27 07:00 -0300
                Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 08:42 -0400
                Re: Java left shift and right shift operators. Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2011-04-27 14:03 +0000
                Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-27 14:54 -0400
        Re: Java left shift and right shift operators. Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-04-26 21:14 -0400
    Re: Java left shift and right shift operators. Travers Naran <tnaran@gmail.com> - 2011-04-26 07:30 -0700
      Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 11:24 -0400
        Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 11:35 -0400
          Re: Java left shift and right shift operators. Sanny <softtanks22@hotmail.com> - 2011-04-26 09:46 -0700
            Re: Java left shift and right shift operators. Lew <noone@lewscanon.com> - 2011-04-26 15:02 -0400
      Re: Java left shift and right shift operators. Lothar Kimmeringer <news200709@kimmeringer.de> - 2011-04-28 09:14 +0200
  Re: Java left shift and right shift operators. Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-04-26 08:41 -0400
  Re: Java left shift and right shift operators. Robert Klemme <shortcutter@googlemail.com> - 2011-04-26 22:06 +0200

csiph-web