From: barmar@think.com (Barry Margolin)
Newsgroups: comp.object,comp.lang.clos
Subject: Re: Beginner's Question - CLOS
Date: 20 Aug 1992 00:05:29 GMT
Organization: Thinking Machines Corporation, Cambridge MA, USA
NNTP-Posting-Host: telecaster.think.com

In article <1992Aug19.213818.21709@tfs.com> eric@tfs.com (Eric Smith) writes:
[Regarding dispatching on multiple arguments]
>But doesn't that make method dispatch very time consuming?  It seems like
>it would involve searching for the method in tables, and that the amount
>of time consumed would depend on how many methods were in those tables and
>how many class arguments each method had.

Most generic functions don't have many methods defined for them, so the
tables generally aren't very large.  Most implementations (including PCL,
the portable implementation) employ caches so that you don't frequently
have to do the full search.  The cache is usually a hash table keyed off
the argument classes; the first time a particular tuple of argument classes
is used, the effective method is computed (this requires finding all the
methods applicable to the argument classes or any of their superclasses)
and stored in the cache.  So method dispatching is unlikely to be an inner
loop bottleneck, since the computation will probably only have to be done
the first time through the loop.  Many implementations also provide a way
to prefill the cache, by running the program a few times and saving out all
the caches that were built.

Note that it's also necessary to search a table in Flavors, the most
prevalent OO extension to Lisp prior to CLOS, even though it dispatched on
a single argument.  In Flavors, the class has a table that maps message
names (or generic functions in New Flavors) to combined methods, while in
CLOS the generic function contains a table that maps class tuples to
methods.

>In C++, method dispatch is trivial to the CPU, such that on most modern
>CPU's it would take a fraction of a microsecond.  I can see the advantages
>of dispatching according to the types of multiple arguments, but I'm just
>wondering how much of a speed impact it has.  In C++ the same functionality
>requires more code, but it seems like it would still be faster.  For
>example, a terminal object's display function would take a base class of data
>as its argument, and then it would get the data converted to its requirement
>by invoking a conversion method on the data object.  That conversion method
>would be known to the terminal object at compile time, so the resulting code
>would involve no lookups other than the initial sub-microsecond dispatch to
>the terminal object's display function, followed by the sub-microsecond
>dispatch to the data objects's conversion function for that terminal object's
>data format.

I've seen discussions about this in comp.lang.c++ and comp.object, and I
don't think there's a way to get real dynamic dispatch on multiple
arguments in C++.  The usual way people try to implement this is with
something like:

class Displayable {
    public:
	virtual void Terminal_display(Terminal*);
	virtual void Window_display(Window*);
}

Terminal::display(Displayable *object) {
	object->Terminal_display(this);
}

Window::display(Displayable *object) {
	object->Window_display(this);
}

The problem with this is that the list of possible destination classes is
hard-coded into the Displayable base class, rather than being extendable.

This isn't the same as your suggestion to have the display() methods
convert the object argument, but that has similar limitations; in that
case, the list of possible displayable classes would be hard-coded into the
display() methods, by virtue of it having to explicitly call the
appropriate conversion function.
-- 
Barry Margolin
System Manager, Thinking Machines Corp.

barmar@think.com          {uunet,harvard}!think!barmar
Newsgroups: comp.object