Hi everybody,
    I'm writing my master's thesis and I would like some advise from you.
(This mail may be a little bit long)

    I've been reading some papers on how to make Smalltalk and Self run
faster. I have an idea on how to make the Smalltalk message lookup faster,
but before doing anything, I would like to have some feedback from you. I'll
try to write a short description of my idea.

    I think that to make the method lookup faster, the following points
should be addressed:
    1) The algorithm that looks for a method should avoid asking the
superclass for a method's implementation if the current class does not have
it.
    2) Store the implementation of a method in a fast search structure. A
MethodDictionary is fast, but if the element I'm looking for is not in the
first slot, I have to continue looking for it until I found it or I reach
the end of the dictionary. (This is really bad for messages that are
implemented in superclasses and not in subclasses)

    If I could minimize the search in point 2) and 1)... The ideal situation
would be an implementation similar to the "virtual tables" of C++. But that
it is impossible in Smalltalk because it does not have types...
    So I thought that maybe instead of asking a class for the implementation
of a selector, I ask the selector for the implementation for a given class.
In this case, the "selector" would be like the "type"...
    The selector should have a method that returns its implementation for a
given class. This method could have different "strategies" depending on
the amount of classes that implement the selector, how often a selector is
used for a given class, etc.
    To avoid point 1)  a selector should have the implementation of all the
subclasses of the class the defines the selector, even thought, the
subclasses do not overwrite it. (This could make the structure too big...)
For
example, class A defines method m1. Class B subclasses A. The search
structure of m1 should have a reference of the compile method of class A and
for class B, that will in this case, be the same because B does not
overwrite m1.
    To avoid point 2) I was thinking of having a class dictionary based in
the idea that each class has a unique
hashcode and that if there is a collision (that is, two classes could be in
the same slot) it will resize the structure instead looking for an empty
slot. Another structure could be binary trees based on the number of times a
message is sent for a specific class, etc.
    Also, I started to have questions like, how would affect this new
structure to the idea of PICs (polimorphic inline cache), splitting, the
method cache, etc.?
    Anyway, any lead to information, paper or research done about this would
be a great help.
    Any comment (good or bad) will be appreciated also.

    Thank you,
    Hernan.

PS: I know that making the message look up faster will not affect directly
the performance of the VM.

_____________________________________________
Hernán A. Wilkinson
BitX S.A. Argentina
Phone: (54-11) 4574-1544  Fax: (54-11)4573-3368
Franco 3419 . 1er piso - (1419)- Buenos Aires - Argentina
Web: www.bitx.com.ar