On Thu, Dec 17, 2009 at 11:18 PM, <[email protected]> wrote: > > Anyway, I'd love to implement this map compaction. > > Hi Anton. What you described would work as well, but it's three passes (one to reallocate maps and write forwarding addresses, one to adjust all map pointers in the heap, one to move maps). You can do it in two passes using a variation of the "two finger" garbage collector, because all objects and holes in map space are the same size.
1. Count maps marked during the marking phase of a full collection. If there are few enough maps that we can get under the encoding limit by compacting, choose to compact. Instead of the normal sweep: 2. Compute the end address of the last live map after compaction. You know how many maps there are and they're fixed size, so you can compute the page number and the offset in the page. 3. Use two pointers. "to" starts at the beginning of map space. "from" starts at the end address of the last map after compaction. Sweep "to" to the first unmarked map, unmarking marked maps on the way. Sweep "from" to the first marked map. Copy this map to the hole pointed to by "to", unmark it (in its new location), write its forwarding address in its old location (tagged to distinguish it as a forwarded map---different from a live map and different from a marked non-map). 4. Continue until "to" reaches the original "from" pointer (the end of the last live map after compaction). 5. Sweep the heap normally to clear mark bits. For objects that may contain map pointers, also sweep their body and update any forwarded maps. 6. Release unused map pages. The advantage of the three pass approach is that it preserves order, but if we're doing mark sweeps we've already been allocating maps off the free list, so they are already not in allocation order. -- v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev
