4 ms·

> GCs typically pay the price at the tail end (deallocation, compaction) but have absurdly fast allocators (a handful of instructions) I don't know how GCs wor

> GCs typically pay the price at the tail end (deallocation, compaction) but have absurdly fast allocators (a handful of instructions) I don't know how GCs work. Don't they still need to find free memory somehow during allocation? I always thought of GCs as manual memory allocators + automatic deallocations

cogman10 3y ago
For allocations, GCs are basically bump allocators. Asking for more memory is just a factor of advancing a pointer based on how much memory is needed. The only thing they have in addition to the bumping is a check to make sure the bump won't push them past what's available. That's the condition that will usually trigger a partial GC (A minor collection). There are some GCs that are much more complicated than that. However, typically, especially for new small allocations, it's just a bump allocator. For larger allocations or when talking about being a generational collector that's when things get more complicated. For JVM's GCs, most of the collectors are "compacting" which means that after a collection the region collected is left with all the live data unfragmented. That means allocating to a given region is simply a process of keeping track of the pointer for that region and bumping it when something needs to go there. The JVM did have the now defunct (thank goodness) CMS collectors which would still compact the minor collection regions, but for the old heap regions it'd maintain a skip list. It would only compact the old gen region when after a major collection it still failed an allocation. In that case it'd take the swiss cheese old gen and squish it together.
- sapiogram 3y ago
  This is only true for generational and/or compacting garbage collectors, right? So not Go, for instance?
  - cogman10 3y ago
    It's true for moving collectors. Go does not have a moving collector so I'm guessing it is doing something like an arena allocation (perhaps just relying on jemalloc and calling free at the right times?). In which case go's allocation speed will be around C's speed. They could be doing something different but I didn't stumble across that googling.

cogman10 3y ago

For allocations, GCs are basically bump allocators. Asking for more memory is just a factor of advancing a pointer based on how much memory is needed. The only thing they have in addition to the bumping is a check to make sure the bump won't push them past what's available. That's the condition that will usually trigger a partial GC (A minor collection). There are some GCs that are much more complicated than that. However, typically, especially for new small allocations, it's just a bump allocator. For larger allocations or when talking about being a generational collector that's when things get more complicated. For JVM's GCs, most of the collectors are "compacting" which means that after a collection the region collected is left with all the live data unfragmented. That means allocating to a given region is simply a process of keeping track of the pointer for that region and bumping it when something needs to go there. The JVM did have the now defunct (thank goodness) CMS collectors which would still compact the minor collection regions, but for the old heap regions it'd maintain a skip list. It would only compact the old gen region when after a major collection it still failed an allocation. In that case it'd take the swiss cheese old gen and squish it together.

sapiogram 3y ago
This is only true for generational and/or compacting garbage collectors, right? So not Go, for instance?
- cogman10 3y ago
  It's true for moving collectors. Go does not have a moving collector so I'm guessing it is doing something like an arena allocation (perhaps just relying on jemalloc and calling free at the right times?). In which case go's allocation speed will be around C's speed. They could be doing something different but I didn't stumble across that googling.