4 ms·

Most GC languages use bump-pointer allocation and/or compacting garbage collection to (try to) ensure that objects are stored in memory in this way regardless o

Most GC languages use bump-pointer allocation and/or compacting garbage collection to (try to) ensure that objects are stored in memory in this way regardless of being dynamically allocated. This means that even naive linked list implementations are typically much more cache efficient than you would expect coming from C, at least after a GC pass. It also means though that changes to the dependency graph of your program can have unexpected effects for your cache hit rates, since the compacting heuristics are pretty simple (they typically work by copying "child" objects immediately after the "parent" object, but there is no mechanism to define the "right" parent for an object)

hinkley 6y ago
In most GCs the mark phase also disrupts the cache by doing what looks a lot like a table scan. That’s one of the reasons for generational collectors. Better cache locality.
gameswithgo 6y ago
I've seen a Linked List get allocated very contiguously at times in .NET when it is just a toy program, like just benchmarking linkedlist performance, it sometimes does really well. But in the context of a big running program with other things in the heap it is much less likely to work out so well.
pradn 6y ago
Modern memory allocators like tcmalloc are pretty good with putting structs of the same size in contiguous areas of the heap. For smaller structs (which most real world cases fall under), it's just one lookup to find the next place to put the new object. So, C and Java will have similar performance for allocating a lot of small objects, I think. There's probably a difference on the deallocation side, especially with fragmentation, but I'm not as knowledgeable about that. If someone has a richer explanation, I'd love to hear.
- scott_s 6y ago
  As someone who worked on memory allocators in a past life: cosign. Size-class based allocation for small objects is how modern memory allocators have worked for a long time now. I'm genuinely baffled by how many people think that the bump-pointer allocation for same-sized objects is unique to garbage collection.
  - pradn 6y ago
    Thanks for confirming this. Do you have an idea of how modern allocators compare with generational GCs on the cleanup / realloc / fragmentation side?
    - scott_s 6y ago
      No, and that would make a great empirical study. (Maybe there has been one! I should check ISMM over the past decade, someone may have done it already.) From first principles, the biggest difference is that manual memory allocation can't move live objects around. But manual memory managers do still have the ability to be smart on deallocation, to the point that calling free will sometimes cause things to happen that would be similar in a garbage collector.
kazinator 6y ago
Even if you have a bump allocator, the fact is that a linked list requires storage for the pointers, which are not needed in an array. That makes the list bigger, and bigger means worse from a caching point of view. Fewer parts of a linked list fit into a cache line and so on. Plus the pointer traversals are dependent loads. Until we load node->next, we don't know what address that is, so we cannot pre-fetch node->next->anything. But when we access array[i], it's possible to pre-fetch array[i+1]. I'm still using linked lists because of the flexibility, functional substructure sharing and allocations you can avoid, but let's not kid ourselves.
- galangalalgol 6y ago
  And if your data is truly contiguous and its struct of arrays instead of the other way around, SIMD becomes much more usable.
- simiones 6y ago
  Absolutely, I'm not claiming linked lists are "better" than arrays. The GP was mentioning memory fragmentation and cache behavior, and I was pointing out that GCs can, at least in some conditions, make linked lists more efficient then they are in C (comparing naive implementations). But yes, linked lists are almost always worse than arrays, unless you're doing huge amounts of add/remove on large amounts of data.

hinkley 6y ago

In most GCs the mark phase also disrupts the cache by doing what looks a lot like a table scan. That’s one of the reasons for generational collectors. Better cache locality.

gameswithgo 6y ago

I've seen a Linked List get allocated very contiguously at times in .NET when it is just a toy program, like just benchmarking linkedlist performance, it sometimes does really well. But in the context of a big running program with other things in the heap it is much less likely to work out so well.

pradn 6y ago

Modern memory allocators like tcmalloc are pretty good with putting structs of the same size in contiguous areas of the heap. For smaller structs (which most real world cases fall under), it's just one lookup to find the next place to put the new object. So, C and Java will have similar performance for allocating a lot of small objects, I think. There's probably a difference on the deallocation side, especially with fragmentation, but I'm not as knowledgeable about that. If someone has a richer explanation, I'd love to hear.

scott_s 6y ago
As someone who worked on memory allocators in a past life: cosign. Size-class based allocation for small objects is how modern memory allocators have worked for a long time now. I'm genuinely baffled by how many people think that the bump-pointer allocation for same-sized objects is unique to garbage collection.
- pradn 6y ago
  Thanks for confirming this. Do you have an idea of how modern allocators compare with generational GCs on the cleanup / realloc / fragmentation side?
  - scott_s 6y ago
    No, and that would make a great empirical study. (Maybe there has been one! I should check ISMM over the past decade, someone may have done it already.) From first principles, the biggest difference is that manual memory allocation can't move live objects around. But manual memory managers do still have the ability to be smart on deallocation, to the point that calling free will sometimes cause things to happen that would be similar in a garbage collector.

kazinator 6y ago

Even if you have a bump allocator, the fact is that a linked list requires storage for the pointers, which are not needed in an array. That makes the list bigger, and bigger means worse from a caching point of view. Fewer parts of a linked list fit into a cache line and so on. Plus the pointer traversals are dependent loads. Until we load node->next, we don't know what address that is, so we cannot pre-fetch node->next->anything. But when we access array[i], it's possible to pre-fetch array[i+1]. I'm still using linked lists because of the flexibility, functional substructure sharing and allocations you can avoid, but let's not kid ourselves.

galangalalgol 6y ago
And if your data is truly contiguous and its struct of arrays instead of the other way around, SIMD becomes much more usable.
simiones 6y ago
Absolutely, I'm not claiming linked lists are "better" than arrays. The GP was mentioning memory fragmentation and cache behavior, and I was pointing out that GCs can, at least in some conditions, make linked lists more efficient then they are in C (comparing naive implementations). But yes, linked lists are almost always worse than arrays, unless you're doing huge amounts of add/remove on large amounts of data.