On C Linked Lists (Profiling and Optimizing)

http://rusty.ozlabs.org/?p=168

by djcapelis • 16 years ago

60 31 16 years ago

rusty.ozlabs.org

tptacek10• 16 years ago

Generally, if you care about performance, you're using a collection that doesn't malloc individual nodes, and allows random access without crawling pointer chains and tearing up your cache.

Instead of wasting more energy on improving the (overused) linked list, write a little resizable array library that doubles size on each fill-up. It's easy and much faster.

nkurz2• 16 years ago

I don't think this a a good suggestion. Sure, it's commonly true, but it completely depends on your use case.

This is a very specific article about optimizing the linked lists as used in the Linux kernel, with wonderful data about real world usage. I find it highly doubtful that the Linux kernel would benefit from dropping linked lists in favor of resizable arrays. Possible of course, but I'd want to see the data before making any recommendations.

In general, it would depend on what's in your list and what you do with it. If each item is the size of a cache line, you're probably not trashing your cache[1]. If the list is large and you are keeping it ordered, you might benefit from easy insertions and deletions. If you've got millions of little lists of non-power-of-2 sizes, maybe doubling the size on a fill up would be problematic.

Obviously you know this and I'm not giving you any new information, but I'm confused why you'd make this recommendation. Is it aimed at Rusty? Or do you truly feel that the linked list has no place in the world?

[1] Well, maybe, but this depends on how often you need to do a full scan through the list. If you're storing unordered, you probably are scanning the array; if ordered, you'll be shuffling memory a lot on inserts. Again, use case matters.

tptacek10• 16 years ago

When modification happens often relative to accesses, and occurs in the middle of the container, lists make sense. When else do they make sense?

(In this article, modification is the most frequent operation, but "replace" is the least frequent; for some of those lists, tail insertion might be the most frequent use case).

For me, the question is, what's the right go-to collection for general purposes? For most C programmers, that's the linked list, and I think that's a bad default.

tedunangst6• 16 years ago

Did you miss the point that these lists aren't being crawled? That's not the slow part.

There are lots of reasons to keep track of things even if finding them is actually rare.

And an array doesn't solve any problem. Searching it is still linear, you're still tearing up the cache doing so because in a case like this you're storing pointers in the array, not data, and now you another memory allocation that can fail. structs with builtin links can always be added to a list without fail, growing an array not so much.

tptacek10• 16 years ago

No, the point of resizable arrays is that you don't store pointers in them.

FooBarWidget• 16 years ago

Arrays don't allow O(1) insertion and deletion except at the end.

neild• 16 years ago

Instead of wasting more energy on improving the (overused) linked list, write a little resizable array library that doubles size on each fill-up. It's easy and much faster.

Don't do this.

Doubling the size of your allocation whenever you expand can easily lead to large amounts of wasted storage in common scenarios. "Yes," you may say. "But memory is cheap." Which it is at the small scale, but when you're allocating 1GB to store a 512MB array you have a problem.

A vastly better approach is to use some form of adaptive rescaling which avoids excessive overcommits.

Here, for example, is the code (and explanatory comment) Python uses to determine the new allocation size for an expanding list:

        /* This over-allocates proportional to the list size, making room
         * for additional growth.  The over-allocation is mild, but is
         * enough to give linear-time amortized behavior over a long
         * sequence of appends() in the presence of a poorly-performing
         * system realloc().
         * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
         */
        new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) + newsize;
        if (newsize == 0)
                new_allocated = 0;

Note that you will also want to avoid using the same calculation for expanding and contracting the allocation size, to avoid thrashing allocations when the list size varies around the pivot point. (i.e., add one element, triggering an expansion; remove the element, triggering a contraction; repeat.)

tptacek10• 16 years ago

This is a great comment and I guess it's good advice, but doubling vectors have never caused a problem for me, I profile, and I've had them dealing with data sets like "each side of every TCP connection traversing 1/8th of an entire tier 1 ISP backbone".

I'll steal the Python trick, because it's neat, but I don't think worrying about your resize function is a good reason to procrastinate moving away from linked lists, which are mostly evil.

antirez• 16 years ago

It is not possible to argue on data structures without the use case at hand. Linked lists have time complexity for head/tail addition and removal of elements that is O(1), and you can't have this with resizable arrays. So there are good use cases for both.

Instead the trick you mention allocating multiple elements per node is actually a linked list of fixed size arrays: there you are trading a constant factor per storage efficiency. This is a good approach for many use cases as you are still O(1) and the cache locality will likely help to compensate for the additional operations you need to perform.

Still it's worth to note that there is to handle such a data structure to make sure, in the case of deletions in the middle, a few adiacent nodes that will end with just a few elements are "compacted" from time to time while traversing the data structure.

tptacek10• 16 years ago

An array with invalidation instead of deletion doesn't have to be O(n) on deletion-from-the-middle. I think anyone would have to concede that if you routinely need insertion in the middle, you can't use a flat data structure.

kvs• 16 years ago

Not necessarily all evil. Only text-book implementations require that one allocate individual nodes. Most implementations I have seen in Linux and FreeBSD can pool allocate the nodes. One can also pull off neat tricks to append link chains in these implementations to expand the list without the need to reallocate memory as needed by arrays.

tptacek10• 16 years ago

Pool allocation only addresses one of the problems with linked list; it still leaves you chasing pointers to iterate, it still decreases locality, and it still adds 4-16 bytes to every element in the container.

Meanwhile: you aren't really saying most people use pool-allocated lists, right? I see people hand-hacking malloc'd lists all the time. I rarely see custom pool allocators. It's what people were taught to do.

rdtsc• 16 years ago

Well it depends on your patterns of access. If you remove nodes a lot then you might end up moving large blocks of indices around. Unless you use a sentinel value, but then before you know it, you are implementing a hash table.

To reduce memory allocation time penalty you can use a memory pool.

However if memory size is a problem (maybe another 2 pointers per element) or if you do mostly adds and random access of elements an array could be a good choice.

ced4• 16 years ago

How does deletion work in ring-style lists when there's only one element in the list? Wouldn't that break a branchless implementation? How is the empty ring represented, anyway?

As for his test purportedly showing that A is better than B on Linux... It's only right if you assume that Linux can only use one type of list in all cases.

rwmj• 16 years ago

An empty ring never needs to be presented. The point about the Linux list is that it lives inside another struct. If there are no instances of that struct, then there is no need to represent an empty list at all!

ced4• 16 years ago

Yeah, I thought about that. But he mentions "emptiness testing" a few times in the rest of the post. If there's no empty list representation, what's the point?

tedunangst6• 16 years ago

I think you're confused. The list head exists outside of the structs that are in the list. The list links (next and prev) live in the struct, but not the head.

To answer the original question, you decide a list is empty when prev == next.

On C Linked Lists (Profiling and Optimizing)

Related Stories