Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Practical Garbage Collection - Part 1: Introduction

worldmodscode.wordpress.com

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Practical Garbage Collection - Part 1: Introduction

#31

Post by rwmj »

aaronblohowiak wrote: post #27
rwmj wrote: post #7

Earlier quoted context omitted.

Unlikely to happen. Reference counting has poor interaction with the CPU memory hierarchy: It makes all objects larger, making the working set correspondingly larger, meaning your data cache is less effective. It makes code larger because of the extra ref counting twiddling code. Larger code means a less effective instruction cache, as well as being slower because of all the extra operations performed. Reference coun…

Gc pauses suck the "magic" out of interactive programs. The great thing about obj-c is that it I trivial to have a c array of vanilla c structs, so your performance sensitive code is still slim and hot. (size and cache locality.) My iOS audio programming mixes c for audio processing and obj-c for ui and control quite effectively.

I didn't say that GC was free ... malloc has overhead too.

For interactive programs, I would recommend two things to avoid (or hide) the pauses. Firstly schedule calls which run the GC when it won't be noticed: between frames in an arcade-style game, or just before accepting user input in a turn-based game. Secondly, size the minor heap large enough so that all computation between the scheduled GC runs can happen without invoking a minor sweep (but not too large that the minor heap is wasting memory -- some experimentation and tuning required).

I've written a couple of interactive games in OCaml that used this strategy and avoided visible GC pauses.

Re: Practical Garbage Collection - Part 1: Introduction

#32

Post by derleth »

nhebb wrote: post #30
lmkg wrote: post #25

Earlier quoted context omitted.

This looks pretty well-answered already, but I'll throw in my $0.02. The stack and heap are the two main regions of memory where data can live in a program. They are (somewhat unhelpfully) named after the data structures originally used to represent them. Pretty much all modern languages have a concept of a stack and a heap, although there are differences both in how explicit they are, and in implementation details.…

There are several things I've never had a good understanding of regarding the stack. How big is the stack? Is it a fixed size dictated by the architecture of the processor? I know I've written recursions that overflow it. Other than gut feel and catching an exception after the fact, how do programmers know when their program might overflow it?

> How big is the stack? Is it a fixed size dictated by the architecture of the processor?

It's more to do with the OS or language runtime; I think the language runtime has a bigger impact for most programs.

> Other than gut feel and catching an exception after the fact, how do programmers know when their program might overflow it?

In general, you don't. You might be able to do some system-specific thing on specific systems or just happen to know what it is on some given system, but there's no way to find out in the general case. Worse, there's generally no way to recover from blowing the stack; this has always made programs written using alloca() or, more recently, variable-length arrays potentially unstable.

Re: Practical Garbage Collection - Part 1: Introduction

#33

Post by ruggeri »

I enjoyed this basic introduction to GC; upvoted. What I'd look forward is further discussion of incremental and concurrent GC algorithms.

Until then, does anyone know what makes concurrent GC non-trivial? It seems like it shouldn't be too hard to trace concurrent to program execution. And if you don't compact, collection seems to just involve updating some structure tracking free blocks. I'd imagine it's possible to write a thread-safe version of that structure where every "free" request doesn't need to block every "malloc" request. But I must have missed something.

I'd also be interested to read how compaction works; how are references remapped from the old address to the new one? Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated? Then you only need to update a single pointer when moving data, but every dereferene incurs an extra layer of indirection.

Re: Practical Garbage Collection - Part 1: Introduction

#34

Post by valyala »

While the article is interesting, it skips important things, which have high influence on practical GC speed - write barriers and finalizers. The following ancient article from Microsoft has better coverage of GC internals http://msdn.microsoft.com/en-us/library/ms973837.aspx (somewhat biased to .NET :) ).

Re: Practical Garbage Collection - Part 1: Introduction

#35

Post by dumael »

ruggeri wrote: post #33

I enjoyed this basic introduction to GC; upvoted. What I'd look forward is further discussion of incremental and concurrent GC algorithms. Until then, does anyone know what makes concurrent GC non-trivial? It seems like it shouldn't be too hard to trace concurrent to program execution. And if you don't compact, collection seems to just involve updating some structure tracking free blocks. I'd imagine it's possible to…

Concurrent GC is somewhat non-trival as the mutator (i.e. the program you write) can delete references to objects from an area of the heap that has not been examined by the GC and introduce references to those same objects in an area that has been examined. This means those objects will be reclaimed since the GC never saw them.

To cope with this the mutator is modified at compile/run time to inform the GC of object updates that could lead to this situation.

During compaction of any sort, the first time an object is encountered that is to be moved it is copied somewhere else and the old copy's header is overwritten with it's forwarding address. Every time the GC encounters a reference to the old object, it re-writes the reference to the old object with it's new location (conveniently located in the old copy's header).

> Is it possible that a reference value is a pointer to a reference "object" which contains the pointer to data, which needs to be updated?

Look up something called 'Brook's style forwarding pointer', it is essentially what you've described.

Re: Practical Garbage Collection - Part 1: Introduction

#36

Post by to3m »

rwmj wrote: post #7
pixie_ wrote: post #5

The complexity of generational garbage collection vs. the speed of manual collection, makes me feel like the happy medium of speed and simplicity is reference counting, like that found in objective-c. iPhone apps are fast, but take a bit longer to design, develop, and debug due to memory management issues. Though with experience these can be minimized. It probably isn't possible without a ton of modification, but I w…

Unlikely to happen. Reference counting has poor interaction with the CPU memory hierarchy: It makes all objects larger, making the working set correspondingly larger, meaning your data cache is less effective. It makes code larger because of the extra ref counting twiddling code. Larger code means a less effective instruction cache, as well as being slower because of all the extra operations performed. Reference coun…

Last I looked, it was a bit hard to follow, but iOS seemed to be storing reference counts separately from the objects. I think you could do (and maybe iOS does?) this on a per-thread basis, to reduce the need for locks.

Re: Practical Garbage Collection - Part 1: Introduction

#37

Post by ruggeri »

dumael wrote: post #35
ruggeri wrote: post #33

I enjoyed this basic introduction to GC; upvoted. What I'd look forward is further discussion of incremental and concurrent GC algorithms. Until then, does anyone know what makes concurrent GC non-trivial? It seems like it shouldn't be too hard to trace concurrent to program execution. And if you don't compact, collection seems to just involve updating some structure tracking free blocks. I'd imagine it's possible to…

Concurrent GC is somewhat non-trival as the mutator (i.e. the program you write) can delete references to objects from an area of the heap that has not been examined by the GC and introduce references to those same objects in an area that has been examined. This means those objects will be reclaimed since the GC never saw them. To cope with this the mutator is modified at compile/run time to inform the GC of object u…

Thanks; upvoted! I think I'm beginning to appreciate that concurrent marking is tougher than I thought; specifically, I can see how it can be hard to prove an object is unreachable. So I imagine the marking side is where the difficulties are.

Your explanation for compaction makes perfect sense. Of course, this won't work trivially concurrently. Only if you stop the world can you complete examination of the entire live heap and know you've updated all references to the moved object and can collect the original space.

Re: Practical Garbage Collection - Part 1: Introduction

#38

Post by dumael »

ruggeri wrote: post #37
dumael wrote: post #35

Earlier quoted context omitted.

Concurrent GC is somewhat non-trival as the mutator (i.e. the program you write) can delete references to objects from an area of the heap that has not been examined by the GC and introduce references to those same objects in an area that has been examined. This means those objects will be reclaimed since the GC never saw them. To cope with this the mutator is modified at compile/run time to inform the GC of object u…

Thanks; upvoted! I think I'm beginning to appreciate that concurrent marking is tougher than I thought; specifically, I can see how it can be hard to prove an object is unreachable. So I imagine the marking side is where the difficulties are. Your explanation for compaction makes perfect sense. Of course, this won't work trivially concurrently. Only if you stop the world can you complete examination of the entire liv…

> I can see how it can be hard to prove an object is unreachable.

The difficulty with concurrent GC is not to prove an object is unreachable but to prove is likely to be reachable. For instance Yusa-type (or snapshot-at-the-beginning) concurrent collectors have a tendency keep dead objects alive. This 'floating garbage' is a small price to pay for a fairly simple correctness proof of never dropping a reachable object.

It's no harm for a GC to keep some dead objects alive but dropping something reachable is completely unacceptable.

> Of course, this won't work trivially concurrently. Only if you stop the world [..] can collect the original space.

Yes, moving objects concurrently requires some serious thinking to get right. Sun's G1 collector does this by recording the location of pointer updates that point into regions which are to be compacted. This pushes the pause times down to the length of time to move objects and update references to them.

If you're real serious about moving objects concurrently, see "A Study of Concurrent Real-Time Garbage Collectors", Pizlo et al, 2008.

Re: Practical Garbage Collection - Part 1: Introduction

#39

Post by bitops »

lmkg wrote: post #25
bitops wrote: post #9

A very good writeup, but one thing always confuses me. What is meant specifically by the "heap" and "stack"? I know what a stack is, but "heap" gets thrown around in many different contexts and I've yet to find any explanation that made it clear. If anyone has a good explanation or good links for those two terms in this context, I'd be very grateful. Thanks! [EDIT: thanks everyone for the answers so far!]

This looks pretty well-answered already, but I'll throw in my $0.02. The stack and heap are the two main regions of memory where data can live in a program. They are (somewhat unhelpfully) named after the data structures originally used to represent them. Pretty much all modern languages have a concept of a stack and a heap, although there are differences both in how explicit they are, and in implementation details.…

Just wanted to say thanks again for the thorough answer. This really made it clear for me.
Post reply on HN