And Anton please go ahead with an implementation /Søren
On Fri, Dec 18, 2009 at 08:41, Kevin Millikin <kmilli...@google.com> wrote: > On Thu, Dec 17, 2009 at 11:18 PM, <ant...@chromium.org> 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 v8-dev@googlegroups.com http://groups.google.com/group/v8-dev
