<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
FONT-SIZE: 10pt;
FONT-FAMILY:Tahoma
}
</style>
</head>
<body class='hmmessage'>> roll forward to gc-point<BR>
<BR>
Right, the paper says the gc will wait till all threads are at gc-points, and gc-points are defined/inserted enough to make it probably not long -- allocations, calls/returns, loop boundaries, <EM>roughly</EM>.<BR>
<BR>
> ambiguous..<BR>
<BR>
The problem in my mind is "how ambiguous?".<BR>
Can't <EM>almost anything </EM>be a pointer in disguise?<BR>
This example from the paper:<BR>
<BR><B><I><FONT face="Times New Roman" size=1>
<P align=left><FONT size=3>Double Indexing: The </FONT></B></I></FONT><FONT face="Times New Roman"><FONT size=3>code</FONT></P></FONT><FONT face="Times New Roman">
<P align=left><FONT size=3>A[i] := 1;</FONT></P>
<P align=left><FONT face="" size=3>B[i] := </FONT></FONT><FONT face="Times New Roman"><FONT size=3>2;</FONT></P>
<P align=left><FONT size=3>may be optimized to</FONT></P></FONT><FONT face=Courier>
<P align=left><FONT face="" size=3>t1 </FONT></FONT><FONT size=3><FONT face="Times New Roman">= </FONT><FONT face="Times New Roman">&A[0] + (i * </FONT></FONT><FONT face="Times New Roman"><FONT size=3>sizeof(int));</FONT></P>
<P align=left><FONT face=""><FONT size=3>t2 = &B[0] - &A[0];</FONT></FONT></P>
<P align=left><FONT size=3>*tl = 1;</FONT></P>
<P align=left><FONT face="" size=3>*(tl + t2) = 2;</FONT></P></FONT><FONT face="Times New Roman">
<P align=left><FONT size=3></FONT> </P>
<P align=left><FONT size=3>which is useful on machines that have addressing modes</FONT></P>
<FONT size=3>with two or more index registers, such as the SPARC.</FONT><BR></FONT><FONT face="Times New Roman" size=2>
<FONT size=3></FONT> <BR>
<FONT size=3>More from the paper, emphasis mine:</FONT><BR>
<FONT size=3></FONT> <BR><FONT face="Times New Roman" size=2>
<P align=left><FONT size=3>Note that a derived value</FONT></P>
<P align=left><FONT size=3>may bean untidy pointer to the interior of an object (strength</FONT></P>
<P align=left><FONT size=3>reduction example), an untidy pointer that points outside the</FONT></P>
<P align=left><FONT size=3>object to which it refers (virtual array origin example),<STRONG> or</STRONG></FONT></P>
<P align=left><FONT size=3><STRONG>even a non-pointer value (double indexing example)</STRONG>, and</FONT></P>
<FONT size=3>the examples given above may not exhaust the possibilities</FONT><BR>
</FONT></FONT><BR> - Jay<BR><BR>
<HR id=stopSpelling>
<BR>
> From: hosking@cs.purdue.edu<BR>> Date: Sun, 2 Dec 2007 12:23:29 -0500<BR>> To: jay.krell@cornell.edu<BR>> CC: m3devel@elegosoft.com<BR>> Subject: Re: [M3devel] returning record by value vs. by ref?<BR>> <BR>> <BR>> On Dec 2, 2007, at 1:15 AM, Jay wrote:<BR>> <BR>> > My quick understanding was that gc-points and mostly preemptive <BR>> > thread scheduling could be combined.<BR>> <BR>> A little but doable: if a thread is preempted and GC occurs then you <BR>> have a problem, needing to roll the thread forward to a GC point.<BR>> <BR>> > You would have to cooperatively yield at gc-points, but you could <BR>> > be preemptively yielded anywhere.<BR>> > Er, maybe that's the point -- no cooperative yielding at all, no <BR>> > computation of gc-points, maybe none of this data.<BR>> <BR>> Yes, that's the point about ambiguous roots collection.<BR>> <BR>> > But you do end up I guess suspending all the threads and reading <BR>> > their registers and guessing as to the contents..the ambiguity you <BR>> > mention. I wonder how that is dealt with, since any integer can be <BR>> > an arbitrarily ffset pointer..<BR>> <BR>> The current ambiguous roots collector pins objects referred to by <BR>> ambiguous roots (thread stacks/registers). It moves objects that are <BR>> not referred to by ambiguous roots.<BR>> <BR>> > I'll have to read more of the code..<BR>> ><BR>> > - Jay<BR>> ><BR>> ><BR>> > > From: hosking@cs.purdue.edu<BR>> > > Date: Sun, 2 Dec 2007 00:16:05 -0500<BR>> > > To: jay.krell@cornell.edu<BR>> > > CC: m3devel@elegosoft.com<BR>> > > Subject: Re: [M3devel] returning record by value vs. by ref?<BR>> > ><BR>> > ><BR>> > > On Dec 1, 2007, at 11:11 PM, Jay wrote:<BR>> > ><BR>> > > > Thanks!<BR>> > > ><BR>> > > > I haven't finished reading it, but it sounds like an optimizing<BR>> > > > compiler is ok, due<BR>> > > > to the reliance on "gc points", which I read ahead to find out how<BR>> > > > they are defined.<BR>> > ><BR>> > > If you want fully accurate (non-ambiguous roots) GC then yes you <BR>> > need<BR>> > > gc-points to avoid having to store pointer information for every PC<BR>> > > location.<BR>> > ><BR>> > > > And I'm GUESSING that CM3 already generates and depends on the <BR>> > sort<BR>> > > > of data described there.<BR>> > > > But maybe not.<BR>> > ><BR>> > > Umm, no. CM3 uses an ambiguous roots technique for thread stacks/<BR>> > > registers that avoids the need for gc-points. Hence, we can use<BR>> > > preemptive system-level thread scheduling.<BR>> > ><BR>> > > > I wonder what the size of the data looks like if you allow a gc<BR>> > > > point at every instruction.<BR>> > > > I guess it probably be too large -- figure a byte or two extra for<BR>> > > > every instruction, but maybe not.<BR>> > > ><BR>> > > > Perhaps it could be encoded in bits instead of bytes and given <BR>> > that<BR>> > > > most instructions don't affect the state<BR>> > > > (ie: operations on integers, floats, comparisons, branches), maybe<BR>> > > > just a zero bit for most instructions.<BR>> > > > So then figure a byte or two for every instruction that moves <BR>> > (load<BR>> > > > or store) or adds/substracts a pointer.<BR>> > > > Or more than that. A byte or two could describe enregistration and<BR>> > > > small adds/subtracts, but not large adds/subtracts<BR>> > > > or memory offsets.<BR>> > > ><BR>> > > > OR perhaps it'd just read the code itself. That's easier with <BR>> > Win32/<BR>> > > > x86 since it is so constrained<BR>> > > > as to what it outputs. That should be feasible. I realize I'm<BR>> > > > changing subjects between the different backends.<BR>> > > ><BR>> > > > The Windows AMD64 calling convention relies on something LIKE <BR>> > this.<BR>> > > > In particular, there is a little encoding associated with every<BR>> > > > prolog/epilog so that exception handling can undo the prolog's<BR>> > > > effects.<BR>> > > > It describes a tiny subset of the instruction set, like register<BR>> > > > moves.<BR>> > > ><BR>> > > > Kind of funny -- once you get into the business of wanting to read<BR>> > > > the code to know what it does,<BR>> > > > you then get tempted to define your own code, for runtime and<BR>> > > > information, and then a possible trick<BR>> > > > is to adopt the existing machine code as your code, or whatever<BR>> > > > subset your compiler produces.<BR>> > > > Hm. The existing machine isn't sufficient. You would need type<BR>> > > > information to augment it.<BR>> > > ><BR>> > > > Which reminds. Another OBVIOUS backend for CM3 for easier<BR>> > > > portability is to persist the calls to m3cg and then<BR>> > > > write an interpreter for that in C.<BR>> > > ><BR>> > > > - Jay<BR>> > > ><BR>> > > ><BR>> > > > > From: hosking@cs.purdue.edu<BR>> > > > > Date: Sat, 1 Dec 2007 17:42:02 -0500<BR>> > > > > To: jay.krell@cornell.edu<BR>> > > > > CC: m3devel@elegosoft.com<BR>> > > > > Subject: Re: [M3devel] returning record by value vs. by ref?<BR>> > > > ><BR>> > > > > If this really interests you then you might read this paper: <BR>> > http://<BR>> > > > > doi.acm.org/10.1145/143095.143140 .<BR>> > > > ><BR>> > > > > On Dec 1, 2007, at 5:36 PM, Jay wrote:<BR>> > > > ><BR>> > > > > > > 2, don't understand<BR>> > > > > ><BR>> > > > > > You said it'd take much cooperation with the compiler, due its<BR>> > > > > > optimizations, but optimizations can be defeated as necessary.<BR>> > > > > > Interior pointers could be marked, perhaps, volatile, so <BR>> > prevent<BR>> > > > > > enregistration. I can see that's a potentially high cost <BR>> > though.<BR>> > > > > ><BR>> > > > > > like<BR>> > > > > > Record_t *Record = GetRecord();<BR>> > > > > > unsigned i;<BR>> > > > > > for (i = 0 ; i != Record->j ; ++i)<BR>> > > > > > {<BR>> > > > > > ...<BR>> > > > > > }<BR>> > > > > ><BR>> > > > > > You'd really like Record->j to not be refetched for every loop<BR>> > > > > > iteration, but if Record is volatile so the GC can move <BR>> > what it<BR>> > > > > > points to and update outstanding pointers, you'd be stuck with<BR>> > > > > > something like that. Besides, if j can't be read in one<BR>> > > > > > instruction, more problems, assuming a concurrent GC, that <BR>> > cannot<BR>> > > > > > reliably get/set the context of other threads. I think, <BR>> > like, you<BR>> > > > > > could reliably get/set context on a uniprocessor system, <BR>> > but not a<BR>> > > > > > multiprocessor. You'd have to suspend, wait for the suspend to<BR>> > > > > > happen.. I guess that could work, but it seems like you'd <BR>> > want to<BR>> > > > > > avoid designs that require suspending threads. ?<BR>> > > > > > Hm. No, it's difficult. This being a short lived pointer, gc<BR>> > > > > > happening on another thread, you'd have to, like, <BR>> > "register" its<BR>> > > > > > location with the gc.<BR>> > > > > ><BR>> > > > > > Hm. Just how does it work?<BR>> > > > > ><BR>> > > > > > gc suspends threads and updates variables? I don't think so.<BR>> > > > > ><BR>> > > > > > Variables that are moved leave some sort of "forwarding <BR>> > address"<BR>> > > > > > for holders of the old value?<BR>> > > > > ><BR>> > > > > > The gc isn't concurrent but is called at function entry/ <BR>> > exit? I<BR>> > > > > > don't think so.<BR>> > > > > ><BR>> > > > > > I should check the docs and code..<BR>> > > > > ><BR>> > > > > > - Jay<BR>> > > > > ><BR>> > > > > ><BR>> > > > > ><BR>> > > > > > > From: hosking@cs.purdue.edu<BR>> > > > > > > Date: Sat, 1 Dec 2007 17:19:46 -0500<BR>> > > > > > > To: jay.krell@cornell.edu<BR>> > > > > > > CC: m3devel@elegosoft.com<BR>> > > > > > > Subject: Re: [M3devel] returning record by value vs. by ref?<BR>> > > > > > ><BR>> > > > > > ><BR>> > > > > > > On Dec 1, 2007, at 5:14 PM, Jay wrote:<BR>> > > > > > ><BR>> > > > > > > > 1) Can pinning not be exposed reasonably in the language?<BR>> > > > > > > > I'll keep my pointer just a short time, in a local.<BR>> > > > > > ><BR>> > > > > > > Yes, that is a *hack* that will work only with the current<BR>> > > > > > > conservative garbage collector. In general, the compiler <BR>> > might<BR>> > > > > > > record that the local is a pointer derived from some base<BR>> > > > reference<BR>> > > > > > > and if the GC decides to move the base object it can <BR>> > adjust the<BR>> > > > > > local<BR>> > > > > > > derived pointer accordingly.<BR>> > > > > > ><BR>> > > > > > > > 2) surely it could be done at an outer layer?<BR>> > > > > > > > Make volatile locals for things you don't want <BR>> > enregistered?<BR>> > > > > > ><BR>> > > > > > > I don't understand what you mean by this.<BR>> > > > > > ><BR>> > > > > > > > Even the accessor function approach seems lame, given <BR>> > that I<BR>> > > > > > > > believe the Win32/x86 compiler doesn't inline.. :(<BR>> > > > > > > > (does the gcc m3 inline across modules, or just compiles<BR>> > > > one at a<BR>> > > > > > > > time?)<BR>> > > > > > ><BR>> > > > > > > gcc m3 inlines only within compilation units.<BR>> > > > > > ><BR>> > > > > > > ><BR>> > > > > > > ><BR>> > > > > > > > - Jay<BR>> > > > > > > ><BR>> > > > > > > ><BR>> > > > > > > > > CC: jay.krell@cornell.edu; m3devel@elegosoft.com<BR>> > > > > > > > > From: hosking@cs.purdue.edu<BR>> > > > > > > > > Subject: Re: [M3devel] returning record by value vs. <BR>> > by ref?<BR>> > > > > > > > > Date: Sat, 1 Dec 2007 15:23:19 -0500<BR>> > > > > > > > > To: rodney.bates@wichita.edu<BR>> > > > > > > > ><BR>> > > > > > > > > Correct! Anytime you create an l-value pointer.<BR>> > > > > > > > ><BR>> > > > > > > > > On Dec 1, 2007, at 2:31 PM, Rodney M. Bates wrote:<BR>> > > > > > > > ><BR>> > > > > > > > > > Tony Hosking wrote:<BR>> > > > > > > > > >> I am assuming 's' here is an open array (REF ARRAY OF<BR>> > > > > > item) in<BR>> > > > > > > > > >> which case it is allocated in the GC'd heap. There is<BR>> > > > > > certainly<BR>> > > > > > > > > >> no way of safely getting an interior pointer to items<BR>> > > > in the<BR>> > > > > > > > > >> stack in Modula-3 -- at least not one that you can <BR>> > upward<BR>> > > > > > expose<BR>> > > > > > > > > >> (to callers) via return from a procedure. The<BR>> > > > difficulty in<BR>> > > > > > > > > >> doing this is that the GC moves objects around and <BR>> > would<BR>> > > > > > need to<BR>> > > > > > > > > >> know where your manufactured interior pointer is <BR>> > being<BR>> > > > > > held and<BR>> > > > > > > > > >> to which *object* (ie, the open array in this <BR>> > case) it<BR>> > > > > > refers so<BR>> > > > > > > > > >> that it can 'fix' the pointer when the array object<BR>> > > > moves.<BR>> > > > > > > > > >> Modula-3 provides a small concession to obtaining<BR>> > > > downward<BR>> > > > > > > > > >> exposed interior pointers using the VAR parameter<BR>> > > > mode. For<BR>> > > > > > > > > >> example you can pass 's[i]' as an actual parameter <BR>> > to a<BR>> > > > > > VAR mode<BR>> > > > > > > > > >> formal, effectively passing a pointer to the <BR>> > callee. GC<BR>> > > > > > can cope<BR>> > > > > > > > > >> with this in one of two possible ways: 1) "Pin" <BR>> > the array<BR>> > > > > > so that<BR>> > > > > > > > > >> it cannot be moved while the interior pointer is held<BR>> > > > on the<BR>> > > > > > > > > >> stack or registers of any thread (this is the <BR>> > approach<BR>> > > > > > that CM3's<BR>> > > > > > > > > >> conservative collector uses for now); or 2) track the<BR>> > > > > > creation of<BR>> > > > > > > > > >> such interior pointers and how they are derived <BR>> > from base<BR>> > > > > > object<BR>> > > > > > > > > >> references for use during GC. 2) requires much <BR>> > more co-<BR>> > > > > > operation<BR>> > > > > > > > > >> from the compiler than the current gcc-based backend<BR>> > > > (with<BR>> > > > > > all of<BR>> > > > > > > > > >> its lovely optimizations and register allocation) is<BR>> > > > > > capable of<BR>> > > > > > > > > >> doing. 1) is very cheap and does not impede<BR>> > > > optimizations and<BR>> > > > > > > > > >> register allocation.<BR>> > > > > > > > > ><BR>> > > > > > > > > > Presumably, this all also applies WITH-bound<BR>> > > > identifiers, when<BR>> > > > > > > > they<BR>> > > > > > > > > > are<BR>> > > > > > > > > > designators of interior components of heap objects? <BR>> > Are<BR>> > > > > > there any<BR>> > > > > > > > > > other<BR>> > > > > > > > > > cases?<BR>> > > > > > > > > ><BR>> > > > > > > > > > --<BR>> > > > > > > > > ><BR>> > > > -------------------------------------------------------------<BR>> > > > > > > > > > Rodney M. Bates, retired assistant professor<BR>> > > > > > > > > > Dept. of Computer Science, Wichita State University<BR>> > > > > > > > > > Wichita, KS 67260-0083<BR>> > > > > > > > > > 316-978-3922<BR>> > > > > > > > > > rodney.bates@wichita.edu<BR>> > > > > > > > ><BR>> > > > > > > ><BR>> > > > > > > ><BR>> > > > > > > > Your smile counts. The more smiles you share, the more we<BR>> > > > donate.<BR>> > > > > > > > Join in!<BR>> > > > > > ><BR>> > > > > ><BR>> > > > > ><BR>> > > > > > Get the power of Windows + Web with the new Windows Live. <BR>> > Power<BR>> > > > up!<BR>> > > > ><BR>> > > ><BR>> > > ><BR>> > > > You keep typing, we keep giving. Download Messenger and join the<BR>> > > > i’m Initiative now. Join in!<BR>> > ><BR>> ><BR>> ><BR>> > Share life as it happens with the new Windows Live. Share now!<BR>> <BR><BR><br /><hr />Your smile counts. The more smiles you share, the more we donate. <a href='www.windowslive.com/smile?ocid=TXT_TAGLM_Wave2_oprsmilewlhmtagline' target='_new'>Join in!</a></body>
</html>