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

[Tony Hosking]

On Dec 2, 2007, at 1:54 PM, Jay wrote:

> > 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.

My problem with this for preemptive scheduling is that roll-forward  
can take a long time -- too long if one wants short GCs.  Currently,  
GC can occur at almost all preemption points.

>  > ambiguous..
>
> The problem in my mind is "how ambiguous?".
> Can't almost anything be a pointer in disguise?

Indeed, for CM3 currently any word-aligned, word-length bit string in  
stacks or registers is treated as a potential ambiguous root.

> 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

This all depends on what sorts of optimizations are permitted, as you  
have already noted.

>
>
>  - 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!