Repacking Garbage Collection

If you have a copying collector, like I do, and you want to have the compiler generate the trace code, like I do, the next logical step is to have the ability to "repack" objects as they are being collected.

Take this example: you have a hash-table implementation you want to resize periodically. The naïve way is to redo the entire table whenever you want to resize. The slightly smarter way is to build a second table and move entries over whenever you look them up. This is how Haskell and SML's hash tables work.

But why not mark the table, and when you allocate the new table, then extend it. Or take something like a tree. You can pack immutable trees into a very dense, very cache-efficient array representation if you create them all at once (think like a binary heap, with a bitmap indicating whether a given slot contains an entry or a pointer to a classical node. This also works for structures that need their own internal garbage collection (like graphs), and lazy structures with some kind of lookahead caching.