Re: become:

Hi Eliot,

I don't see this as being a big problem in Strongtalk.  As you pointed
out, deoptimization takes care of the problem nicely.  

That is in fact one reason why I have been adamant that #become: be
specified as a slow operation.   If a heap scan is already being done,
and the become is a rare 'user-level' operation, then the additional
overhead of selectively deoptimizing (or even just deoptimizing
everything) shouldn't be that terrible.

The multi-threading issues won't be a problem until some theoretical
day in the distant future when the VM is internally multi-threaded,
and I'm not even sure that is such a good idea, given how difficult it
is to program in a thread-safe way under such a model, see Java.  And
it is certainly doable, since we already did it for the Java VM; you
just let the other threads continue and halt at the next safepoint,
deoptimize, and off you go.  Ensuring that there is a safepoint in
loops is of course necessary, but they can be unrolled to amortize the
overhead.

Off the top of my head I think the only additional thing is doing some
additional validation of the deoptimized contexts to make sure that
instance var refs are still valid.

Deoptimization may be a pain to code, but it is really handy once you
have it!
-Dave

--- In [email protected], "eliotemiranda" <eliot.miranda@...>
wrote:
>
> --- In [email protected], Gilad Bracha <gilad@> wrote:
> >
> > To add some perspective on become:
> > 
> > I don't see a problem implementing it (the slow way, traversing the  
> > heap). There are some uses that would be perfectly acceptable that  
> > way. In most cases I think a one-way become: is sufficient, which  
> > allows it to be type-safe, and allows for fast implementations in
the  
> > special case where the object size does not change. There are also  
> > schemes that do this lazily (though object identity has to be taken  
> > care of carefully). It hasn't been a priority.
> >
> 
> IMO, the issue with become: isn't how its implemented at the GC level
> but how it, and the other meta-behavioural prim,itives, ineract with
> the optimizer.  Let me explain.
> 
> There are a number of "mta-behavioural" primitives in Smalltalks that
> have the ability to change the size and/or class of an object, or in
> general change an objects' bevahiour.  For example
> 
> a become: b swaps two objects a and b so that after the operation all
> prior references to object a now refer to object b and all prior
> references to object b now refer to object a.
> 
> a oneWayBecome: b swaps two objects a and b such that after the
> operation all prior references to object a refer to object b and there
> are no remaining references to object a.
> 
> a changeClassToThatOf: b changes the class of a to that of b (provided
> the two are compatible, e.g. that if a has pointers, b must have
> pointers and a must have at least as many slots as there are named
> inst vars defined by b's class, or that if a is a byte object b mst be
> a byte object)
> 
> a adoptInstance: b (a.k.a. b changeClassTo: a) changes the class of b
> to be a provided that b is compatible (as for changeClassToThatOf:).
> 
> There are other apparently less radical meta-behavioural primitives,
> but as we shall see these are no less priblematical, e.g.
> 
> a setImmutability: aBoolean changes a's mutability such that once a is
> immutable attempts at modifying its state (assign to any field within
> it, change its class, perform a become: on it) will raise an error.
> 
> Now these primitives are extremely useful in development e.g.:
>    ability to dynamically add inst vars to an object,
> in distribution and persistence, e.g.:
>   ability to "fault" objects in from adatabase or across the network
> by becoming: a proxy (reference to some external entity) to a local
> reification (of the external entity)
> 
> and so on.  Many important production systems rely on these kinds of
> facilities, especially thinks ike the interface to the GemStone
> Smalltalk database.  But these facilities wrek havoc with one's
> ability to optimize.
> 
> For example, consider the following method
> ArrayedCollection methods for clarification
> sum
>     | sum |
>     sum := 0.
>     1 to: self size do:
>         [:i|
>         sum := sum + (self at: i)].
>     ^sum
> 
> An adaptive optimizer will easily be able to optimize thus:
> 
> 1. prove that (for some subset of the subclasses of ArrayedCollection)
> self size binds to a primitive that
> - does not fail
> - answers a non-negative SmallInteger less than SmallInteger maxVal
> - answers a SmallInteger in the range 0 to the number of indexed inst
> vars in the receiver
> - answers the number of indexable inst vars in the receiver
> 
> 2. that (for some subset of the subclasses of ArrayedCollection) self
> at: binds to a primitive that answers the n'th indexable field o the
> receiver
> 
> 3. that for some subset of the subclasses of ArrayedCollection, none
> of the classes are byte objects.
> 
> and hence that within the loop
> 1. the (implicit) computation i := i + 1 can be performed without
> cheking for integer overflow
> 2. that the at: primitive can be replaced by code that indexes the
> receiver without bounds-checking.
> 
> In effect the loop can be rewritten as something like
>     | i numNamed limit |
>     numNamed := self class instSize. "Number of named inst vars"
>     limit := self pointerSize + numNamed. "No need to check for byte
> objects"
>     i := numNamed + 1.
>     [i <= limit] whileTrue:
>         [sum := sum + (self noCheckSlotAt: i).
>          i := i noCheckAdd: i]
> 
> The code generated or this can beequivalent to that produced by a C
> compiler, eliminating bounds checking and tag checking.
> 
> But how does this interact with become: et al?  If the system is
> natvely multi-threaded, or if there is a potential process-switch
> point (yield point) in the loop (as there had better be because self
> size could be very large) then in anothe rprocess, effectively in
> paralel, a meta-behavioural primitive could be applied to the object
> being summed and all the invariants the optimizer is depending on
> could be violated:
> 
> - the class could change to redefine at:, size, the pointer-ness of
> the array, etc.
> 
> - the object could be shortened so that the next noCheckSlotAt: i
> would be out of bounds
> 
> 
> So what to do?  I think this is still a research question.  here are
> some potential answers
> 
> 1. ban meta-behavioural primitives
> 
> 2. make the meta=behavioural primitives check for any activations of
> optimized methods that references their arguments and deoptimize these
> activations as part of the primitive.
> 
> 2a. somehow mark objects as optimizable (the default when objects are
> created), make the meta-behavioural primitives check, and add a guard
> to check for the mark in any loop, and then do 2. only for marked
objects.
> 
> 3. have the optimizer do escape analysis and only perform
> optimizations like the above on objects which it can prove can't
> escape to code that could become: them.
> 
> Any other good ideas?  I think this is a) a really important issue and
> b) really hard.  I think some version of 2 is workable but can imagine
> in some contexts (eg. GemStone applications) that its just too
> expensive and ence one will want to do 3.  But 3. is really, really
> hard and probably drastically reduces the number of opportunities for
> this kind of optimization.
>






 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/strongtalk/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/strongtalk/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/