Reflexion

Reflexion bezeichnet die Fähigkeit eines Programms, seine Struktur zu kennen (Introspection) und gegebenenfalls anzupassen (Intercession). Sie ist die Grundlage für selbstadaptive Systeme. Hier spielt Template Metaprogramming seine wahre Stärke aus – insbesondere mit der neuen Bibliothek »type_traits« [8] des kommenden C++0x-Standards, die von neueren GCC-Versionen angeboten wird. Sie erlaubt es, Typ-Eigenschaften abzufragen, sie zu vergleichen und zu modifizieren, was die Grundlage für automatische Code-Anpassungen zur Compilezeit bildet. Der Kopieralgorithmus in Listing 7 stellt dies exemplarisch dar.

01 #include <string.h>
02 #include <chrono>
03 #include <iostream>
04 #include <type_traits>
05
06 namespace my{
07   template<typename I1, typename I2, bool b>
08   I2 copy_imp(I1 first, I1 last, I2 out, const std::integral_constant<bool, b>&){
09     while(first != last){
10       *out = *first;
11       ++out;
12       ++first;
13     }
14     return out;
15   }
16
17   template<typename T>
18   T* copy_imp(const T* first, const T* last, T* out, const std::true_type&){
19     memcpy(out, first, (last-first)*sizeof(T));
20     return out+(last-first);
21   }
22
23   template<typename I1, typename I2>
24   I2 copy(I1 first, I1 last, I2 out){
25     typedef typename std::iterator_traits<I1>::value_type value_type;
26     return copy_imp(first, last, out, std::has_trivial_assign<value_type>());
27   }
28 }
29
30 const int arraySize = 1000;
31 const int counter=100000;
32
33 int intArray[arraySize] = {0,};
34 int intArray2[arraySize]={0,};
35 int* pArray = intArray;
36 const int* pArray2 = intArray2;
37
38 int main(){
39
40   auto begin= std::chrono::monotonic_clock::now();
41   for(int i = 0; i < counter; ++i){
42       my::copy(pArray2, pArray2 + arraySize, pArray);
43    }
44   auto last=  std::chrono::monotonic_clock::now() - begin;
45   std::cout <<  " takes " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;
46
47   begin= std::chrono::monotonic_clock::now();
48   for(int i = 0; i < counter; ++i){
49       my::copy(intArray2, intArray2 + arraySize, intArray);
50    }
51   last=  std::chrono::monotonic_clock::now() - begin;
52   std::cout <<  " takes " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;
53
54 }

Das Programm kopiert zwei Arrays der Länge 1000, und dies genau 100000-mal. Es initialisiert beide Arrays mit 0, auf das erste Array greift es direkt, auf das zweite jedoch mit einem Pointer zu. Der indirekte Zugriff bewirkt, dass für das erste Array ein optimierter Kopieralgorithmus Anwendung findet (Zeile 18), für das zweite Array (Zeile 7) aber nur der Default-Kopieralgorithmus. Dieser Algorithmus kopiert jedes Element (Zeilen 9 bis 13) einzeln, während der optimierte ganze Datenblöcke (Zeile 19) mit der C-Funktion »memcpy()« [9] dupliziert. Dazu verwenden beide Implementierungen die C++-Iteratoren »first« , »last« und »out« , um mit den Containern der Standard Template Library (STL) kompatibel zu sein. Das Ergebnis kann sich sehen lassen (Abbildung 7): Der optimierte Algorithmus ist nahezu um den Faktor 20 schneller.

Abbildung 7: Die Laufzeiten der Kopieralgorithmen unterscheiden sich beträchtlich.

Der Hintergrund: Der Compiler wertet in dem Ausdruck »copy_imp(first, last, out, std::has_trivial_assign<value_type>())« (Zeile 26) die Eigenschaften des Quell- und Zieltyps aus, um abhängig von dessen Eigenschaften die passende Implementierung für »my::copy_imp« (Zeilen 8 und 18) zu verwenden. Entscheidungskriterien für den Compiler, den optimierten Kopieralgorithmus zu verwenden, sind:

• Die Iteratoren müssen Pointer sein: »const T* first, const T* last, T* out« (Zeile 18).
• Die Iteratoren müssen auf die gleichen Typen verweisen: »const T* first, const T* last, T* out« (Zeile 18) enthält nur einen Typ »T« , im Gegensatz zu den zwei Typen »I1« und »I2« in »I1 first, I1 last, I2 out« (Zeile 8).
• Die Elemente des Containers müssen einen trivialen, vom Compiler automatisch erzeugten Zuweisungsoperator besitzen »const std::true_type&« (Zeile 18).

Entrollt

Die Auflösung von Schleifen, besser bekannt unter dem Namen Loop Unwinding oder Loop Unrolling [10], ist eine beliebte Technik, um an der Performance-Schraube des Executable zu drehen. Auch hierfür lässt sich Template Metaprogramming einsetzen. Darüber hinaus zeigt das Listing 8 schön, wie sich Compile- und Laufzeit-Berechnung in einem Algorithmus elegant kombinieren lassen.

01 #include <iostream>
02
03 inline int power(const int& m, int n){
04   int r = 1;
05   for(int k=1; k<=n; ++k) r*= m;
06   return r;
07 }
08
09 template<int m, int n>
10 struct Power{
11   enum { value = Power<m,n-1>::value * m };
12 };
13
14 template<int m>
15 struct Power<m,0>{
16   enum { value = 1 };
17 };
18
19 template<int n>
20 inline int power(const int& m){
21   return power<n-1>(m) * m;
22 }
23
24 template<>
25 inline int power<1>(const int& m){
26   return m;
27 }
28
29 template<>
30 inline int power<0>(const int& m){
31   return 1;
32 }
33
34 int main(){
35   std::cout << "power(2,10):        " << power(2,10) << std::endl;
36   std::cout << "power<10>(2):       " << power<10>(2) << std::endl;
37   std::cout << "Power<2,10>::value: " << Power<2,10>::value << std::endl;
38 }

Die drei verschiedenen Aufrufe »power (2,10)« , »power<10>(2)« und »Power <2,10>::value« führen zum gleichen Ergebnis (Abbildung 8). Trotzdem gibt es feine Unterschiede. Während »power (2,10)« zur Laufzeit berechnet wird, erfolgt die Evaluierung von »Power <2,10>::value« zur Compilezeit.

Abbildung 8: Lauf- und Compilezeit-Varianten der Power-Funktion.

Zu welchem Zeitpunkt findet aber die Auswertung von »power<10>(2)« statt? Zur Lauf- und zur Compilezeit: Das Template-Argument »10« wird zur Compilezeit ausgewertet, das Funktionsargument »2« zur Laufzeit. Das Evaluieren des Template-Arguments bewirkt, dass zur Laufzeit lediglich das Funktionsargument in die aufgelöste Schleife »m*m*m*m*m*m*m*m*m*m« eingesetzt werden muss.