Re: Compile time of Expression Templates in C++

[Mike Stump <mrs at apple dot com>]

On Oct 10, 2006, at 6:25 AM, Jochen Haerdtlein wrote:
>     I am a PhD student working on the extended use of expression  
> templates for solving partial differential equations.

> Since compile time of huge expression template programs is a severe  
> problem

I fear that trying to solve that problem will result in orders of  
magnitude decrease in compilation speed at best, after you speed it  
up, as compared to new competing technologies for larger projects.   
The benefit is that those tricks are standard and can be relied upon.   
If you're up for innovation, identify those things that slow  
compilation to a crawl in traditional C++, design a system, say based  
upon a lisp system, that can `compile' that fast.  Map that over to a  
more static C++ environment,  and then implement that in g++ and then  
try it out on your problem.  If it works, propose the system as  
extensions to the C++ language.  I think C++ would benefit from it.

Let me give you a concrete example, take:

#include <stdio.h>

template <int I, int J>
class divides {
public:
  enum { answer = I%J == 0 || divides<I,J-1>::answer };
};

template<>
template <int I>
class divides<I, 1> {
public:
  enum { answer = 0 };
};

template <int I>
class is_prime {
public:
  enum { answer = divides<I,(I-1)/2+1>::answer == 0};
};

template <>
class is_prime<1> {
public:
  enum { answer = 0 };
};

template <>
class is_prime<2> {
public:
  enum { answer = 1 };
};

template <>
class is_prime<3> {
public:
  enum { answer = 1 };
};

main() {
#define T(N)  printf("Is %d a prime, %s.\n", N, is_prime<N>::answer ?  
"yes" : "no");
  T(2);
  T(3);
  T(4);
  T(5);
  T(6);
  T(7);
  T(8);
  T(9);
  T(10);
  T(11);
  T(12);
  T(13);
  T(14);
  T(47797);
}

for example, it takes around 3m9.947s to compile on my system.  The  
competition, seen at the end, clocks in at 1862x faster, around  
0m0.102s to compile.   The problem is that the second isn't guaranteed  
to be solved at compile time, while the above is.  If this were the  
only problem to so fix, one could just change g++ to evaluate all  
constant expressions at compile time, no matter what and do all the  
required inlining for this, and then one could write the above program  
as the one at the end, and have the guarantee, as well as cleaner and  
clearer code, benefits all the way around.

Just as there exists an alternative way of doing the above, I'd expect  
there is an alternative way of doing what you want to do, that would  
be 2-3 orders of magnitude faster than the current compilation speed  
of the current solution and hopefully remain 1-2 orders faster _after_  
you sped the g++ compilation speed up using more traditional techniques.

If this is secondary to your goal or if you want to remain true to the  
standard, you should be able to spot bad things like linear  
instantiation scans in the compiler and sped up those things in  
straight forward ways and gain 2-10x in speed on some problems (n ==  
5-200 type things).  Just crank up the problem size and watch for the  
n^2 curve and when it dominates, get a gprof at that point, and take a  
look at what dominates and then fix it.  The usual culprit will be a  
linear search of a list (vector) with n things on it, where that is  
done n times.  When you see something related to templates, say (from  
cp-tree.h):

/* For a static member variable template, the
   DECL_TEMPLATE_INSTANTIATIONS list contains the explicitly and
   implicitly generated instantiations of the variable.

or

/* For a function template, the DECL_TEMPLATE_SPECIALIZATIONS lists
   contains all instantiations and specializations of the function,
   including partial instantiations.

you know you are about in the right place.  If you wanted to  
statically look for these things, a quick grep or these two finds  
things like:

tree
maybe_process_partial_specialization (tree type)
{
[ ... ]
          for (t = DECL_TEMPLATE_INSTANTIATIONS
                 (most_general_template (CLASSTYPE_TI_TEMPLATE  
(type)));
               t; t = TREE_CHAIN (t))

and

      if (!class_specializations_p
          && TREE_CODE (DECL_TEMPLATE_RESULT (tmpl)) == TYPE_DECL)
        sp = &DECL_TEMPLATE_INSTANTIATIONS (tmpl);
      else
        sp = &DECL_TEMPLATE_SPECIALIZATIONS (tmpl);
      head = sp;
      /* Iterate through the list until we find a matching template.   
*/
      while (*sp != NULL_TREE)
        {

I'll leave it as an exercise for the reader what algorithm would best  
replace these sorts of things, or even if, for any particular one, it  
is possible to do better.

Hope that helps.

Anyway, here is the obvious version that compiles faster:


#include <stdio.h>

static int
divides(int I, int J)
{
  if (J == 1)
    return 0;
  return I%J == 0 || divides(I,J-1);
}

static int
is_prime(int I)
{
  if (I == 1)
    return 0;
  if (I == 2 || I == 3)
    return 1;
  return divides(I,(I-1)/2+1) == 0;
}

main() {
#define T(N)  printf("Is %d a prime, %s.\n", N, is_prime(N) ? "yes" :  
"no");
  T(2);
  T(3);
  T(4);
  T(5);
  T(6);
  T(7);
  T(8);
  T(9);
  T(10);
  T(11);
  T(12);
  T(13);
  T(14);
  T(47797);
}