Dr. Dobb's Journal - April 2008 - (Page 53)

d04sutt_p5ds 2/13/08 9:54 AM Page 53 such partial information to run faster by excluding entire sections of their search space—subtrees under heavy nodes, or regions where x and y are too far apart—without having to traverse those areas at all to inspect their contents for possible matches. Still another potential path to superlinearity is to perform speculative execution. Let’s say that you have two alternative algorithms available to compute a result, such as two search algorithms where one has better average-case performance and the other has better worst-case performance. Now, most of the time you’re better off just picking one of the algorithms and using available hardware to run it in parallel. But sometimes you can do better by running both of them, and seeing which gets the answer first. The cost is that you’re doing more work, but you can get the answer faster (including avoiding the bad worst case of one algorithm). Sometimes the extra work can be relatively “free,” at least from your selfish point of view; for example, when the two operations are two database or web service queries against different servers, and one server might get the answer in a different way than the other because the servers may be experiencing different loads or may use different methods to compute the answer. The bad news about all of the effects we’ve covered so far is that none of them are going to help you go superlinear with algorithms that have to visit every element in a range anyway, such as when you’re calculating the sum of all nodes. The good news, however, is Figure 2: Intel Kentsfield core and cache utilization: 1 thread versus 3 threads. Figure 3: AMD Barcelona core and cache utilization: 1 thread versus 3 threads. Get moving. Stay focused. Take control. Enterprise Architect from Sparx Systems redefines visual modeling with a huge set of built-in tools, technologies and capabilities, coupled with a lightweight footprint and great agility. With deep support for UML 2.1 and its related standards, Enterprise Architect 7.1 is the ideal tool to analyze, design, build and manage your next software project. Keep your project moving, keep your team focused and stay in total control. Visit sparxsystems.com for a free trial April 2008 l www.ddj.com l Dr. Dobb’s Journal 53 http://sparxsystems.com http://sparxsystems.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - April 2008

Dr. Dobb's Journal - April 2008 Contents Hmmmm Alia Vox Developer Diaries Dr. Dobb's Excellence in Programming Award Conversations Fast String Search on Multicore Processors The Byzantine Generals Problem Optimizing Math-Intensive Applications with Fixed-Point Arithmetic Random Numbers in a Range Using Generic Programming The Agile Edge Effective Concurrency Swaine's Flames

Dr. Dobb's Journal - April 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.