Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg
From: pcg@cs.aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.object
Subject: Re: Examples of Multiple Inheritance?
Message-ID: <PCG.90Dec22154707@odin.cs.aber.ac.uk>
Date: 22 Dec 90 15:47:07 GMT
References: <18090@neptune.inf.ethz.ch>
	<1990Dec13.035418.28040@Neon.Stanford.EDU> <47353@apple.Apple.COM>
	<1990Dec17.223306.25756@Neon.Stanford.EDU>
Sender: pcg@aber-cs.UUCP
Organization: Coleg Prifysgol Cymru
Lines: 65
Nntp-Posting-Host: odin
In-reply-to: craig@Neon.Stanford.EDU's message of 17 Dec 90 22:33:06 GMT

On 17 Dec 90 22:33:06 GMT, craig@Neon.Stanford.EDU (Craig D. Chambers) said:

craig> In article <47353@apple.Apple.COM> lins@Apple.COM (Chuck Lins) writes:

lins> In article <1990Dec13.035418.28040@Neon.Stanford.EDU>
lins> craig@Neon.Stanford.EDU (Craig D. Chambers) writes:

craig> If you're concerned about space overheads of MI, other implementations
craig> of MI than the one in C++ 2.0+ have low space overheads, comparable to
craig> pre-MI C++ implementations (i.e. a word or two extra per object).

This is not strictly true: the space overhead of MI in C++ 2.x when
implemented without code thunks is not in the object, but in pointers to
virtual member functions for the object's class. Also, multiple
virtual inheritance also requires N-1 extra pointer words in the object
for each suboject inherited virtually inherited N times.

lins> Could you provide some examples or references to papers describing
lins> such implementations? For some of us this (oo research) is a
lins> part-time endeavor and we don't always have the time to read every
lins> single paper. (Our limits, not yours.) Thanks in advance.

craig> Languages based on separate hash tables for message lookup (like Self,
craig> Smalltalk, many Lisp-based systems, Trellis/Owl, and (I think) Eiffel)
craig> can use one extra word in the beginning of the object to identify the
craig> object's run-time type.

Or they can use a BIBOP system and thus tagging the address space
instead of the data space (the tag is contained not in the object's
contents but in its location). In other words they would be using hash
linking, a little known but useful technique.

craig> This could either be a pointer to a class object, an invisible
craig> map object as in Self, or a table of defined methods.  No extra
craig> words per object are needed.

So, in a BIBOP implementation, we could have *in theory* zero space
overhead multiple inheritance.  But this is only because of an illusion,
unfortunately.

craig> C++'s MI implementation is designed to trade away some space per
craig> object to get faster message lookup

No, the "problem" is that in C++, but for one case, all components of an
object, whether inherited or not, are expanded inline, and functions are
not dynamically overloaded by default.

In the languages you mention functions are dyncamically overloaded by
default and subobjects they are accessed by a very convenient extra
level of indirection. The extra overhead of MI is thus absorbed in these
two already existing overheads. As Dave Weinreb remarks in another
article, there is an overhead of one pointer for every member of a CLOS
object, for example.

In C++ the one exception is virtual multiple inheritance, which indeed
causes problems, because it means that pointers to virtual member
functions must be more complex than otherwise even when not necessary.

In non C++ languages this extra complexity is not explicitly required
for MI because it is already required for other reasons, thus giving
rise to the illusion that MI costs relatively less than in C++.
--
Piercarlo Grandi                   | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk