Type-Traits - Performanz zählt

Type Traits offenbaren bei genauen Hinblick ein großes Optimierungspotential. Da die Type-Traits Bibliothek es erlaubt, im ersten Schritt den Code zu Compilezeit zu analysieren, kann dieser im zweiten Schritt optimiert werden. Wie ist das möglich? Abhängig vom Typ einer Variable wird eine besondere, schnelle Variante eines Algorithmus gewählt.

Arbeiten auf ganzen Speicherbereichen

Die Idee ist ganz einfach und wird in modernen Implementierungen der Standard Template Library (STL) umgesetzt. Sind die Elemente eines Containers hinreichend einfach, dann können Algorithmen der STL wie std::copy, std::fill oder auch std::equal direkt auf dem ganzen Speicherbereich agieren. Anstelle elementweise mit std::copy die Elemente zur kopieren, wird der Container in einem Rutsch kopiert. Intern kommen dann bekannt C-Funktionen wie memcmp, memset, memcpy oder auch memmove zum Einsatz. Der feine Unterschied zwischen memcpy und memmove ist es, dass sich bei memmove die Speicherbereiche überlappen können.

Die Implementierung der Algorithmen std::copy, std::fill oder auch std::equal folgt einem typischen Pattern. Ein Algorithmus wie std::copy agiert als Wrapper. Dieser prüft nur, ob seine Elemente hinreichend einfach sind. Ist dies der Fall, delegiert der Wrapper die Kopierarbeit an die optimierte Implementierungsfunktion, die den ganzen Speicherbereich kopiert. Ist dies nicht der Fall, kommt die allgemeine Implementierungsfunktion um Einsatz, die die Elemente einzeln kopiert. Um zu entscheiden, ob die Elemente hinreichend einfach sind, kommen die Funktionen der Type-Traits Bibliothek zum Einsatz. 

Die Abbildung bringt die Strategie nochmals auf den Punkt:

Das war die Theorie, jetzt kommt die Praxis. Welche Strategie verwendet std::fill unter der Decke?

std::fill

std::fill weist jedem Element seines Bereichs einen Wert zu. In dem Listing stelle ich eine einfache Implementierung vor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// fill.cpp
 
#include <cstring>
#include <chrono>
#include <iostream>
#include <type_traits>

namespace my{

  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 std::integral_constant<bool,std::has_trivial_copy_assign<T>::value && (sizeof(T) == 1)> boolType;
    typedef std::integral_constant<bool,std::is_trivially_copy_assignable<T>::value && (sizeof(T) == 1)> boolType;
    fill_impl(first, last, val, boolType());
  }
}

const int arraySize = 100000000;
char charArray1[arraySize]= {0,};
char charArray2[arraySize]= {0,};

int main(){

  std::cout << std::endl;

  auto begin= std::chrono::system_clock::now();
  my::fill(charArray1, charArray1 + arraySize,1);
  auto last=  std::chrono::system_clock::now() - begin;
  std::cout <<  "charArray1: " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;

  begin= std::chrono::system_clock::now();
  my::fill(charArray2, charArray2 + arraySize, static_cast<char>(1));
  last=  std::chrono::system_clock::now() - begin;
  std::cout <<  "charArray2: " << std::chrono::duration<double>(last).count() << " seconds" << std::endl;

  std::cout << std::endl;

}

In Zeile 26 fällt my::fill die Entscheidung, welche Implementierungsvariante von my::fill_impl zur Anwendung kommen soll. Um die optimierte Variante einzusetzen, müssen die Elemente des Containers einem vom Compiler automatisch erzeugten Copy-Zuweisungsoperator besitzen std::is_trivially_copy_assignable<T> und 1 Byte lange sein: sizeof(T) == 1. Die Funktion std::is_trivially_copy_assignable ist Teil der Type-Traits Bibliothek. Im Artikel Typeigenschaften abfragen erkläre ich die Magie hinter den Type-Traits Funktionen.

Mein GCC 4.8 bietet die Funktion std::is_trivially_copy_assignable der Type-Traits Bibliothek noch unter dem Namen std::has_trivial_copy_assign an. Der vom Compiler mit dem Schlüsselwort default angeforderte Copy-Zuweisungsoperator gilt als trivial. 

struct TrivCopyAssign{
  TrivCopyAssign& operator=(const TrivCopyAssign& other)= default;
};

Nun aber zurück zum Codebeispiel. Ergibt die Evaluierung des Ausdrucks boolType() in Zeile 27 true, so kommt die optimierte Version von my::fill_impl in den Zeilen 18 - 21 zum Einsatz. Diese füllt im Gegensatz zu generischen Varianten von my::fill_impl in den Zeilen 10 -16 den ganzen Speicherbereich - bestehend aus 100 Millionen Zeichen (Zeile 32 und 33) - mit dem Wert 1. Der kleine Trick, das int-Literal 1 in ein char zu konvertieren, erlaubt es, den optimierten Algorithmus anzuwenden. Der Grund ist, dass sizeof(char) 1 ist. 

Welche Sprache spricht die Ausführung des Programms? Sowohl und Windows als auch unter Linux habe ich die ausführbare Datei ohne Optimierungsflags erzeugt. Das Ausführen des optimierten Algorithmus ist unter Windows um den Faktor 3, unter Linux um den Faktor 20 schneller.

Microsoft Visual 15

GCC 4.8

 Das Entscheidung, welche Varianten des Algorithmus angewandt werden soll, ist nicht immer so leicht zu verdauen wie bei std::fill.

std::equal

Einen speziellen Humor kann der Implementer des std::equal Algorithmus nicht verheimlichen, hat er doch sein Entscheidungskriterium __simple genannt. Der Code ist aus der STL Implementierung des GCC 4.8.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

template<typename _II1, typename _II2>
inline bool __equal_aux(_II1 __first1, _II1 __last1, _II2 __first2){
  typedef typename iterator_traits<_II1>::value_type _ValueType1;
  typedef typename iterator_traits<_II2>::value_type _ValueType2;
  const bool __simple = ((__is_integer<_ValueType1>::__value
                         || __is_pointer<_ValueType1>::__value )
                        && __is_pointer<_II1>::__value
                        && __is_pointer<_II2>::__value
                        &&__are_same<_ValueType1, _ValueType2>::__value
                        );
  return std::__equal<__simple>::equal(__first1, __last1, __first2);
}

 __simple stelle ich mir anders vor. Um den optimierten std::equal Algorithmus zu verwenden, müssen die Containerelemente einige Zusicherungen erfüllen, die mit den Funktionen der Type-Traits Bibliothek geprüft werden. So müssen die Containerelemente den gleichen Typ besitzen (Zeile 9) und entweder eine natürliche Zahl oder ein Zeiger sein (Zeile 5 und 6). Darüber hinaus gilt, dass bei iteratoren Zeiger sein müssen (Zeile 7 und 8).

Wie geht's weiter?

In den C++98-Standard haben sie es nicht mehr geschafft. Im C++11-Standard sind sie enthalten: Hashtabellen. Offiziell heißen sie ungeordnete assoziative Arrays, werden aber auch gerne Dictionaries genannt. Sie versprechen vor allem eins: Performanz. Denn die Zugriffszeit auf ihre Elemente ist im optimalen Fall konstant.

Was es mit den ungeordneten assoziativen Containern auf sich hat? Worin sie sich von den bereits im C++98-Standard enthaltenen geordneten assoziativen Container (std::map, std::set, std::multimap und std::multiset) unterscheiden? Davon handelt der nächste Artikel.