<div class="gmail_quote">On Mon, Mar 28, 2011 at 6:25 PM, Gary Byers <span dir="ltr"><<a href="mailto:gb@clozure.com">gb@clozure.com</a>></span> wrote:<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
 If the situation's changed or if I'm portraying it incorrectly, please let me know.<br>
<br>
If I'm correct about that, I personally think that precise GC in the<br>
presence of native threads is too important to seriously consider the<br>
idea of using an LLVM-based backend (and I have other concerns about that<br>
as well.) </blockquote><div><br></div><div>The one concrete example I could find of using LLVM with native threads and garbage collection is the VMKit implementation of a JVM and CLI. Geoffray et al used the MMTk memory management toolkit for this, which originally implemented multithreaded GC for the JikesRVM.  Interestingly, the MMTk is apparently written in Java, so they had to bootstrap with a primitive no-op GC, compile the MMTk into LLVM IR using their Java->LLVM IR compiler, and then they could actually compile MMTk to native code/incorporate it into their new JVM and use it for their CLI.  </div>
<div><br></div><div>But I think the most important thing to note is that it looks quite slow, since any GC appears to require all threads to sync up.  And they aren't able to utilize registers effectively, it appears, due to design constraints of LLVM.</div>
<div><br></div><div>Quoting from <a href="http://vmkit.llvm.org/publications/vmkit.html">http://vmkit.llvm.org/publications/vmkit.html</a> summarizes the situation:</div><div><br></div><div><p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica">
<span class="Apple-style-span" style="font-size: small;">"To address the constraints of efficient multi-threaded garbage</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">collection, we associate each thread with thread-local storage implemented</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">in the first few pages of the thread’s execution stack.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">Because each stack is aligned on a power of 2 boundary, finding</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">a pointer to the local storage of a thread requires only masking</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">the thread’s stack pointer with the boundary complemented by two.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">This approach gives access to the thread local storage without performing</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">a function call, as would be required with POSIX. Alternatively,</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">we could have reserved a register to hold a pointer to the</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">thread-local storage, but this approach would have required modifications</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">to LLVM.</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;"><br></span></p><p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">"As shown in Figure 1, a high-level MRE must provide to the</span></p>

<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">thread manager a function for finding the root objects in the execution</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">stack of each thread. When a garbage collection is triggered, all</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">threads must join a handshake, so that the garbage collector knows</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">the objects referenced on the stacks. To implement a handshake,</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">a thread-local boolean variable is regularly polled by the threads</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">(on return calls and backward branches) to verify if a collection is</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">happening. Once all threads have joined the handshake, the thread</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">manager invokes the function provided by the high-level MRE to</span></p>
<p style="margin: 0.0px 0.0px 0.0px 0.0px; font: 9.0px Helvetica"><span class="Apple-style-span" style="font-size: small;">find the root objects in the threads’ execution stacks."</span></p></div><div><br></div><div>
Assuming CCL does not require thread synchronization in order to collect garbage (correct me if I'm wrong) I would expect CCL to beat the pants off the above strategy.</div><div><br></div></div>