Metaprogramming: Tool or toy? Case study: A law based test automaton

Summary: For the implementation of a law based test
automaton (LaBatea) metaprogramming techniques worked
extremely well especially concerning genericity and
expressive power. But the compiletime and the codesize
of the compiled program scaled quite badly with the
number of law instances. Increasing numbers of law
instances resulted in unacceptable compile times and
code bloat of the compiled program. Gcc performed worse
than msvc.

Since I looked at Loki::typelist for the first time,
I was faszinated and inspired by metaprogramming and it's
possibilities. So I looked for some good real world
problems that might be solved *best* using metaprogramming
techniques.

Since I have developed some library code on interval_sets,
interval_maps and cubes (Interval Template Library:
http://sourceforge.net/projects/itl) where a lot of formal
laws are known about, I wrote a "Law based Test Automaton
(LaBatea;)" which works like this:

forever loop:
1. Select a law to test.
2. Generate test objects for that law.
3. Test the law
4. If the law is violated report the instance.

This project seemed to be highly appropriate for
metaprogramming techniques because of this:

The basic class template 'Law' needs polymorphic
typelists for input and output variables in order to
be really general:

template <typename InputTypes, typename OutputTypes>
class Law
{
public:
  typedef typename Loki::tuple<InputTypes> input_tuple;
  typedef typename Loki::tuple<OutputTypes> output_tuple;
public:
  virtual ~Law(){}
  virtual bool holds()=0;
  ...
}

Now we can define e.g. a general commutativity law that
can be instantiated for all kinds of types (builtin,
class types, instantiated template types, function types, ..)
input_types for variables a, b; output_types for the left and
right hand side rhs=a+b and lhs=b+a:

template <typename Type,
          template<class>class BinaryOp = op_plus>
class Commutativity:
  public Law<LOKI_TYPELIST_2(Type,Type),
             LOKI_TYPELIST_2(Type,Type)>
{/* a+b==b+a; */...}

The validity of a law for some given types is a
completely 'static' matter. Or more precisely it
is an algebraic (alias concept) matter. Only internal
affairs of program logic. So the instantiation of the
typelists involved is never dependent on dynamic aspects
of the program. So again: Metaprogramming seems to be
the *right* way to do it.

Results:
(1) Without the background of Andrej Alexandrescu's book
Modern c++ Design I would not have been successful. It
was both inspiration and tool. The central class template
in 'LaBatea' is a typelist generated polymorphic tuple,
that is based on Andrej's ground breaking technique
of typelist driven class generation.

(2) Except for some unavoidable abstraction headaches
involved in metaprogramming, the project was a lot of
fun. In terms of the expressive power my expectations
have been exceeded. Using metaprogramming I was able
to achieve nearly all of my goals for my automatic
law tester: LaBatea's source code is quite small, in
it's overall structure quite simple and yet very powerful.
The main achievement is, that it is possible to define
a general law like Commutativity as a class template
in effect only *once*.

(3) The law based tester is among other things a
perfect basis for radical and 'carefree' refactoring.
I dare say it is at least as useful as a well crafted
system of unit tests.
(I'm sorry if I am getting overenthusiastic. I am speaking
not only about my LaBatea tester but also about law based
automatic testing in general; see axioms in c++0x).

But now come the downsides :(

The problem with LaBatea began as I was happily implementing
laws and law instances types, so the body of my law and
instance base grew and thrived. (Which is desired, like in
unit testing). With the number of laws and instance types
the compile time also grew nastily.

Not only that, also the code generated by compilers piled
up hugely: Here are some numbers from a first profiling:

+--------+------------+------------+-------------+
|law |compile time|program size|program speed|
|instance|(seconds) |(kBytes) |sec/10kTests |
|count | vc8 | gcc | vc8 | gcc | vc8 | gcc |
+--------+------+-----+-----+------+------+------+
| 15 | 52 | 44 | 260 | 3815| 9 | 41 |
| 30 | 61 | 59 | 392 | 4734| 14 | 64 |
| 52 | 99 | 111 | 652 | 6934| 13 | 60 |
| 74 | 130 | 161 | 832 | 8486| 12 | 58 |
| 96 | 163 | 217 |1000 | 9848| 15 | 73 |
| 118 | 176 | 238 |1240 | 10592| 19 | 80 |
| 168 | 269 | 420 |1636 | 14167| 19 | 88 |
| 212 | 375 | *** |1904 | ***| 21 | *** |
+--------+------+-----+-----+------+------+------+
{ table formatting fixed manually -mod }

When plotted in a diagram
(see: http://www.herold-faulhaber.de/itl/LaBatea_performance.xls)
compile time and program size are growing linearly with law
instances before going through the roof, when ressource limits
are hit: With 212 law instances gcc did not terminate within
half an hour (***).

The problem is that the slope of the function is much to steep
for vc8 and even worse for gcc. Even with the faster vc8 we spend
about 1.8 seconds compile time and 9 kBytes program size for
every law instance. Even the program speed that should be a
constant function suffers from the generated code especially with
gcc.

This is a little depressing because: Had I implemented LaBatea
using pointer poymorphism instead of metaprogramming, the compile
time, program size and program speed would have been much much
less *and* constant, that is independent of the number of law
instances.

Any ideas how to tackle these compiletime and codebloat problems
are highly apperciated.

Cheers
Joachim Faulhaber

The code of LaBatea is inculded in the the
'Interval Template Library (ITL)' that can be downloaded from
http://sourceforge.net/projects/itl. Documentaion and performance
charts are availabel from http://www.herold-faulhaber.de/itl/

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]