Programmierung zur Compilezeit

 

Schön zeigt die folgende Abbildung (siehe PDF), dass der Wert der Fakultät von 5 bereits zur Laufzeit als Konstante vorliegt. Dabei instanziiert der Compiler den Ausdruck Factorial<5>::value. Um diesen Wert zu berechnen, benötigt er den Ausdruck Factorial<4>::value. Diese Rekursion endet dann, wenn der Wert Factorial<1>::value benötigt wird, denn deren Wert ist 1.

Funktionen wie die Factorial Funktion, die zur Compilezeit ausgeführt werden, werden Metafunktionen genannt. Sie besitzen ein paar interessante Eigenschaften. Neben Ganzzahlen können sie auch Typen und Klassen-Typen als Template-Parameter verwenden. Metafunktionen sind unter der Decke Klassen-Templates. Sie können ihre Daten nicht modifizieren, sondern erzeugen auf Bedarf neue Daten.

Template-Metaprogrammierung, die auf Metafunktion basiert, die zur Compilezeit auf ihren Metadaten agieren, ist eine rein funktionale Subsprache in der imperativen Sprache C++. Diese funktionale Subsprache ist Turing-vollständig [1], und entspricht in ihrer Mächtigkeit der der Programmiersprachen C++, C oder Java.

Template Metaprogrammierung ist die Grundlage für viele Boost-Bibliotheken [2]. Das trifft auch auf die Type-Traits Bibliothek zu, die seit C++11 Teil des C++-Standards ist.

Die Type-Traits Bibliothek

Die Type-Traits Bibliothek erlaubt es, Typabfragen, -vergleiche und -transformationen zur Compilezeit auszuführen. Sie ist eine Anwendung der Template-Metaprogrammierung und verfolgt for allem zwei Zwecke: Korrektheit und Optimierung:

Korrektheit

Die Type-Traits Bibliothek erlaubt es in Kombination mit dem static_assert Ausdruck, verbindliche Bedingungen an den Sourcecode zu stellen, die zur Compilezeit angewendet werden.

Der qcd-Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier Ganzzahlen ist viel zu generisch. So lässt er sich zwar mit Fließkommazahlen, Strings und unterschiedlichen Datentypen wie int (100) und long int (10L) verwenden. Der Compiler quittiert dies aber mit einer sehr wortreichen Fehlermeldung.

 

#include <iostream>

#include <type_traits>

 

template<typename T>

T gcd(T a, T b){

  if( b == 0 ) return a;

  else return gcd(b, a % b);

}

 

int main(){

  std::cout << gcd(100,10) << std::endl;        //  10

  std::cout << gcd(100,33) << std::endl;        //  1

  std::cout << gcd(100,0) << std::endl;         //  100

  std::cout << gcd(3.5,4.0) << std::endl;       // ERROR

  std::cout << gcd("100","10") << std::endl;    // ERROR

  std::cout << gcd(100,10L) << std::endl;       // ERROR

}

 

Durch die Type-Traits Bibliothek lassen sich die Bedingungen an den Algorithmus explizit stellen. Und das alles ohne zusätzliche Kosten für die Laufzeit des Programmes.

 

template<typename T1, typename T2>

typename std::conditional<(sizeof(T1)<sizeof(T2)),T1,T2>::type gcd(T1 a, T2 b){

  static_assert(std::is_integral<T1>::value, "T1 should be integral!");     

  static_assert(std::is_integral<T2>::value, "T2 should be integral!");

  if( b == 0 )return a; 

  else return gcd(b, a % b); 

}

 

So prüft der neue qcd-Algorithmus, ob die beiden Template-Argumente T1 und T2 Ganzzahlen sind: std::is_integral<T1>::value. Als Rückgabetyp für den größten gemeinsamen Teiler gibt der qcd-Algorithmus den kleineren der beiden Typen zurück: std::conditional<(sizeof(T1)<sizeof(T2)),T1,T2>::type.

 

Optimierung

Code zu schreiben, der sich beim Übersetzen selbst optimiert, das erlaubt die Type-Traits Bibliothek. So enthält die Standard Template Library (STL) optimierte Versionen der bekannten Algorithmen std::copy, std::fill oder std::equal. 

Die Idee ist recht einfach. Immer, wenn die Algorithmen auf Container agieren, deren Elemente hinreichend einfach sind, kommt ein optimierter Algorithmus zum Einsatz. Damit ist es möglich, die Elemente nicht elementweise zu kopieren (std::copy), zu füllen (std::fill) oder zu vergleichen (std::equal), sondern ganze Containerbereiche zu bearbeiten. Dafür kommen die C-Funktionen memmove, memset und memcpy zum Einsatz.

Ob die Containerelemente hinreichend einfach sind, entscheiden zur Compilezeit die Funktionen der Type-Traits Bibliothek.

 

template <typename I, typename T, bool b>

void fill_impl(I first,I last,const T& val,

               const std::integral_constant<bool, b>&){

   while(first != last){

    *first = val;

    ++first;

  }

}

 

template <typename T>

void fill_impl(T* first, T* last, const T& val, const std::true_type&){

  std::memset(first, val, last-first);

}

 

template <class I, class T>

inline void fill(I first, I last, const T& val){

  typedef integral_constant<bool,is_trivially_copy_assignable<T>::value

                                 && (sizeof(T) == 1)> boolType;

  fill_impl(first, last, val, boolType());

}

 

Wird std::fill aufgerufen, verwendet der Compiler die Implementierungsfunktion fill_impl mit std::memset genau dann, wenn die Elemente des Containers einen vom Compiler automatisch erzeugten Kopierkonstruktor besitzen und ein Byte groß sind: is_trivially_copy_assignable<T>::value && (sizeof(T) == 1.

Der Performanzunterschied ist signifikant. So wird in dem Programm ein Array mit 100.000.000 Elementen gefüllt.

 

const int arraySize = 100'000'000;

char charArray1[arraySize]= {0,};

char charArray2[arraySize]= {0,};

 

int main(){

  auto begin= std::chrono::system_clock::now();

  fill(charArray1, charArray1 + arraySize,1);

  auto last= std::chrono::system_clock::now() - begin;

  cout << "charArray1: " << duration<double>(last).count() << " seconds";

  begin= std::chrono::system_clock::now();

  fill(charArray2, charArray2 + arraySize, static_cast<char>(1));

  last= std::chrono::system_clock::now() - begin;

  cout << "charArray2: " << duration<double>(last).count() << " seconds";

}

 

Während die Elemente des charArray1 mit der Zahl 1 initialisiert werden, die in der Regel 4 oder 8 Byte große ist, wird charArray2 mit einer char initialisiert: static_cast<char>(1).   

Die performante Version des Algorithmus ist um den Faktor 20 schneller (siehe Abbildung, PDF-Datei).

 

Konstante Ausdrücke

Konstante Ausdrücke können zur Compilezeit evaluiert und im ROM gespeichert werden. Sie geben dem Compiler tiefen Einblick in den Sourcecode und sind implizit threadsicher.

Konstante Ausdrücke gibt es als Variablen, benutzerdefinierte Typen und Funktionen. Im Gegensatz zu Template-Metaprogrammierung erlauben sie das Programmieren zur Compilzeit im imperativen Stil. Damit konstante Ausdrücke zur Compilezeit evaluiert werden können, gilt es ein paar Regeln zu beachten.

• Variablen sind implizit const und müssen durch konstante Ausdrücke initialisiert werden: constexpr double pi= 3.14;
• Benutzerdefinierte Typen können keine virtuelle Basisklasse besitzen. Ihr Konstruktor muss vom Compiler erzeugt werden und selbst ein konstanter Ausdruck sein. Methoden, die Objekte von benutzerdefinierten Typen verwenden, müssen konstante Ausdrücke und können nicht virtuell sein.
• Funktionen können keine statische und thread_local Variablen enthalten

 

Die gcd-Funktion ist ein konstanter Ausdruck. Sind ihre Argumente auch konstante Ausdrücke, kann sie zur Compilezeit evaluiert werden. Genau das zeigt das folgende Program:

#include <iostream>

 

constexpr auto gcd(int a, int b){ 

  while (b != 0){

    auto t= b;

    b= a % b;

    a= t;

  }

  return a;

}

 

int main(){

  constexpr int i= gcd(11,121);    

  std::cout << i << std::endl;           // 11

  constexpr int j= gcd(100,1000);         

  std::cout << j << std::endl;           // 100

}

 

Ein tiefer Blick in den Objektcode zeigt, dass die Ergebnisse der gcd-Aufrufe bereits zur Compilezeit vorliegen:

 

 

 

constexpr-Funktionen unterscheiden sich im Detail deutlich von Metafunktionen, die bei der Template-Metaprogrammierung zum Einsatz kommen. So können konstante Ausdrücke zur Compile- und Laufzeit ausgeführt werden, Sprung- und Iterationsanweisungen sowie auch bedingte Anweisungen enthalten. Darüber hinaus unterstützen constexpr-Funktionen das Verändern von Daten und das Arbeiten mit Fließkommazahlen.

 

 

Template-Metaprogrammierung, die Type-Traits Bibliothek und konstante Ausdrücke haben gemein, dass sie zu Compilezeit ausgeführt werden. Während Template-Metaprogrammierung aber ein tiefes Verständnis von rein funktionaler Programmierung voraussetzt, ist der Einsatz der neuen C++11 Type-Traits Bibliothek deutlich intuitiver für den imperativ geschulten Programmierer. Nur die Namenskonventionen erinnern an Template-Metaprogrammierung. Konstante Ausdrücke mit dem C++14-Standard erlauben direkt das Programmieren im imperativen Stil.

 

 

[1] Turing-Vollständigkeit

[2] Boost-Bibliothek

Rainer Grimm, "C++11 für Programmierer", O’Reilly 2013

Rainer Grimm, "Modernes C++ in der Praxis", Serie im Linux-Magazin

 

Beitrag als PDF-Datei herunterladen

---

Echtzeit - MicroConsult Trainings & Coachings

Wollen Sie sich auf den aktuellen Stand der Technik bringen?

Dann informieren Sie sich hier zu Schulungen/ Seminaren/ Trainings/ Workshops und individuellen Coachings von MircoConsult zum Thema Embedded- und Echtzeit-Softwareentwicklung.

Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie hier.

---

Echtzeit - Fachwissen

Wertvolles Fachwissen zum Thema Embedded- und Echtzeit-Softwareentwicklung steht hier für Sie zum kostenfreien Download bereit.

Zu den Fachinformationen

 
Fachwissen zu weiteren Themen unseren Portfolios finden Sie hier.