3 ms·

This article makes the classic mistake of assuming linked list = mutable doubly linked list. Immutable, singly linked lists (aka cons lists) are a different be

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.

gumby 4y ago
And cdr-coded lists, or sublists, can have vastly improved cache performance, especially when you have a transporting GC.
- bjoli 4y ago
  Does any implementation updated in the last 25 years use CDR coding??
  - gumby 4y ago
    I don't know -- most implementations on popular architectures only have two (low order) bits for tagging due to alignment issues, so there may not be room. Might be easier in the case of a RISC V with the tagging extension. 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).
    - hayley-patton 4y ago
      On a 64-bit machine where everything is aligned to two words (like SBCL), you get 4 bits for tags.
Const-me 4y ago
> 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-fragmentation-heap 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.
- flaviut 4y ago
  To be pedantic, Linux doesn't care about how malloc is implemented. That's purely userspace's concern. 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_Heaps https://sourceware.org/glibc/wiki/MallocInternals#Arenas_and...

gumby 4y ago

And cdr-coded lists, or sublists, can have vastly improved cache performance, especially when you have a transporting GC.

bjoli 4y ago
Does any implementation updated in the last 25 years use CDR coding??
- gumby 4y ago
  I don't know -- most implementations on popular architectures only have two (low order) bits for tagging due to alignment issues, so there may not be room. Might be easier in the case of a RISC V with the tagging extension. 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).
  - hayley-patton 4y ago
    On a 64-bit machine where everything is aligned to two words (like SBCL), you get 4 bits for tags.

Const-me 4y ago

> 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-fragmentation-heap 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.

flaviut 4y ago
To be pedantic, Linux doesn't care about how malloc is implemented. That's purely userspace's concern. 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_Heaps https://sourceware.org/glibc/wiki/MallocInternals#Arenas_and...