[Vm-dev] Copy Down to avoid Looking Up

[Eliot Miranda]

Hi Ken,

On Wed, Mar 17, 2021 at 8:13 AM <ken.dickey at whidbey.com> wrote:

>
> You can help me out.
>
> I keep getting this wacky idea which does not seem to go away.  You can
> tell me what is wrong with it.
>
> OK.  Here it is:
>
> To get rid of PICs and dynamic method lookups, each Class knows
> selectors of methods it defines.  Each successful method definition is
> added not only to the method dictionary of the class, but copied down
> transitively to all subclasses, and their sub-subclasses, who have not
> defined a method with the same selector.
>
> At #DeepRehash time, _each_ method dictionary knows all of its selectors
> and creates a "perfect hash" function, or something close to it.
>
> So lookup is just into the specific method dictionary of the instance's
> class which yields the proper method (backstop method is DNU).  Never a
> miss.  No class hierarchy search for inherited methods.
>
> Memory is cheap these days, but selectors and compiled methods are
> mostly shared and the memory cost of method dictionaries is probably
> balanced out by elimination of PICS at the call sites.
>
> The UI tools need to keep some simple rules (e,g, transitively deleting
> methods from subclass method dictionaries), but these should be simple
> and obvious.
>
> The above seems simple enough, but nobody seems to be doing it.
>

I don't think no one is doing this.  I expect for example that the SqueakJS
effort would explore this.


> Why not?
>

Speaking for myself when I did my threaded code version of BrouHaHa in the
late '80's/early '90's I added copy down in the bytecode-to-threaded-code
JIT so that self sends were statically bound.  t was an interesting
experiment, and placed some additional constraints on become: if become
changes any object's class then all activations must be visited and checked
for validity, changing the current method to match the receiver if its
class no longer matches the activation's copied down method.  This is easy
to do with a threaded code JIT because there is a direct mapping between
bytecode and threaded code, at least in my design, so that each byte of
bytecode produced 8 bytes of threaded code (function and parameter, 32 bit
arch).  But in general it can be difficult.  One wants to be able to take
advantage of the static receiver, but if one does, then mapping activations
between different versions of a copied down (& possibly optimized) method
at any suspension point can become problematic.

When I joined Parc Place in '95 I got to know the world's best Smalltalk
JIT at that time, Peter Deutsch's, HPS (Schiffman's context-to-stack mapper
& Jackson's and Ungar's GC).  This VM doesn't do copy-down and it
influenced my work on the VM (I improved method caching, co-designed a new
bytecode set and closure representation, designed a much improved
context-to-stack mapping scheme, improved old space free space management,
and did the 64-bit object representation which introduced class indices in
headers rather than class pointers.  This experience from '95 through '06
heavily influenced my work on Cog and Spur.  Indeed the architectural idea
for Sista/Scorch was inspired by performance analysis work Peter did,
written up in the internal documentation for HPS.  Peter had introduced an
in-line primitive bytecode so he could hand-generate static code to measure
where the time is spent executing Smalltalk.

With Sista/Scorch the entire policy for code management is moved up to the
image, and is no longer a VM decision.  Scorch is freely able to copy-down
and if it chooses to mediate become and class schema migration it has far
more power to manage more aggressive optimization and code duplication than
the VM.  So I'm looking forward to exploring copy-down in that context.  Of
course, now that Clément has gone to Google, this work won't get done
unless I can find collaborators.  And here I sound like a broken record.

>
> Thanks much for insights!
> -KenD
>


-- 
_,,,^..^,,,_
best, Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20210318/f736f473/attachment.html>