Garbage Collectors Are Scary

https://www.enyo.de/fw/notes/garbage-collectors-are-scary.html

by Tomte • 2 years ago

107 167 2 years ago

le-mark• 2 years 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• 2 years ago

Writing a good concurrent garbage collector is harder than writing a compiler.

naasking5• 2 years 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_o...

hgs3• 2 years 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

mike_hearn7• 2 years 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/...

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• 2 years ago

There is no programming language as scary as Java

stingraycharles4• 2 years ago

Eh, it’s not the most sexy language, because across all dimensions, there are more scary languages.

C++ is much more scary than Java in a “shoot yourself in the foot” kind of way.

INTERCAL is much more scary than Java in a “this is impossible to understand code” kind of way.

Haskell is much more scary than Java in a “this language has FP constructs” kind of way.

So why is Java scary?

ajross• 2 years ago

I don't love it either. But let's be brutally honest here: the single inflection point where the world of software shifted from "usually buggy, routine crashes" to "usually works, presumptively secure" was the arrival and gradual embrace of Java and its managed runtime in the late 90's and early 2000's.

Were there other technologies that do the same thing? Sure. Were they better? In some cases. Was Java really the "first" by whatever metric? No.

But Java is where the world changed, it just is.

agilob2• 2 years ago

Please elaborate more than "haha java bad"

swayvil• 2 years ago

I have written a lot of java.

I like it because it's comprehensively organized. I mean it does everything it should and does it a nice orderly way. The whole class system and c-like system, all together, works good. And addresses everything I want it to address.

And it does that without adding a bunch of crap. Or at least I find that crap easy to ignore. But ya, they do seem to be adding a lot of crap.

In a nutshell, it's a nice neat system. Python is a mess, comparatively.

I'm looking for a new language tho. Orderly and comprehensive like Java, but succincter.

apantel• 2 years ago

Java is an extremely simple, non-scary language. It’s almost impossible to shoot yourself in the foot.

The things that people build using “idiomatic Java” are scary.

bitwize• 2 years ago

A trivia nugget often recounted here on HN is that .NET's GC was originally written in Lisp, then translated to C++.

lloydatkinson• 2 years ago

And is such a long file GitHub can’t even display it. I get collocation but is one file that’s so large it has editor problems as a result, really such a good thing?

jbosh4• 2 years 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.

stingraycharles4• 2 years ago

How is that possible? Which language was this in?

taspeotis• 2 years ago

AAA game is likely C++

npalli• 2 years ago

GC and AAA probably C#.

rwmj3• 2 years ago

I don't know, but we had a similar bug in OCaml, although in reverse.

Linux/x86-64 expects the stack to always be 16 byte aligned (although the ABI documentation at the time didn't make this assumption very clear). OCaml called into C with a non-aligned stack. GCC-generated code, assuming the stack was 16 byte aligned, used some strange Intel AVX instruction that only works on aligned data, unlike every other Intel instruction ever that can work on any alignment (albeit maybe more slowly).

This manifested itself as rare and totally unreproducible crashes (because stack alignment differed between runs). It was a bit of a nightmare to solve.

jbosh4• 2 years ago

C++, it was an in house engine to make everything fit in memory on PS3. Removing fragmentation gave ~10% of usable memory back.

packetlost• 2 years ago

Probably a custom one built for an in-house engine in C++ if it's a AAA studio. Alternatively one of the various off-the-shell ones you can #include, though my money is on the former. Note: I am not GP, I'm making educated guesses about what may have happened :)

saberience3• 2 years 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• 2 years ago

Thank you for giving the rest of us an opportunity to have that concept deeply embedded as well…

saberience3• 2 years 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!

habibur• 2 years 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• 2 years ago

This is how I write my compilers. Indeed, it's how I write all my software.

mpweiher• 2 years ago

One of the reasons I prefer reference counting.

While it does a little less, the complexity tradeoff just makes more sense to me.

rwmj3• 2 years ago

Having dealt with many, many reference counting bugs in Python extensions, I disagree.

xandrius• 2 years ago

Just don't write the bugs, easy! /s

naasking5• 2 years ago

It's not less complex because it doesn't handle cycles, and naive ref counting performs much worse than naive tracing.

_f5ah• 2 years 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/tra...

[2] https://github.com/mykolav/coollang-2020-fs/blob/master/src/...

[3] https://github.com/mykolav/coollang-2020-fs

phyzome2• 2 years ago

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

sph4• 2 years ago

There's at least one in this very thread.

phyzome2• 2 years 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.

neonsunset7• 2 years 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-K8... (can be listened at 1.5 speed)

*i.e. all the "unboxed" primitives discussed in the original post.

szszrk• 2 years 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.

sph4• 2 years 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.

neonsunset7• 2 years ago

Lack of multi-threading simplifies a lot, but is at odds with performance.

wongarsu• 2 years 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

eru3• 2 years ago

People recommend tracing garbage collection because it performs better than atomic reference counting, even though reference counting is much simpler.

Reference counting is a lot more complicated! It turns every read into a write.

[...] if my goal is performance and predictable latency?

Reference counters don't have predictable latency: a single reference decrement can lead to an arbitrary amount of follow up work, like more decrements and deallocations.

Performance of reference counting isn't generally better than that of garbage collectors. (Especially since you still need a backup solution to deal with cycles.)

Figuring out a lot of your memory management at compile time is definitely a win. But doesn't really have much to do with reference counting.

sph4• 2 years ago

Reference counting is a lot more complicated! It turns every read into a write.

Why? Maybe it's crucial to the story, but I am exploring Rust-like single ownership semantics.

You would have to "write" only when you create a new reference to something, or the reference is destroyed. But it wouldn't turn any read into a write, no?

jstimpfle• 2 years ago

Reference counters don't have predictable latency: a single reference decrement can lead to an arbitrary amount of follow up work, like more decrements and deallocations.

You can push the cleanup work on a queue to do it asynchronously, to bound the amount of work per deref / to even the work out.

cesarb3• 2 years ago

It turns every read into a write.

Not exactly; it turns every passing of a reference, even when it's going to be used only for reading (or not used at all, or just passed on further) into a write of the reference count. But if you can read without passing the reference to somewhere else (or if the compiler can prove that the reference the caller has outlives the reference it would have passed), it can omit the write.

And tracing garbage collection is not completely immune to this; some kinds also turn every read into a write (into a card marking table), copying gc periodically rewrites unmodified objects (when moving them during garbage collection), and the tracing itself might need to read cold objects which might even be located on disk (swapped out).

Reference counters don't have predictable latency: a single reference decrement can lead to an arbitrary amount of follow up work, like more decrements and deallocations.

However, they have a predictable place for that latency: it can only happen when there's a reference decrement (and the amount of extra work at that point is bounded by the size of the graph which can be reached from that reference). It also will not affect other unrelated threads. With a stop-the-world GC, a thread which allocates too much can cause pauses in threads which are not even allocating or releasing memory at that moment.

Performance of reference counting isn't generally better than that of garbage collectors. (Especially since you still need a backup solution to deal with cycles.)

However, the memory use of reference counting is generally better than that of tracing garbage collectors, since it releases memory as soon as it can be released. That is, tracing garbage collectors trade extra memory use for their speed; giving them more memory (up to a point) means they can do less work, and giving them too little extra memory can make them much slower.

Figuring out a lot of your memory management at compile time is definitely a win. But doesn't really have much to do with reference counting.

It does, because it can help reduce the cost of reference counting (by eliding most of the reference count manipulation when it's not necessary).

mike_hearn7• 2 years ago

Yes you do still benefit, otherwise V8 would use refcounting for everything.

Problems with refcounting:

1. You leak cycles. Given the point of a memory management scheme is to reliably not leak, this is a major weakness. Cycles are very common and natural things to find in heaps, and even if you avoid them they can easily be introduced years later by people you will never meet who weren't aware of the entire heap topology. You say you'd just "forbid cyclic references": how will you do that? Require everything to be written in Rust?

2. Every object gets bigger, as it must store a reference. This increases memory usage and reduces locality. With a GC it's possible to squeeze the overhead down to a vtable pointer (required anyway in most cases) and then a few bits on top!

3. All the incs/decs bloat your code, creating a form of pervasive slowness that doesn't show up in profilers except in hot loops. This tempts you to micro-optimize add/decrefs, but that increases the chance of mistakes.

4. Requires a very consistent protocol for how and when references are taken and released. The details here can get complicated. For example do containers add/decref for you, or do they expect you to do that?

5. You are exposed to use-after-free bugs, which are a major source of security holes.

There are probably more. And obviously the restriction to not use threads is catastrophic for any system that cares about performance.

The problem with having the ability to hold managed pointers from kernel<->userspace (whether using rc or gc) is that a process might be malicious or arbitrarily buggy, in the standard OS model. It means you have to be able to kill the process and release all its resources, which means the kernel must know where all the references to kernel-side objects are coming from so they can be removed on kill.

To allow object graphs to span the user/kernel space boundary therefore requires the kernel to mandate the use of a specific compiler that's a part of the TCB (i.e. a part of the kernel itself). That radically changes the design of the whole OS. In particular you cannot implement a UNIX that way.

WalterBright• 2 years ago

The decrement also needs to be in a "finally" exception handler.

There's also a problem when taking a reference to the contents of an object - that reference can survive the release of the object.

pornel• 2 years ago

Rust has this. Data can be placed in atomic or non-atomic refcounted containers, and the type system disallows sharing non-thread-safe types across threads.

Additionally, data can be borrowed from inside the refcounted wrapper, and used freely within a scope without touching the reference count.

p_l2• 2 years ago

As sibling comment mentioned, reference counting is very much non-predictable in latency.

If you want predictable, you want your GC to run either in constant time slice, or an upper-bounded timeslice.

Deferred refcounts can become quite complex if you want to avoid "I have just released last reference to something that contained a lot of other referenced" (there are some funny threads where Rust users discover that they sometimes need to spin an extra thread to not have effective "stop the world" XD).

So instead common approach is tracing GC with some form timesliced running collector, guaranteeing that time taken from mutator will be upper-bounded. For example, instead of stopping the world, concurrent GC will usually only require a synchronization point. Sometimes it also means that the collector will be given explicit timeslice to ensure that there's certain amount of work being done - it's all tradeoffs based on how much throughput and latency you want.

You can speed up tracing collectors through things like escape analysis and 1bit reference counting (for example, you set a bit if a new reference is passed outside of current scope, every object without bit set can be assumed to have all referenced contained in given scope, etc).

naasking5• 2 years ago

The dislike started earlier than the rise of pervasive threading. As another poster said, every read turns into a write, meaning, everytime you pass a reference into a function you have to increment the counter, and decrement when the function exits. It turns out, the vast majority of of inc/dec ops are pointless ones like this, which is considerable overhead for literally no benefit.

You can elide some of them using a sort of borrow analysis. But borrowed refs can only be used in certain ways, and so this analysis isn't perfect and can't eliminate all of the unnecessary overhead. This was all hashed out in the 80s and 90s IIRC, before multithreading even became a big issue.

The complex analyses needed to make RC perform well end up destroying the simplicity argument, and even after they still aren't competitive with tracing.

holbrad• 2 years ago

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

egnehots• 2 years 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_• 2 years ago

I'd like to add using tracing when the references might cause a cycle (statically analyzed?).

p_l2• 2 years ago

Static analysis isn't easy, though.

matheusmoreira2• 2 years 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• 2 years 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.

matheusmoreira2• 2 years ago

I assumed that param would still be reachable because foo_object is reachable. If this is not the case, is it because struct foo_object differs from the obj type? Perhaps that causes the garbage collector to fail to find the pointers.

Will the code be correct if I ensure that every value on the stack can be recognized by the garbage collector?

If not, then I suppose the way to avoid those issues is to tell the compiler the variable is used somehow. There's the volatile keyword and also lots of compiler attributes I can use. I'm finding it pretty difficult to determine which variables need to be marked this way though.

What is the proper discipline? How did you solve the problem?

I compile with strict aliasing disabled because of problems like these... Maybe I need to disable more optimizations.

davexunit• 2 years 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/

Garbage Collectors Are Scary

Related Stories