© SvitlanaPonurkina-123RF

Entwickler schätzen C++ vor allem wegen seiner Performance. Doch nicht jede Optimierung ist eine gute Optimierung.

Der heutige Artikel zu den C++ Core Guidelines beschäftigt sich mit einer ureigenen Domäne von C++: Performance. Allerdings kommt es hier häufig zu einer unheiligen Allianz: Entwickler, die sich überschätzen, und unterschätzte Optimierer. Da tut Aufklärung Not.

Weise Worte

Bevor sich der Artikel dem emotionalen Performance-Thema widmet, bringen ein paar weise Worte erste Erleuchtung. Donald Knuth [1] brachte das Problem der falsch eingesetzten Optimierung in seinem Artikel “Computer Programming as an art” [2] bereits 1974 auf den Punkt: “The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming.”

Abbildung 1: Die sechs Regeln aus der Performance-Abteilung der C++ Core Guides klopfen voreiligen Entwicklern auf die Finger.

In eine ähnliche Kerbe schlagen auch die ersten sechs Regeln der C++ Core Guidelines [3], die nicht ohne Grund alle negativ formuliert sind (Abbildung 1). Doch welche Handlungsempfehlungen lassen sich aus den weisen Worten von Donald Knuth und den Guideline-Regeln ableiten?

Am Anfang war die Zahl

Ein schnelles Programm ist der Stolz jedes erfahrenen C++-Entwicklers. Daher verwundert es wenig, dass viele Programmierer vermeintliche Performance-Probleme ihres Programms aus einem diffusen Gefühl heraus lösen. Bitte aufhören! Im besten Fall kosten die Optimierungen nur viel Schweiß und Zeit, im schlechtesten machen sie das Programm langsamer und den Code komplizierter. Im Ergebnis erfordert jeder weitere Versuch, das Programm zu optimieren, deutlich mehr Arbeitsaufwand.

Zunächst mal sollte jede Optimierung eines Programms die folgenden drei Fragen beantworten: Welcher Teil des Programms ist der Flaschenhals? Wie schnell muss das Programm sein? Wie schnell könnte das Programm potenziell sein? Die Antworten auf diese Fragen enthalten bereits eine Handlungsanweisung in fünf Schritten, um ein Programm zu optimieren:

• Einen Performance-Test erstellen und umsetzen.
• Die Performance-Engstelle suchen.
• Einen Referenzwert für optimale Performance ermitteln.
• Die Optimierung umsetzen.
• Die Performance-Veränderungen messen.

Zunächst gilt es, den Flaschenhals des Programms zu ermitteln. Dazu muss der Entwickler Performance-Tests entwickeln und ausführen. Diese Tests gehören zum Programm und sollten daher auch mit unter die Versionskontrolle, um sie später bei Bedarf zu wiederholen.

Um es etwas formaler auszudrücken: Die Performance-Charakteristik eines Programms bildet eine wichtige Komponente von dessen nichtfunktionalen Anforderungen. Während also funktionale Anforderungen die gewünschten Fähigkeiten des Systems abdecken (“Was soll das System tun?”), bestimmen die nichtfunktionalen Anforderungen über die Qualität eines Programms. Interessanterweise scheitern die meisten Projekte an den nichtfunktionalen Anforderungen [4].

Liegen die Zahlen auf dem Tisch und ist der Flaschenhals identifiziert, gilt es innezuhalten und die Zahlen zu interpretieren. Genau diesen Schritt ignorieren Entwickler tendenziell allzu häufig. Denn über die weitere erfolgreiche Analyse entscheiden die stark korrelierten zwei folgenden Fragen: Wie weit müsste der Flaschenhals sein? Wie weit kann der Flaschenhals im Optimalfall sein?

Die erste Frage definiert die Grenzen der Optimierung. Die zweite gibt Aufschluss darüber, ob die Optimierung überhaupt erfolgreich sein kann. Vernachlässigt der Entwickler die erste Frage, führt das vor allem zu unnötigem Optimieren. Beantwortet er zweite Frage nicht, führt das zu einer erfolglosen Optimierung. Zum Beispiel kann eine rechenintensive Operation, die der Entwickler auf n CPUs verteilt, maximal n-mal so schnell laufen wie auf einer einzelnen CPU.

Nach dem Abarbeiten der Optimierung gilt es, die Ergebnisse zu protokollieren und die Performance-Tests unter Versionskontrolle zu stellen. Warum? Zum einen erlebte es der Autor dieser Zeilen schon zu häufig, dass die Ergebnisse früher Performance-Test vergessen oder infrage gestellt wurden. Zum anderen muss der Programmierer den Performance-Test erneut starten, sobald sich die Randbedingungen ändern. Zu solchen variablen Randbedingungen zählen neue Hardware, ein aktualisierter oder neuer Compiler und auch schon andere Compiler-Flags.

Nach so viel Theorie zeigt der Artikel die fünf Schritte nun exemplarisch an einem Beispiel.

Wenn es schnell sein muss

Vor langer Zeit schrieb der Autor einen Blog-Artikel über eine Thread-sichere Initialisierung des Singleton-Patterns [5]. Die zentrale Idee des Artikels lag darin, das Singleton 40 Millionen Mal aus vier Threads aufzurufen und die Ausführungszeit zu messen. Das Singleton wird dabei erst bei Bedarf initialisiert. Zugleich ist der erste Aufrufer, der es verwendet, für seine Initialisierung verantwortlich.

Der Artikel implementierte das Singleton-Pattern in vielen Variationen. Zum Einsatz kamen ein »std::lock_guard« sowie die Funktion »std::call_once« in Kombination mit dem »std::once_flag«. Auch statische Variablen mit Blockgültigkeit waren mit von der Partie. Zwei Implementierungen setzten auf atomare Datentypen, eine davon brach die sequenzielle Konsistenz aus Performance-Gründen.

Der vorliegende Artikel vergleicht unter dem Aspekt der Performance nur die einfachste sowie die anspruchsvollste Implementierung. Die einfachste ist das sogenannte Meyers-Singleton. Es ist Thread-sicher, da die C++-11-Laufzeit zusichert, dass sie Variablen mit Blockgültigkeit Thread-sicher initialisiert. Die komplizierteste Variante verwendet atomare Variablen mit Acquire-Release-Semantik.

#include <chrono>
#include <iostream>
constexpr auto tenMill = 10000000;
class MySingleton{
public:
  static MySingleton& getInstance(){
    static MySingleton instance;
    volatile int dummy{};
    return instance;
  }
private:
  MySingleton() = default;
  ~MySingleton() = default;
  MySingleton(const MySingleton&) = delete;
  MySingleton& operator=(const MySingleton&) = delete;
};
int main(){
  constexpr auto fourtyMill = 4 * tenMill;
  auto begin= std::chrono::system_clock::now();
  for (size_t i = 0; i <= fourtyMill; ++i){
    MySingleton::getInstance();
  }
  auto end = std::chrono::system_clock::now() - begin;
  std::cout << std::chrono::duration<double>(end).count() << std::endl;
}

Der Flaschenhals des Programms lässt sich einfach identifizieren: Es geht um 40 Millionen Aufrufe des Singleton aus vier Threads. Welche Performance kann das Programm maximal besitzen? In diesem Fall lässt sich die untere Schranke für die Performance-Messung einfach ermitteln. Wenn vier Threads jeweils ein Singleton 10 Millionen Mal aufrufen, muss die addierte Ausführungszeit der vier Threads größer sein als wenn ein Thread ein Singleton 40 Millionen Mal aufruft: Im Gegensatz zum Single-Thread-Fall muss die Multi-threaded-Variante die Aufrufe zusätzlich noch synchronisieren.

Das Programm aus Listing 1 lief auf einem Linux-Desktop mit vier Kernen. Als Compiler kam GCC 6.2.1 zum Einsatz, wobei das Programm mit maximaler Optimierung übersetzt wurde. Abbildung 2 zeigt das Setup des Compilers.

Abbildung 2: GCC 6.2.1 übersetzte im Test den Code mit der hier gezeigten Konfiguration.

Als Referenzimplementierung für das Singleton-Pattern diente das bereits erwähnte Meyers-Singleton, benannt nach Scott Meyers [6]. Die Eleganz dieser Implementierung besteht darin, dass das Singleton-Objekt in Zeile 9 eine statische Variable mit Blockgültigkeit ist. Daher initialisiert der Code »instance« nur genau ein Mal. Diese Initialisierung findet dann statt, wenn er die statische Methode »getInstance()« (Zeilen 8 bis 12) das erste Mal ausführt.

#include <chrono>
#include <iostream>
#include <future>
constexpr auto tenMill = 10000000;
class MySingleton{
public:
  static MySingleton& getInstance(){
    static MySingleton instance;
    volatile int dummy{};
    return instance;
  }
private:
  MySingleton() = default;
  ~MySingleton() = default;
  MySingleton(const MySingleton&) = delete;
  MySingleton& operator=(const MySingleton&) = delete;
};
std::chrono::duration<double> getTime(){
  const auto begin = std::chrono::system_clock::now();
  for (size_t i = 0; i <= tenMill; ++i){
      MySingleton::getInstance();
  }
  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);
    const auto total= fut1.get() + fut2.get() + fut3.get() + fut4.get();
    std::cout << total.count() << std::endl;
}

Besondere Aufmerksamkeit verdient die »volatile«-Variable in Zeile 10. Übersetzt der Autor das Programm mit maximaler Optimierung, optimiert der Compiler den Aufruf »MySingleton::getInstance()« in Zeile 25 weg oder – mit einem neueren GCC – sogar die ganze For-Schleife. Der »volatile«-Aufruf erzeugt keinen Effekt, er verhindert nur die Aggressivität des Optimierers. Abbildung 3 stellt die Referenzzahl für Linux im Single-threaded-Anwendungsfall vor.

Abbildung 3: 40 Millionen Single-threaded Singleton-Aufrufe.

Das Beispielprogramm in Listing 2 basiert auf dem Programm in Listing 1. Hier kommen jedoch vier Threads zum Einsatz. Die Performance-Zahlen für Linux in Abbildung 4 sind recht beeindruckend. Die addierte Ausführungszeit des Meyers-Singletons steigt nur um etwa 30 Prozent. Sie liegt damit schon verdächtig nah an der unteren Schranke, obwohl das System die gleichzeitigen Zugriffe auf das Singleton synchronisieren muss.

Abbildung 4: Multi-threaded-Singleton mit dem Meyers-Singleton.

Das gute Ergebnis hielt den Autor jedoch nicht davon ab, noch weiter an der Performance-Schraube zu drehen und zum Äußersten zu greifen: dem Einsatz von atomaren Variablen. Atomare Variablen machen die Implementierung des Singleton-Patterns deutlich anspruchsvoller. Selbst die verwendete Speicherordnung passt der Entwickler jetzt feinkörnig für jede atomare Operation an – schneller geht es kaum. Der Einfachheit halber stellt Listing 3 nur die Implementierung des Singletons vor, da das Hauptprogramm nahezu identisch ist.

Zugegeben, diese Implementierung der statischen Methode »getInstance()« ist nichts für schwache Nerven. Weiter unten folgt eine vereinfachte Erklärung des Quellcodes. Für starke Nerven bietet Jeff Preshing auf seinem Blog “Preshing on Programming” [7] eine deutlich detailliertere Erklärung an.

Die hier gezeigte Implementierung basiert auf den Double-checked Locking-Pattern [8]. Hierzu prüft zuerst die Zeile 13 auf billige Weise, ob das Singleton bereits initialisiert ist. Falls nicht, folgt unmittelbar in Zeile 14 ein teurer Lock-Aufruf. Die Tatsache, dass zwischen den Zeilen 13 und 14 ein anderer Thread starten könnte, erfordert einen zweiten Check in Zeile 16. Die zwei Checks und der Lock erklären dann auch den Namen des Patterns.

Nun aber zu den atomaren Variablen, die zusichern, dass diese Methode Thread-sicher ist. Die entscheidende Beobachtung: Die »acquire«-Operation in Zeile 12 beruht auf derselben atomaren Variable »instance« wie die »release«-Operation in Zeile 18. Das etabliert eine sogenannte Acquire-Release-Relation. Das bedeutet, dass sich eine »acquire«-Operation auf einer atomaren Variable mit einer »release«-Operation auf derselben atomaren Variable synchronisiert und eine »happen-before«-Relation etabliert.

Das bedeutet im Wesentlichen, dass die »acquire«-Operation aus Zeile 12 den Effekt der »release«-Operation (Zeile 18) wahrnimm und die zusätzliche Ordnungsgarantie gilt: Das Programm initialisiert das Singleton in Zeile 17 vor dem Einsatz des Singleton in Zeile 12. Genau diese Beobachtung sichert zu, dass diese Implementierung Thread-sicher ist.

#include <atomic>
#include <iostream>
#include <future>
#include <mutex>
#include <thread>
constexpr auto tenMill = 10000000;
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;

Geschafft! Anspruchsvoller lässt sich das Singleton-Pattern wohl nicht mehr Thread-sicher umsetzen. Wenn sich Komplexität auszahlt, dann sollte dies die schnellste Implementierung des Singleton-Pattern sein. Sollte – denn Abbildung 5 lässt die Performance-Träume des Autors abrupt platzen. Die Thread-sichere Umsetzung des Singleton-Pattern mithilfe der Acquire-Release-Semantik läuft fast nur halb so schnell wie die Thread-sichere Umsetzung des Meyers-Singleton in Abbildung 4.

Abbildung 5: Multi-threaded Singleton mit atomaren Variablen und Acquire-Release Semantik.

Leider ist das noch nicht das Ende der Lektion zur falsch-motivierten Optimierung. Würde der Autor behaupten, dass in der Implementierung von Listing 3 ein Fehler steckt, könnten die meisten Leser diese Behauptung weder widerlegen noch bestätigen. Die hochkomplexe Implementierung mithilfe der Acquire-Release-Semantik ist nicht nur langsamer als die Implementierung basierend auf dem Meyers-Singleton, sondern auch sehr schwer zu verstehen.

Wie geht’s weiter?

C++ wäre nicht C++, wenn das bereits alle Regeln zur Performance in den C++ Core Guidelines wären. Im nächsten Artikel dieser Reihe geht es insbesondere um Datenstrukturen, die für schnelles Verarbeiten optimiert sind. (kki)