15 ms·

Garbage Collectors Are Scary

107 points by Tomte 3y ago

le-mark 3y ago
Nice to see someone exploring from first principals and implementing interesting things. And referencing past work! Gives me hope actually. One nit; I disagree with “scary”, I think “interesting” and even “fun”!
- amelius 3y ago
  Writing a good concurrent garbage collector is harder than writing a compiler.
  - naasking 3y ago
    I suppose it depends on precisely what you mean by "good". There are some very decent concurrent collectors that are very simple. The Chicken collector is fairly straightforward and real-time to boot, and seems to have only slightly lower throughput than concurrent MS: https://www.researchgate.net/publication/220752316_A_study_of_concurrent_real-time_garbage_collectors https://www.researchgate.net/publication/220752316_A_study_o...
  - hgs3 3y ago
    Depends how you define "good". I consider this concurrent GC algorithm [1] to be "good" and it can be implemented in a few hundred lines of C. I'm going to disagree with the article and say GC's aren't "scary" but they do require thorough testing. [1] https://dl.acm.org/doi/10.1145/1255450.1255453 https://dl.acm.org/doi/10.1145/1255450.1255453
mike_hearn 3y ago
They are indeed scary, but one thing that can make them less so is writing them in a high level language. A nice code base to study if you're new to GCs is the GenScavange module of SubstrateVM, a JVM written entirely in Java. Start here: https://github.com/oracle/graal/blob/master/substratevm/src/com.oracle.svm.core.genscavenge/src/com/oracle/svm/core/genscavenge/GCImpl.java https://github.com/oracle/graal/blob/master/substratevm/src/... It gets compiled to native code for use. It's actually a bit of a dialect of Java because of course, you need low level memory and stack access. So you can see at parts there is use of special APIs that get compiled to things like stack allocations, so it can avoid allocating on the heap whilst working with it. Even so the "business logic" of a GC can be easily seen here, especially if you don't know C++.
- mark38848 3y ago
  There is no programming language as scary as Java
  - agilob 3y ago
    Please elaborate more than "haha java bad"
    - otikik 3y ago
      JavaBadAbstractFactoryObjectFactoryException
      - Geezus_42 3y ago
        This is what I hate about supporting Java apps. Why are the errors so indecipherable and rarely well documented?
        mike_hearn 3y ago
        Well, compared to what? The alternative to exceptions is usually worse: 1. Error codes. Try debugging Win32 software and have fun working out with all those HRESULTs mean, especially as every Google hit for any given code is just endless support forums with people complaining their computer is broken. 2. Panics. You get an error message no more helpful than an exception, except with no stack trace to help you figure out what's wrong. 3. Segfaults. You get nothing. Exceptions are the best form of error handling yet invented. Making programmers more helpful is hard, but exceptions have auto-generated error messages that at least tell you where the program died, how it got there, and very often the chain of problems that led to that surface level problem (a particular weakness of error codes where causal chains are often lost). They also often have JavaDocs explaining what they mean. Although it's not really a weakness of Java or exceptions per se, I think some people don't like them because lazy devs don't bother translating them into something more user friendly (especially for developer tools). There are simple patterns that fix that though. My company makes a CLI developer tool written in Java+Kotlin running on the JVM (see bio) and it defines a dedicated UserError exception type. If an exception bubbles to the top level of the program and it descends from UserError then it's formatted nicely with colors and shown as you'd expect. If it's not then the exception is logged and a crash reporter is started, the user is asked if they'd like to report the crash. The exception details are then printed without the stack trace and polished slightly ("FooBarException: abc" -> "Foo Bar: abc") which often makes the messages good enough that the user can unstick themselves. There are utility methods to catch and rethrow exceptions as user errors when the underlying messages are already good enough, and the product is careful to rethrow manually if the messages need to be improved. There are also utilities to verify that a file/directory exists and if not, throw a special subtype of UserError that yields a spelling corrector [1] The result is that if you check our homepage, you'll see at least one customer explicitly praised our error message quality! They were very happy to never see a stack trace from a developer tool, only actionable errors that tell you what to do. So exceptions can definitely yield a great UX. You just have to care and put in a bit of effort. IntelliJ is another example of a product where the exception UX is highly polished. Its exception reporter can figure out which plugin an error comes from, route error reports automatically, deduplicate errors based on the stack traces, attach files that the exception object advertises and so on. [1] https://hshell.hydraulic.dev/14.1/user-interaction/#path-assertions https://hshell.hydraulic.dev/14.1/user-interaction/#path-ass...
jbosh 3y ago
So scary. I was working on a garbage collection bug for a AAA video game one time for months. It'd crash once a day on a tester machine and we'd add more and more prints to try and narrow it down. Finally got enough information and realized that the padding of a specific object was wrong (GC expected 16 bytes, object was 12 bytes). This caused dozens of other corruption bugs to disappear that we didn't even think were GC related.
- stingraycharles 3y ago
  How is that possible? Which language was this in?
  - taspeotis 3y ago
    AAA game is likely C++
  - npalli 3y ago
    GC and AAA probably C#.
    - mike_hearn 3y ago
      If C# they'd have been using the MS authored GC. It was probably a custom GC for C++ heaps. Quite a few games do this, it's a smart productivity hack. Unreal uses a simple form of mark/sweep GC for its C++ game state heap. https://unrealcommunity.wiki/garbage-collection-36d1da https://unrealcommunity.wiki/garbage-collection-36d1da It works fine because most RAM in games is consumed by assets that don't need to be scanned.
      - 60654 3y ago
        Interesting fact: Unity doesn't use a Microsoft GC, or the Microsoft implementation of CLR. They had integrated the competing Mono implementation early on, and it came with its own "stop the world" Boehm GC. They've been trying to move to Microsoft runtime for years but it's slow going.
    - 3y ago
saberience 3y ago
For some reason I read this as "garbage disposals are scary" and then I got a flashback to reading a Stephen King novel as a child (iirc it was Firestarter) where a character commits suicide by sticking their arm into their kitchen garbage disposal, it horrified me at the time and appears to have remained deeply embedded in my personal neural network...
- cwillu 3y ago
  Thank you for giving the rest of us an opportunity to have that concept deeply embedded as well…
  - saberience 3y ago
    Hopefully I didn't trigger too many folks... judging by the "votes" on my post, I may have done. Ah well, you can't please everybody!
    - samatman 3y ago
      I believe the kiddos refer to this as "trauma dumping". The topic was programming. You switched it to horrific mutilation. Don't do that.
      - saberience 3y ago
        Oh come on, kids are watching movies like Goodfellas and Casino. Me mentioning someone losing an air is hardly going to give anyone sleepless nights.
deleted 3y ago
[deleted]
habibur 3y ago
Get ready to through out your GC as soon as it works and build a better one or different one. And then again, and then again. It's more like art.
- vsnf 3y ago
  This is how I write my compilers. Indeed, it's how I write all my software.
mpweiher 3y ago
One of the reasons I prefer reference counting. While it does a little less, the complexity tradeoff just makes more sense to me.
- rwmj 3y ago
  Having dealt with many, many reference counting bugs in Python extensions, I disagree.
  - xandrius 3y ago
    Just don't write the bugs, easy! /s
- naasking 3y ago
  It's not less complex because it doesn't handle cycles, and naive ref counting performs much worse than naive tracing.
_f5ah 3y ago
A couple months ago I finished translating a simple generational garbage collector from MIPS[1] to x86-64 assembly[2], so that programms emitted by my toy compiler[3] run on the actual hardware instead of a MIPS emulator. And sure enough, I had introduced a few bugs along the way. Here is a part of just one commit message: > NoLeak-InsertionSort.cool exposed a problem where we make a copy of a prototype object to pass it as `this` to the constructor. But while evaluating all the other constructor parameters the copy gets promoted to Old Area. As a result any assignments the constructor makes end up recorded in the assignment stack. So that the referenced objects survive the next minor collection whereas they shouldn't have otherwise. [1]: https://theory.stanford.edu/~aiken/software/cooldist/lib/trap.handler https://theory.stanford.edu/~aiken/software/cooldist/lib/tra... [2]: https://github.com/mykolav/coollang-2020-fs/blob/master/src/Runtime/rt_gen_gc.s https://github.com/mykolav/coollang-2020-fs/blob/master/src/... [3]: https://github.com/mykolav/coollang-2020-fs https://github.com/mykolav/coollang-2020-fs
phyzome 3y ago
Interestingly, I've never heard of a correctness bug in a GC, let alone one causing a real-world problem.
- sph 3y ago
  There's at least one in this very thread.
  - phyzome 3y ago
    I mean sure, a post on the topic of correctness bugs in GCs is going to bring out some examples of correctness bugs in GCs. But I haven't encountered any independently.
neonsunset 3y ago
For anyone interested in GC internals for a language that mixes low-level and high-level primitives*, I can strongly recommend watching Konrad Kokosa lectures on .NET's GC internals. They are very accessible and only assume you have light C++ background. https://www.youtube.com/watch?v=8i1Nv7wGsjk&list=PLpUkQYy-K8Y-wYcDgDXKhfs6OT8fFQtVm https://www.youtube.com/watch?v=8i1Nv7wGsjk&list=PLpUkQYy-K8... (can be listened at 1.5 speed) *i.e. all the "unboxed" primitives discussed in the original post.
- szszrk 3y ago
  He also wrote a pretty huge book with A LOT of .net memory goodness that has nice reviews. Great lad to work with as well, open minded to various angles and whole stack from browser experience to deployment.
sph 3y ago
People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. Now, suppose I were designing a language where data is always owned by at most one thread. I can skip making the ref counter an atomic variable, and with some help of the language do reference counting at compile time: would I still benefit from the complexity of a tracing GC if my goal is performance and predictable latency? I want to have automatic memory management for both kernel and apps. Creating a concurrent tracing GC that walks the entire user and kernel space sounds incredibly more complicated than just inc/dec'ing a counter and freeing if it reaches zero (again, assuming only one thread can access a single object) I know that I would have to add language support for weak pointers or forbid cyclic references altogether, but I wonder if the dislike for reference counting only exists because it doesn't work well for data that's shared across threads. EDIT: thanks all, you have brought excellent arguments and you have convinced me. In fact, in this actor-based OS I am working on, GC+arena based allocation per actor might be the most performing approach. GC collection can happen in the scheduler between messages (so becomes virtually pauseless), and when an actor terminates, just reclaim the entire arena.
- neonsunset 3y ago
  Lack of multi-threading simplifies a lot, but is at odds with performance.
  - wongarsu 3y ago
    You can still have multithreading, you just have to forbid shared data. You can move data between threads at thread creation and termination, and for everything else the language can provide channels/queues to move data between threads. Erlang operates under that model and is great at multithreading
    - hu3 3y ago
      "just have to forbid shared data" That's a too severe constraint to be qualified as "just".
    - 3y ago
holbrad 3y ago
I honestly thought the title was about bin men for a second...
egnehots 3y ago
I think that an easy-to-implement and reasonably performant garbage collector (GC) would combine two approaches: - Let the compiler automatically free variables that go out of scope (using static analysis to insert free calls). - Use reference counting when the scope is too hard to determine (fall back on a dynamic check).
- nick_ 3y ago
  I'd like to add using tracing when the references might cause a cycle (statically analyzed?).
- p_l 3y ago
  Static analysis isn't easy, though.
matheusmoreira 3y ago
"Scary" is actually something of an understatement. They weren't kidding when they said it was one of the most shark infested areas of programming. My lisp's garbage collector works by scanning the stack for pointers. I neglected to spill the registers onto the stack and it led to such nonsensical problems that I'm not even sure how I debugged it. I think my mind has blocked out the experience as a bad memory. I've gotten into the habit of hacking in a call into the garbage collector directly into the eval and cons of debug builds just to stress the garbage collector as much as possible and try to find corruptions near their sources.
- kazinator 3y ago
  Not spilling registers into the stack will show up quickly. You have to instigate a GC torture test as part of your testing, combined with a way of detecting use-after-free. (An obvious way is to reset the type of freed objects, so any use of such an object runs into type mismatches.) A GC torture tests causes the collection routine to be called often, like after every allocation. If an object is allocated, and now held only in an unspilled register, and then another object is allocated; that first object will be wrongly freed. This is what we want: reproduce the problem, and then hopefully detect it. If you're garbage collecting underneath a compiler that doesn't know about garbage collection, you have to worry about not only values held in registers not being spilled, but values that are optimized away entirely, which your garbage collector has to see. For instance: obj foo_create(obj param) { struct foo_object *foo = malloc(sizeof *fo); foo->bar_attribute = param; return create_heap_object(foo_type, foo); } The problem is that param has no next use after it is assigned to bar_attribute; as far as the optimizer is concerned, it is now a dead variable. Whatever register it occupied can be reused for something else. Let's assume our garbage collector is conservative only w.r.t. stack scanning. Heap objects are traced precisely. We are not scanning every malloc object in existence, in other words, and so, the bar_attribute is not visible to the garbage collector. Once we call create_heap_object(foo_type, foo), the foo_object structure becomes hooked up to a garbage-collected heap object, and then it is visible to the garbage collector. The foo_type has garbage collector hooks for traversing the "struct foo_object". Problem is, create_heap_object calls into the garbage collection module to allocate a new heap object, and that can trigger GC. When GC runs, it can wrongly collect the param object. This can happen if the function has a caller which itself has let go of the param object, like: obj caller(obj cparam) { obj tparam = transform_somehow(cparam); obj foo = foo_create(tparam); return foo; } Again, tparam has no next use, and so it can cease to exist in this stack frame the moment that foo_create is called. I.e. the only reference to tparam in the entire program is the activation frame of foo_create. Scanning the stack of caller will not find it.
davexunit 3y ago
Garbage collectors can be scary, but I wouldn't want to live without them! I have observed what feels like an irrational fear of GC in different programming communities. Those communities tend to invent something else that they don't call GC but is either complicated in its own way or not nearly as robust as a proper GC. I am personally very excited about a new state-of-the-art GC with no dependencies that is easy to embed called Whippet. The project has received grant funding through NLnet to finish implementation: https://nlnet.nl/project/Whippet/ https://nlnet.nl/project/Whippet/

107 points by Tomte 3y ago

Nice to see someone exploring from first principals and implementing interesting things. And referencing past work! Gives me hope actually. One nit; I disagree with “scary”, I think “interesting” and even “fun”!

amelius 3y ago
Writing a good concurrent garbage collector is harder than writing a compiler.
- naasking 3y ago
  I suppose it depends on precisely what you mean by "good". There are some very decent concurrent collectors that are very simple. The Chicken collector is fairly straightforward and real-time to boot, and seems to have only slightly lower throughput than concurrent MS: https://www.researchgate.net/publication/220752316_A_study_of_concurrent_real-time_garbage_collectors https://www.researchgate.net/publication/220752316_A_study_o...
- hgs3 3y ago
  Depends how you define "good". I consider this concurrent GC algorithm [1] to be "good" and it can be implemented in a few hundred lines of C. I'm going to disagree with the article and say GC's aren't "scary" but they do require thorough testing. [1] https://dl.acm.org/doi/10.1145/1255450.1255453 https://dl.acm.org/doi/10.1145/1255450.1255453

mike_hearn 3y ago

They are indeed scary, but one thing that can make them less so is writing them in a high level language. A nice code base to study if you're new to GCs is the GenScavange module of SubstrateVM, a JVM written entirely in Java. Start here: https://github.com/oracle/graal/blob/master/substratevm/src/com.oracle.svm.core.genscavenge/src/com/oracle/svm/core/genscavenge/GCImpl.java https://github.com/oracle/graal/blob/master/substratevm/src/... It gets compiled to native code for use. It's actually a bit of a dialect of Java because of course, you need low level memory and stack access. So you can see at parts there is use of special APIs that get compiled to things like stack allocations, so it can avoid allocating on the heap whilst working with it. Even so the "business logic" of a GC can be easily seen here, especially if you don't know C++.

mark38848 3y ago
There is no programming language as scary as Java
- agilob 3y ago
  Please elaborate more than "haha java bad"
  - otikik 3y ago
    JavaBadAbstractFactoryObjectFactoryException
    - Geezus_42 3y ago
      This is what I hate about supporting Java apps. Why are the errors so indecipherable and rarely well documented?
      - mike_hearn 3y ago
        Well, compared to what? The alternative to exceptions is usually worse: 1. Error codes. Try debugging Win32 software and have fun working out with all those HRESULTs mean, especially as every Google hit for any given code is just endless support forums with people complaining their computer is broken. 2. Panics. You get an error message no more helpful than an exception, except with no stack trace to help you figure out what's wrong. 3. Segfaults. You get nothing. Exceptions are the best form of error handling yet invented. Making programmers more helpful is hard, but exceptions have auto-generated error messages that at least tell you where the program died, how it got there, and very often the chain of problems that led to that surface level problem (a particular weakness of error codes where causal chains are often lost). They also often have JavaDocs explaining what they mean. Although it's not really a weakness of Java or exceptions per se, I think some people don't like them because lazy devs don't bother translating them into something more user friendly (especially for developer tools). There are simple patterns that fix that though. My company makes a CLI developer tool written in Java+Kotlin running on the JVM (see bio) and it defines a dedicated UserError exception type. If an exception bubbles to the top level of the program and it descends from UserError then it's formatted nicely with colors and shown as you'd expect. If it's not then the exception is logged and a crash reporter is started, the user is asked if they'd like to report the crash. The exception details are then printed without the stack trace and polished slightly ("FooBarException: abc" -> "Foo Bar: abc") which often makes the messages good enough that the user can unstick themselves. There are utility methods to catch and rethrow exceptions as user errors when the underlying messages are already good enough, and the product is careful to rethrow manually if the messages need to be improved. There are also utilities to verify that a file/directory exists and if not, throw a special subtype of UserError that yields a spelling corrector [1] The result is that if you check our homepage, you'll see at least one customer explicitly praised our error message quality! They were very happy to never see a stack trace from a developer tool, only actionable errors that tell you what to do. So exceptions can definitely yield a great UX. You just have to care and put in a bit of effort. IntelliJ is another example of a product where the exception UX is highly polished. Its exception reporter can figure out which plugin an error comes from, route error reports automatically, deduplicate errors based on the stack traces, attach files that the exception object advertises and so on. [1] https://hshell.hydraulic.dev/14.1/user-interaction/#path-assertions https://hshell.hydraulic.dev/14.1/user-interaction/#path-ass...

jbosh 3y ago

So scary. I was working on a garbage collection bug for a AAA video game one time for months. It'd crash once a day on a tester machine and we'd add more and more prints to try and narrow it down. Finally got enough information and realized that the padding of a specific object was wrong (GC expected 16 bytes, object was 12 bytes). This caused dozens of other corruption bugs to disappear that we didn't even think were GC related.

stingraycharles 3y ago
How is that possible? Which language was this in?
- taspeotis 3y ago
  AAA game is likely C++
- npalli 3y ago
  GC and AAA probably C#.
  - mike_hearn 3y ago
    If C# they'd have been using the MS authored GC. It was probably a custom GC for C++ heaps. Quite a few games do this, it's a smart productivity hack. Unreal uses a simple form of mark/sweep GC for its C++ game state heap. https://unrealcommunity.wiki/garbage-collection-36d1da https://unrealcommunity.wiki/garbage-collection-36d1da It works fine because most RAM in games is consumed by assets that don't need to be scanned.
    - 60654 3y ago
      Interesting fact: Unity doesn't use a Microsoft GC, or the Microsoft implementation of CLR. They had integrated the competing Mono implementation early on, and it came with its own "stop the world" Boehm GC. They've been trying to move to Microsoft runtime for years but it's slow going.
  - 3y ago

saberience 3y ago

For some reason I read this as "garbage disposals are scary" and then I got a flashback to reading a Stephen King novel as a child (iirc it was Firestarter) where a character commits suicide by sticking their arm into their kitchen garbage disposal, it horrified me at the time and appears to have remained deeply embedded in my personal neural network...

cwillu 3y ago
Thank you for giving the rest of us an opportunity to have that concept deeply embedded as well…
- saberience 3y ago
  Hopefully I didn't trigger too many folks... judging by the "votes" on my post, I may have done. Ah well, you can't please everybody!
  - samatman 3y ago
    I believe the kiddos refer to this as "trauma dumping". The topic was programming. You switched it to horrific mutilation. Don't do that.
    - saberience 3y ago
      Oh come on, kids are watching movies like Goodfellas and Casino. Me mentioning someone losing an air is hardly going to give anyone sleepless nights.

deleted 3y ago

[deleted]

habibur 3y ago

Get ready to through out your GC as soon as it works and build a better one or different one. And then again, and then again. It's more like art.

vsnf 3y ago
This is how I write my compilers. Indeed, it's how I write all my software.

mpweiher 3y ago

One of the reasons I prefer reference counting. While it does a little less, the complexity tradeoff just makes more sense to me.

rwmj 3y ago
Having dealt with many, many reference counting bugs in Python extensions, I disagree.
- xandrius 3y ago
  Just don't write the bugs, easy! /s
naasking 3y ago
It's not less complex because it doesn't handle cycles, and naive ref counting performs much worse than naive tracing.

_f5ah 3y ago

A couple months ago I finished translating a simple generational garbage collector from MIPS[1] to x86-64 assembly[2], so that programms emitted by my toy compiler[3] run on the actual hardware instead of a MIPS emulator. And sure enough, I had introduced a few bugs along the way. Here is a part of just one commit message: > NoLeak-InsertionSort.cool exposed a problem where we make a copy of a prototype object to pass it as `this` to the constructor. But while evaluating all the other constructor parameters the copy gets promoted to Old Area. As a result any assignments the constructor makes end up recorded in the assignment stack. So that the referenced objects survive the next minor collection whereas they shouldn't have otherwise. [1]: https://theory.stanford.edu/~aiken/software/cooldist/lib/trap.handler https://theory.stanford.edu/~aiken/software/cooldist/lib/tra... [2]: https://github.com/mykolav/coollang-2020-fs/blob/master/src/Runtime/rt_gen_gc.s https://github.com/mykolav/coollang-2020-fs/blob/master/src/... [3]: https://github.com/mykolav/coollang-2020-fs https://github.com/mykolav/coollang-2020-fs

phyzome 3y ago

Interestingly, I've never heard of a correctness bug in a GC, let alone one causing a real-world problem.

sph 3y ago
There's at least one in this very thread.
- phyzome 3y ago
  I mean sure, a post on the topic of correctness bugs in GCs is going to bring out some examples of correctness bugs in GCs. But I haven't encountered any independently.

neonsunset 3y ago

For anyone interested in GC internals for a language that mixes low-level and high-level primitives*, I can strongly recommend watching Konrad Kokosa lectures on .NET's GC internals. They are very accessible and only assume you have light C++ background. https://www.youtube.com/watch?v=8i1Nv7wGsjk&list=PLpUkQYy-K8Y-wYcDgDXKhfs6OT8fFQtVm https://www.youtube.com/watch?v=8i1Nv7wGsjk&list=PLpUkQYy-K8... (can be listened at 1.5 speed) *i.e. all the "unboxed" primitives discussed in the original post.

szszrk 3y ago
He also wrote a pretty huge book with A LOT of .net memory goodness that has nice reviews. Great lad to work with as well, open minded to various angles and whole stack from browser experience to deployment.

sph 3y ago

People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler. Now, suppose I were designing a language where data is always owned by at most one thread. I can skip making the ref counter an atomic variable, and with some help of the language do reference counting at compile time: would I still benefit from the complexity of a tracing GC if my goal is performance and predictable latency? I want to have automatic memory management for both kernel and apps. Creating a concurrent tracing GC that walks the entire user and kernel space sounds incredibly more complicated than just inc/dec'ing a counter and freeing if it reaches zero (again, assuming only one thread can access a single object) I know that I would have to add language support for weak pointers or forbid cyclic references altogether, but I wonder if the dislike for reference counting only exists because it doesn't work well for data that's shared across threads. EDIT: thanks all, you have brought excellent arguments and you have convinced me. In fact, in this actor-based OS I am working on, GC+arena based allocation per actor might be the most performing approach. GC collection can happen in the scheduler between messages (so becomes virtually pauseless), and when an actor terminates, just reclaim the entire arena.

neonsunset 3y ago
Lack of multi-threading simplifies a lot, but is at odds with performance.
- wongarsu 3y ago
  You can still have multithreading, you just have to forbid shared data. You can move data between threads at thread creation and termination, and for everything else the language can provide channels/queues to move data between threads. Erlang operates under that model and is great at multithreading
  - hu3 3y ago
    "just have to forbid shared data" That's a too severe constraint to be qualified as "just".
  - 3y ago

holbrad 3y ago

I honestly thought the title was about bin men for a second...

egnehots 3y ago

I think that an easy-to-implement and reasonably performant garbage collector (GC) would combine two approaches: - Let the compiler automatically free variables that go out of scope (using static analysis to insert free calls). - Use reference counting when the scope is too hard to determine (fall back on a dynamic check).

nick_ 3y ago
I'd like to add using tracing when the references might cause a cycle (statically analyzed?).
p_l 3y ago
Static analysis isn't easy, though.

matheusmoreira 3y ago

"Scary" is actually something of an understatement. They weren't kidding when they said it was one of the most shark infested areas of programming. My lisp's garbage collector works by scanning the stack for pointers. I neglected to spill the registers onto the stack and it led to such nonsensical problems that I'm not even sure how I debugged it. I think my mind has blocked out the experience as a bad memory. I've gotten into the habit of hacking in a call into the garbage collector directly into the eval and cons of debug builds just to stress the garbage collector as much as possible and try to find corruptions near their sources.

kazinator 3y ago
Not spilling registers into the stack will show up quickly. You have to instigate a GC torture test as part of your testing, combined with a way of detecting use-after-free. (An obvious way is to reset the type of freed objects, so any use of such an object runs into type mismatches.) A GC torture tests causes the collection routine to be called often, like after every allocation. If an object is allocated, and now held only in an unspilled register, and then another object is allocated; that first object will be wrongly freed. This is what we want: reproduce the problem, and then hopefully detect it. If you're garbage collecting underneath a compiler that doesn't know about garbage collection, you have to worry about not only values held in registers not being spilled, but values that are optimized away entirely, which your garbage collector has to see. For instance: obj foo_create(obj param) { struct foo_object *foo = malloc(sizeof *fo); foo->bar_attribute = param; return create_heap_object(foo_type, foo); } The problem is that param has no next use after it is assigned to bar_attribute; as far as the optimizer is concerned, it is now a dead variable. Whatever register it occupied can be reused for something else. Let's assume our garbage collector is conservative only w.r.t. stack scanning. Heap objects are traced precisely. We are not scanning every malloc object in existence, in other words, and so, the bar_attribute is not visible to the garbage collector. Once we call create_heap_object(foo_type, foo), the foo_object structure becomes hooked up to a garbage-collected heap object, and then it is visible to the garbage collector. The foo_type has garbage collector hooks for traversing the "struct foo_object". Problem is, create_heap_object calls into the garbage collection module to allocate a new heap object, and that can trigger GC. When GC runs, it can wrongly collect the param object. This can happen if the function has a caller which itself has let go of the param object, like: obj caller(obj cparam) { obj tparam = transform_somehow(cparam); obj foo = foo_create(tparam); return foo; } Again, tparam has no next use, and so it can cease to exist in this stack frame the moment that foo_create is called. I.e. the only reference to tparam in the entire program is the activation frame of foo_create. Scanning the stack of caller will not find it.

davexunit 3y ago

Garbage collectors can be scary, but I wouldn't want to live without them! I have observed what feels like an irrational fear of GC in different programming communities. Those communities tend to invent something else that they don't call GC but is either complicated in its own way or not nearly as robust as a proper GC. I am personally very excited about a new state-of-the-art GC with no dependencies that is easy to embed called Whippet. The project has received grant funding through NLnet to finish implementation: https://nlnet.nl/project/Whippet/ https://nlnet.nl/project/Whippet/