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

[Tony Hosking]

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!