Xref: utzoo comp.lang.c++:12408 comp.object:2843 comp.lang.objective-c:211
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!pacbell!m5!tma
From: tma@m5.COM (Tim Atkins)
Newsgroups: comp.lang.c++,comp.object,comp.lang.objective-c
Subject: Re: Static typing and OOP efficiency
Message-ID: <4679@m5.COM>
Date: 22 Mar 91 20:02:30 GMT
References: <1991Feb16.121825.15353@gpu.utcs.utoronto.ca> <27BFDF44.3EA6@tct.uucp> <PCG.91Feb19202728@odin.cs.aber.ac.uk> <27C523A2.2155@tct.uucp> <PCG.91Feb27190941@odin.cs.aber.ac.uk>
Reply-To: tma@m5.UUCP (Tim Atkins)
Followup-To: comp.lang.c++
Organization: Object Sciences Corp., Menlo Park, CA
Lines: 51

In article <PCG.91Feb27190941@odin.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:
>
>pcg> 3) Dynamic dispatchin can be made impressively fast, by the use of
>pcg> various tricks (hashed tables, type deductive compilers, clever
>pcg> linkers, hinting and caching).
>
>chip> There's no way, however, that the dynamic dispatching of
>chip> Objective-C can outperform even a virtual C++ member function,
>chip> much less a normal member function, assuming that the C++
>chip> implementor was in her right mind when she wrote the code
>chip> generator.
>
>As to dynamic overloading, C++ has an advantage in that it has manifest
>types with bounded runtime overloading, while Objective C has latent
>types with unbounded runtime overloading. This means that C++ can use
>double indirection into vtbls, where Objective C has to use hash tables
>or caching, hinting, and the like.
>

At my last company I spent a bit of time examining and working on improved
runtime dynamic message binding schemes.  My final dispatcher for Objective
C does a full run-time dynamic bind with only ~20% more time overhead
than C++ uses for its limited form of dynamic binding with known type
family and relative position of implementation info.  The principal change
to the scheme used by Objective C and Smalltalk was to invert the conceptual
lookup table so that the primary index is by message (selector) instead
of by class.   Both classes and selectors are encoded as relative indices
and the actual class/implementation list is further indexed by an
augmented bit-vector with on-bits signifying that the corresponding class
implements the message.    Therefore the principal space cost is the size
of the bit vector.  At a modest decrease in efficiency the bit vector may
be trimmed to only the set of classes that implement the message.  In space
this dispatch mechanism is smaller than that of either Objective C or 
C++.  The mechanism also does not preclude Multiple Inheritance as the standard
Objective C mechanism does.  

Of course the binding time is significantly improved in the presence of compile
time type hints.  The dispatch time is constant unlike in the traditional 
scheme and is twice as fast for a full dispatch as the speed acheived for
a cache hit in the original Objective C dispatcher!


One thing that seems to be forgotten in such comparisons is that the comparison
should not be the ratio of d(A) to d(B) where d is dispatch speed and A and
B are languages but should instead be the ration of (f + d(A)) to (f + d(B))
where f is the time taken for the average method execution.  This of course
assumes that f is comparable in both languages which is the case when 
comparing Objective C and C++ for methods that do normal C-ish things.


- Tim Atkins