Live data from Hacker News

Conservative GC: Is It Really That Bad?

excelsiorjet.com

21–30 of 48 posts

Re: Conservative GC: Is It Really That Bad?

#21
post #4

The problematic code in the article is, AFAICT, using an object finalizer to free manually allocated memory; such approaches seldom work well, even with precise GCs. Thread stacks are effectively manually allocated blocks of memory. You create a thread, which allocates the stack, and as long as the thread lives, the stack is kept alive - it's self-sustaining. The thread must die by explicit programmatic action, which…

Your argument against finalizers completely ignores that FFI is a thing. Finalizers can be managing things that are memory, just not memory that the GC allocated because it is coming from a foreign system.

You also have to use them as a safe-guard against programmers that are not used to manually managing scope failing to manually manage scope. In some cases it's also just not a practical expectation, as the language is structured entirely around the idea that you aren't supposed to be manually managing scope. An open file that weaves its way throughout an application as it's a constant read/write backing for something? That can often be non-trivial to figure out when to call close() on it exactly, and by the time you've written such a system you've just re-invented manual reference counting (error prone) or a garbage collector of some sort anyway, and should have just used a finalizer.

Calling finalizers an anti-pattern only works to the extent that you can ban everything not controlled by GC'd world. Which would be great, except that you can't even do "hello world" with that constraint.

Re: Conservative GC: Is It Really That Bad?

#22
post #20
post #18

Interestingly enough, SBCL on x86/x64 has a conservative, but moving, GC. It can know some, but not all roots precisely, so it pins any objects that are reachable through conservative roots. It's earlier implementations were on RISC chips that had 24 or more GPRs so the implementation was simple: 2 stacks and divide the local registers in half for boxed and unboxed values. This obviously didn't work when porting to x…

> divide the local registers in half for boxed and unboxed values Fondly remembers the separate address and data registers on 68000. Why didn't they go back to this approach for x86_64 (16 registers), now that no one really cares about 32 bit x86?

The conservative GC approach has worked well enough in practice that nobody is going to do the work. Also there is a performance tradeoff in non-allocating code: Sometimes you need more unboxed registers, other times you need more boxed registers so with only ~6 of each[1] you will run into register pressure.

1: 2 stacks means 2 stack pointers and 2 frame pointers leaving only 12 registers left for values; it's also possible that the SBCL ABI uses a global register for something else as well, which would leave only 11. PowerPC is a really luxurious platform in which you have 32 GPRs so even if you use 8 GPRs for various bookkeeping purposes that leaves 24 remaining, which is enough for pretty much everyone.

Re: Conservative GC: Is It Really That Bad?

#23
post #7
post #4

The problematic code in the article is, AFAICT, using an object finalizer to free manually allocated memory; such approaches seldom work well, even with precise GCs. Thread stacks are effectively manually allocated blocks of memory. You create a thread, which allocates the stack, and as long as the thread lives, the stack is kept alive - it's self-sustaining. The thread must die by explicit programmatic action, which…

Absolutely agree with you about finalizers! However, please note that this "threadReaper" code is from JDK class, so, the problem can appear on every application that just use Timer class. Of course, there are many other examples of false-roots, but this concrete class caused unexpected OOMs on several applications of our clients, so we made this small sample and used it for sanity checking during implementing precis…

I take it you are part of the ones behind the article? Did you ever see the papers about a conservative variant of immix, which would be both compacting and conservative?

Re: Conservative GC: Is It Really That Bad?

#24
The Chakra Javascript engine uses a conservative generational mark and sweep collector with many phases running in parallel to code execution. It looks like Chakra is now on github (and with an MIT license). In chakra the GC is called it a 'Recycler', which can throw one for a loop when searching for the GC implementation.

Re: Conservative GC: Is It Really That Bad?

#25
post #4

The problematic code in the article is, AFAICT, using an object finalizer to free manually allocated memory; such approaches seldom work well, even with precise GCs. Thread stacks are effectively manually allocated blocks of memory. You create a thread, which allocates the stack, and as long as the thread lives, the stack is kept alive - it's self-sustaining. The thread must die by explicit programmatic action, which…

Your argument against finalizers completely ignores that FFI is a thing. Finalizers can be managing things that are memory, just not memory that the GC allocated because it is coming from a foreign system. You also have to use them as a safe-guard against programmers that are not used to manually managing scope failing to manually manage scope. In some cases it's also just not a practical expectation, as the language…

> Your argument against finalizers completely ignores that FFI is a thing

Nope. Memory that is indirectly allocated via FFI is not normally[0] accounted for by GC memory pressure and so it should be managed explicitly, not using finalizers. That memory is invisible to the GC. It won't know to collect it. It won't know when the foreign heap has allocated too much, and it won't know to run a more expensive GC collection to try harder when foreign space gets tight.

(If you have a relatively infinite amount of RAM, or your FFI object sizes are a constant factor of the size of their GC world counterparts and you account for this in your GC max heap size, you may get away with it. But these constraints aren't typical.)

> That can often be non-trivial to figure out when to call close() on it exactly, and by the time you've written such a system you've just re-invented manual reference counting (error prone) or a garbage collector of some sort anyway, and should have just used a finalizer.

You're right that it can be hard to figure these things out. But figure them out you must, for any long-lived program using scarce resources, or you're just creating a problem for the future.

Working these things out is not actually rocket science. It's what we did in the days before GC, and it was actually tedious more than difficult, because the best way to do it meant dogmatically following certain idioms when programming, being rigorous in your error handling and consciously aware of ownership semantics as data flowed around the program.

We even developed a bunch of strategies to make it simpler, e.g. arena allocation and stack marker allocation. You can adapt these approaches for deterministic resource disposal in GC environments too (e.g. keep a list of things to dispose, or markers on a stack of things to dispose).

The biggest wins from GC are from two effects: memory safety and expression-oriented programming. Memory safety means you never get dangling pointers or dynamic type errors from reused memory, a major increase in reliability, as well as making certain types of lock-free programming much easier. Expression-oriented programming means you can safely and easily write functions that take complex values and return complex values without thinking too hard about the ownership of these complex values. This in turn lets you program in a functional style that is much harder without GC.

What GC doesn't give you is a world free of non-functional requirements. You still need to know about memory allocation of your big algorithms and program overall; you need to know where big object graphs get rooted for longer periods of time before dying (the middle age problem[1]), and you need to track the ownership of your resources rigorously, or you will run into resource exhaustion and non-deterministic failure modes - some of the worst kinds of failures.

[0] https://docs.microsoft.com/en-us/dotnet/api/system.gc.addmem...

[1] https://blogs.msdn.microsoft.com/ricom/2003/12/04/mid-life-c...

Re: Conservative GC: Is It Really That Bad?

#26

This is something that I just love about Go. Get rid of the GC stalling like you have with Java.

The primary difference is that Go creates less garbage than Java. Of course this results in significantly shorter GC pauses but they still exist.

Re: Conservative GC: Is It Really That Bad?

#27

I am not an expert in garbage collection techniques, but this article does not even mention locality of reference (copying GCs improve locality on each compaction) and how many cache misses are introduced by increased fragmentation. Are there any benchmarks on this?

I'm no expert either, but some of the literature I've read says that copying GCs aren't a panacea when it comes to improving locality. For some object graphs, they help, for others they actually reorder the objects in ways that make locality worse.

Consider, for example, a copying GC that copies using a depth-first traversal of the object graph and then running it over a tree that your program always processes in breadth-first order.

Re: Conservative GC: Is It Really That Bad?

#28

This is just off the top of my head, but it made me wonder: are there any VMs that put a stack map header of some sort as a literal in the stack? E.g. for each frame the compiler orders roots first and then other primitives. Then, as you enter the frame, write the number of roots to the stack. When the GC walks the stack it can see precisely which are roots.

The paper "Accurate Garbage Collection in an Uncooperative Environment" goes over a very roughly similar technique for compiling a GC language to C in a way that lets you easily find the roots because managed objects are stuffed in structs on the C stack in a certain way.

It's a really really neat paper that I've been itching to implement for a while.

Re: Conservative GC: Is It Really That Bad?

#29
post #18

Interestingly enough, SBCL on x86/x64 has a conservative, but moving, GC. It can know some, but not all roots precisely, so it pins any objects that are reachable through conservative roots. It's earlier implementations were on RISC chips that had 24 or more GPRs so the implementation was simple: 2 stacks and divide the local registers in half for boxed and unboxed values. This obviously didn't work when porting to x…

FWIW Clozure CL has a precise gc on x86/x64. The register usage is detailed here: https://ccl.clozure.com/docs/ccl.html#register-and-stack-usa...

Re: Conservative GC: Is It Really That Bad?

#30

I am not an expert in garbage collection techniques, but this article does not even mention locality of reference (copying GCs improve locality on each compaction) and how many cache misses are introduced by increased fragmentation. Are there any benchmarks on this?

On SBCL the bigger win for using a copying collector isn't the locality of reference (which helps with some loads, but hurts with others), but rather the fact that you can make an allocation be about two instructions in the non-GC case (pointer increment plus a bounds check).

I hadn't spent a lot of time thinking about how much faster this is than malloc/free until a question came up the other day here on HN to the extent of "why would anyone dynamically allocate an object that is smaller than a cache line?" In lisp a commonly allocated structure is a CONS cell which is two pointers in size, and is often smaller than the cache line. It would be very wasteful to do a malloc/free of 8 (or 16) bytes, in C but throughput is approximately identical compared to stack allocating them with SBCLs allocator.

Post reply on HN