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

[Tony Hosking]

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!