<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
FONT-SIZE: 10pt;
FONT-FAMILY:Tahoma
}
</style>
</head>
<body class='hmmessage'>My quick understanding was that gc-points and mostly preemptive thread scheduling could be combined.<BR>
You would have to cooperatively yield at gc-points, but you could be preemptively yielded anywhere.<BR>
Er, maybe that's the point -- no cooperative yielding at all, no computation of gc-points, maybe none of this data.<BR>
But you do end up I guess suspending all the threads and reading their registers and guessing as to the contents..the ambiguity you mention. I wonder how that is dealt with, since any integer can be an arbitrarily ffset pointer..<BR>I'll have to read more of the code..<BR>
<BR> - Jay<BR><BR>
<HR id=stopSpelling>
<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 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 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 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 (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 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 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: 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 prevent<BR>> > > > enregistration. I can see that's a potentially high cost 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 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 cannot<BR>> > > > reliably get/set the context of other threads. I think, like, you<BR>> > > > could reliably get/set context on a uniprocessor system, 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 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, "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 address"<BR>> > > > for holders of the old value?<BR>> > > ><BR>> > > > The gc isn't concurrent but is called at function entry/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 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 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 enregistered?<BR>> > > > ><BR>> > > > > I don't understand what you mean by this.<BR>> > > > ><BR>> > > > > > Even the accessor function approach seems lame, given 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. 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 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 would<BR>> > > > need to<BR>> > > > > > > >> know where your manufactured interior pointer is being<BR>> > > > held and<BR>> > > > > > > >> to which *object* (ie, the open array in this 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 to a<BR>> > > > VAR mode<BR>> > > > > > > >> formal, effectively passing a pointer to the callee. GC<BR>> > > > can cope<BR>> > > > > > > >> with this in one of two possible ways: 1) "Pin" 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 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 from base<BR>> > > > object<BR>> > > > > > > >> references for use during GC. 2) requires much 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? 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. 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 /><hr />Share life as it happens with the new Windows Live. <a href='http://www.windowslive.com/share.html?ocid=TXT_TAGLM_Wave2_sharelife_112007' target='_new'>Share now!</a></body>
</html>