lookupMethodInDictionary hash hit ratio issue?

John M McIntosh johnmci at smalltalkconsulting.com
Mon Mar 5 17:28:22 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?


PS
index _ (mask bitAnd: (self hashBitsOf: messageSelector)) + SelectorStart
where
hashBitsOf:
((self baseHeader: oop) >> 17) bitAnd: 16rFFF

or ((16r00020000 >> 17 ) bitAnd: 16rFFF) -> 1
which means in a 16MB image there are only 128 hash locations, but 
this hash is dependent on a random distribution of methods in the 
image based on memory location. However *is* there a tendency for 
methods to cluster near each other (within 128k) if you file a class 
in for example?

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





More information about the Squeak-dev mailing list