Re: Overload Resolution in Ada (Re: The Red Language)

[bobduff@world.std.com (Robert A Duff)]

In article <Pine.SGI.3.95.970918180906.18953A-100000@shellx.best.com>,
Brian Rogoff  <bpr@shellx.best.com> wrote:
>My apologies for the off topic post...

Heh?  Surely you jest!

>Out of curiosity, what is the worst case running time(s) of the two pass 
>algorithm(s)?

Umm, I don't know.  I guess you can make it arbitrarily slow.  Are you
asking for O(f(N)), where N is the number of nodes in the expression
tree (in the "complete context", which is a single statement or
declaration or whatever).  Well, I don't think you can answer that
usefully, because it's also affected by the number of currently visible
declarations, and by the symbol table organization, and by the details
of the identifier lookup mechanism, and by the representation chosen for
"sets of possible interpretations".  E.g.:

    procedure P(X: T_1);
    procedure P(X: T_2);
    ...
    procedure P(X: T_10_000);

    X: T1;

    P(X);

Resolving the procedure call is probably going to have to look at 10,000
declarations of P, and we can make it arbitrarily worse without changing
the size of the procedure call.  On the other hand, the compiler could
make this particular sort of case much faster using various tricks.

I suppose you could say the 2-pass algorithm looks at each node O(N)
times (at most twice each), but that's a useless measure, since the
"look at node" operation is an enormously complicated algorithm.  Symbol
table lookups in compilers often have pretty good average time, but
horrible worst-case time.  A hash table is linear in the worst case, for
example, making a compiler O(M*N) overall (even without overloading),
where M is the number of decls, and N is the number of references.  A
compiler isn't a hard real-time program, so people tend to worry about
average or typical case times more than worst case times.

Well, maybe it's not totally useless.  I guess I would worry if the
compiler had to look at each node O(N**2) times.  Hmm.  N isn't usually
very big in Ada, since it's not an expression language, but it can be --
I've seen things like "X := (... 10_000 component positional aggregate ...);"
in machine-generated code.  Note that Ada has a special rule for
aggregates -- the compiler has to figure out the type of the aggregate
*before* looking inside it.

Anyway, in an *optimizing* compiler, overload resolution is probably not
the bottleneck.

- Bob