[M3devel] returning record by value vs. by ref?

[Jay]

> roll forward to gc-point
 
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, roughly.
 
 > ambiguous..
 
The problem in my mind is "how ambiguous?".
Can't almost anything be a pointer in disguise?
This example from the paper:
 
Double Indexing: The code
A[i] := 1;
B[i] := 2;
may be optimized to
t1 = &A[0] + (i * sizeof(int));
t2 = &B[0] - &A[0];
*tl = 1;
*(tl + t2) = 2;
 
which is useful on machines that have addressing modes
with two or more index registers, such as the SPARC.
 
More from the paper, emphasis mine:
 
Note that a derived value
may bean untidy pointer to the interior of an object (strength
reduction example), an untidy pointer that points outside the
object to which it refers (virtual array origin example), or
even a non-pointer value (double indexing example), and
the examples given above may not exhaust the possibilities
 - Jay



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