Channels ▼
RSS

Design

Linked Lists Are, Like, So Last Century


Processing all nodes. In serial, to process every element in a linked list, simply start at the head node of the list, process the node, move to the next node, and repeat until the last node is done. If the processing of a node is independent of the processing of any other node, processing of nodes can be done in any order and concurrently by multiple processes or threads. If the data is structured in a tree, before or after a node is processed by a thread (task), processing of the tree rooted at each child of the current node can be done as a parallel task. Once enough tasks have been generated to keep the system resources busy, no more new tasks need be generated and the processing of child nodes from that point is done by the executing task.

To better load balance the processing of nodes by tasks, your tree structure should be balanced or nearly balanced. If tasks are created at the same level of the tree, each task should have the same number of nodes to process. There are many different types of balanced trees that can be used. Find a good Data Structures reference to learn more about the options. Your choice will be dictated by what operations are needed or most used on the data collection and whether or not multiple threads can potentially access and update the tree in parallel.

Search. In this case, I'm thinking of unordered search. (If you have the data in sorted order, a single thread can traverse down a binary search tree to find the desired element without all the overhead of generating tasks.) For binary trees, there are three standard traversal algorithms: preorder, inorder, and postorder. All three are defined recursively, so you should immediately see where parallel tasks could be spawned. If you're not familiar with these traversal operations, pick up that Data Structures reference again.

If you are looking for a unique item in the data collection, the tricky part of a parallel search is to signal executing threads that the search is completed, terminate the currently executing tasks, and ensure that any pending tasks don't start execution. On the other hand, if the search must be exhaustive, meaning there may be more than one copy of the desired data item, don't terminate the search when an instance of the item is found.

Emulate a queue or stack. In these two cases, data is being inserted and removed from the shared structure. Those last two words should trigger the two words "mutual exclusion" in your mind. Like a shared linked list emulating a queue or stack, a tree doing the same function will need to ensure that when two or more threads attempt to insert an element or remove an element (or some combination of insertion and removal), then access to that tree structure must guarantee that no data is lost, duplicated, or corrupted. (I hope these last few sentences were just wasted typing on my part and you already were aware of all that.)

As for the queue or stack emulation, a priority queue can be done easily by enforcing a heap structure (back to that Data Structures reference?) on the tree. The strict implementation of a simple queue or stack will be a tad more complex with a tree. Consider that parallel execution order of tasks can be nondeterministic (as long as the output is deterministic). Even if we use a linked list for a stack within a parallel computation, then, by the very nature of the parallelism, the order of element processing is going to be unknown and unknowable in most cases. (If the algorithm requires a specific order to processing elements in and out of a stack, then you shouldn't be using parallelism.) Thus, as long as you have a method to safely insert and remove data elements, you should be well-served with any tree structure implementation (like a heap).

Have I been able to convince you to give up your sequential linked lists in favor of tree structures for all of your unordered data when processing that data in parallel? I'm mostly convinced myself. It sounds like a good idea and I'm swayed by my arguments above, though I've not had the opportunity to put this idea into practice. Nevertheless, I do wonder if there are some operations on data that traditionally use a linked list that cannot be rendered with a tree. My first thought is a frequency ordered list (again, back to the Data Structures reference for more than superficial details about frequency ordered list implementations). However, this structure is based on sequential access to elements and sequential ordering of searches. Can you think of any list access method/algorithm that could execute in parallel, but requires a sequential linked list or whose structure could not be made to fit into some variation of a tree?

(Author's Note: I kept wanting to write "Data Structures textbook" in the above. With so many online sources and eBooks available, the word "reference" was more appropriate. Plus, I've not seen too many textbooks in my time that cover frequency ordered lists.)


Dr. Clay Breshears Clay is the author of The Art of Concurrency, published by O'Reilly Media. He serves as the Technical Advisor to the Intel Software Network Parallel Programming Community and is the co-host of the weekly online show "Parallel Programming Talk.?


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

ubm_techweb_disqus_sso_-07fe5f3661053e93d9b42e32f8f83358
2012-10-19T02:09:08

You might refer to this article http://www.stroustrup.com/Soft... where Stroustrup compares std::vector and std::list. In his example and on his machine std::vector is the better representation of a list up to list sizes way larger than 500k, which I found quite surprising.


Permalink
ubm_techweb_disqus_sso_-4f781ffe5790fe5c8db6ded12877bb7d
2012-03-09T22:10:27

Sequential Processing is dead for any non-trivial application so make sense to me.


Permalink
AndrewBinstock
2012-02-13T18:43:07

Not sure I see how the article "misses the point." Most modern languages (not just C++, but C#, and Java, as well as Scala and many others) have extensive libraries of data structures. But grabbing any old data structure off the shelf and dropping in another is not the goal of this richness. Rather thoughtful matching of the data structure to the program's needs is.

In that context, few developers today would even consider a tree in lieu of a list to implement some parallel functionality. This article shows how the tree is a viable alternative in such cases and why. As I discuss in my current editorial, the choice of which canned data structure to use and which algorithms to deploy are beginning to shift dramatically under the pressures caused by parallel programming. Breshears' article is just one of many examples of how that change will affect data structures.


Permalink
ubm_techweb_disqus_sso_-eedc6d454628af292e3eda19d6e0fc12
2012-02-13T10:05:34

calumg states about std:: data structures "that they don't contain inefficient operations". That is not true - for some problem you may have to use several operations, and since a data structure may have different advantages, there may sometimes be some gotcha's.
So it should be part of the professional programmer's knowledge to know enough back ground about the different data structures to choose the most optimal taking into account the case at hand, but then of course choose one that is already implemented and tested.
Otherwise we would all be script kiddies!


Permalink
ubm_techweb_disqus_sso_-9aa571133382c03d44870572d54501f7
2012-02-07T10:33:27

This article misses the point that programming isn't about writing data structures any more. They've been written already, they are in the standard library, and if you are seriously going to reimplement what's in the standard library then you are either ignorant or a show-off.

Nowadays, you just pick a data structure based on your requirements, and if you suddenly realise that you need random access, then you change your typedef - in one place usually - from a std::list to a std::map. Job done.

In fact, the C++ standard library defines a standard interface for containers, so most containers interoperate: the same code can work on both a std::list, std::map or std::vector much of the time.

I can't recall where I read this (possibly Stroustrup), but std::vector is assumed to be the default container in terms of overall utility and efficiency. That hasn't changed, but you just need to know your big-O.

What's wonderful about the C++ containers is that they don't contain inefficient operations. So if you pop_front() a std::vector, the compiler will generate an error. Change your data structure to a std::deque and all is tickety-boo.

Now, sometimes standard containers aren't good enough, but 99% of the time they are, and you can wrap them in a mutex if required.

If you are going to write your own tree structures (if for some reason the std:: ones are not acceptable based on some flawed premature optimization), then lock-free trees and rebalancing RB-trees are seriously fiddly and distracting, hence why canned data structures are so great.


Permalink
ubm_techweb_disqus_sso_-48d6925060ef87cdf7114d2982cca188
2012-01-25T12:36:49

You glossed over one of the big problems with trees: re-balancing. If your tree is static, or its contents change infrequently, then you balance it once when you create it and then infrequently after that as your application runs. However, if the data is constantly changing then you either have to re-balance frequently, which can be hideously expensive, or you have to accept performance degradation over time as the tree becomes less and less balanced, followed by a pause in processing while you re-balance.

The Data Structures References that I have seen leave the task of determining when to re-balance the tree as an exercise for the reader, simply because the author doesn't actually have a generally satisfactory answer to when it should be done, nor how it should be done efficiently or incrementally. To my mind, if the experts cannot offer useful guidance that can be encapsulated into a library, then the data structure is not suited to the problem space. In the case of constantly changing data, trees look like a bad choice.


Permalink
ubm_techweb_disqus_sso_-1bfa87c60a75bbe9face4c19c2eb3e86
2012-01-25T00:33:52

It seems to me that if you have a set of nodes you wish to process in parallel, you still have to assign nodes to threads, either with a producer-consumer model (where a single thread collects the nodes starting with the first and moving to the "next", and then dispenses them to the worker threads) or with each thread moving to the "next" node (or spawning new threads to do so). Either way, there has to be a defined mechanism to iterate through the nodes, so the efficiency only comes through the speed with which moving to the "next" node can occur. With the producer-consumer model I'd think the linked list would beat a tree hands-down, because there's no need for the tree traversal code (e.g. depth-first recursion, etc.).


Permalink
ubm_techweb_disqus_sso_-bd3a998eabdbc6b77233f3df87191797
2012-01-24T16:31:07

Constant time if you add the appropriate scaffolding to the list structure or O(n) if you don't. (Any implementation would have that extra pointer, so this is a specious argument on my part.)

Even so, you've seen through to the "fly in the ointment" of the idea to replace all lists with trees. Any kind of dynamic activity onto or from a list requires housekeeping to preserve the structure of the list. Simple additions or deletions with a list (like for an active queue or stack) are easier/faster to do, even in parallel, than they would be to a tree, as you point out. This is why I can't see an easy way to use a tree for frequency ordered lists; each access changes the order of items on the list.


Permalink
ubm_techweb_disqus_sso_-5576c507a5e85544c3edebbc7b7fbbf9
2012-01-20T13:35:32

The complexity of the structure of data varies by the "nature" of that data (one size does not fit all). A meta-data graph structure can encode linked lists, matrices, even recurrent structures. The operations on a graph therefore can use the most economical, therefore optimized, methods.


Permalink
ubm_techweb_disqus_sso_-2ca243258b22c498340dcd0569e0cfff
2012-01-19T14:47:28

It's a bad idea to force a structure upon trees, which they are not suited for. E.g. why would I pay logN cost to emulate a stack/queue using a tree when I can use constant time operations on a linked list.

My point being that serial or parallel, there are certain operations that linked lists are best suited for. e.g. constant time joining of two lists. O(N) merging of two sorted lists without allocating extra space. Parallel FIFO implementation etc


Permalink
jdhildebrand
2012-01-18T21:45:51

Hm. Okay, all that makes a lot of sense.

So in addition to linked lists, what other data structures might need to be replaced because of these considerations?


Permalink

Video