© Igor Zakharevich / 123RF.com

C++ bietet fünf sequenzielle Container an. Aus Perspektive der Performance betrachtet, reduziert sich diese Auswahl auf die zwei Container std::array und std::vector.

Die Bezeichnung sequenzielle Container beschreibt die Charakteristik der Container »std::array«, »std::vector«, »std::deque«, »std::list« und »std::forward_list«, die den sequenziellen Zugriff auf die enthaltenen Elemente ermöglichen.

Beste Freunde

In 99 Prozent aller Anwendungsfälle für einen sequenziellen Container sind »std::array« und »std::vector« die idealen Kandidaten. Höre ich Bedenken? Hier gilt die Faustregel: Falls es gilt, Elemente aus einem Container zu entfernen oder hinzuzufügen, ist »std::vector« der ideale Kandidat, anderenfalls »std::array«.

Die C++ Core Guidelines bestätigen die Faustregel mit der folgenden Formulierung: “Prefer using STL vector by default unless you have a reason to use a different container.” Laut der dortigen Beschreibung [1] punkten »std::array« und »std::vector« mit den folgenden Eigenschaften:

• “The fastest general-purpose access (random access, including being vectorization-friendly)”,
• “the fastest default access pattern (begin-to-end or end-to-begin is prefetcher-friendly)”, und
• “the lowest space overhead (continuous layout has zero per-element overhead, which is cache-friendly)”.

Dieser Artikel dreht sich um die Performance der sequenziellen Container. Damit steht der zweite Punkt der Aufzählung im Fokus dieses Artikels. Allerdings gilt es, vorab eine deutlich elementarere Frage zu beantworten: Welche sequenziellen Container bietet C++ an? Die einfache Antwort lautet: »std::array«, »std::vector«, »std::deque«, »std::list« und »std::forward_list« [2]. Eine kompakte Übersicht liefern die Tabelle “Sequenzielle Container in C++” sowie Abbildung 1. Abhängig vom Anwendungsfall passt »std::vector« in 95 Prozent aller Fälle, in denen man einem Container Elemente hinzufügen oder welche daraus löschen will.

Abbildung 1: Die Schlüsseleigenschaften sequenzieller Container in C++.

0(i) bezeichnet die Komplexität (Laufzeit) einer Operation. Dabei bedeutet 0(1), dass die Laufzeit einer Operation auf einem Container konstant ist, und 0(n), dass sie linear von der Anzahl der Elemente abhängt. Bei einem »std::vector« oder »std::array« bleibt die Zugriffszeit unabhängig von der Anzahl der Elemente immer dieselbe. Hingegen ist das Einfügen oder Löschen eines beliebigen Elements bei »k« zusätzlichen Elementen bei einem »std::vector« um den Faktor »k« langsamer.

Zwar bieten »std::array« und »std::vector« ähnliche Zugriffszeiten, weisen aber ein großen Unterschied auf, den viele Entwickler nicht im Blick haben. Ein »std::array« wird typischerweise auf dem Stack angelegt, »std::vector« verwaltet seine Elemente jedoch auf dem Heap. Das bedeutet, dass ein »std::array« nur eine eingeschränkte Anzahl von Elementen besitzen kann, während ein »std::vector« eine fast unbeschränkte Anzahl von Elementen umfassen darf.

Mit C++11 unterstützen »std::vector« und »std::deque« die neue Member-Funktion »shrink_to_fit()«. Die Anzahl der Elemente (»size«) eines »std::vector« oder »std::deque« ist in der Regel kleiner als die Anzahl der für einen »std::vector« oder »std::deque« reservierten Elemente (»capacity«). Das hat einen einfachen Grund: Das Vergrößern eines »std::vector« oder eines »std::deque« führt nicht automatisch zu einer neuen, teuren Speicheranforderung. Die neue Member-Funktion »shrink_to_fit()« erlaubt es, die Kapazität eines »std::vector« oder »std::deque« auf dessen tatsächliche Größe zu reduzieren. Dieser Aufruf ist aber nicht bindend, die Laufzeitumgebung kann ihn ignorieren. Auf den populären Plattformen hat »shrink_to_fit()« aber den gewünschten Effekt.

Auch wenn der Zugriff auf die Elemente eines »std::vector« genauso wie der Zugriff auf ein »std::deque« die Komplexität 0(1) besitzt, bedeutet das keineswegs, dass beide Operationen gleich schnell ablaufen. Die Komplexitätszusicherung 0(1) für das Einfügen oder Löschen neuer Elemente in eine doppelt oder einfach verkettete Liste »std::list« beziehungsweise »std::forward_list« gilt nur unter der Annahme, dass bereits ein Iterator auf das Element verweist.

Es muss schon einen überzeugenden Grund geben, um den sehr speziellen sequenziellen Container »std::forward_list« zu verwenden. Sie verwenden das auf minimale Speicheranforderung und hohe Performance optimierte »std::forward_list« dann, wenn das Hinzufügen, Extrahieren oder auch Löschen von Elementen nur benachbarte Elemente betrifft. Der Grund für dieses besondere Verhalten ist offensichtlich: »std::forward_list« kennt als einfach verknüpfter Container nur einen Vorwärts-Iterator, aber nicht seine Größe. Damit lässt sich eine »std::forward_list« in vielen Algorithmen der STL nicht verwenden.

Speicherzugriffe

Wie bereits erläutert, steht die Zugriffszeit O(1) auf die Elemente eines »std::vector« oder eines »std::deque« nicht für dieselbe Zahl. Der entscheidende Faktor für die Performance ist das Speicherlayout des Containers.

Beim Lesen einer Variable des Typs »int« aus dem Hauptspeicher liest die CPU tatsächlich deutlich mehr als 4 Bytes aus dem RAM und speichert sie im Cache. Der Vorgang erfolgt für eine komplette Cacheline, die auf modernen Architekturen typischerweise 64 Bytes umfasst. Bei einer erneuten Variablenanforderung aus dem Hauptspeicher befindet sich der gesuchte Wert meist bereits im Cache, sodass die Leseoperation deutlich schneller erfolgt.

Das Programm aus Listing 1 erlaubt einen Vergleich, was diese Aussage für einen »std::vector«, eine »std::deque«, eine »std::list« und eine »std::forward_list« bedeutet, indem es die Elemente addiert. Aufgrund der limitierenden Größe bleibt dabei das »std::array« außen vor.

#include <forward_list>
#include <chrono>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <string>
#include <vector>
#include <numeric>
#include <random>
const int SIZE = 100'000'000;
template <typename T>
void sumUp(T& t, const std::string& cont) {
  std::cout << std::fixed << std::setprecision(10);
  auto begin= std::chrono::steady_clock::now();
  std::size_t res = std::accumulate(t.begin(), t.end(), 0LL);
  std::chrono::duration<double> last=  std::chrono::steady_clock::now() - begin;
  std::cout << cont <<  '\n';
  std::cout << "time: " << last.count() << '\n';
  std::cout << "res: " << res << '\n';
  std::cout << '\n';
  std::cout << '\n';
}
int main(){
  std::cout << '\n';
  std::random_device seed;
  std::mt19937 engine(seed());
  std::uniform_int_distribution<int> dist(0, 100);
  std::vector<int> randNumbers;
  randNumbers.reserve(SIZE);
  for (int i=0; i < SIZE; ++i){
      randNumbers.push_back(dist(engine));
  }
  {
    std::vector<int> myVec(randNumbers.begin(), randNumbers.end());
    sumUp(myVec,"std::vector<int>");
  }
  {
    std::deque<int>myDec(randNumbers.begin(), randNumbers.end());
    sumUp(myDec,"std::deque<int>");
  }
  {
    std::list<int>myList(randNumbers.begin(), randNumbers.end());
    sumUp(myList,"std::list<int>");
  }
  {
    std::forward_list<int>myForwardList(randNumbers.begin(), randNumbers.end());
    sumUp(myForwardList,"std::forward_list<int>");
  }
}

Das Programm in Listing 1 erzeugt zuerst einmal 100 Millionen Zufallszahlen zwischen 0 und 100 (Zeilen 29 bis 36). Dann summiert es die Zahlen mit einem »std::vector« (Zeile 39), einer »std::deque« (Zeile 43), einer »std::list« (Zeile 47) und einer »std::forward_list« (Zeile 51). Die eigentliche Arbeit findet in der Funktion »sumUp()« statt (Zeilen 14 bis 25).

Schnell ist das Programm mit maximaler Optimierung unter Linux (GCC) und Windows (Visual Studio Compiler) übersetzt. Abbildung 2 zeigt die Laufzeit in Sekunden auf dem Linux-Rechner (einem Desktop), Abbildung 3 die auf dem Windows-Rechner (einem Laptop). Interessant ist vor allem die relative Performance beim Lesen der vier unterschiedlichen Container, die Abbildung 4 visualisiert.

Abbildung 2: Performance unter Linux.

Abbildung 3: Performance unter Windows.

Abbildung 4: Sequenzielle Container: Vergleich der Performance unter Linux und Windows.

Fazit

Aus den Zahlen lässt sich eine einfache Beobachtung ableiten: Je besser eine Datenstruktur für Cachelines optimiert ist, desto schneller klappt der Zugriff. Am schnellsten arbeitet »std::vector«, dann folgen »std::deque« und als Schlusslichter »std::list« sowie »std::forward_list«. Der hier außen vor gebliebene »std::string« bietet dasselbe Interface an wie »std::vector« und teilt auch dessen Performance-Charakteristik.

Ausblick

Gibt es eine ähnlich einfache Faustregel wie bei den sequenziellen Containern auch für die Performance assoziativer Container wie »std::map« und »std::unordered_map«? Die einfache Antwort lautet ja. Warum, das erklärt der nächste Artikel dieser Serie. (jcb/jlu)