Listing 7
Kopieralgorithmus für Container
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.
Listing 8
Die Power-Funktion
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.
Mächtige DSEL
Ziel dieses Artikels war es zum einen, die Techniken hinter Template Metaprogramming zu vermitteln, zum anderen, deren Innovationskraft für C++ aufzuzeigen. Die wahre Stärke von Template Metaprogramming liegt in seinen Eigenschaften einer Domain Specific Embedded Language (DSEL). Das bezeichnet eine Sprache, die auf eine spezielle Domäne ausgerichtet und zudem in die Gastgebersprache eingebettet ist. Anders ausgedrückt: Es ist mit Template Metaprogramming möglich, in der Universalsprache C++ eine mächtige, spezielle Subsprache für besondere Anwendungsbereiche zu definieren. Das Schöne daran ist, dass sowohl die Gast- als auch die Gastgebersprache der C++-Syntax genügen.
