This article reminds me of performance advice I was starting to see in the 2000s decade. Basically it was to not introduce a bunch of pointer heavy data structures to get lower algorithmic complexity. Stuff it all into a vector. You will use some algorithms that the computer science textbook will say it's slower, but if it fits all in cache it doesn't matter. The cache misses following pointers all over town hurts you more.
This is partly because the C++ stdlib looks like they've given you all the basic tools you need - unlike the C standard library - yet in fact many of these tools are hopelessly obsolete. It's not quite PHP's "fractal of bad design", these are all reasonable tools... if it's 1985. The linked lists make sense on hardware where five pointer fetches and five consecutive memory reads cost roughly the same - 1985 hardware.
The growable array type std::vector<T> is least impacted by these archaic choices out of the tools in the box you're likely to reach for. So it will make sense very often to choose this type first.
Linked lists are great data structures for the use cases where you need their properties. It’s just that you don’t encounter those scenarios very often in most kinds of software.
You say not very often, but the true usefulness is almost never. Extremely little. One in a trillion times. Even when you think linked lists would be faster, they usually aren't.
Naturally the mind races to think of where linked lists are used.
The Linux kernel uses them, at least some of the time they're used with their lock-free RCU pattern. I'm not sure if it's for performance reasons though, I think they're using it in contexts where correctness requires the absence of blocking operations.
I'd expect a lock-free non-linked-list solution would also be possible, but I don't know enough to state that definitively.
Linux is definitely a mix of "It's a linked list because multiple CPUs are simultaneously doing swap operations on the list while it is still in use, with linked lists that's an atomic operation whereas if we did something else it would need a lock" and "C does not provide a growable array type, so I used a linked list 'cos that's easy to write in C"
My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
> My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
asveikau · · focus · HN ↗
tialaramex · · focus · HN ↗
The growable array type std::vector<T> is least impacted by these archaic choices out of the tools in the box you're likely to reach for. So it will make sense very often to choose this type first.
adrianN · · focus · HN ↗
someonebaggy · · focus · HN ↗
MaxBarraclough · · focus · HN ↗
The Linux kernel uses them, at least some of the time they're used with their lock-free RCU pattern. I'm not sure if it's for performance reasons though, I think they're using it in contexts where correctness requires the absence of blocking operations.
I'd expect a lock-free non-linked-list solution would also be possible, but I don't know enough to state that definitively.
<a href="https://docs.kernel.org/RCU/listRCU.html" rel="nofollow">https://docs.kernel.org/RCU/listRCU.html
tialaramex · · focus · HN ↗
My guess for the 0.x releases in particular is that there's a lot of the latter and as Linux goes from "Like Minix but I made it in my bedroom" to Serious Business™ more and more of the former.
asveikau · · focus · HN ↗
In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
MaxBarraclough · · focus · HN ↗
Or are pools used to avoid that?
someonebaggy · · focus · HN ↗
Well not explicitly, but it uses a version of malloc that has a pool for every rounded object size.