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
|