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

by Herb Sutter Effective Concurrency Choose Concurrency-Friendly Data Structures Some structures that are great for sequential work can be downright hostile to concurrent code WHAT IS A high-performance data structure? To answer that question, we’re used to applying normal considerations like Big-Oh complexity, and memory overhead, locality, and traversal order. All of those apply to both sequential and concurrent software. But in concurrent code, we need to consider two additional things to help us pick a data structure that is also sufficiently concurrency-friendly: • In parallel code, your performance needs likely include the ability to allow multiple threads to use the data at the same time. If this is (or may become) a high-contention data structure, does it allow for concurrent readers and/or writers in different parts of the data structure at the same time? If the answer is, “No,” then you may be designing an inherent bottleneck into your system and be just asking for lock convoys as threads wait, only one being able to use the data structure at a time. • On parallel hardware, you may also care about minimizing the cost of memory synchronization. When one thread updates one part of the data structure, how much memory needs to be moved to make the change visible to another thread? If the answer is, “More than just the part that has ostensibly changed,” then again you’re asking for a potential performance penalty, this time due to cache sloshing as more data has to move from the core that performed the update to the core that is reading the result. Linked Lists Linked lists are wonderfully concurrency-friendly data structures because they support highly localized updates. In particular, as illustrated in Figure 1, to insert a new node into a doubly linked list, you only need to touch two existing nodes; namely, the ones immediately adjacent to the position the new node will occupy to splice the new node into the list. To erase a node, you only need to touch three nodes: the one that is being erased, and its two immediately adjacent nodes. This locality enables the option of using fine-grained locking: We can allow a potentially large number of threads to be actively working inside the same list, knowing that they won’t conflict as long as they are manipulating different parts of the list. Each operation only needs to lock enough of the list to cover the nodes it actually uses. For example, consider Figure 2, which illustrates the technique of hand-overhand locking. The basic idea is this: Each segment of the list, or even each individual Figure 1: Localized insertion into a linked list. It turns out that both of these answers are directly influenced by whether the data structure allows truly localized updates. If making what appears to be a small change in one part of the data structure actually ends up reading or writing other parts of the structure, then we lose locality; those other parts need to be locked, too, and all of the memory that has changed needs to be synchronized. To illustrate, let’s consider two common data structures: linked lists and balanced trees. Figure 2: Hand-over-hand locking in a linked list. July 2008 l www.ddj.com l Dr. Dobb’s Journal 57 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.