method dictionary lookups and walking up the inheritance tree

[Michael Haupt-3]

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]

Hi Michael,

on Tue, 16 May 2006 18:06:32 +0200, you <mhaupt@...> 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]

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]

Hi Andreas,

On 5/16/06, Andreas Raab <andreas.raab@...> 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]

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 <andreas.raab@...> 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 <johnmci@...> 1-800-477-2659
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

[tim Rowledge]

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; tim@...; http://www.rowledge.org/tim
World Ends at Ten! Pictures at 11 on Fox News!

[John M McIntosh]

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; tim@...; http://www.rowledge.org/tim
> World Ends at Ten! Pictures at 11 on Fox News!
>
>

--
========================================================================
===
John M. McIntosh <johnmci@...> 1-800-477-2659
Corporate Smalltalk Consulting Ltd.  http://www.smalltalkconsulting.com
========================================================================
===

[Andreas Raab]

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

[tim Rowledge]

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; tim@...; http://www.rowledge.org/tim
CChheecckk yyoouurr dduupplleexx sswwiittcchh..