Die Type-Traits-Bibliothek: Optimierung

Inhaltsverzeichnis

Die Type-Traits-Bibliothek hat zwei Hauptziele: Korrektheit und Optimierung. Heute steht die Optimierung im Fokus.

Dieser Beitrag ist der letzte in meiner Miniserie über die Type-Traits-Bibliothek. Ich habe bereits die folgenden Beiträge geschrieben:

• Die Type-Traits-Bibliothek: Typprüfungen
• Die Type-Traits-Bibliothek: Typvergleiche
• Die Type-Traits-Bibliothek: std::is_base_of
• Die Type-Traits-Bibliothek: Korrektheit

Bevor ich beginne, über Optimierung in C++ zu schreiben, möchte ich eine kurze Anekdote erzählen. In meinen Kursen führe ich oft das folgende Gespräch mit meinen Teilnehmern:

• Ich: Warum haben wir in C++ das Feature ABC?
• Teilnehmer: Ich weiß es nicht.
• Ich: Wenn Sie keine Antwort haben, sagen Sie einfach Performance. Das funktioniert in C++ immer.

Daher schreibe ich über die Bibliothek der Type Traits aus der Perspektive der Optimierung.

Optimierung

Die Idee ist recht simpel und wird in der Standard Template Library (STL) verwendet. Wenn die Elemente eines Ranges einfach genug sind, werden die Algorithmen der STL wie std::copy, std::fill oder std::equal direkt auf den Speicher angewendet. Anstatt mit std::copy jedes Element einzeln zu kopieren, wird alles in einem einzigen großen Schritt erledigt. Intern werden C-Funktionen wie memcmp, memset, memcpy oder memmove verwendet. Der kleine Unterschied zwischen memcpy und memmove besteht darin, dass memmove mit überlappenden Speicherbereichen umgehen kann.

Die Implementierungen des Algorithmus std::copy, std::fill oder std::equal verwenden eine einfache Strategie. std::copy ist eine Art Wrapper. Dieser Wrapper prüft, ob die Elemente einfach genug sind. Wenn ja, delegiert der Wrapper die Arbeit an die optimierte Kopierfunktion. Wenn nicht, wird der konservative Kopieralgorithmus verwendet. Dieser konservative Algorithmus kopiert jedes Element einzeln. Um die richtige Entscheidung zu treffen, werden die Funktionen der Type-Traits Bibliothek intensiv genutzt.

Die Grafik zeigt die allgemeine Strategie:

Das war die Theorie, aber hier ist die Praxis. Welche Strategie wird von std::fill verwendet?

std::fill

std::fill weist jedem Element im Bereich einen Wert zu. Das Listing zeigt eine GCC-inspirierte Implementierung von std::fill.

// fillGCC.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>                             // (2)
  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::is_trivially_copy_assignable<T>::value 
              && (sizeof(T) == 1)> boolType;       // (1)
    fill_impl(first, last, val, boolType());
  }
}

const int arraySize = 100'000'000;
char charArray1[arraySize]= {0,};
char charArray2[arraySize]= {0,};

int main(){

  std::cout << '\n';

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

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

  std::cout << '\n';

}

Zurück zum Codebeispiel. Wenn der Ausdruck boolType() in (1) wahr ergibt, wird die optimierte Version von my::fill_impl in (2) verwendet. Diese Variante füllt den gesamten Speicher von 100 Millionen Einträgen mit dem Wert 1. sizeof(char) ist 1.

Wie sieht es mit der Performance des Programms aus? Ich habe das Programm ohne Optimierung kompiliert, um die nicht optimierte Leistung zu messen.

Die optimierte Version in Zeile (2) ist etwa zehnmal schneller. Interessanterweise sind beide Varianten gleich schnell, wenn ich die vollständige Optimierung aktiviere, da der Compiler für beide Varianten denselben Code erzeugt. Auch die allgemeine Version (3) verwendet memset: mit maximaler Optimierung im Compiler Explorer.

Ich habe eine alte GCC-Implementierung von std::fill vorgestellt, weil die Neueren nicht so einfach zu lesen sind. Hier sind die wesentlichen Teile der GCC 6 Implementierung.

// fill  
// Specialization: for char types we can use memset.                   
template<typename _Tp>
  inline typename
  __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type     // (1)
  __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
  {
    const _Tp __tmp = __c;
    if (const size_t __len = __last - __first)
    __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
  }

Die GCC 6-Implementierung setzt SFINAE ein. Die vollständige Spezialisierung des Funktions-Templates __fill_a verwendet __builtin_memset. Der entscheidende Ausdruck in dieser Implementierung ist Zeile (1): __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type. Folgendermaßen sieht dieser Ausdruck lesbarer umgeschrieben und mit den Namen des Standards aus:

std::enable_if<std::is_byte<Tp>::value, void>::type

Der Ausdruck prüft zunächst, ob der Template-Parameter TP ein Byte ist: std::is_byte<T>::value. Wenn dieser Ausdruck dank std::enable_if aus der type-traits-Bibliothek false ergibt, tritt SFINAE in Aktion. SFINAE steht für "Substitution Failure Is Not An Error" (Substitutionsfehler ist kein Fehler) und wird bei der Überladungsauflösung eines Funktions-Templates angewendet. Das heißt, wenn die Substituierung des Template-Parameters fehlschlägt, wird die Spezialisierung aus der Menge der Überladungen verworfen. Dieser Fehler verursacht aber keinen Compilerfehler. Das bedeutet in diesem konkreten Fall: Wenn die Bedingung std::is_byte<T>::value false zurückgibt, wird diese vollständige Spezialisierung verworfen und eine allgemeine Version von __fill_a verwendet.

Wie geht es weiter?

Zuerst mache ich eine Weihnachtspause von zwei Wochen. Mein nächster Beitrag wird am 10. Januar 2022 veröffentlicht. Ich werde über constexpr-Funktionen schreiben, da sie viele Gemeinsamkeiten mit Templates haben und mit C++20 noch leistungsfähiger werden.

Zweitens möchte ich meinen professionellen Unterricht in C++ verbessern. Deshalb plane ich, ein Mentorenprogramm für C++ zu starten. Bald werde ich mehr Details auf meinem englischen Blog Modernes C++ Idee veröffentlichen. ()