lookupMethodInDictionary hash hit ratio issue?

Dan Ingalls Dan.Ingalls at disney.com
Mon Mar 5 23:59:31 UTC 2001


>I had a few hours over the weekend on a plane to poke about in the VM 
>and had a question about lookupMethodInDictionary. This gets calls to 
>find a method in a class if the method cache doesn't contain the 
>entry when you do a message send.
>
>The algorithm uses a hash to lookup an entry in a dictionary. Now I'm 
>not sure what the original objectives were but when I looked at the 
>hit ratio I was surprised to see that after running the VM for a 
>while I got
>
>number of calls to lookupMethodInDictionary = 488,549
>number of probes ----------------> 934,247
>number of times found the method = 193,236
>number of times found nil object = 295,313
>number of times lookup wrapped to end of dictionary = 4,204
>
>What is interesting here is the ratio of probes to calls is 1.91. I 
>would have expected say 1.1. I think this implies the current hash 
>isn't quite as good as it should be? So does anyone have some 
>thoughts on this?

John -

I think your expectation of 1.1 is for a single method table, in which you expect to find a hit.  But *many* message lookups fail as the VM goes running up the superclass chain.  That is why the method cache is so important.  If you're expecting failures, then you can get close to 1, but you need a much sparser dictionary to achieve it.  There's no doubt you can improve this statistic, but it will make the image larger.  We've always leaned toward close packing becuase the method cache does a pretty good job of short-circuiting this lookup.  It's been a while since I checked, but it used to give better than a 95% hit factor.  There again, you will find a slightly high probe ratio, but in that case it is due to an algorithm that allows for easy selective removal.

Hope this helps

	- Dan






More information about the Squeak-dev mailing list