TEAM-ADA Archives

Team Ada: Ada Programming Language Advocacy

TEAM-ADA@LISTSERV.ACM.ORG

Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Subject:
From:
"Fowler, Kenneth" <[log in to unmask]>
Reply To:
Fowler, Kenneth
Date:
Wed, 2 Dec 1998 11:06:05 -0500
Content-Type:
text/plain
Parts/Attachments:
text/plain (142 lines)
Team members,
A friend and past colleague (Jim McKelvey, project scientist) at JPL finds
the new C++ templates to be an advantage over Ada generics (Ada83), but I
will
let him speak for himself. This topic overlaps Ada promotion and Ada
technology (Info Ada Usenet). Please comment as appropriate and cc. to
[log in to unmask]
--Ken Fowler, MITRE

        "C++ is a lot of fun, even though I would probably push Ada-95. The

> C++ "templates" are much more powerful than Ada generics, unless
> Ada-95 has beefed them up. (Are you familiar with the Blitz project?
> They use templates in a  radically new way. It  might be usable with
> Ada generics as well.)
>
      To describe template expressions (as in Blitz), let's make up a
      scenario. Suppose we want a class to do matrix operations, and we
      want it to use operator overloading. So we want to do:

                A = B + C + D;

        to add some 3x4 matrices.  What really happens is:

                Create and initialize a temporary (say X)
                Set it to the value of B + C
                Create and initialize a temporary (say Y)
                Set it to the value of X + D
                Assign the value of Y to A
                Destroy X and Y

        The overhead is horrendous, and it's difficult for an optimizer to
do
        much to help.

        We can recast it as procedure calls:

                add(B, C, X);
                add(X, D, A);

        which is faster. But we have lost our nice notation, and still need
a
        temporary.

        We could do:

                add(B, C, A);
                add(A, D, A);

        with a little more work.

        In Blitz, though, the matrix expression A = B + C + D
        would construct code to compute A = B + C + D as an
        expression. In other words, the generated code would
        look more like this:

        for (i = 0; i < 3; i++)
        {
           for (j = 0; j < 4; i++)
           {
                       A[i][j] = B[i][j] + C[i][j] + D[i][j];
           }
        }

        No temporaries - and the more complicated the expression, the
greater the speedup. In fact, we could even unroll the loops for a
greater speedup. The situation is readily understood by an optimizer.

        How does it do THAT you ask? By aggressively applying two
techniques:

        Recursive template instantiation (mostly implicitly)
        function Inlining


        In fact, C++ is moving in the direction of extensive use of
templates,      even in situations where they are not expected. The new
library is
        the Standard Template Library after all.

        The major down side to all this is that not one programmer in a
thousand will ever really understand how a package like Blitz works,    and
not one programmer in a million will ever undertake a project
        using template expressions.


        The real work at runtime is done in Blitz methods that are not
        normally inlined. So there is no great increase in memory.
        Here's a C++ example to try:

        #include <iostream.h>

        // Template
        template <const unsigned long int n>

        struct Factorial
        {
                static const unsigned long int factorial =
                        n * Factorial<n - 1>::factorial;
        };

        // Specialization of template
        struct Factorial<2>
        {
                static const unsigned long int factorial = 2;
        };

        // Specialization of template
        struct Factorial<1>
        {
                static const unsigned long int factorial = 1;
        };

        // Specialization of template
        struct Factorial<0>
        {
                static const unsigned long int factorial = 1;
        };

        int main(void)
        {
                cout << Factorial<6>::factorial << endl;

                return 1;
        }

        Compile this with full optimization and look at the generated code!
        Can this be translated into Ada95? The implicit instantiations can
        be made explicit -- the kicker is the specialization to end the
        recursion.

        Note that you cannot end the recursion (at least in C++) by
        changing the main expression to something like:

        (n > 1) ? (n * Factorial<n - 1>::factorial) : 1

        because the expression is not evaluated until after template
        expansion. Instead you'll bomb out by exceeding the template
        recursion depth."

                                                                --Jim

ATOM RSS1 RSS2