Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!goblin1!goblin.stu.neva.ru!postnews.google.com!news1.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: Sat, 02 Jul 2011 21:55:13 -0500 Date: Sat, 02 Jul 2011 19:55:18 -0700 From: Patricia Shanahan User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.18) Gecko/20110616 Thunderbird/3.1.11 MIME-Version: 1.0 Newsgroups: comp.lang.java.programmer Subject: Re: StringBuilder Difficulties References: <976q3jF3etU2@mid.individual.net> <9796kgFoijU3@mid.individual.net> <979v96F7epU1@mid.individual.net> In-Reply-To: <979v96F7epU1@mid.individual.net> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Message-ID: Lines: 36 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 70.230.196.78 X-Trace: sv3-z7HI4Je0YoJMXHiAAB+pUBl+zjGPElBAYI0RDxWpeA8vs/Br9oXg4vSgWnZTcie/is5uRsDrMm/4Rwk!NxWYGjfCrEXqmsJfY0NnExilJlpqhmjOVeAmQEjk24bjO01rdJFWnKbBMzr6WH1jLvdims6JWezo!qXnN9W/38MowGp6qYEUZc1NESSKJJSDXCatYv1l5ruOABA== 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: 2970 Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:5828 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