Garbage Collection: Algorithms for Automatic Dynamic Memory Management

Author: Richard Jones, Rafael Lins
4.3
All Stack Overflow 8

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

4.3

Review Date:

Comments

by anonymous   2017-08-20

The answer is that this depends on the garbage collection algorithms used. In some cases, you are correct that all threads are stopped during GC. In other cases, you are incorrect in that garbage collection proceeds while normal threads are running. To understand how GC's achieve that, you need a detailed understanding of the theory and terminology of garbage collectors, combined with an understanding of the specific collector. It is simply not amenable to a simple explanation.

Oh yes, and it is worth pointing out that many modern collectors don't have a compaction phase per-se. Rather they work by copying live objects to a new "space" and zeroing the old "space" when they are done.

If I am incorrect my question would be answered by a simple explanation of the strategy used to minimise blocking.

If you really want to understand how garbage collectors work, I recommend:

... and beware that finding accurate, detailed, public descriptions of the internals of production garbage collectors is not easy. (Though in the case of the Hotspot GC's, you can look at the source code ...)

EDIT: in response to the OP's comment ...

"It seems it is as I thought -- there is no getting around the "stop the world" part."

It depends. In the case of the Java 6 Concurrent Collector, there are two pauses during the marking of the roots (including stacks), and then marking / copying of other objects proceeds in parallel. For other kinds of concurrent collector, read or write barriers are used while the collector is running to trap situations where the collector and application threads would otherwise interfere with each other. I don't have my copy of [Jones] here right now, but I also recall that it is possible to make the "stop the world" interval negligible ... at the cost of more expensive pointer operations and/or not collecting all garbage.

by David G   2017-08-20

Only a very naive implementation would have a problem with circular references. Wikipedia has a good article on the different GC algorithms. If you really want to learn more, try (Amazon) Garbage Collection: Algorithms for Automatic Dynamic Memory Management . Java has had a good garbage collector since 1.2 and an exceptionally good one in 1.5 and Java 6.

The hard part for improving GC is reducing pauses and overhead, not basic things like circular reference.

by anonymous   2017-08-20

How the compiler and run-time environment handle memory management has grown up over a long period of time. The stack memory v.s. heap memory allocation decision had a lot to do with what could be known at compile-time and what could be known at runtime. This was before managed run times.

In general, the compiler has very good control of what's on the stack, it gets to decide what is cleaned up and when based on calling conventions. The heap on the other hand, was more like the wild west. The compiler did not have good control of when things came and went. By placing function arguments on the stack, the compiler is able to make a scope -- that scope can be controlled over the lifetime of the call. This is a natural place to put value types, because they are easy to control as opposed to reference types that can hand out memory locations (pointers) to just about anyone they want.

Modern memory management changes a lot of this. The .NET runtime can take control of reference types and the managed heap through complex garbage collection and memory management algorithms. This is also a very, very deep subject.

I recommend you check out some texts on compilers -- I grew up on Aho, so I recommend that. You can also learn a lot about the subject by reading Gosling.