Posted by todsacerdoti 5 days ago
The practices that apply to kernel development do not generally apply to very much else.
But then again... I never thought I'd need to know music waveform theory while I was watching the magic school bus as a kid... Turns out that was incredibly useful when I needed to implement a music note generator for a VoIP client... You never know when something might actually be really useful.
1. You have linked lists in Rust. They're in the standard library.
2. Linked lists do not have "unmatched performance" - they are slower than almost anything, outside of highly specialized use cases. Even moreso for intrusive linked lists. Worst of all, they are horrible for cache locality.
There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
There's a lot of things to learn that appear to to not makes sense... until suddenly they do.
> There are valid uses of linked lists, that's why they exist, but most people don't have those use cases.
Isn't that pretty much what I said?
I'm pretty sure we agree that they're useful, but their usefulness isn't as universal nor as common as the pattern is.
Their one benefit - O(1) ordered removal - is easily achieved with a flat array, in at least two common ways: swap in the last element if you don't care about the order, or mark the index as vacant if you do care about the order, or if you care about the stability of references.
I mean, I agree that they're kind of neat from a certain perspective, but they're almost never the right choice.
Personally I have not met a case where a random removal in the middle of a list is common -- b/c finding the needle is slow to begin with O(n). In such case linked hash sets are O(1) but way more memory intense (which is a very advanced linked list)
That being said linked queues are great for concurrent lock free cases.
Linked list have higher const cost memory wise compared to array backed structures. Even when an array back structure is half empty it's still takes less memory.
uh... what?
Maybe you only see these projects as a user, but linked lists are not uncommon. Your experience reflects your, well, experience. We all sit in different niches.
Mind you, most of those will be written in C on a typical Linux installation, and linked lists happen to be one of the two collection types that are relatively easy to use in C (the other being a flat array), so I will concede that some software is using linked lists out of desperation, rather than it being the correct choice. :-)
Of all of those mentioned I literally looked up their source repositories up and searched for obvious indicators like "linked", "list", ".next" or "->next" and then verified that I was indeed looking at one or more linked lists. Where does your confidence come from? Oh right, you already mentioned it: it's based on your experience of the projects you've worked on.
The rest of your reply is just moving goalposts, mind reading and a glaring category error. Get back if and when you have something useful to add.
In larger C software sometimes a use of linked lists is costing meaningful performance and a growable array type would be a huge win - but the other side of the coin is that sometimes in these perf critical environments a linked list actually is the right choice, and a C programmer might luck into that since it was the first tool to hand while say a C++ or Rust programmer might take longer to realise that this data structure is the best option.
- conventionally we put the `node' struct at the start of the `user' struct. The advantage is that we can convert from node* to user* with a simple cast instead of messing around with offsets. Knowing the offset stuff is still potentially useful in case you want multiple `node's in a single struct, but that is seldom the case so you can almost always get by with just a cast.
- this strategy is, especially with the node at the start of the user, equivalent to inheritance. I take it from the fine article that zig doesn't have inheritance? If they are planning on adding more interfaces like this linked list one, then inheritance would be a good idea. We often treat inheritance using analogies to the animal kingdom or to geometric shapes, but data structures like linked lists are (to my understanding) the problem that inheritance is actually designed to solve, and it is really the best approach to solving problems like in the OP.
- just lol on zig speed running being a crappier C++.