Hi Ralph,

On Sun, Jul 19, 2009 at 10:17 PM, Ralph Boland <rpboland at gmail.com> wrote:

> I have been looking at MethodDictionary.
> It seems to have very little to do with Methods.
> It seems to me that a better design would have been
> to have a class VarDictionary which does not use
> Associations (similar to MethodDictionary).
> MethodDictionary would inherit from VarDictionary
> and add the couple of additional methods it needs.
> VarDictionary would then be available for others to use.
>
> Better still would be to have MethodDictionary not
> be a variable class at all but simply use an additional
> variable  "values".  Again MethodDictionary should
> really inherit from a class that provides this service.
> I would use this service in my own code.
>
> Ralph Boland


Actually I think the best representation for MethodDictionary is as a flat
pair-wise sequence of selector and method, sorted by selector
identityHash.

Advantages:

One saves significant space.  There is one less object per method dictionary
(no values array) and no empty space in the sequence.  We shrank the image
by about 8% when we did this for VisualWorks.

Small method dictionaries (say size <= 16 entries) are linearly scanned
without needing to fetch the identityHash of the selector.  This is faster
for small dictionaries because the cost of three memory references in
different places (selector's hash, dictionary's selector sequence,
dictionary's method sequence) is higher on modern machines than the one scan
of the dictionary's contents sequence.

nil looks ot the VM like an empty MethodDictionary so classes with no
methods (there are quite a few) don't need a dictionary object at all.

Disadvantages:
Large dictionaries are looked up using binary search, which can be slower,
because one has to fetch the hash of the selector being probed for to
comp[are it with the message selector's hash.  But this isn't the common
case.

Dictionaries must be grown whenever a selector/method par is added or shrunk
whenever one is removed, but this is rare (only happens when compiling a new
method or removing an old) and can be e.g. batched if creating a new
dictionary (e.g. if loading code form some binary stream).


Something we didn't yet do in VisualWorks is to make the identityHash of a
Symbol dependent on its contents.  If this is done then within images with
the same hash width dictionaries will always have the same order because
selectors will have the same hashes, which means loading binary code can be
faster since the order of the dictionary on disc is the same as in memory.

I plan to implement the above when doing the new image format work later
this year.

2¢

best
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20090720/854c172d/attachment.htm