Re: become:

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