Dr. Dobb's Journal - July 2008 - (Page 59)

more locks, even all the way up to the root; and (b) the higher-level nodes will still end up being high-contention resources that bottleneck scalability. Also, the code to do this is much more complicated. As Fraser noted in 2004: “One superficially attractive solution is to read-lock down the tree and then write-lock on the way back up, just as far as rebalancing operations are required. This scheme would acquire exclusive access to the minimal number of nodes (those that are actually modified), but can result in deadlock with search operations (which are locking down the tree).” [2] He also proposed a fine-grained locking technique that does allow some concurrency, but notes that it “is significantly more complicated.” There are easy answers, but few easy and correct answers. To get around these limitations, researchers have worked on alternative structures such as skip lists [4], and on variants of red-black trees that can be more amenable to concurrency, such as by doing relaxed balancing instead of rebalancing immediately when needed after each update. Some of these are significantly more complex, which incurs its own costs in both performance and correctness/maintainability (for example, relaxed balancing was first suggested in 1978 but not implemented successfully until five years later). For more information and some relative performance measurements showing how even concurrent versions can still limit scalability, see [3]. Linked lists are wonderfully concurrency-friendly data structures Remember: • In parallel code, your performance needs likely include the ability to allow multiple threads to use the data at the same time. • On parallel hardware, you may also care about minimizing the cost of memory synchronization. In those situations, prefer concurrencyfriendly data structures. The more a container supports truly localized updates, the more concurrency you can have as multiple threads can actively use different parts of the data structure at the same time, and (secondarily but still sometimes importantly) the more you can avoid invisible memory synchronization overhead in your highperformance code. Notes [1] H. Sutter. “Use Lock Hierarchies to Avoid Deadlock” (Dr. Dobb’s Journal, January 2008). [2] K. Fraser. “Practical lock-freedom” (University of Cambridge Computer Laboratory Technical Report #579, February 2004). [3] S. Hanke. “The Performance of Concurrent Red-Black Tree Algorithms” (Lecture Notes in Computer Science, 1668:286-300, Springer, 1999). [4] M. Fomitchev and E. Ruppert. “Lock-Free Linked Lists and Skip Lists” (PODC ’04, July 2004). 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. July 2008 l www.ddj.com l Dr. Dobb’s Journal Conclusions Concurrency-friendliness alone doesn’t singlehandedly trump other performance requirements. The usual performance considerations of Big-Oh complexity, and memory overhead, locality, and traversal order all still apply. Even when writing parallel code, you shouldn’t choose a data structure only because it’s concurrency-friendly; you should choose the right one that meets all your performance needs. Lists may be more concurrency-friendly than balanced trees, but trees are faster to search, and “individual searches are fast” can outbalance “multiple searches can run in parallel.” (If you need both, try an alternative like skip lists.) 59 http://www.nxtbook.com/nxtbooks/cmp/ddj0108/index.php?startid=67 http://www.birdstep.com/database http://www.gotw.ca http://www.ddj.com

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

Dr. Dobb's Journal - July 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook Engineers Without Borders Conversations Patricia Tries Event-Based Architectures Graphs Versus Objects Lock-Free Queues Dr. Dobb’s Architecture & Design World Java and the Nokia N10 Internet Tablet Effective Concurrency The Agile Edge Swaine’s Flames

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