Hacker News Reader

Comment by somenewacc | Hacker News Reader

For CPU bound stuff, the 80%/20% rule is to learn that an array/vector is typically much faster than a linked list, and this is due to how CPU caches work. (this is thinking about how much information is being moved around, but between the processor and RAM)

Also, for parallel stuff: locks tend to be bottlenecks. Writing parallel code is tricky overall. Stick to libraries that provide high level lockless data structures like mpsc queues if possible.

View on HN

Who uses linked lists? Outside of niche algorithms that splice lots of lists together there are practically zero occasions where linked lists beat dynamic arrays.

Linked lists are very common, especially for non performance critical code. Dynamic arrays either carry a large performance cost at expansion, or is rather complicated to implement in a amortized way. Linked list in comparison is simple, and since it doesn't require a large continues block of memory, the memory pressure is smaller.

A dynamic array has an average (armotized) time of O(1) but a worst case of O(n) – whenever your next insert is longer then the size of the list. Furthermore, it needs a lot of ram whenever copying elements. A linked list is always O(1) and its ram usage is consistent (although not better – normally it is twice or three times as big).

A linked list is basically only better on embedded systems because you have much better knowledge about the used ram/runtime. It’s also useful if you have a very large data structure and you need real time performance (a lag of a few hundred milliseconds are unacceptable for some applications such games or financial applications). But whenever your insert becomes too expensive, a linked list is probably not the best choice either and you should consider why your data structure is so big.

Lastly a linked list is rather simple to implement but that’s also only really useful for embedded stuff.

I think it's a cultural thing rather than a technical one. I haven't used a linked list in 15+ years, because in C++ a std::vector is the 'default'. Before that, I wrote (some) C for Gnome, and the 'default' in Glib is a linked list. I don't know/remember if there is a reasonable, easy to use data structure that wraps a dynamically allocated array in Glib, but most of the 'sample' code at the time used the glib list. So that's what everybody kept on doing.

I think GArray is the wrapper for a dynamically allocated array.

Ah yes it is, thank you. I should have know about this 15 years ago :)

I've seen LinkedList often used as the go-to list in Java, instead of ArrayList. They're also common in C, for example, a huge number of structures in the Linux kernel are linked lists.

> for example, a huge number of structures in the Linux kernel are linked lists.

Which allocator is used for these? I'm not familiar with the Linux kernel, but since there is no malloc() in the kernel, I would guess that they allocate from an arena that's going to be page-aligned and thus exhibit the same locality characteristics as a vector.

Oh, they have malloc, it's just kalled kmalloc.

Pretty much anyone using a functional language or immutable data structures.

The default immutable "list" types in current mainstream functional languages (eg. Scala, Clojure) have much better performance characteristics than naive head:tail linked lists. A typical implementation is a n-ary balanced tree where n is typically on the order of 100, making operations "effectively O(1)" and also keeping cache behavior acceptable in many common cases.

Haskell still uses head:tail linked lists a lot. However, a lot of effort has been spent in optimizing away the data creation entirely. For example `sum [1..100]` will not actually allocate the list in memory.

What about any time you're working with frequent adds/deletes in arbitrary positions, rather than just at the end of the list?

That's not a "niche algorithm" to me, but rather a reasonable use case. The add and delete operations should be faster than for the array case.

(Not that I actually use linked list much myself, but I mean I see the use of them.)

Even then, linked lists are only faster than arrays if the list has at least 100s of items.

That's pretty much a standard use case. IIRC the rule of thumb is that if the container isn't expected to hold many elements then the default choice is to use std::vector no questions asked. Otherwise, random insertions and deletions in a sizable container requires a std::list.

If the list fits in cache it is often to faster to insert into a dynamic array and shift the elements. It of course depends a bit on the allocator that you use how expensive creating a new list node is.

That's a good point, thanks.

> Who uses linked lists?

Isn't the linked list pretty much the main collection data structure in the Linux kernel?

I use deques A LOT, e.g. interthread messaging, and decaying/windowed time series calculations.

Like, if you want a running mean of the last 250ms, you put a timestamp and value pair in the back a deque, and every update you check the front of the deque to see if it should be popped (i.e. the timestamp is older than 250ms), and the mean updated.

I suppose you could use a circular buffer with a vector as well, but you have to guess what your max size will ever be, or handle dynamic resizing. Maybe it would be worth it in some circumstances.

If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.

Reply on news.ycombinator.com