13 ms·
Linked Lists Are Still Hard
- andreasvc 10y agoWhy would one ever prefer a linked list over a dynamic array? I know about the asymptotic performance, but if you take actual memory performance into account (locality, cache, pointers are slow, etc), it seems dynamic arrays should be simpler and perform better.
- dozzie 10y agoBecause (doubly) linked lists can do something an array cannot? Like join operations in O(1)? Or removing an arbitrary element in O(1) once you have its handle?
- blibble 10y agoif it's unordered (like you'd expect a list of sockets to be) you can get O(1) removal for an array by swapping the end item into the removed slot
- dozzie 10y ago...unless something else holds a pointer to the handle you're swapping with.
- blibble 10y agokernels don't tend to give userspace raw pointers into kernel memory
- staticassertion 10y agoThis is already a problem if you're removing an item, regardless of whether it's done with swap remove or not.
- toast0 10y agoFor the item you're removing, you are presumably removing it because all handles have been closed. But the item you're potentially swapping with may certainly have open handles.
- staticassertion 10y agoTrue.
- bmon 10y agoInsertion and deletion are prime examples, often requiring you to move large chunks of memory. The same operation just requires pointer changes (after finding where you want to insert or delete). I think in this example it would be common to be removing structs from the center of the list.
- signa11 10y ago> Insertion and deletion are prime examples, often requiring you to move large chunks of memory. on modern cpu's with huge caches, i seriously doubt this claim. fwiw, i have played around with synthetic problems where: i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. and almost always, vectors outperform lists by at least couple of orders of magnitude. or to put it another way, it is almost never about either lists / vectors or something else, and boils down to couple of 'rules' e.g. access data predictably (avoid trashing the cache), keep data compact (more cache utilization) etc. etc.
- jstimpfle 10y ago> i insert sequence of random integers into a sorted sequence, then remove those elements one by one as determined by a random sequence of positions. Which means that you scan the list twice for each node. First for insertion and then for deletion. Starting at maybe a hundred that would be much more efficient with a balanced search tree. They have a good Red-black tree in Linux. But if it's only arrays vs lists - with linked lists, pointers to items are never invalidated. With dynamic arrays, they are. Dynamic arrays are fine for plain old data arrays. But it's harder for data that has "identity" and is frequently mutated. And if a node is in multiple lists, I guess arrays are out. You'd need to store the data redundantly. Extra bad if you need atomic mutations.
- yongjik 10y agoWell on a 64-bit machine each node of a singly-linked list of integers will be 16 bytes (8 byte pointer + 4 byte integer + 4 byte for padding). That's 300% overhead. Becomes 500% for doubly-linked lists. So it's not surprising that linked lists perform very poorly in such circumstances.
- SamReidHughes 10y agoNo error handling code when adding an element to the set. Also, a list maintains elements in order, unlike an array pointing to objects that keep track of their position in said array.
- chriswarbo 10y ago> Why would one ever prefer a linked list over a dynamic array? (Singly) linked lists are trivial to implement in an immutable way (the article talks about the difficulty of doubly-linked lists, implemented in a mutable way). It's trivial to have linked lists share a tail; this makes datastructures like cactus stacks really easy. Linked lists are amenable to reasoning by induction (e.g. in Coq, Agda, Idris, etc.). Linked lists are amenable to lazy algorithms (e.g. iterators/generators). Linked lists can be heavily optimised, e.g. using stream fusion. That's off the top of my head. Note that in many cases it might be preferable to use linked lists in the source, but have them compiled to some other representation like arrays (or, in the case of fusion, a single tight loop).
- jstimpfle 10y agoWhat you say doesn't apply to the kernel, which uses doubly linked lists.
- biocomputation 10y ago* Also, lists are a reasonable way of managing unrelated types.
- koverstreet 10y agoBecause with intrusive lists, insertion/removal can't fail due to memory allocation failure - with dynamic arrays, it can. In the kernel, where you have to handle every single error path, this is a big deal.
- robmccoll 10y agoIf you are using a slab allocator like in this case, you are effectively splitting the middle. Allocation of the nodes is contiguous in the slab, so locality of the nodes overall is likely better than malloc()ing each one. Allocation is cheap since you are likely just grabbing the head of a free list in the slab (or incrementing a counter if you never intend to free intermediate data), and you get less heap fragmentation/ higher utilization than a pure linked list. You still get fast insertion and removal anywhere in the list. There's a bit of storage overhead for pointers and pointer jumping on access, but ideally your list isn't super fragmented, so close to linear cache reads. If the list is long lived / has certain turnover patterns, some of these effects fall away. You could implement your own defrag/resort, but that assumes being able to relocate the data. Also in some cases the linked list header may be embedded in other structures, so you'd have to pull the header out to go with a purely vector-based approach for when you need to shift (assuming you can't move the entire structure). And if the structure needs to reference itself in the list for quick removal, that's a problem if its index is changing. Otherwise you could just search the vector for references at linear cost.
- falcolas 10y ago> Why would one ever prefer a linked list over a dynamic array? Consistent performance. Every insert and every delete requires the same amount of time, at the cost of a higher average traversal time. You can ameliorate some of the deletion reordering cost if you can change the order of the array, but not all use-cases allow for this. Also, intrusively linked lists (that is, the same item represented in multiple lists) are just as poor, performance wise, when implemented with arrays. I did a quick test of this at one point, comparing C++ std::list with a linked list; the performance of the dynamic array was significantly higher for most operations (about one order of magnitude for my test), but the worst-case was much, much worse than the linked list (somewhere close to two orders of magnitude).
- jekub 10y agoThere is a lot of reason why you can prefer a linked-list over an array, even with the hardware changing they are still a lot more efficient in some cases : * In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays ; * For intrusive list, insertion and deletion can't fail due to memory allocation ; * If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array ; * Merging two list is only one pointer operation ; * Intrusive list have better memory allocation properties ; * ... If you look at the usage of linked-list in the kernel you will see that they are used for reasons. The problem is that, on new hardware, linked list should be used in less cases that in the past and some people have generalized this to linked-list should never be used. This is false, if you care about performances you should keep thinking and testing what is the best data-structure in different cases. If you don't care about performances, you should use an abstraction who implement what you need and don't car about the underlying data-structure.
- josefx 10y ago> In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays I just love when multithreaded code frees the element I currently iterate over in a different thread. > For intrusive list, insertion and deletion can't fail due to memory allocation ; As long as you store your elements on the stack or use static values you mean? Heap allocation happens at some point, you just move the location where it happens. > If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array Use a circular buffer. Until the array is full you can just modify the start/end pointers.
- brenns10 10y agoMore important than any of the sibling arguments is that we're talking about a socket control block. I don't control where it is allocated or freed, so I can't dictate its location in memory. Even if I did control it, there are probably several lists a socket might be a part of. Storing the socket in a dynamic array will only work for one of those lists. It's similar to a sparse database index - you can only have one of them. The rest of the lists have to be linked. Not to mention, when items are shuffled around in a dynamic array, you lose the ability to have a consistent pointer to them.
- dahart 10y ago> Why would one ever prefer a linked list over a dynamic array? I thought this same thing when I started doing embedded console game development and saw a lot of linked lists going on. I came to realize there are a bunch of really good reasons to use linked lists. The biggest difference in practice is that linked list pointers are commonly fields inside the data that you're linking, as opposed to being a separate data structure. With a dynamic array, it's usually a separate data structure. Neither of those is absolute or always, but that's how it normally plays out. With that in mind: Sometimes you're loading a block of pre-formatted binary data off disk or from a network that has space for linked list pointers. Rather than allocate anything else, you can fill in the list pointers. Sometimes you have a lot of small lists to manage. If you're allocating space for your list data, and the dynamic array doesn't get big enough for amortizing to take over, then you're doing double allocations, one for the data and one for the dynamic array & potentially first couple of reallocs. Fragmentation is worse with a dynamic array (when it's a separate data structure), and re-ordering events are much costlier in arrays than with linked lists.
- qeternity 10y agoI am hardly a kernel programmer, but it seems the real issue here is still that the release_sock() call isn't actually doing what he assumed.
- deleted 10y ago[deleted]
- brenns10 10y agoYeah, this is the real problem. To be clear though (the article skimmed over lots of details to remain generally accessible), I was not discussing the release_sock() function which releases a lock on a socket [1]. Instead, my code registers a set of function pointers in a struct [2]. While release_sock() does have documentation, the function pointer of the same name does not, and the only examples I have are other files of code within the MPTCP protocol implementation. The callback is related to the function, to be sure, and so I should have connected the dots, but this is how we learn. While I was making a baseless assumption, I like to believe that it was baseless because there was not enough available information, and not because I was ignoring obvious sources of information :P [1]: http://lxr.free-electrons.com/ident?v=4.1;i=release_sock http://lxr.free-electrons.com/ident?v=4.1;i=release_sock [2]: https://github.com/multipath-tcp/mptcp/blob/e77e2ca0b5339af20b67d6c8d81169470900e6da/include/net/mptcp.h#L230 https://github.com/multipath-tcp/mptcp/blob/e77e2ca0b5339af2...
- noelwelsh 10y ago"I guess the moral of this story is that tools are excellent, and you should probably use them." This is, in my opinion, a rather generous interpretation of events. What I see when reading this is a system (the Linux kernel and surrounding infrastructure like the C language) that is very poorly designed. For example, resource allocation is a fundamental issue and a constant source of problems. We've known this as a field for a very long time. Why are fundamental things like resource allocation at least not standardised in the kernel? Better would be to enforce safe resource usage by static checking. Rust is an example of what can be done here, but much more is possible. (I'm not trying to suggest the kernel should be rewritten in Rust. I'm just using it as an example that resource usage [in particular, memory allocation in Rust] can be done in a way that prevents errors.) Burning huge amounts of human effort is a popular approach to software development but I really hope we can do better in the next few decades. The worst thing about the current situation is the programmer blames themself ("This one kept me up until 3AM. In hindsight, every bug looks simple, and when I figured it out, I was embarassed that it took me so long") rather than wondering why this problem is even possible in the first place.
- Chris2048 10y ago> The worst thing about the current situation is the programmer blames themself ... rather than wondering why this problem is even possible in the first place. Absolutely agree. I think environment is partly to blame. Devs fight fires rather than prevent them because it makes their efforts more visible. It's the reason you can demand metrics to justify everything - the only metric that justifies defensive programming are examples of bugs/failure, and it would be better to just avoid them in the first place.
- foldr 10y agoOne issue with Rust (which I know you weren't actually suggesting for use in the kernel) is that it's difficult to implement recursive mutable data structures in a way that makes the borrow checker happy. Recursive mutable data structures are pretty common in the kernel, I should think.
- deckiedan 10y ago
- grabcocque 10y agoA linked list is almost certainly not what you want either. They're so deeply cache-unfriendly that their appearance in kernel code should be viewed as suspect.
- justinhj 10y agoThe article indicates use of a slab cache which means that all the socket structures will be together in memory.
- deleted 10y ago[deleted]
- UK-AL 10y agoI was under the impression, that linked lists are quite common in the Linux kernel.
- huhtenberg 10y agoThey indeed are.
- forgotpwtomain 10y ago> They're so deeply cache-unfriendly There a number of variations on linked lists, which are cache friendly (e.g. unrolled linked lists)
- panic 10y agoWhat would you use instead?
- Johnny_Brahms 10y agoHave you looked at the Linux source? It is full of linked lists everywhere.
- tropo 10y agoThey are cache-friendly in normal Linux kernel usage. There are not distinct allocations for list links; the pointers are embedded (via a small struct) in the struct that is being dealt with. In walking the list, you normally need to look at that stuff anyway, and with everything together you can share cache lines. It isn't normal to run down the entire length of a list without looking at the data. Since you need to look at the data anyway, it is best that the data share cache lines with the linked list info.
- monomaniar 10y agosee the resume of the author. good boy.
- ReligiousFlames 10y agoThere are numerous, tested macro libraries to prevent reinventing common data-structure/algorithm bugs. Here's one: https://github.com/troydhanson/uthash https://github.com/troydhanson/uthash
- joosters 10y agoAh, Hacker News comments, you are so predictable. Naturally, this article inspires multiple comments declaring that the way the kernel allocates or arranges memory is so obviously stupid and wrong, and that they know the right way of doing it. I love the certainty of Hacker News posters! So confident in their own abilities and opinions. Never a moment of concern, introspection or doubt. What a world to live in! Also, has someone thought of writing a 'it should be re-implemented in Rust' comment auto-generator? Or is that already running here?
- fao_ 10y agoYou might like http://n-gate.com/ http://n-gate.com/ It's a nice antidote to Hacker News, on days when Hacker News is too... Hacker Newsy :^)
- Jaruzel 10y agoI don't think my eyes are ever going to recover after reading[1] the n-gate.com about page. :O --- [1] 'reading' being a highly optimistic term.
- TurboHaskal 10y agoGood laugh. Whenever I stumble upon a website made with werc I know I'm in for a treat.
- pc86 10y ago> Now that they've got some hard data to ignore, they have another shitfest of lies, confusion, and using the word "generally" to mean "in the cases I have noticed." One Hackernews wonders what the big deal is with the Constitution. Someone shows up to compare it to software. That is a stunningly apt description of those comments. And I am definitely guilty of using "generally" in that manner.
- dooglius 10y agoThere seems to be a lot of jumping to conclusions and knee-jerk reactions in this thread. As a C developer, and having worked on Linux drivers, the description here is quite strange; memory is always freed by the same "layer" that allocated it. The implementation of release_sock (http://lxr.free-electrons.com/source/net/core/sock.c#L2536 http://lxr.free-electrons.com/source/net/core/sock.c#L2536) appears to have a callback, and appears to not free memory, so it doesn't look like we have the full story here. What is clear is that the author misunderstood the "right way" to use the API in some way, and the lack of good documentation for a lot of kernel APIs is a big problem. Perhaps Rust could have prevented the bug? I don't know. I haven't looked into Rust a great deal, but the impression I get from what I've read is that it severely limits expressiveness (read: the ways in which you can define APIs) unless you encapsulate things in blocks annotated "unsafe", at which point you lose any checking the Rust does. Would it even be possible to port the sockets code to Rust without fundamentally changing the APIs and data structures? To the Rust people: it comes off pretty badly when you throw around claims like "C effectively is unsafe everywhere" because "unsafe" in English doesn't mean what it means in Rust nomenclature; calling something "unsafe" implies it has bugs or security holes. It is perfectly possible to write bug-free secure C code, and also perfectly possible to write buggy or insecure Rust code. What I think you mean is: C code is roughly equivalent to what you'd find in a Rust block annotated "unsafe", and thus cannot perform some of the compile-time checks that Rust can. Calling it something else like "lowlevel", "expressive", or "tricky" would be better.
- brenns10 10y ago> so it doesn't look like we have the full story here I omitted so many details writing this -- otherwise the main story would have dragged on way too long. My comment here [1] gives some context. [1]: https://news.ycombinator.com/item?id=14184148 https://news.ycombinator.com/item?id=14184148
- sbierwagen 10y agoIt is perfectly possible to write bug-free secure C code, https://cve.mitre.org/data/downloads/allitems.html https://cve.mitre.org/data/downloads/allitems.html
- 10y ago
- tytso 10y agoThe real problem is that developer (who is a graduate student) doesn't understand how to do use the kernel structure. You can't just have "your own linked list". In order to do what you are doing, you have to add a list_head structure to the struct sock structure just for that linked list, and that struct list_head has to be initialized when the struct sock is initialized, and list_del() is called when the struct sock is released --- oh, and you need to handle locking properly to avoid races between adding a struct sock to the list and removing it. Or you can use RCU, but you do need to avoid races one way or another. It's not hard, but you do need to understand the idiom. Why isn't there safety mechanisms? Because the kernel is optimized for speed, and instead of adding run-time checks which can be expensive, there are various debugging tools, including slab poisoning and KASAN to find such issues.
- brenns10 10y agoAnother possibility: the developer understands these things, but wrote a blog post with an explanation that omits some details in order to appeal to a broader audience.
- pera 10y agoEh to be fare, because the kernel linked list implementation is slightly different from what most people think of a linked list, I believe it's easy to get a bit confused with it from time to time... I agree with you that it's not hard per se, but some of the bugs one can introduce with this type of linked list are a bit hard to track down, at least in my own experience.
- nickpsecurity 10y ago"It turns out that MPTCP sockets are allocated using a slab cache. I found this out early on, but forgot about it nearly as soon as I found out." The real problem isn't linked lists. It's that the author learned how something worked (the spec), forgot about that, and then essentially coded against the wrong spec. The title might have instead been: "I forgot something and broke a kernel." Much more accurate given people who know they're dealing with slab allocators, linked lists, etc usually use them correctly. They can also sleep a bit better instead of being up until 3am debugging.