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 uses linked lists because they can reserve a fixed amount of memory for the linked list cells inside the element itself (intrusive list) and they can be allocated non-continguously aka you can freely extend them as you like. This is useful if you want to reserve a chunk of memory statically. This guarantees that you can do work before your allocator is online and then when the allocator is online, you can transparently extend your memory with further allocations.
You can also take independent modules that provide their own statically allocated memory and chain them together using the reserved linked list cells. (think kernel modules)
This is a bit of a wishy washy explanation because I work on a highly adjacent project that has similar constraints but I never looked at the kernel source (strictly working with statically allocated memory during startup).
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
imtringued · · focus · HN ↗
You can also take independent modules that provide their own statically allocated memory and chain them together using the reserved linked list cells. (think kernel modules)
This is a bit of a wishy washy explanation because I work on a highly adjacent project that has similar constraints but I never looked at the kernel source (strictly working with statically allocated memory during startup).