6 ms·

An in-depth look at OCaml’s new “best-fit” garbage collector strategy

176 points by testcross 7y ago

StreamBright 7y ago
"Remember that whatever works best for you, it’s still better than having to malloc and free by hand. Happy allocating!" Nice, they are saying exactly the same as those pesky game developers. https://www.youtube.com/watch?v=tK50z_gUpZI https://www.youtube.com/watch?v=tK50z_gUpZI
- k__ 7y ago
  What's their opinion on Rust?
  - StreamBright 7y ago
    Great question. I am really hoping that the non-GC world is taking off with Rust.
    - joppy 7y ago
      How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. The user can open and close windows in random orders, and so on. Perhaps some windows generate a lot of associated data which should be disposed of when that window closes, but can also be dragged over into the other windows and duplicated around, so the data is not “owned” by a single window. It seems to me that this is where the GC “set and forget” model really shines, since otherwise you just have to do all that work manually using an allocation and a free, or a constructor and a destructor, or some similar pattern. Perhaps Rust has some clever answer for this?
      - nitnelave 7y ago
        It seems like you want a reference-counted pointer: you get shared ownership, and the object is deleted when the last reference to the pointer is deleted. Similar to C++'s std::shared_ptr
        joppy 7y ago
        Right, but then you take on a bunch of baggage you don’t have in a GC setting. For instance if you want to make zillions of these objects and delete them you are paying overhead for lots of allocations and deallocations made heavier by the reference counting. You pay time overhead for atomic increment/decrement, and if there are cyclic structures then you pay a big price in the code complexity to deal with them properly and not cause memory leaks.
      - steveklabnik 7y ago
        > How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? The issue is not really the scope, the issue is how many owners the data needs to have. A variable that needs to live longer than a scope, but only has a single owner, can be directly returned from that scope. Once you have the need for multiple owners, the most straightforward answer is "reference count them," but it depends on your exact requirements. > A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. GTK heavily uses reference counting. People are also investigating what a "rust-native" UI toolkit would look like; taking strong influences from ECSes. It's an open question if those architectures end up better than refcounts.
  - Jhsto 7y ago
    I would imagine excited. Rust's affine type system is an application of logic theory. OCaml is initially French academic production and (from an anecdotal experience) those academics tend to dis how impure most software (and memory management) is. While Rust does not have the purest theoretical foundations, it's still fresh air and will likely result in people paying more attention to the work of researchers in theoretics.
  - gopiandcode 7y ago
    Before self-hosting, the rust compiler was originally in OCaml so presumably there's an overlap in communities there.
    - k__ 7y ago
      I mean, game developers, not OCaml devs The point was, they said "do manaual memory management" if you want speed.
- pjmlp 7y ago
  Yeah, like Tim Sweeney. "It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." https://twitter.com/timsweeneyepic/status/880607734588211200 https://twitter.com/timsweeneyepic/status/880607734588211200 https://wiki.unrealengine.com/Garbage_Collection_Overview https://wiki.unrealengine.com/Garbage_Collection_Overview Which was it again, the engine chosen by Nintendo, Microsoft and Google as first party to their 3D APIs? https://developer.nintendo.com/tools https://developer.nintendo.com/tools https://docs.microsoft.com/en-us/windows/mixed-reality/unity-development-overview https://docs.microsoft.com/en-us/windows/mixed-reality/unity... https://stadia.dev/blog/unity-production-ready-support-for-stadia-now-available/ https://stadia.dev/blog/unity-production-ready-support-for-s... https://developer.android.com/games/develop/build-in-unity https://developer.android.com/games/develop/build-in-unity The anti-GC crowd on the games industry, is no different than the ones that fought adoption of C/Modula-2/Pascal over Assembly, and then fought adoption of C++ and Objective-C over C. Eventually they will suck it up when the major platform owners tell them it is time to move on.
  - marcinzm 7y ago
    >"It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." Why is that surprising? Games are basically about humans predicting things and random spikes prevent that from happening in time sensitive games. Beyond game play implications, I suspect there's also something about jerkiness in movement that bugs human senses.
    - sgrove 7y ago
      It's not entirely surprising, but one might imagine a different approach: always allocate a 1% buffer for an unexpected GC. It's not a very satisfactory answer (and there are likely much better tradeoffs to be made), but given the 10x and 1% comparison (not entirely apples to apples though) the comment sounds a bit more interesting.
      - loopback_device 7y ago
twic 7y ago
I'm not aware of any other industrial-strength GC using this strategy. Are there any? If not, is there something about OCaml that makes this strategy more suitable than it is for other languages? If not, is this a case of this being the best strategy they have the resources to implement, rather than the best possible strategy?
- the8472 7y ago
  I think the hotspot's CMS old gen allocator used best-fit strategy since its collector didn't compact. But CMS has been deprecated because newer, compacting low pause collectors have taken over its use-cases while being less fragile.
  - hinkley 7y ago
    If memory serves, the new one uses an extra object header that points from the old object to the new one during move operations, and any reads of the old object get forwarded to the new one. I'm pretty sure that would have not performed well without the aggressive prediction logic in modern processors. Java 1's object accesses always read through an indirect pointer, but that went away in the name of performance, either when Hotspot was introduced, or on the next round of GC impromevents.
    - _old_dude_ 7y ago
      They are two new GCs Shenandoah and ZGC. Indirect pointers or Brooks pointers has it is called were used in Shenandoah v1 to allow an application thread that perform a read to not move the object during the evacuation phase. This strategy has been removed in Shenandoah v2 to have a better throughput so now both read and write by the application move the object during the evacuation phase. ZGC has never used Brooks pointers.
      - MaxBarraclough 7y ago
        I had to look up 'Brooks pointers'. For anyone else in this position, these two blog posts seem a good place to start: https://rkennke.wordpress.com/2013/10/23/shenandoah-gc-brooks-pointers/ https://rkennke.wordpress.com/2013/10/23/shenandoah-gc-brook... , https://blog.plan99.net/modern-garbage-collection-part-2-1c88847abcfd https://blog.plan99.net/modern-garbage-collection-part-2-1c8...
jjoonathan 7y ago
Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency hell because someone thought it would be a good idea to use a full-blown SAT solver for package management. Grr.
- ignoramous 7y ago
  > ...someone thought it would be a good idea to use a full-blown SAT solver for package management Relevant: https://research.swtch.com/version-sat https://research.swtch.com/version-sat
  - jjoonathan 7y ago
    Right. SAT solvers are an excellent theoretical fit and a terrible practical fit, at least at the current state of tooling. Their runtime _does_ explode and the tooling _is not_ any good at hinting as to why even when the explanation turns out to be very simple. "lol install takes an hour now" makes for a very poor error message, and debugging a black box that takes an hour to evaluate each input is just.... ugggggghh, and I can only thank my lucky stars that it did finish after an hour rather than taking an indefinite amount of time. In contrast, the "danger" of heuristics is that they fail to dig up an exceedingly clever combination of archaic package versions that technically fit the user's specified requirements. It's such a small problem that it might even be considered a feature, since said exceedingly clever combinations are likely to be the result of poor version definitions and unlikely to be what the user actually wants. Of course, if the only people who can be persuaded to write package managers are people doing research in the subject, then I suppose letting them inflict their pet projects on us is one way to compensate them for an otherwise thankless task, and perhaps in that sense it's fair.
    - cwzwarich 7y ago
      Do you have an example of a real-world package dependency situation that generates a truly difficult SAT instance?
- 7y ago
adultSwim 7y ago
Shout out to Damien Doligez, a phenomenal engineer
jeffdavis 7y ago
This reminds me somewhat of the main postgresql allocator. It keeps segregated freelists for smaller allocations, and then larger allocations are handled by malloc.
hyustan 7y ago
Surprised not see any talk about slab allocations. Typical malloc implementations today use slabs: A variety of allocation-classes is defined; for example, 1B, 2B, 4B, 8B, ... Each allocation-class is essentially its own independent heap. Slabs are really good: Allocation is fast: a few cycles to determine the slab, then pick the first available cell, done. Compaction is easy: all cells have the same size! And I repeat, all cells within an allocation-class have the same size! This means things like pin cards, etc... Compared to the pointer-chasing inherent to a splay-tree... I do wonder.
fjfaase 7y ago
What about the following strategy: Find the first space that is large enough. If it is smaller than double the size of the required, take it. (A little more space is allocated than would be strictly needed.) If it larger than double the size, split it. This leaves a piece that is at least as big as the current size. Assuming that the allocations have some distribution, it is likely that another piece of memory with this size will be allocated in the future. In this way, the distribution of available spaces will remain about the same as the wanted spaces. (Of course, one should also first round up the size to some power of two and possibly implement a minimum size.)
- judofyr 7y ago
  Sounds similar to a buddy allocator: https://en.wikipedia.org/wiki/Buddy_memory_allocation https://en.wikipedia.org/wiki/Buddy_memory_allocation

176 points by testcross 7y ago

"Remember that whatever works best for you, it’s still better than having to malloc and free by hand. Happy allocating!" Nice, they are saying exactly the same as those pesky game developers. https://www.youtube.com/watch?v=tK50z_gUpZI https://www.youtube.com/watch?v=tK50z_gUpZI

k__ 7y ago
What's their opinion on Rust?
- StreamBright 7y ago
  Great question. I am really hoping that the non-GC world is taking off with Rust.
  - joppy 7y ago
    How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. The user can open and close windows in random orders, and so on. Perhaps some windows generate a lot of associated data which should be disposed of when that window closes, but can also be dragged over into the other windows and duplicated around, so the data is not “owned” by a single window. It seems to me that this is where the GC “set and forget” model really shines, since otherwise you just have to do all that work manually using an allocation and a free, or a constructor and a destructor, or some similar pattern. Perhaps Rust has some clever answer for this?
    - nitnelave 7y ago
      It seems like you want a reference-counted pointer: you get shared ownership, and the object is deleted when the last reference to the pointer is deleted. Similar to C++'s std::shared_ptr
      - joppy 7y ago
        Right, but then you take on a bunch of baggage you don’t have in a GC setting. For instance if you want to make zillions of these objects and delete them you are paying overhead for lots of allocations and deallocations made heavier by the reference counting. You pay time overhead for atomic increment/decrement, and if there are cyclic structures then you pay a big price in the code complexity to deal with them properly and not cause memory leaks.
    - steveklabnik 7y ago
      > How does Rust deal with long-lived objects that cannot be block-scoped (or request-scoped, in the context of a server for example)? The issue is not really the scope, the issue is how many owners the data needs to have. A variable that needs to live longer than a scope, but only has a single owner, can be directly returned from that scope. Once you have the need for multiple owners, the most straightforward answer is "reference count them," but it depends on your exact requirements. > A typical example here would be a UI framework, where memory has to be managed for the window and its widgets, and then the entire application is suspended until the next event. GTK heavily uses reference counting. People are also investigating what a "rust-native" UI toolkit would look like; taking strong influences from ECSes. It's an open question if those architectures end up better than refcounts.
- Jhsto 7y ago
  I would imagine excited. Rust's affine type system is an application of logic theory. OCaml is initially French academic production and (from an anecdotal experience) those academics tend to dis how impure most software (and memory management) is. While Rust does not have the purest theoretical foundations, it's still fresh air and will likely result in people paying more attention to the work of researchers in theoretics.
- gopiandcode 7y ago
  Before self-hosting, the rust compiler was originally in OCaml so presumably there's an overlap in communities there.
  - k__ 7y ago
    I mean, game developers, not OCaml devs The point was, they said "do manaual memory management" if you want speed.
pjmlp 7y ago
Yeah, like Tim Sweeney. "It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." https://twitter.com/timsweeneyepic/status/880607734588211200 https://twitter.com/timsweeneyepic/status/880607734588211200 https://wiki.unrealengine.com/Garbage_Collection_Overview https://wiki.unrealengine.com/Garbage_Collection_Overview Which was it again, the engine chosen by Nintendo, Microsoft and Google as first party to their 3D APIs? https://developer.nintendo.com/tools https://developer.nintendo.com/tools https://docs.microsoft.com/en-us/windows/mixed-reality/unity-development-overview https://docs.microsoft.com/en-us/windows/mixed-reality/unity... https://stadia.dev/blog/unity-production-ready-support-for-stadia-now-available/ https://stadia.dev/blog/unity-production-ready-support-for-s... https://developer.android.com/games/develop/build-in-unity https://developer.android.com/games/develop/build-in-unity The anti-GC crowd on the games industry, is no different than the ones that fought adoption of C/Modula-2/Pascal over Assembly, and then fought adoption of C++ and Objective-C over C. Eventually they will suck it up when the major platform owners tell them it is time to move on.
- marcinzm 7y ago
  >"It's interesting that many games can afford a constant 10x interpretation overhead for scripts, but not a spikey 1% for garbage collection." Why is that surprising? Games are basically about humans predicting things and random spikes prevent that from happening in time sensitive games. Beyond game play implications, I suspect there's also something about jerkiness in movement that bugs human senses.
  - sgrove 7y ago
    It's not entirely surprising, but one might imagine a different approach: always allocate a 1% buffer for an unexpected GC. It's not a very satisfactory answer (and there are likely much better tradeoffs to be made), but given the 10x and 1% comparison (not entirely apples to apples though) the comment sounds a bit more interesting.
    - loopback_device 7y ago

twic 7y ago

I'm not aware of any other industrial-strength GC using this strategy. Are there any? If not, is there something about OCaml that makes this strategy more suitable than it is for other languages? If not, is this a case of this being the best strategy they have the resources to implement, rather than the best possible strategy?

the8472 7y ago
I think the hotspot's CMS old gen allocator used best-fit strategy since its collector didn't compact. But CMS has been deprecated because newer, compacting low pause collectors have taken over its use-cases while being less fragile.
- hinkley 7y ago
  If memory serves, the new one uses an extra object header that points from the old object to the new one during move operations, and any reads of the old object get forwarded to the new one. I'm pretty sure that would have not performed well without the aggressive prediction logic in modern processors. Java 1's object accesses always read through an indirect pointer, but that went away in the name of performance, either when Hotspot was introduced, or on the next round of GC impromevents.
  - _old_dude_ 7y ago
    They are two new GCs Shenandoah and ZGC. Indirect pointers or Brooks pointers has it is called were used in Shenandoah v1 to allow an application thread that perform a read to not move the object during the evacuation phase. This strategy has been removed in Shenandoah v2 to have a better throughput so now both read and write by the application move the object during the evacuation phase. ZGC has never used Brooks pointers.
    - MaxBarraclough 7y ago
      I had to look up 'Brooks pointers'. For anyone else in this position, these two blog posts seem a good place to start: https://rkennke.wordpress.com/2013/10/23/shenandoah-gc-brooks-pointers/ https://rkennke.wordpress.com/2013/10/23/shenandoah-gc-brook... , https://blog.plan99.net/modern-garbage-collection-part-2-1c88847abcfd https://blog.plan99.net/modern-garbage-collection-part-2-1c8...

jjoonathan 7y ago

Hell is other peoples' algorithmic choices. My GC-fu isn't high level enough to comment on this one, but I just spent the last two days suffering in dependency hell because someone thought it would be a good idea to use a full-blown SAT solver for package management. Grr.

ignoramous 7y ago
> ...someone thought it would be a good idea to use a full-blown SAT solver for package management Relevant: https://research.swtch.com/version-sat https://research.swtch.com/version-sat
- jjoonathan 7y ago
  Right. SAT solvers are an excellent theoretical fit and a terrible practical fit, at least at the current state of tooling. Their runtime _does_ explode and the tooling _is not_ any good at hinting as to why even when the explanation turns out to be very simple. "lol install takes an hour now" makes for a very poor error message, and debugging a black box that takes an hour to evaluate each input is just.... ugggggghh, and I can only thank my lucky stars that it did finish after an hour rather than taking an indefinite amount of time. In contrast, the "danger" of heuristics is that they fail to dig up an exceedingly clever combination of archaic package versions that technically fit the user's specified requirements. It's such a small problem that it might even be considered a feature, since said exceedingly clever combinations are likely to be the result of poor version definitions and unlikely to be what the user actually wants. Of course, if the only people who can be persuaded to write package managers are people doing research in the subject, then I suppose letting them inflict their pet projects on us is one way to compensate them for an otherwise thankless task, and perhaps in that sense it's fair.
  - cwzwarich 7y ago
    Do you have an example of a real-world package dependency situation that generates a truly difficult SAT instance?
7y ago

adultSwim 7y ago

Shout out to Damien Doligez, a phenomenal engineer

jeffdavis 7y ago

This reminds me somewhat of the main postgresql allocator. It keeps segregated freelists for smaller allocations, and then larger allocations are handled by malloc.

hyustan 7y ago

Surprised not see any talk about slab allocations. Typical malloc implementations today use slabs: A variety of allocation-classes is defined; for example, 1B, 2B, 4B, 8B, ... Each allocation-class is essentially its own independent heap. Slabs are really good: Allocation is fast: a few cycles to determine the slab, then pick the first available cell, done. Compaction is easy: all cells have the same size! And I repeat, all cells within an allocation-class have the same size! This means things like pin cards, etc... Compared to the pointer-chasing inherent to a splay-tree... I do wonder.

fjfaase 7y ago

What about the following strategy: Find the first space that is large enough. If it is smaller than double the size of the required, take it. (A little more space is allocated than would be strictly needed.) If it larger than double the size, split it. This leaves a piece that is at least as big as the current size. Assuming that the allocations have some distribution, it is likely that another piece of memory with this size will be allocated in the future. In this way, the distribution of available spaces will remain about the same as the wanted spaces. (Of course, one should also first round up the size to some power of two and possibly implement a minimum size.)

judofyr 7y ago
Sounds similar to a buddy allocator: https://en.wikipedia.org/wiki/Buddy_memory_allocation https://en.wikipedia.org/wiki/Buddy_memory_allocation