Dr. Dobb's Journal - June 2008 - (Page 51)

d06sutt_p3ds 4/11/08 11:19 AM Page 51 to share the same variable. It’s also called ping-ponging because that’s an apt description of how the cache line ownership keeps hopping back and forth madly between the two cores. Even in this simple example, what could we do to ensure x and y are on different cache lines? First, we can rearrange the data: For example, if x and y are data values inside the same object, perhaps we can rearrange the object’s members so that x and y are sufficiently further apart. Second, we can add padding: If we have no other data that’s easy to put adjacent to x, we can ensure x is alone on its cache line by allocating extra space, such as by allocating a larger object with x as a member (preceded/followed by appropriate padding to fill the cache line) instead of allocating x by itself as a naked integer. This is a great example of how to deliberately waste space to improve performance. False sharing arises in lots of hard-to-see places. For example: • Two independent variables or objects are too close together, as in the above examples. • Two node-based containers (lists or trees, for example) interleave in memory, so that the same cache line contains nodes from two containers. ing thread can make progress at all, and so typically trumps other important cache considerations. Second: Keep data that is frequently used together close together in memory. If a thread that uses variable A frequently also needs variable B, try to put A and B in the same cache line if possible. For example, A and B might be two fields in the same object that are frequently used together. This is a traditional technique to improve memory performance in both sequential and concurrent code, which now comes second to keeping separate data apart. Third: Keep “hot” (frequently accessed) and “cold” (infrequently accessed) data apart. This is true even if the data is conceptually in the same logical object. This helps both to fit “hot” data into the fewest possible cache lines and memory pages and to avoid needlessly loading the “colder” parts. Together these effects reduce (a) the cache footprint and cache misses, and (b) the memory footprint and virtual memory paging. Discover a New World in Programming Looking for a career with an innovative company where you can use your programming skills to make a difference in the world? Join ESRI and design and develop the next generation of our world-leading geographic information system (GIS) mapping software. We are seeking software developers with solid core programming skills and a passion for inventing new technology. We have opportunities to work on everything from database and Web development to graphics, 2D–3D rendering, and core server technology. Our developers work with the latest technologies including Java, .NET, and Flash/Flex. At ESRI you’ll have exceptional benefits, opportunities for growth, and the satisfaction of developing software that is making a difference. Join us and be a part of changing the world. Next Steps Achieving parallel scalability involves two things: 1. Express it: Find the work that can be parallelized effectively. 2. Then don’t lose it: Avoid visible and invisible scalability busters like the ones noted in this article. We’ve seen some ways to avoid losing scalability unwittingly by invisibly adding contention. Next time, we’ll consider one other important way we need to avoid invisibly adding contention and losing scalability: Choosing concurrency-friendly data structures, and avoiding concurrencyhostile ones. Stay tuned. Cache-Conscious Design Locality is a first-order issue that trumps much of our existing understanding of performance optimization. Most traditional optimization techniques come after “locality” on parallel hardware (although a few are still equally or more important than locality, such as big-Oh algorithmic complexity for example). Arrange your data carefully by following these three guidelines, starting with the most important: First: Keep data that are not used together apart in memory. If variables A and B are not protected by the same mutex and are liable to be used by two different threads, keep them on separate cache lines. (Add padding, if necessary; it’s a great way to “waste” memory to make your code run faster.) This avoids the invisible convoying of false sharing (ping-pong) where in the worst case only one contend- Learn more about ESRI and apply online at www.esri.com/ddj. Notes [1] H. Sutter. “Break Amdahl’s Law!” (www.ddj.com/cpp/205900309) [2] H. Sutter. “Super Linearity and the Bigger Machine” (www.ddj.com/architect/ 206903306). DDJ Herb is a software development consultant, a software architect at Microsoft, and chair of the ISO C++ Standards committee. He can be contacted at www.gotw.ca. Copyright © 2007 ESRI. All rights reserved. ESRI, the ESRI globe logo, and www.esri.com, are trademarks, registered trademarks, or service marks of ESRI in the United States, the European Community, or certain other jurisdictions. Other companies and products mentioned herein may be trademarks or registered trademarks of their respective trademark owners. ESRI is an Equal Opportunity Employer. June 2008 l www.ddj.com l Dr. Dobb’s Journal 51 http://www.esri.com/ddj http://www.esri.com/ddj http://www.ddj.com/cpp/205900309 http://www.ddj.com/architect/206903306 http://www.ddj.com/architect/206903306 http://www.gotw.ca http://www.ddj.com

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

Dr. Dobb's Journal - June 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries There Must Be Contest Conversations Building a Test Harness for RTOS QT and Windows CE Software to Hardware Parallelization Performance Portable C++ Effective Concurrency The Agile Edge Swaine's Flames

Dr. Dobb's Journal - June 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.