hoodwink.d enhanced


Minimizing Row Displacement Dispatch Tables #

by babie in inspect

Translated from matz blog, 2005-02-21:

This report is old, but I didn’t know.

For implementing Dynamic Dispatch, the technique that uses the dispatch table like Virtual Table(VTABLE) of C++ is often used in statically-typed language. This is because a statically-typed language has properties such as “fast” and “abundant infomation on compile”.

The above-mentihoned report are written about applying such a dispatch table technique to a dynamically-typed language like Smalltalk. It’s considered about the point how it deals when a class or method is dynamically added.

Novel points are:

  • It compress two dimensional tables(class x selector) to one dimensional one. It sorts a sparse table, and it stores elements in desc order. It uses the offset to get.
  • When compressing the table, though it is usually splitted by class, this report recommends to split by selector. Therefore, the efficiency when updating is up because adding a selector ends only adding a line.
  • When a class is added, it deals by using two or more dispatch tables (fall-back the 2nd table by method_missing). Though a new class is a little slow, it’s possible to gain a whole perfomance. In an idle moment, it restructures dispatch tables.

The effeciency seems to be quite good. However, it may be that this technique is inefficient on like Ruby that has a open class, an existing class can be added the method, by increasing table-restructuring.

I think how to solve it.

said on 28 Feb 2005 at 13:52


Keep in mind that I got B’s and C’s in Math class. ;)

said on 28 Feb 2005 at 14:54

I don’t think it’s the math that’s causing the problem.

goes in search of “Teach Yourself Japanese In 24 Hours”

said on 28 Feb 2005 at 15:26

Interesting approach. One wonders if it wouldn’t just be simpler and faster to cache the results of method search, and to have modifications of the class tree invalidate the appropriate cache entries, if any.

said on 28 Feb 2005 at 15:53

Jason: I think Ruby already does exactly that. So if matz is thinking about this it will likely have advantages over that scheme. Perhaps we’ll see something like this in YARV soon?

said on 28 Feb 2005 at 20:48

Please give me “Teach Yourself English In 24 Hours”.

Well, this translation is more difficult than ever. I couldn’t read the all of report. Please refer it.

said on 28 Feb 2005 at 21:18

This shows I’m always seeking a better way, not that I chose this scheme.

said on 01 Mar 2005 at 13:31

It is cited by a few people if that helps.

said on 02 Mar 2005 at 05:29

I don’t get why open classes would make this inefficient – one defines methods so much less frequently than one calls them that I’d think you could afford a complete rewrite of the table every time a method was added.

said on 14 Feb 2006 at 10:35

I agree – or use the two level table approach and do a table compression when the user demands it.

Comments are closed for this entry.