C.2. Managing Compilation Time

The first and most important thing you can do to improve your metaprograms' execution (compilation) time is to reduce their computational complexity. Use an mpl::vector if you need access to arbitrary elements, because each such access will be O(1) instead of O(N), as it would be with an mpl::list. Don't search linearly for an element in a sequence when you could use mpl::lower_bound, and so forth. There is no substitute for picking the right algorithms and data structures.

Unfortunately, most compilers weren't designed with template metaprogramming in mind, and many use an inferior implementation strategy. For example, an ideal compiler would store all memoized template specializations in a hash table for O(1) lookups. However, as of this writing most implementations use one linked list to store all instantiations of a particular class template. Thus, lookups are technically linear in the number of instantiations of that template that have come before. Usually, this O(N) effect is swamped by the cost of instantiation, but as we shall see, it can be observed.

We happen to know this implementation detail of the compilers we've tested, but there are many more individual quirks of specific compilers that we don't know about. By using special-purpose test programs, we can get an idea of the real-world effects of our metaprogram design choices, and which compilers to use when metaprogram speed matters. In this appendix we'll discuss the empirical results of these black-box tests, and we'll reveal some techniques you can use to avoid the trouble spots we've found.

Note that complete details of the tests we describe here can be found on this book's companion CD.