Re: Templates in C++

Norman Ramsey <norman@flaubert.bellcore.com> wrote:
>I can't resist pointing out that one of the joys of programming in
>Standard ML is that you can get this kind of polymorphism without any
>unsafe casting and without replicating code. It works because the ML
>type system is powerful enough that you can write functions to operate
>on values of type 'a list (pronounced ``alpha list''), which stands
>for any list type. A single instance of each function suffices for
>all possible list types, and the proper use of these functions is
>checked statically.


Modern implementations of ML (such as SML/NJ versions 103 and higher,
Xavier Leroy's Gallium compiler, and our own Til compiler) make it
possible to represent polymorphic data structures in non-uniform ways
(i.e. unboxed) and this has been found to have a significant impact on
both space and running time of programs. In effect, many of the ideas
of templates are carried over to a modern ML implementation, resulting
in many of the same problems with code bloat that you get for C++
templates. The big difference is that the compiler can change
representations (i.e. choose boxed/unboxed, rearrange fields for
maximal alignment, etc.) to mitigate the costs -- in C++, you're stuck
with the representation that the programmer chooses because there are too
many ways to "observe" a change in representations.


Furthermore, modern ML implementations, unlike C++, deal with issues
of true separate compilation. In particular, they do _not_ require
that you suck in your template definitions into each source file that
uses the template. This means that you do not have to recompile a
client of an abstraction each time the implementation changes. However,
when representations are held abstract across compilation boundaries,
the resulting code is slower. For SML/NJ and Gallium, more boxing
and unboxing results. For Til, more run-time type dispatch occurs.
The result is that the programmer can choose: fast code or fast compile.
For C++, you have one choice: fast code and slow compile (relatively
speaking of course).


Finally, the same link-time optimizations (like collapsing all of the
template instantiations down to a minimal set [glorified common subexpression
elimination] or doing link-time type dispatch, etc.) are all applicable to
both languages and seem to be increasingly important.


So, in summary, modern ML and C++ implementations are actually converging.
Furthermore, we see many of the same "bad" dynamic properties introduced
by both languages, like more indirect jumps, small basic blocks, etc.
I'm just waiting for the first join implementation conference :-)


-Greg Morrisett
  jgmorris@cs.cmu.edu






--

Return to the comp.compilers page.
Search the comp.compilers archives again.