<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
<br><div><div>On Jan 22, 2008, at 5:04 PM, Vesa Karvonen wrote:</div><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">I don't know how the double pointers would actually be used and</span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">whether a single object may be accessed in parallel by multiple cores</div></blockquote><div><br class="webkit-block-placeholder"></div><div>My work is based on the Cheng-Blelloch collector, but is lock-free (except for a barrier at the beginning and end of a collection). Like Cheng-Blelloch, the double pointers are necessary for garbage collecting some, but not all of the heap. Stopping and switching over all the pointers incurs an unbounded pause. If you collect the entire heap, then you can build the "new" memory graph using pointers to the new objects, and continue to have mutators access the old memory graph until collection is complete, then switch over only a very small number of pointers at the end of collection. However, global variables don't get copied, and there can be a large number of them. Also, with generations, there might be a large number of objects which aren't copied, and thus, still have pointers to either the old graph, which vanishes, or to the new one, which isn't ready until the end of collection. Switching over all the pointers has to happen very quickly.</div><div><br class="webkit-block-placeholder"></div><div>The solution to this is double-pointers. Pointers consist of two slots. For objects that aren't copied, like static data, a different generation, or an exiting thread, the collector stores the pointer to the new object in the unused slot. At the end of collection, a flag is toggled, causing the program to switch which slot is used. It should be noted that you pay this cost, as well as the cost of the write-barrier for the benefit of parallel collection.</div><br><blockquote type="cite"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; "><span class="Apple-style-span" style="-webkit-text-stroke-width: -1; ">One thought that comes to mind here is that it</span></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">might make sense to layout objects in such a way that all the pointers</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">used by the collector are stored as a contiguous block (within an</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; ">object) and likewise for the pointers used by the mutator.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; min-height: 14px; "><br></div></blockquote><br></div><div>MLton already lays things out this way. Pointers are all in a cluster, which follows the non-pointer data. However, what I was talking about was the object's header itself. In the parallel collector, the header must contain a forwarding pointer (the pointer to the new object), which allows writes to be copied to the new object (the write barrier, which I won't explain right now, mostly because it's one of the things I still have to implement). The collectors themselves "claim" a given object by CASing in an actual value to the forwarding pointer slot. This prevents an object from being processed twice. However, as the object header is now subject to a CAS, it need to be a cache-line in size so as to avoid data fighting (other unrelated data getting cache-invalidated due to CASing).</div><br><div> <span class="Apple-style-span" style="border-collapse: separate; border-spacing: 0px 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; text-align: auto; -khtml-text-decorations-in-effect: none; text-indent: 0px; -apple-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div>-- </div><div>Eric McCorkle</div><div>Brown University</div><div>CS Graduate Student</div><br class="Apple-interchange-newline"></span> </div><br></body></html>