11 ms·

The number of arguments I've gotten into with other engineers that "manual memory allocation is deterministic, GCs are not!" is too high. First off, GCs are qu

The number of arguments I've gotten into with other engineers that "manual memory allocation is deterministic, GCs are not!" is too high. First off, GCs are quite deterministic, unless they are calling rand() someplace. I've walked through GC code under controlled conditions with identical repeated allocations, GCs do the exact same thing under the exact same circumstances every time. Second off, you have to pay the price of allocation and deal with memory fragmentation somewhere. GCs typically pay the price at the tail end (deallocation, compaction) but have absurdly fast allocators (a handful of instructions), where as manual memory allocators pay the price for allocation (finding a slab of memory) up front, and unless you know how to work around the details of your allocator, you end up dealing with fragmentation yourself. FWIW this also means many, many, types of applications can gain a boost from intelligent memory allocation strategies. There is the famous example of the cruise missile that never worried about deallocation because it would explode before it ran out of memory, but scenarios involving bespoke memory management being better than "just use libc!" are actually quite common. Have a stateless microservice? If you know the max size of memory it'll use, for each connection that comes in just allocate a slab of memory and when the connection closes free the entire slab, far more efficient than using a GC or any standard allocator. Also having to calculate the max amount of memory a single connection can use is a great way to figure out how much load an instance can handle (depending if you are CPU bound or not). For certain stages of compilation, compilers can get away with not freeing memory and just exiting and letting the OS reclaim everything. (Of course less doable now days with compilers running as background services recompiling code as it is typed, and also whole program optimization has made it so compilers use a lot more memory, so I don't know if this strategy is still in use in these modern times!) The tl;dr is that freeing memory is complicated no matter if you have a GC or not. It is something every developer should be thinking about from time to time.

Karellen 3y ago
I thought that GCs are often run in their own thread, and because scheduling at the OS layer is seen as non-deterministic from the application's viewpoint (you never know when your own threads are going to get stopped/started), you can't control exactly when the GC is run? Is that wrong? Or obsolete? Or GC-dependent? But also, just because something is theoretically deterministic (e.g. it might technically be possible to work out when a GC sweep will run, and multiple runs of the exact same program will cause the exact same set of GC sweeps), actually working out when a GC sweep will run is so non-trivial the only way to actually work it out is to run the program and watch it happen, and also it becomes impossible to predict how any changes at all to a program will affect how the GC runs as a result (other than making the change and running it). Or are there ways to deduce when GC sweeps will run for a given program, without actually running it?
- cogman10 3y ago
  > Is that wrong? Or obsolete? Or GC-dependent? GC-dependent. Though most GCs are threaded so there is always a level of indeterminism there. That being said, the same can be said of any application. Unless you are doing actual real time programming you always have at least a little indeterminism for how your app will behave based on the rest of what's going on in the OS. > you can't control exactly when the GC is run? Depends. A number of SDKs will expose a "trigger the GC" API, though that's generally seen as an anti-pattern. But speaking of GCs, there's roughly 2 big categories of GCs. The first is a full stop the world while the GC is running, the second has the GC running concurrently with the application. For a full stop the world GC, that is fairly predictable when it comes to how it will behave. GC is pretty much always triggered on an allocation failure. For full stop the world GCs, that will involve tracing through the live memory roots and somehow marking what's still used and discarding what isn't (State of the art, AFAIK, is a moving collector where live data is moved to a new memory region. This has an advantage of always compacting the data can (but isn't always) be pretty cache friendly as related data is very often colocated. For the second type, generally what's happening is some signal is sent that indicates it's time to collect memory. The world stops for that signal to propagate but after that happens the app is allowed to continue to run while the garbage collector runs on a parallel thread. The whole app is only completely stopped to wait on when you run into a "you are still collecting and I want to allocate, but there's no space" so of scenario. In these second types of applications it's common for there to be an added GC logic hoisted into the application when memory is accessed because "obviously this is still live so do the GC work as part of the regular app work". This sort of collector would be the hardest to reason determinism about as what happens when you access a memory location will be determined by where the collector currently is and what the application is doing. The first type of collector can be seen in the JVMs parallel and serial collectors. The second type can be seen in the JVM's G1GC (partially), ZGC, Shenendoah. It's also fairly closely related to how Go's GC works and how (AFAIK) javascript's GC works. There is 1 other semi common category of GC, that's reference counting. There you have a VERY high level of determinism as there's no side threads and collection happens purely based on application actions and not any sort of opaque memory investigation. However, RC has it's own set of issues that tracing collectors do not.
- devbent 3y ago
asalahli 3y ago
> 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.

Karellen 3y ago

I thought that GCs are often run in their own thread, and because scheduling at the OS layer is seen as non-deterministic from the application's viewpoint (you never know when your own threads are going to get stopped/started), you can't control exactly when the GC is run? Is that wrong? Or obsolete? Or GC-dependent? But also, just because something is theoretically deterministic (e.g. it might technically be possible to work out when a GC sweep will run, and multiple runs of the exact same program will cause the exact same set of GC sweeps), actually working out when a GC sweep will run is so non-trivial the only way to actually work it out is to run the program and watch it happen, and also it becomes impossible to predict how any changes at all to a program will affect how the GC runs as a result (other than making the change and running it). Or are there ways to deduce when GC sweeps will run for a given program, without actually running it?

cogman10 3y ago
> Is that wrong? Or obsolete? Or GC-dependent? GC-dependent. Though most GCs are threaded so there is always a level of indeterminism there. That being said, the same can be said of any application. Unless you are doing actual real time programming you always have at least a little indeterminism for how your app will behave based on the rest of what's going on in the OS. > you can't control exactly when the GC is run? Depends. A number of SDKs will expose a "trigger the GC" API, though that's generally seen as an anti-pattern. But speaking of GCs, there's roughly 2 big categories of GCs. The first is a full stop the world while the GC is running, the second has the GC running concurrently with the application. For a full stop the world GC, that is fairly predictable when it comes to how it will behave. GC is pretty much always triggered on an allocation failure. For full stop the world GCs, that will involve tracing through the live memory roots and somehow marking what's still used and discarding what isn't (State of the art, AFAIK, is a moving collector where live data is moved to a new memory region. This has an advantage of always compacting the data can (but isn't always) be pretty cache friendly as related data is very often colocated. For the second type, generally what's happening is some signal is sent that indicates it's time to collect memory. The world stops for that signal to propagate but after that happens the app is allowed to continue to run while the garbage collector runs on a parallel thread. The whole app is only completely stopped to wait on when you run into a "you are still collecting and I want to allocate, but there's no space" so of scenario. In these second types of applications it's common for there to be an added GC logic hoisted into the application when memory is accessed because "obviously this is still live so do the GC work as part of the regular app work". This sort of collector would be the hardest to reason determinism about as what happens when you access a memory location will be determined by where the collector currently is and what the application is doing. The first type of collector can be seen in the JVMs parallel and serial collectors. The second type can be seen in the JVM's G1GC (partially), ZGC, Shenendoah. It's also fairly closely related to how Go's GC works and how (AFAIK) javascript's GC works. There is 1 other semi common category of GC, that's reference counting. There you have a VERY high level of determinism as there's no side threads and collection happens purely based on application actions and not any sort of opaque memory investigation. However, RC has it's own set of issues that tracing collectors do not.
devbent 3y ago

asalahli 3y ago

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