English | 中文 | Русский | Français

2,856 Posts served

8,606 Conversations started

Linked Lists - Incompatible with Parallel Programming?

By Arch Robison (Intel) (19 posts) on December 20, 2007 at 3:08 pm

I've been asked several times why TBB does not have a concurrent list class; i.e., a list that supports concurrent access. The answer is that we'd add one if:

• We could figure out semantics that are useful for parallel programming and
• We could implement it reasonably efficiently on current hardware.

I usually try to avoid linked lists even for sequential programming if I'm programming for performance. My reasons are:

• Linked lists are often misused in ways that create asymptotic slowness. Usually the culprit is searching the list. Yes, similar abuses can occur for other data structures too. But lists seem to attract this abuse.
• Linked lists are unfriendly to cache. Adjacent items in a list tend to be scattered in memory. With cache misses costing on the order of 100x a cache hit, this can be a significant performance issue.

For parallel programming, add another flaw:

• Traversing a linked list is inherently serial. [Theorists will point out that traversal can be done in parallel if you have a processor per node in the list. Feel free to buy that many Intel processors -- I own Intel stock.]

Two traditional attractions of linked lists are:

1. Linked lists are about the easiest dynamic data structure to write from scratch.
2. Prepending and appending take O(1) time.

But modern polymorphic language like C++ provide dynamic data structures like std::vector and std::deque. You don't have to write them from scratch. Prepending or appending to a deque also takes O(1) time. Appending to a vector takes O(1) amortized time. Amortized time is the time averaged over many append operations.

Here's a speed test you might want to try. Construct a container, append n items, walk the container once, and destroy it. Here's the code:

template<typename Container>

int Iota( int n ) {

    Container container;

    for( int i=0; i<n; ++i )

        container.push_back(i);

    int sum = 0;

    for( typename Container::const_iterator j=container.begin(); j!=container.end(); ++j )

        sum += *j;

    return sum;

}

I tried this fragment on a Linux box and found that std::deque was slightly faster than std::list when n>=3, and std::vector was slightly faster when n>=10. When n>=100, std::deque was more than 10x faster than std::list, and even std::vector more than 3x faster than std::list. So for very short collections, std::list might pay off. But for big collections, its second-rate.

Of course linked lists do have some virtues, notably when concatentating lists, splicing lists, and inserting items in the middle. I use lists when I need to do that. But getting back to parallelism, which set of those operations make any sense in parallel programming? Concurrent splicing and inserting seems awfully tricky to use correctly. For example, if I really need to insert in the middle of the list, it must be because there is something special about the insertion context. But if there are other threads inserting at the same time, how do I know the context will not be broken?

The two operations on lists that I think could be useful in parallel programming are:

1. concatenating two lists, in constant time
2. splitting a list into two sublists, or at least view it as two sublists, in constant time

For example, a parallel reduction could use "concatenate" as its reduction operation, and thus build a list of N items in O(N/P+log(P)) time. The log(P) term arises from a tree reduction at the end. The problem is the second operation. To keep a list from becoming a serial bottleneck, we need a way to traverse it in parallel. That probably means it is no longer a linked list, but some kind of (balanced?) tree structure.

I've had a recurring thought that we should add this kind list, one that supports concatenation and splitting in constant time. But we really need motivating use cases before implementing it. Suggestions for good use cases or demos appreciated.

- Arch Robison

P.S. I though about writing this blog as a politcal attack ad, but given the technical details, decided against it. If I had done it that way, it would have started:

Mr. Linked List is running for office. He's popular everywhere. But here's what Mr. Linked List doesn't want you to know... .

Categories: Parallel Programming, Threading Building Blocks

Comments (16)

Trackbacks (0)

Leave a comment  

Name (required)*

Email (required; will not be displayed on this page)*

Your URL (optional)


Comment*