C++ Core Guidelines: Regeln zu Performanz

Bevor ich über die Regeln zur Performanz schreibe, muss ich erst eine einfache Aufgabe erledigen: auf die Elemente eines Containers sukzessive zugreifen.

Dies ist die letzte Regel zur Arithmetik.

ES.107: Don’t use unsigned for subscripts, prefer gsl::index

Habe ich gesagt, dass das eine einfache Aufgabe wird? Das war eine Lüge! Viel kann schiefgehen. Hier ist ein Beispiel mit einem std::vector:

vector<int> vec = /*...*/;

for (int i = 0; i < vec.size(); i += 2)     // may not be big enough (2)
    cout << vec[i] << '\n';
for (unsigned i = 0; i < vec.size(); i += 2)  // risk wraparound     (3)
    cout << vec[i] << '\n';
for (auto i = 0; i < vec.size(); i += 2)    // may not be big enough (2)
    cout << vec[i] << '\n';
for (vector<int>::size_type i = 0; i < vec.size(); i += 2)// verbose (1)
    cout << vec[i] << '\n';
for (auto i = vec.size()-1; i >= 0; i -= 2)    // bug                (4) 
    cout << vec[i] << '\n';
for (int i = vec.size()-1; i >= 0; i -= 2)  // may not be big enough (2)
    cout << vec[i] << '\n';

Verängstigt? Verständlich! Lediglich die Zeile (1) ist korrekt. In den Zeilen (2) kann es passieren, dass die Variable i zu klein ist. Der Effekt ist dann gegebenenfalls ein Überlauf. Das gilt nicht für die Zeile (3), denn i ist vorzeichenlos. In diesem Fall winkt eine Modulo-Operation. Ich schrieb bereits in meinem letzten Artikel über dieses Phänomen: "C++ Core Guidelines: Regeln zu Anweisungen und zur Arithmetik". Um genau zu sein, war es die Regel ES.106.

Damit bleibt noch die Zeile 4 übrig. Sie ist mein eindeutiger Favorit. Was ist das Problem? vec.size() vom Typ std::size_t ist. std::size_t ist ein vorzeichenloser Typ und kann daher keine negativen Zahlen repräsentieren. Überlege nun, was passieren soll, wenn der Vektor leer ist. Das bedeutet, dass vec.size() - 1 genau -1 ist. Damit erhalten wir den maximalen Wert für std::size_t.

Das Programm index.cpp zeigt dieses besondere Verhalten:

// index.cpp

#include <iostream>
#include <vector>

int main(){
    
    std::cout << std::endl;
    
    std::vector<int> vec{};
    
    auto ind1 = vec.size() - 1 ;
    int ind2 = vec.size() -1 ;
    
    std::cout << "ind1: " << ind1 << std::endl;
    std::cout << "ind2: " << ind2 << std::endl;
    
    std::cout << std::endl;
    
}

Hier folgt auch schon die Ausgabe des Programms.

Die Guidelines schlagen vor, dass die Variable i den Typ gsl::index besitzen soll:

for (gsl::index i = 0; i < vec.size(); i += 2)             // ok
    cout << vec[i] << '\n';
for (gsl::index i = vec.size()-1; i >= 0; i -= 2)          // ok
    cout << vec[i] << '\n';

Falls das keine Option ist, verwende den Typ std::vector<int>::size_type für i.

Performanz ist die Domäne von C++! Ich denke, dass ist ein Glaubenssatz in der C++-Community. Daher war ich gespannt darauf, über die Regeln zur Performanz schreiben zu dürfen. Aber das ist kaum möglich, da die bestehenden Regeln sehr wenig Substanz besitzen. Meist bestehen sie nur aus dem Titel und einer Begründung. Dazu fehlt häufig auch die Begründung.

Da muss ich durch. Hier sind die ersten Regeln:

• Per.1: Don’t optimize without reason
• Per.2: Don’t optimize prematurely
• Per.3: Don’t optimize something that’s not performance critical
• Per.4: Don’t assume that complicated code is necessarily faster than simple code
• Per.5: Don’t assume that low-level code is necessarily faster than high-level code
• Per.6: Don’t make claims about performance without measurements

Anstelle jetzt allgemeine Sätze zu Gemeinplätzen von mir zu geben, werde ich ein paar Beispiele für die Regeln präsentieren. Los geht es mit den Regeln Per.4, Per.5 und P.6:

Per.4: Don’t assume that complicated code is necessarily faster than simple code

Per.5: Don’t assume that low-level code is necessarily faster than high-level code

Per.6: Don’t make claims about performance without measurements

Bevor ich meinen Artikel fortsetze, muss ich mich zuerst absichern. Ich empfehle, nicht das Singleton Pattern verwenden. Ich will nur darlegen, dass anspruchsvoller und Low-level-Code sich nicht immer auszahlt. Um meine Aussage zu belegen, werde ich natürlich die Performanz messen.

Lang, lang ist es her, da schrieb ich einen Artikel zur thread-sicheren Initialisierung des Singleton Pattern: "Thread sicheres Initialisieren eines Singleton". Die zentrale Idee des Artikels war es, das Singleton Pattern 40 Millionen Mal aus vier Threads aufzurufen und die Ausführungszeit zu messen. Das Pattern wird erst bei Bedarf initialisiert. Der erste Aufruf, der es verwendet, initialisiert es.

Ich habe das Singleton Pattern in vielen Variationen implementiert. Ich tat es mit einem std::lock_guard und der Funktion std::call_once in Kombination mit dem std::once_flag. Ich tat es mit einer statischen Variable. Ich wendete auch atomare Datentypen an und brach die Sequential-Konsistenz aus Performanzgründen.

In diesem Artikel werde ich die einfachste und die anspruchsvollste Implementierung vorstellen.

Die einfachste Implementierung ist das sogenannte Meyers' Singleton. Sie ist thread-sicher, da die C++-Laufzeit zusichert, dass Variablen mit Blockgültigkeit thread-sicher initialisiert werden.

// singletonMeyers.cpp

#include <chrono>
#include <iostream>
#include <future>

constexpr auto tenMill= 10000000;

class MySingleton{
public:
  static MySingleton& getInstance(){
    static MySingleton instance;                         // (1)
    // volatile int dummy{};
    return instance;
  }
private:
  MySingleton()= default;
  ~MySingleton()= default;
  MySingleton(const MySingleton&)= delete;
  MySingleton& operator=(const MySingleton&)= delete;

};

std::chrono::duration<double> getTime(){

  auto begin= std::chrono::system_clock::now();
  for ( size_t i= 0; i < tenMill; ++i){
      MySingleton::getInstance();                        // (2)
  }
  return std::chrono::system_clock::now() - begin;
  
};

int main(){
                                                          
    auto fut1= std::async(std::launch::async,getTime);
    auto fut2= std::async(std::launch::async,getTime);
    auto fut3= std::async(std::launch::async,getTime);
    auto fut4= std::async(std::launch::async,getTime);
    
    auto total= fut1.get() + fut2.get() + fut3.get() + fut4.get();
    
    std::cout << total.count() << std::endl;

}

Zeile (1) nützt die Zusicherung aus, dass das Singleton thread-sicher initialisiert wird. Jeder der vier Threads in der main-Funktion ruft 10 Millionen Mal das Singleton in Zeile (2) auf. Das macht in Summe 40 Millionen Aufrufe.

Das kann ich besser. In meiner zweiten Implementierung verwende ich atomare Datentypen, um das Singleton thread-sicher zu initialisieren. Meine Implementierung basiert auf dem berühmt-berüchtigten double-checked locking pattern. Der Einfachheit halber stelle ich nur die Implementierung der Klasse MySingleton vor.

class MySingleton{
public:
  static MySingleton* getInstance(){
    MySingleton* sin= instance.load(std::memory_order_acquire);
    if ( !sin ){
      std::lock_guard<std::mutex> myLock(myMutex);
      sin= instance.load(std::memory_order_relaxed);
      if( !sin ){
        sin= new MySingleton();
        instance.store(sin,std::memory_order_release);
      }
    }   
    // volatile int dummy{};
    return sin;
  }
private:
  MySingleton()= default;
  ~MySingleton()= default;
  MySingleton(const MySingleton&)= delete;
  MySingleton& operator=(const MySingleton&)= delete;

  static std::atomic<MySingleton*> instance;
  static std::mutex myMutex;
};


std::atomic<MySingleton*> MySingleton::instance;
std::mutex MySingleton::myMutex;

Es ist keine Geheimnis mehr: double-checked locking pattern is broken. Das gilt natürlich nicht für meine Implementierung. Falls du mir nicht glaubst, beweise mir das Gegenteil. Zuerst musst du dich in diesem Fall mit dem Speichermodell auseinandersetzen, danach die Acquire-Release-Semantik studieren und zuallerletzt dir Gedanken dazu machen, welche Synchronisations- und Ordnungsbedingungen diese in diesem konkreten Fall garantiert. Das ist keine einfache Aufabe. Was macht man nicht alles für die Performanz.

Ich habe die Regel Per.6 vergessen. Hier sind die Performanzahlen zum Meyers' Singleton auf Linux. Ich habe das Programm mit maximaler Optimierung übersetzt. Die Zahlen auf Windows befinden sich in einer ähnlichen Größenordnung.

Jetzt bin ich neugierig. Was sprechen die Performanzzahlen zu meinem hochoptimierten Code? Eine eindeutige Sprache:

50 Prozent langsamer, und wir wissen nicht einmal, ob die Implementierung korrekt ist. Nur zur Sicherheit: Die Implementierung ist korrekt.

In der Tat war das Meyers' Singleton die einfachste und performanteste Varianten ein Singleton Pattern thread-sicher umzusetzen. Weitere Details zu dem Singleton Pattern gibt es hier: "Thread-sicheres Initialisieren eines Singleton".

Wie geht's weiter?

Es gibt noch mehr als 10 Regeln zur Performanz in den Guidelines. Obwohl es relativ anspruchsvoll ist, über diese sehr allgemeinen Regeln zu schreiben, habe ich ein paar Ideen für den nächsten Artikel im Kopf.

Weitere Informationen

• Wahl des nächsten PDF-Päckchen. Auf meinem deutschen Blog und meinem englischen Blog findet gerade die Wahl zum nächsten PDF-Päckchen statt. Hier sind die Links zur Wahl:
• Deutscher Blog: Welches PDF-Päckchen soll ich zusammenstellen? Mache dein Kreuz!
  
• Englischer Blog: Which PDF bundle should I provide? Make your choice!

()