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

Re: StringBuilder Difficulties

Date	2011-07-02 19:55 -0700
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.lang.java.programmer
Subject	Re: StringBuilder Difficulties
References	<c4tk07dv1pq7u8k32qd6b7o1brc2rj8r30@4ax.com> <976q3jF3etU2@mid.individual.net> <e9ps07h56utkftkp8fcarm7uhkk5t999le@4ax.com> <9796kgFoijU3@mid.individual.net> <979v96F7epU1@mid.individual.net>
Message-ID	<CZGdnS-Ag6OPR5LTnZ2dnUVZ_oqdnZ2d@earthlink.com> (permalink)

Show all headers | View raw

On 7/2/2011 6:34 PM, blmblm@myrealbox.com wrote:
...
> Both programs (yours and mine) now consistently report sequential
> search to be faster than binary search.  Weird, but not as weird as
> the two being different in that regard ....
...

Binary search can have a much higher constant multiplier on its time
than sequential search. If the searches are long enough, the O(log n) vs
O(n) complexity difference should dominate over the constant multiplier,
but for short searches the constant multiplier can dominate.

Binary search is more expensive than it looks because of branch
prediction.

A lot of processors have deep, wide pipelines. The problem is that the
processor has to decide which instructions to feed into the pipeline
immediately after feeding in a conditional branch, but will not *know*
whether the branch was taken or not until it gets near the other end of
the pipeline. The solution is to cache information about the conditional
branches, and try to predict the branch based only on branch history and
the cache. Performance of code with a lot of conditional branches
depends on how well the processor does at predicting the branches.

Each binary search iteration includes an unpredictable branch which will
be guessed wrong about half the time.

On the other hand, the conditional branch in each iteration of the
sequential search will usually be correctly predicted, except for the
one at the end of the search.

The only way to know which way round this will come out is indeed to
measure, making sure the searches are as similar as possible to the real
workload.

Patricia

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

Thread

StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-28 17:54 -0700
  Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-28 21:29 -0400
    Re: StringBuilder Difficulties Lew <noone@lewscanon.com> - 2011-06-29 00:48 -0400
      Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 12:19 -0700
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 12:11 -0700
      Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-29 22:06 -0400
  Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-29 20:17 +0000
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 18:55 -0700
      Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-30 20:30 +0000
        Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-30 14:17 -0700
          Re: StringBuilder Difficulties Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-30 21:36 -0400
            Re: StringBuilder Difficulties "John B. Matthews" <nospam@nospam.invalid> - 2011-07-01 01:41 -0400
        Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-30 14:26 -0700
          Re: StringBuilder Difficulties Steve Sobol <sjsobol@JustThe.net> - 2011-06-30 17:33 -0700
          Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-01 20:47 +0000
            Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-01 17:29 -0700
              Re: StringBuilder Difficulties rossum <rossum48@coldmail.com> - 2011-07-02 11:36 +0100
              Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-02 12:58 +0200
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 07:52 -0700
                Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-04 21:45 +0200
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-05 02:06 -0400
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 09:32 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-05 14:13 -0400
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 12:51 -0700
                Re: StringBuilder Difficulties Silvio <silvio@moc.com> - 2011-07-05 23:16 +0200
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 15:08 -0700
                Re: StringBuilder Difficulties Silvio <silvio@moc.com> - 2011-07-06 09:41 +0200
                Re: StringBuilder Difficulties "eye" <eye@mocka.com> - 2011-07-06 09:55 +0000
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 05:37 -0400
                Re: StringBuilder Difficulties "thoolen" <thoolen@tholenbot.thorium> - 2011-07-06 08:43 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 22:30 -0400
                Re: StringBuilder Difficulties "Stefan Robacki" <noemail@noemail.foobar> - 2011-07-06 00:04 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 05:45 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 08:26 -0400
                Re: StringBuilder Difficulties thoolen <thoolen@tholenbot.thorium> - 2011-07-06 22:36 -0400
                Re: StringBuilder Difficulties "tholen@antispam.ham" <tholen@ifa.hawaii.edu> - 2011-07-06 06:09 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:40 -0400
                Re: StringBuilder Difficulties John Doe <jdoe@usenetlove.invalid> - 2011-07-14 06:50 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-14 02:58 -0400
                Re: StringBuilder Difficulties Jane Doe <jdoe@love.in.d.jungle.invalid> - 2011-07-14 10:20 -0400
                Re: StringBuilder Difficulties thoolen <tholen01@gmail.com> - 2011-07-14 07:33 -0700
                Re: StringBuilder Difficulties Stanimir Stamenkov <s7an10@netscape.net> - 2011-07-05 23:44 +0300
                Re: StringBuilder Difficulties markspace <-@.> - 2011-07-05 14:08 -0700
              Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-02 18:33 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-02 16:56 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-03 01:34 +0000
                Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-07-02 19:55 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-04 03:32 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 08:04 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 19:12 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 14:06 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 21:16 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 17:29 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:59 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:52 -0400
                Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-07-06 16:58 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:52 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 21:54 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:18 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:41 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-08 17:45 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 05:48 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:59 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-06 10:56 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-08 17:44 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-08 11:51 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-10 19:08 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-11 07:54 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-11 22:37 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-11 15:52 -0700
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 08:25 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:41 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 19:58 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 21:57 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:17 -0400
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 22:44 -0400
                Re: StringBuilder Difficulties Steve Erwin <trollHunter@Usenet.4.usenetizens.org.invalid> - 2011-07-07 12:51 +1000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-06 23:02 -0400
                Re: StringBuilder Difficulties John Doe <jdoe@usenetlove.invalid> - 2011-07-14 06:32 +0000
                Re: StringBuilder Difficulties supercalifragilisticexpialadiamaticonormalizeringelimatisticantations <supercalifragilisticexpialadiamaticonormalizeringelimatisticantations@averylongandannoyingdomainname.com> - 2011-07-14 02:57 -0400
                Re: StringBuilder Difficulties Jane Doe <jdoe@love.in.d.jungle.invalid> - 2011-07-14 10:07 -0400
                Re: StringBuilder Difficulties thoolen <tholen01@gmail.com> - 2011-07-14 07:24 -0700
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-04 07:58 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 19:09 +0000
                Re: StringBuilder Difficulties KitKat <kitkat_11697@gmail.example.com> - 2011-07-05 15:15 -0400
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 20:03 +0000
                Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-07-05 14:11 -0700
                Re: StringBuilder Difficulties blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-06 16:55 +0000
      Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-03 00:08 -0700
        Re: StringBuilder Difficulties Robert Klemme <shortcutter@googlemail.com> - 2011-07-03 12:35 +0200
          Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-04 04:07 -0700
  Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 14:38 -0700
    Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 15:00 -0700
      Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 15:52 -0700
        Re: StringBuilder Difficulties Gene Wirchenko <genew@ocis.net> - 2011-06-29 18:58 -0700
          Re: StringBuilder Difficulties Patricia Shanahan <pats@acm.org> - 2011-06-29 19:26 -0700
          Re: StringBuilder Difficulties lewbloch <lewbloch@gmail.com> - 2011-07-03 00:11 -0700
  Re: StringBuilder Difficulties Roedy Green <see_website@mindprod.com.invalid> - 2011-06-29 18:32 -0700

csiph-web