Smalltalk › Squeak › Old EZMLM Archive › Squeak - VM

method dictionary lookups and walking up the inheritance tree

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

9 messages Options

Michael Haupt-3

method dictionary lookups and walking up the inheritance tree

Hi,

once more, apologies for cross-posting.

From ClassBuilder, I could see that, when a new class is created, the
superclass's method dictionary contents are copied to the method
dictionary of the new class. Still, the interpreter climbs, in
Interpreter>>lookupMethodInClass:, up the inheritance tree to resolve
a method.

Why is that? Have I missed a spot where subclass creation does not
entail method dictionary copying?

Thanks,

Michael

Klaus D. Witzel

Re: method dictionary lookups and walking up the inheritance tree

Hi Michael,

on Tue, 16 May 2006 18:06:32 +0200, you <[hidden email]> wrote:

> Hi,
>
> once more, apologies for cross-posting.
>
> From ClassBuilder, I could see that, when a new class is created, the
> superclass's method dictionary contents are copied to the method
> dictionary of the new class.

I have not checked the code of ClassBuilder but in such a case the result
is as follows (I do the same every now and then):

a) the VM cannot crash because the method dict field being initially nil
b) every subclass which has the same methods as its superclass has, is
invariant

So if the VM doesn't find a method in such a subclass, it will not find
said method in the superclass, too.

What are you looking for?

/Klaus

> Still, the interpreter climbs, in
> Interpreter>>lookupMethodInClass:, up the inheritance tree to resolve
> a method.
>
> Why is that? Have I missed a spot where subclass creation does not
> entail method dictionary copying?
>
> Thanks,
>
> Michael

Andreas.Raab

Re: method dictionary lookups and walking up the inheritance tree

In reply to this post by Michael Haupt-3

Michael Haupt wrote:
> From ClassBuilder, I could see that, when a new class is created, the
> superclass's method dictionary contents are copied to the method
> dictionary of the new class. Still, the interpreter climbs, in
> Interpreter>>lookupMethodInClass:, up the inheritance tree to resolve
> a method.

Your observation is incorrect. The superclass' method dictionary will
not be copied. What you see in ClassBuilder is that the method
dictionary of an "old version" of the class is being copied. This is
necessary to support class migration, e.g., adding and removing
variables in a class or one of its superclasses.

Cheers,
- Andreas

Michael Haupt-3

Re: method dictionary lookups and walking up the inheritance tree

Hi Andreas,

On 5/16/06, Andreas Raab <[hidden email]> wrote:
> Your observation is incorrect. The superclass' method dictionary will
> not be copied. What you see in ClassBuilder is that the method
> dictionary of an "old version" of the class is being copied. This is
> necessary to support class migration, e.g., adding and removing
> variables in a class or one of its superclasses.

indeed; Tim Rowledge has pointed this out on the Squeak-dev list
already. Next time I'll look a little closer. :-)

So, the only optimisation that is performed for method lookups is the
method cache in the Interpreter, right? Is it correct that its size is
initialised to 512 entries (I'm not sure; I found that in
InterpreterSimulator)?

Are there other optimisations that one could implement, e.g., as a
first step in Squeak VM hacking? Not that I had myself in mind... ;-)

Best,

Michael

johnmci

Re: method dictionary lookups and walking up the inheritance tree

I'll note the cache is very efficient, someone a few years back
attempted to make some changes and make the cache much much bigger
In testing on various platforms we could not show any improvement in
the standard benchmarks to justify the additional memory requirements.

On 16-May-06, at 11:54 AM, Michael Haupt wrote:

> Hi Andreas,
>
> On 5/16/06, Andreas Raab <[hidden email]> wrote:
>> Your observation is incorrect. The superclass' method dictionary will
>> not be copied. What you see in ClassBuilder is that the method
>> dictionary of an "old version" of the class is being copied. This is
>> necessary to support class migration, e.g., adding and removing
>> variables in a class or one of its superclasses.
>
> indeed; Tim Rowledge has pointed this out on the Squeak-dev list
> already. Next time I'll look a little closer. :-)
>
> So, the only optimisation that is performed for method lookups is the
> method cache in the Interpreter, right? Is it correct that its size is
> initialised to 512 entries (I'm not sure; I found that in
> InterpreterSimulator)?
>
> Are there other optimisations that one could implement, e.g., as a
> first step in Squeak VM hacking? Not that I had myself in mind... ;-)
>
> Best,
>
> Michael

--
========================================================================
===
John M. McIntosh <[hidden email]> 1-800-477-2659
Corporate Smalltalk Consulting Ltd. http://www.smalltalkconsulting.com
========================================================================
===

timrowledge

Re: method dictionary lookups and walking up the inheritance tree

On 16-May-06, at 12:05 PM, John M McIntosh wrote:

> I'll note the cache is very efficient, someone a few years back
> attempted to make some changes and make the cache much much bigger
> In testing on various platforms we could not show any improvement
> in the standard benchmarks to justify the additional memory
> requirements.
I think it was worse - on several machines of plausible spec it
actually got slower.

VisualWorks (and probably other VMs at a guess) got some serious
benefits out of polymorphic inline caches. I rather doubt inline
caching is going to work in an interpreter but there might be some
advantage in making the current global cache polymorphic. It could be
a decent experiment to try out as a class exercise for example, since
even if it turns out not to be beneficial it would be instructive and
require all the usual investigative, analytical and explicative
skills. I'd even volunteer to help with reviewing and grading,
subject to time constraints.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
World Ends at Ten! Pictures at 11 on Fox News!

johnmci

Re: method dictionary lookups and walking up the inheritance tree

I recall cross checking the squeak VM at: and methodcache hit ratio's
in 2001? and the numbers I got where still in line with
numbers observed in the "Green book"

On 16-May-06, at 12:31 PM, tim Rowledge wrote:

>
> On 16-May-06, at 12:05 PM, John M McIntosh wrote:
>
>> I'll note the cache is very efficient, someone a few years back
>> attempted to make some changes and make the cache much much bigger
>> In testing on various platforms we could not show any improvement
>> in the standard benchmarks to justify the additional memory
>> requirements.
> I think it was worse - on several machines of plausible spec it
> actually got slower.
>
> VisualWorks (and probably other VMs at a guess) got some serious
> benefits out of polymorphic inline caches. I rather doubt inline
> caching is going to work in an interpreter but there might be some
> advantage in making the current global cache polymorphic. It could
> be a decent experiment to try out as a class exercise for example,
> since even if it turns out not to be beneficial it would be
> instructive and require all the usual investigative, analytical and
> explicative skills. I'd even volunteer to help with reviewing and
> grading, subject to time constraints.
>
> tim
> --
> tim Rowledge; [hidden email]; http://www.rowledge.org/tim
> World Ends at Ten! Pictures at 11 on Fox News!
>
>

Andreas.Raab

Re: method dictionary lookups and walking up the inheritance tree

In reply to this post by timrowledge

Hi Tim -

> VisualWorks (and probably other VMs at a guess) got some serious
> benefits out of polymorphic inline caches. I rather doubt inline caching
> is going to work in an interpreter but there might be some advantage in
> making the current global cache polymorphic. It could be a decent
> experiment to try out as a class exercise for example, since even if it
> turns out not to be beneficial it would be instructive and require all
> the usual investigative, analytical and explicative skills. I'd even
> volunteer to help with reviewing and grading, subject to time constraints.

But isn't the global method cache polymorphic by definition? It maps
class+selector -> method (actual class of object; not class where the
method is defined in) and unless I got the meaning of the word wrong
this is polymorphic, is it not? ;-)

Cheers,
- Andreas

timrowledge

Re: method dictionary lookups and walking up the inheritance tree

On 16-May-06, at 12:43 PM, Andreas Raab wrote:

> Hi Tim -
>
>> VisualWorks (and probably other VMs at a guess) got some serious
>> benefits out of polymorphic inline caches. I rather doubt inline
>> caching is going to work in an interpreter but there might be some
>> advantage in making the current global cache polymorphic. It could
>> be a decent experiment to try out as a class exercise for example,
>> since even if it turns out not to be beneficial it would be
>> instructive and require all the usual investigative, analytical
>> and explicative skills. I'd even volunteer to help with reviewing
>> and grading, subject to time constraints.
>
> But isn't the global method cache polymorphic by definition? It
> maps class+selector -> method (actual class of object; not class
> where the method is defined in) and unless I got the meaning of the
> word wrong this is polymorphic, is it not? ;-)

No, I think you got the word ok, I was being rather imprecise. I was
thinking that maybe having the global cache be more like a bucket
collection might be interesting (and I may be using a poor term here,
think of a collection of collections)
becasue you could avoid (maybe) the hash-clash-cache-smash problem. I
was perhaps recalling some of the details about the PICs in VW as
explained to me a long time ago when I could still remember what day
it was.

Using this 'bucket-cache' we could keep a plain list at each hash
value and deal with multiple entries by having, er, multiple entries
instead of 'yahay, smash the next entry in the list!' hooliganism.
Sort of hanging the hash-chains off the side instead of squeezing
them into the main toothpaste tube.

tim
--
tim Rowledge; [hidden email]; http://www.rowledge.org/tim
CChheecckk yyoouurr dduupplleexx sswwiittcchh..