The actual GC of freeing memory is indeed possible (and common) without stop the world. Heap defrag is another story, though. This involves moving objects to different locations in memory, and if the memory is mutable, measures like stop the world is required since multi-byte move is not atomic.
Doesn't matter. In an immutable model, the old copy is guaranteed not to change, so you can safely copy it non-atomically. (That's one of the big benefits of immutability.)
