Re: Real OO

[donh@syd.csa.com.au (Don Harrison)]

Norman wrote (responding to Joachim):

:> The results
:> presented by Calder and Grunwald in their 1994 POPL paper are different.
:> Among other things, they measured:
:>
:>    1. the percentage of indirect function calls executed during their
:>       experiments that invoked methods that were never overridden
:>       (a condition that it is, in principle, straightforward to detect
:>       at link time, but not sooner)
:>
:>    2. the percentage of indirect function calls executed during their
:>       experiments at call sites from which only one target was invoked
:>       during THAT execution of the program
:>
:> ...
:>
:> Calder and
:> Grunwald describe Measurement 2 as an upper bound on the number of
:> dynamic calls that could be turned into static calls by powerful
:> interprocedural optimizations, and Measurement 1 as the lower bound we
:> would expect of such optimizations, since that much improvement can be
:> achieved even by a naive interprocedural optimization.  The mean values,
:> over the programs they measured, were 31.6% for Measurement 1 and 66.3%
:> for Measurement 2, a far cry from your Booch's 80%.

To get a real idea of (theoretical) relative performance of dynamic binding
compared to static binding, you need to know:

1) What is the relative performance of indirect calls as a fraction of the 
performance of direct calls. Are they 50% as efficient?, 40%?, 60%?, 70%?.

2) Are the above statistics (for C++?) the same for Eiffel and Ada?

If we assume the statistics hold for Eiffel and Ada (which I wouldn't care to), 
the average relative performance of an optimised dynamic call compared with a 
statically bound call might be given by:

%P_db_to_sb = ( (%_opt * 1) + ( (100 - %_opt) * %P_ind) ) / 100

where 
  - %_opt is the percentage of dynamic calls that are optimised into static calls
  - %P_ind is the percentage relative performance of an indirect call compared
       to a direct call.

This gives the following table of values for %P_db_to_sb:

         %_opt |  32  |  40  |  50  |  60  |  66
%P_ind         | 
----------------------------------------------------------------------
40             |  59  |  64  |  70  |  76  |  79
50             |  66  |  70  |  75  |  80  |  83
60             |  73  |  76  |  80  |  84  |  86
70             |  80  |  82  |  85  |  88  |  90
80             |  86  |  88  |  90  |  92  |  93

Has anyone got any reliable statistics on %P_ind?
Are any Eiifel vendors willing to offer values for %_opt?

Note that this IS NOT an indication of relative performance of Eiffel to Ada.
The statistics would apply equally well to both languages for equivalent code.

Also, performance compared with complete static binding would be better than
this because it excludes frozen declarations.

-----
Hardware is out of my depth but what I'm wondering is whether the hardware could
optimise by determining the indirection ahead of time so that the indirect call 
is effectively reduced to a direct one. If this were possible for 100% of calls 
(which I doubt), there would be no performance penalty for dynamic binding.

Don.