[dumael]

> 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.