Re: Information on dispatch-techniques

Here is the summary of the answers I got to my question:
>
> I'm looking for papers/information on different dispatch techniques
> for object oriented languages. I'm interesting in everything from the
> most efficient to the most flexible. I'm also interested in any
> measurements made on the efficiency of the different techniques.
>


Thanks to all the people who replied:


"Stanley R. Allen" <s_allen@hso.link.com>
gaigner@VNET.IBM.COM
evan cheng <evan@servtech.com>
Karel Driesen <karel@cs.ucsb.edu>
pardo@cs.washington.edu
Sam Kendall <kendall@cybercom.net>
vitek jan <jvitek@cui.unige.ch>
Anthony Green <green@cygnus.com>
Bruce Ediger <bediger@csn.net>




From: "Stanley R. Allen" <s_allen@hso.link.com>


There is an interesting paper on an Ada95 implementation
of dispatching at http://www.gnat.com, "Ada 9x Tagged Types
and their implementation in GNAT".




From: gaigner@VNET.IBM.COM


Karel Driesen has written a paper that summarizes dispatch techniques.
You should look for his homepage which is somewhere at the UCSB.


It might be: www.cs.ucsb.edu/~karel




From: evan cheng <evan@servtech.com>


See Karel Driesen's master thesis: "Method Lookup Strategies in
Dynamically Typed Object-Oriented Programming Languages."
http://www.cs.ucsb.edu/oocsb/papers/Mthesis93.html


Evan




From: Karel Driesen <karel@cs.ucsb.edu>


On my homepage (http://www.cs.ucsb.edu/~karel) you'll find references
to a master's thesis, a survey paper, and a number of other publications
that deal with this.


The survey paper was presented at ECOOP'95 and it has an outline of most
current techniques, and the references section has most publications
in the field, so it is a good place to start.




From: pardo@cs.washington.edu


A bunch of the SmallTalk papers are good. I'd start poking around
OOPSLA proceedings. Also, Deutsch-Schiffman is a classic (though it
doesn't say a lot, it says it well).


%A Peter Deutsch
%A Alan M. Schiffman
%T Efficient Implementation of the Smalltalk-80 System
%J 11th Annual Symposium on Principles of Programming Languages
(POPL-11)
%D January 1984
%P 297-302




From: Sam Kendall <kendall@cybercom.net>


There was a thorough paper in the most recent OOPSLA on dispatch
overhead in C++ using the two most common techniques of that language.
Papers on the implementation of Smalltalk and Self might also be of
interest.




From: vitek jan <jvitek@cui.unige.ch>


Hello,


You can probably find references to many of the exsting techniques
from the reference list at the end of my master thesis. For slightly
more recent work there is ECOOP paper and a CC paper.


All of the above to be found at:
http://cuiwww.unige.ch/OSG/Vitek/Publications/index.html




From: Anthony Green <green@cygnus.com>


When I was working on OO method dispatch code, I based most of my
work on these papers:


Agrawal, DeMichiel and Lindsay, "Static Type Checking of Multi-Methods",
OOPSLA '91, pp. 113-128


Urs Holze and David Ungar, "Optimizing Dynamically-Dispatched Calls
with Run-Time Type Feedback", SIGPLAN Conference on Programming Language
Design and Implementation, June 1994


The language I was implementing supported multi-methods, so the first
paper was particularly useful. The second one describes one technique
for making it fast.




From: Bruce Ediger <bediger@csn.net>


Here's what I had lounging in my notebooks. I'm sorry the citations
are so vague: I mostly ftp'ed postscript files and printed them.


There's another paper I thought I had but couldn't find. It had something
to do with in-memory layout of C++ objects and vtables. I think one
of the authors is named "Pugh", but I can't find the paper or a citation.


If you get any more suggestions, would it be possible for you to post
a summary of what you get to comp.compilers? I would be appreciative
of such an effort.


"Optimizing Message Lookup in Dynamic Object-Oriented Languages
  with Sparse Arrays"
Kresten Krab Thorup
    This appeared in some proceedings of a conference held in Russia,
    and Thorup worked at NeXT last time I heard. I wish I could give you
    a better pointer to this one. It's about Objective-C method dispatch.


The "SELF" implementation papers at <http://self.smli.com/papers/papers.html>
would appear to be of interest, particularly the one at:
<http://self.smli.com/papers/implementation.html>
"An Efficient Implementation of Self, a Dynamically-Typed Object-Oriented
  Language Based on Prototypes"
Craig Chambers, David Ungar, and Elgin Lee
OOPSLA '89 Conference Proceedings, pp. 49-70, New Orleans, LA, October, 1989.
Published as SIGPLAN Notices 24(10), October, 1989. Also published in
Lisp and Symbolic Computation 4(3), Kluwer Academic Publishers, June, 1991.


"Measurement and Application of Dynamic Receiver Class Distributions"
Charles D. Garrett, Jeffery Dean, David Grove, Craig Chambers
University of Washington Technical Report 94-03-05, May, 1994


"Quantifying Behavioral Differences Between C and C++ Programs"
Brad Calder, Dirk Grunwald, Benjamin Zorn
Univeristy of Colorado Technical Report CU-CS-698-94


"Do object-oriented languages need special hardware support?"
Urs Holzle, David Ungar
University of California, Santa Barbara, Technical Report TRCS 94-21




From: Bruce Allen Ediger <metamatic!ediger@uucp-1.csn.net>


I just found another paper that may be of interest, yet has such a poor
citation that you won't be able to find it:


"On Object Layout for Multiple Inheritance"


  William Pugh, pugh@cs.umd.edu and Grant E. Weddell,
  gweddell@watdragon.uwaterloo.edu


This one doesn't even have a tech report number or anything on it.
The abstract claims it's an extention of work done for:


    "Two-directional record layout for multiple inheritance"
    Proceedings of ACM SIGPLAN Conf. on Programming Language Design
    and Implementation, pp 85-91, June, 1990


by the same authors.


I can only tell you that I ftp'ed a PostScript file from some place,
and printed this paper.


The paper deals with placing members of C++ objects that have multiple
inheritance so as to greatly decrease the time to access them. Peripherally
related to method dispatch, I suppose, but if a member function has to be
looked up before invocation, this might be a clue as to an alternative
way of doing it (rather than "vtbl").






[ This response is heavily edited. The bibliography used in this
news-article is contained in one of Jan Vitek's latest papers
available from hits home page. The article is over 700 lines so I
don't post it here. Those who would like a copy of it can mail me. It
should be available from a comp.lang.objective-c archive, but I
couldn't find any.]


Bruce Allen Ediger <metamatic!ediger@uucp-1.csn.net> wrote:


I found an old usenet article about method dispatch in Objective-C.


The bibliography this guy includes may be more interesting than his article.


Article 1595 of comp.lang.objective-c:
From: jvitek@cui.unige.ch (Jan VITEK)
Subject: Dynamic Binding Speed and Optimization
Organization: University of Geneva - CUI
Date: Sun, 21 May 1995 23:24:31 GMT




[...]
REFERENCES




The paper by Kresten Krab Thorup can be obtained from


                http://cuiwww.unige.ch/OSG/Vitek/HomePage.html


then follow the link to the *Lobby* and then to *E-Archive*, or use
the direct URL:


                http://cuiwww.unige.ch/OSG/Vitek/Ressources/Archive/index.html


[ The correct URL is
http://cuiwww.unige.ch/OSG/Vitek/Resources/Archive/index.html and I
couln't find it from HomePage.html ]


Some of the other papers mentioned in the references can be found there
as well.


I maintain many links to home pages of researcher in this field:


                http://cuiwww.unige.ch/OSG/Vitek/Ressources/Languages/people.html


My papers are available from:


                http://cuiwww.unige.ch/OSG/Vitek/Publications/index.html
[...]






astor
--
Alexander Kjeldaas
<astor@guardian.no>
Guardian Networks AS
--

Return to the comp.compilers page.
Search the comp.compilers archives again.