This article makes the classic mistake of assuming linked list = mutable doubly linked list.
Immutable, singly linked lists (aka cons lists) are a different beast entirely, and don't benchmark well in languages with heap fragmentation issues.
Immutable, singly linked lists (aka cons lists) are a different beast entirely, and don't benchmark well in languages with heap fragmentation issues.
Microsoft has solved most of these issues on Windows, couple decades ago. The feature was introduced in WinXP, and enabled by default in Vista and all newer versions: https://docs.microsoft.com/en-us/windows/win32/memory/low-fr...
I’m not an expert in Linux but I would be surprised if Linux didn’t do the same. RAM costs have plummeted. The losses from RAM usage overhead of LFH became insignificant compared to the issues caused by the fragmentation.
But yes, the default glibc allocator does have dedicated areas for specific sizes of allocation:
> The normal bins are divided into "small" bins, where each chunk is the same size, and "large" bins, where chunks are a range of sizes[1]
But fixing heap fragmentation doesn't make linked lists suddenly fast. You still have your cache bloated with the overhead bytes needed for allocation. List elements can still be allocated non-contiguously, giving the prefetcher a bad day.
[1]: https://sourceware.org/glibc/wiki/MallocInternals#Arenas_and...
Also it would be possible to implement such an approach in a C++ list container where you don't need boxing (the content type is known).