NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/object/3271

Internet Message Format | 1992-08-20 | 8.2 KB

Xref: sparky comp.object:3271 comp.lang.clos:675
Path: sparky!uunet!mcsun!uknet!gdt!aber!aberfa!pcg
From: [e-mail] (Piercarlo Grandi)
Newsgroups: comp.object,comp.lang.clos
Subject: Re: Beginner's Question - CLOS
Message-ID: <[e-mail]>
Date: 20 Aug 92 15:37:25 GMT
References: <graham.714230337@galois> <[e-mail]>
    <[e-mail]> <[e-mail]>
Sender: [e-mail] (USENET news service)
Reply-To: [e-mail] (Piercarlo Grandi)
Organization: Prifysgol Cymru, Aberystwyth
Lines: 155
In-Reply-To: [e-mail]'s message of 20 Aug 92 00: 05:29 GMT
Nntp-Posting-Host: aberdb

On 20 Aug 92 00:05:29 GMT, [e-mail] (Barry Margolin) said:

barmar> (Eric Smith) writes:
barmar> [Regarding dispatching on multiple arguments]

Smith> But doesn't that make method dispatch very time consuming?  It
Smith> seems like it would involve searching for the method in tables,

Yes, what really happens is that overload resolution is *always* done by
having a table, say something like a relation (operator, signature,
implementation). In single-method overload resolution one knows that the
'signature' is always just a single typename, so one can just cluster
the full table by that column and split it into subtables, where each
subtable contains all the (operator, implementation) pairs for a
typename. Then if dinamic overload resolution is done the table must be
made available to the runtime overload resolutor agent, and it gets
called 'vtbl' in C++ or 'method dispatch table', else it can just exist
only for the duration of compilation.

But even if one does not restrict overloading to the type of the first
argument, there are lots of ways to exploit regularities in the
(operator, signature, implementation) overload table, both at compile
time and run time. At worst, at program linking time, one can glue
together all the tables for all the sepratarely compiled modules, and
build a global hash table. This is what Eiffel implementations do at
system build time for certain reasons of their own, even if they don't
have multiple overloading.

Smith> and that the amount of time consumed would depend on how many
Smith> methods were in those tables and how many class arguments each
Smith> method had.

Not quite. What happens is that the search is now based on a longer,
composite key, but I surmise that it is not the length of the key that
domaintes the cost of the search, it is the table size and its
clustering.

Indeed this usually applies too:

barmar> Most generic functions don't have many methods defined for them,
barmar> so the tables generally aren't very large.  Most implementations
barmar> (including PCL, the portable implementation) employ caches so
barmar> that you don't frequently have to do the full search.  The cache
barmar> is usually a hash table keyed off the argument classes; [ ... ]

Even if strictly speaking it is not really anything special about
multiple overloads. The same techniques are applied for single
overloads, when the overloading can be more or less unbounded, e.g. in
Smalltalk and Objective-C.

The only difference really between multiple and single overloading is
that multiple overloading requires searches using a composite key. Quite
orthogonal to this is the problem of whether overloading is static or
dynamic, and bounded or unbounded:

Smith> In C++, method dispatch is trivial to the CPU, such that on most
Smith> modern CPU's it would take a fraction of a microsecond.

This is mostly because overload resolution is yes dynamic, but bounded,
in that dynamic overload resultion can only be done among objects
belonging to classes in the same inheritance line; when this is true,
then we can partition the overload resolution table into smaller tables,
one for each line.

When instead this condition is weakened, as for example in C++ for
multiple, maybe virtual, inheritance, things get much more difficult,
and are solved more or less haphazardly with larger tables (as
essentially the acyclic inheritance graph is really converted to a tree
by copying shared subtrees), which may or may not be appropriate.

Smith> I can see the advantages of dispatching according to the types of
Smith> multiple arguments, but I'm just wondering how much of a speed
Smith> impact it has.

In itself, _none_. C++ for example already has it, in the form of static
overload resolution (you can well declare friend functions that are
overloaded on multiple arguments, for example), and since it gets
entirely resolved at compile time, it costs nothing at run time.

Bounded dynamic multiple overload resolution is going to cost the same
as bounded dynamic single overload resolution, and so on.

In saying above that probably it is not the lenthening of the search key
that dominates the cost, I think that the real is related to the
'unbounded' and to the 'dynamic', not to the 'multiple' aspects of
overload resolution.

But, but: available evidence suggests that using the techniques
mentioned by Margolin, even unbounded and dynamic overload resolution,
whether multiple or single, is speedy enough. Studies of Smalltalk and
Objective-C code and implementations show that in the common case there
are fairly predictable overloading patterns, and with a little care the
overhead of overload resolution can be made a small part of the cost of
running a program.

I have read of several instances, especially for application
programming, where Objective-C or Smalltalk code was competitive with
C++ code in speed, even if, thanks to the *possibility* of dynamic and/or
unbounded overload resolution, the flexibility was much greater.

In general, while not thinking that it has anything to do with OOness,
dynamic/unbounded overload resolution (aka "latent/dynamic typing" in
some circles) has serious advantages and is less expensive than commonly
expected:

Smith> In C++ the same functionality requires more code, but it seems
Smith> like it would still be faster.

Probably not, because it amounts to a particular implementation of table
squeezing and searching for multiple bounded overload resolution, and
one that is too rigid, and also probably inefficient; more on this
later.

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

barmar> [ ... the usual Smalltalk like, seedy N>1 level dispatch trick,
barmar> where resolution for overloaded arguments for N>=2 is
barmar> implemented by hand by the programmer ... ]

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

Fully agreed. Another way to put it is that this is not *direct* support
of multiple overloads; it is just like using switches instead of virtual
functions for resolving single overloads.

Also it might be quite inefficient, as it creates an overload resolution
tree, where the tree might well be thin and tall, which is bad for
search trees. It is often more efficient to just hash, in this case.

  Explanation: if we must search on keys K1,K2,K3,... we can build a
  search tree, with all the values of K1 at the first level, then with
  those of K2 appended, and so on. But if the Kns are sparse, this
  creates a bad or unbalanced tree. It might often be more efficient
  have an hash table, keyed by  HASH_N(K1,K2,K3,...), as Margolin
  mentions above.

The fact that a tree is built is just a squeeze of the general
(operator, signature, implementation) table, one done taking advantage
of the fact that in C++ dynamic overloading is bounded.

A generic overload resolution system could well analyze the table for
regularities and just obtain the same effect automatically.  I think
that some CLOS implementation do that (aided by the fact that after all
more or less regrettably CLOS does have a notion of inheritance, even if
it is somewhat ennobled by the possibility to redefine in a quite
general way the metaobject protocol).
--
Piercarlo Grandi                   | JNET: [e-mail]
Dept of CS, University of Wales    | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: [e-mail]