chased@rbbb.Eng.Sun.COM (David Chase) (03/13/91)
I've been trying to follow this discussion, but there's a bit too much
heat and a little too little content. Could someone please sit down
and take the time to summarize what appear to be the two positions?
Now, a small contribution. I implemented the C-generating back-end
for Modula-3 back when Olivetti had a research center in Menlo Park.
The language specified a "TYPECODE" for each type. These were
implemented with substantial support from the language system. The
major differences (for purposes of this discussion) between M-3 and
C++ are:
1) C++ has multiple inheritance, Modula-3 does not.
2) Modula-3 has more "interesting" ways to do information-hiding
(Strictly speaking, the compiler might not know where member fields
or functions are located. This can be resolved at (pre-)link
time.)
3) M-3 has no constructors or destructors (yet).
4) In M-3, ALL member functions are virtual.
Things to note:
a) If all member functions are virtual, the run-time cost for typecodes
is as small as it can get. That information can be stored in the
virtual function table at little cost.
b) The (known) lookup algorithms for single inheritance are much
simpler and cheaper than those for multiple inheritance. "Is x a T"
can be implemented with two comparisons. "TYPECASE" is more complex,
but take time O(log # cases). The data structure implementing these
things can be updated in the event of dynamically-loaded code (with
new and old types in it) in a multi-threaded system, with minimal
synchronization requirements (readers must see writes in the same
order than writers make them -- NARROW sometimes takes longer in the
event that a race is lost, but it never lies).
c) TYPECASE is NOT equivalent to "switch".
d) TYPECODES are NOT necessarily repeated from run to run. Thus, they
are not useful by themselves for saving and restoring pickled
data. (What if you relink in a different order? The data should
still be good, etc.)
We used this information to help implement a "pickling" (storing data
to disk) system. The pre-linker also generated "fingerprints" which
were in fact large (63-bit?) numbers carefully hashed from the
structure of a type, and these served to identify types from run to
run. (We cheated, and did not also write out the type strings, so
there was a vanishingly small probability of our algorithm being
thwarted.)
At run-time, the interface went from [type or object] to typecode to
type-fingerprint. The typecodes might vary, but the fingerprints did
not. To read the data back in, fingerprints were mapped to typecodes
which gave access to a (low-level) interface to virtual function
tables, object size information, user-defined (*) unmarshalling code,
etc.
(*) the default marshalling and unmarshalling code was automatically
generated by a language-processing tool. It is also possible to
perform a slower interpreted unmarshalling based on the structure of
the type. Again, this information is stored behind an interface which
makes use of TYPECODEs.
A second use for typecodes was in implementing a verifiable type case
("NARROW") and TYPECASE. One can argue that TYPECASE is not
object-oriented (I understand that argument, and TYPECASE clearly
becomes less necessary if you have correctly working multiple
inheritance), but NARROW appears to be necessary fairly often in C++
code (perhaps less so when templates are added, but I don't have any
experience with that, so I can't be sure).
We didn't use typecodes for garbage collection, but that was because
(i) it would have been too inefficient and (ii) we never had the time
to do that much engineering of the garbage collector. In principle,
however, the information to help the GC could be attached to the
virtual function table along with the typecode.
----------------------------------------------------------------
In summary, TYPECODEs were fantastically useful, even if their only
use was to provide a nice name for a type in the interface to run-time
information about types. Please consider the value of an interface to
run-time type information that actually hides some of the
implementation details.
I also think that the language system should support these features,
but that is probably a religious argument. Certainly, if nifty
features are confined to objects with vptrs the costs can be kept low.
David Chase
Sunjimad@microsoft.UUCP (Jim ADCOCK) (03/15/91)
In article <9661@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: |I also think that the language system should support these features, |but that is probably a religious argument. Certainly, if nifty |features are confined to objects with vptrs the costs can be kept low. Help me out. The obvious implementations to me would be either to store such information in a given vtable slot [slot "0" say] or indirect via a vtable function that is always automatically defined [for classes that support runtime type info.] Either approach would seem to defeat the not-too-uncommon situation in C++ where two classes can share a vtable in common. Or am I missing something?
chased@rbbb.Eng.Sun.COM (David Chase) (03/19/91)
In article <71305@microsoft.UUCP> jimad@microsoft.UUCP (Jim ADCOCK) writes: >In article <9661@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: >|I also think that the language system should support these features, >|but that is probably a religious argument. Certainly, if nifty >|features are confined to objects with vptrs the costs can be kept low. > >Help me out. The obvious implementations to me would be either to >store such information in a given vtable slot [slot "0" say] or >indirect via a vtable function that is always automatically defined >[for classes that support runtime type info.] Either approach would >seem to defeat the not-too-uncommon situation in C++ where two classes >can share a vtable in common. Or am I missing something? No, you're not missing anything. That's the technique I'd use. I wasn't aware that space consumed by a vtables was a big deal, except in those cases where the compilation-and-linking system produced many vtables for a single class (I've heard about that). How big do vtables usually get, how often can they be shared, and (given a one-per-class implementation) how much space does this sharing usually save? David Chase Sun
jimad@microsoft.UUCP (Jim ADCOCK) (03/23/91)
In article <9997@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM (David Chase) writes: |No, you're not missing anything. That's the technique I'd use. I |wasn't aware that space consumed by a vtables was a big deal, except |in those cases where the compilation-and-linking system produced many |vtables for a single class (I've heard about that). How big do |vtables usually get, how often can they be shared, and (given a |one-per-class implementation) how much space does this sharing usually |save? I guess I'm not convinced either that inability to share vtables is that big a deal. However, size of vtables can be limiting in the kind of programming that implements many many methods per class, and only changes a few methods when deriving [ala Smalltalk.] In such situations, vtable costs can be large compared to the code size of the few methods being changed. For right now, C++ programmers avoid the problem by not using such a coding style. Eventually, smarter compilers may be necessary that know how to dispatch methods using a variety of techniques automatically chosen to match the situation. A simple example: at the cost of an additional indirection, vtables could be broken into subtables, and the common subtables shared between classes. When a method is overridden, only the subtable needs to change, not an entire vtable. Still, I don't think the situation comes up often today where a C++ programmer would be willing to pay an additional indirection on every dispatch in order to get smaller vtables.