Newsletter heise-Bot heise-Bot Push Nachrichten Push Push-Nachrichten

C++ Core Guidelines: Die verbleibenden Regeln zur Performanz

Es fehlten in der Blogserie noch zehn weitere Regeln zur Performanz. Das hört sich nach einem sehr langen Artikel an, ist er aber nicht, da nur zwei Regeln einen Inhalt besitzen.

In Pocket speichern vorlesen Druckansicht 23 Kommentare lesen
Lesezeit: 10 Min.
Developer
Von
  • Rainer Grimm

Heute geht es um die zehn verbleibenden Regeln zur Performanz. Das hört sich nach einem sehr langen Artikel an, ist er aber nicht, da nur zwei Regeln einen Inhalt besitzen.

Hier sind die restlichen Regeln zur Performanz:

Ich werde einen genaueren Blick auf die Regeln Per.11 und Per.19 werfen.

Per.11: Move computation from run time to compile time

Das Beispiel zeigt den einfachen gcd-Algorithmus, der den größten gemeinsamen Teiler zweier Zahlen zur Laufzeit des Programms ermittelt. gcd verwendet für seine Berechnung den euklidischen Algorithmus:

int gcd(int a, int b){
    while (b != 0){
        auto t= b;
        b= a % b;
        a= t;
    }
    return a;
}

Indem gcd als konstanter Ausdruck deklariert wird, lässt er sich einfach zur Funktion erklären, die auch zur Übersetzungszeit ausgeführt werden kann. Es gibt in C++14 nur noch wenige Einschränkungen für constexpr-Funktionen. gcd darf keine statischen oder thread-lokale Variablen verwenden. Darüber hinaus sind keine Ausnahmebehandlungen und goto-Anweisungen zulässig. Variablen müssen direkt initialisiert werden und einen literalen Typ besitzen.

Das muss ich ausprobieren:

// gcd.cpp

#include <iostream>

constexpr int gcd(int a, int b){
    while (b != 0){
        auto t= b;
        b= a % b;
        a= t;
    }
    return a;
}

int main(){

    std::cout << std::endl;

    constexpr auto res = gcd(121, 11);            // (1)
    std::cout << "gcd(121, 11) = " << res << std::endl;

    auto val = 121;                               // (3)
    auto res2 = gcd(val, 11);                     // (2)
    std::cout << "gcd(val, 11) = " << res2 << std::endl;
  
    std::cout << std::endl;

}

Das gcd zur constexpr-Funktion erklärt wird, heißt nicht, dass sie automatisch zur Übersetzungszeit ausgeführt wird. Das bedeutet nur, dass die Funktion gcd das Potenzial besitzt, zur Übersetzungszeit ausgeführt zu werden. Eine constexpr-Funktion muss zur Übersetzungszeit ausgeführt werden, wenn sie in einem konstanten Ausdruck verwendet wird. (1) ist ein konstanter Ausdruck, da ich das Ergebnis mit der constexpr-Variable res annehme (2). (3) ist kein konstanter Ausdruck, denn res2 ist kein konstanter Ausdruck. Wenn ich res2 als constexpr auto res2 deklariere, bekomme ich einen Fehler. Der Grund ist, dass val kein konstanter Ausdruck ist. Der Screenshot zeigt die Ausgabe des Programms;

Hier nochmals meine zentrale Aussage: Du kannst eine constexpr Funktion zur Laufzeit und zur Übersetzungszeit ausführen. Um zur Übersetzungszeit ausgeführt werden zu können, benötigt sie Argumente, die konstante Ausdrücke sind.

Du glaubst mir nicht, dass die Zeile (1) zur Übersetzungszeit ausgeführt wird? Hier ist der Beweis: Die Abbildung zeigt die der Zeile (1) entsprechenden Assember Anweisungen, die der GCC 7.3 mit maximaler Optimierung erzeugt hat. Die Ausgabe habe ich mithilfe des Compiler Explorer von Matt Godbolt erzeugt.

Der Funktionsaufruf gcd(121, 11) reduziert sich direkt auf das Ergebnis: 11.

Templates werden gerne verwendet, um Entscheidungen zur Übersetzungszeit zu treffen. Die C++ Core Guidelines stellen ein schönes Beispiel dazu vor. Eine beliebte Technik ist es, einen Handle für das Speichern von Daten auf dem Stack anzulegen, wenn diese klein genug sind. Wenn nicht, werden die Daten auf dem Heap verwaltet. Hier ist das Beispiel:

template<typename T>
struct Scoped {     // store a T in Scoped
        // ...
    T obj;
};

template<typename T>
struct On_heap {    // store a T on the free store
        // ...
        T* objp;
};

template<typename T>
using Handle = typename std::conditional<(sizeof(T) <= on_stack_max),  // (1)
                    Scoped<T>,      // first alternative        (2)
                    On_heap<T>      // second alternative       (3)
               >::type;

void f()
{
    Handle<double> v1;                   // the double goes on the stack
    Handle<std::array<double, 200>> v2;  // the array goes on the free store
    // ...
}

Wie funktioniert das Ganze? std::conditional in Zeile (1) ist ein ternärer Operator aus der Type-Traits Bibliothek. Im Gegensatz zum ternären Operator (a ? b : c) wird er aber zur Übersetzungszeit ausgeführt. Das bedeutet, falls std::condition<sizeof(T) <= on_stack_max) zu true evaluiert wird, wird die erste Alternative ausgewählt. Falls nicht, die zweite.

Per.19: Access memory predictably

Was soll das heißen? Wenn eine Variable int vom Hauptspeicher gelesen wird, wird tatsächlich deutlich mehr als 4 Bytes vom Speicher gelesen. Ein ganze Cacheline wird gelesen und im Cache gespeichert. Auf modernen Architekturen besitzt eine Cacheline typischerweise 64 Bytes. Wenn nun nochmals eine Variable aus dem Hauptspeicher angefordert wird und sich die Variable bereits im Cache befindet, verwendet die Leseoperation direkt den Cache und ist damit deutlich schneller.

Ein Container wie std::vector, der seine Daten in einem kontinuierlichen Speicherbereich speichert, ist eine Datenstruktur, die Cachelines optimal ausnützt. Ein std::vector besitzt eine Größe und eine Kapazität und wächst nur in eine Richtung. Seine Kapazität ist größer als seine Größe und sie zeigt an, wann Speicher neu allokiert werden muss. Diese Argumentation gilt auch für std::string und std::array. Das std::array besitzt aber keine Kapazität.


Meine Argumentation zum std::vector gilt aber nicht für std::list oder std::forward_list. Beide Container bestehen aus Knoten, die doppelt oder einfach verknüpft sind.

Die std::foward_list kann nur in eine Richtung wachsen.

std::deque bewegt sich zwischen beiden Extremen , denn sie ist eine Art doppelt verkettete Liste von Speicherbereichen.


Dies war die Theorie zu den Cachelines. Nun bin ich aber neugierig: Macht es einen Performanzunterschied, alle Elemente einer std::vector, einer std::deque, einer std::list und einer std::forward_list zu lesen und mit std::accumulate ihre Summe zu berechnen? Dieses kleine Programm liefert die Antwort:

// memoryAcess.cpp

#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){            // (6)
  
  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 <<  std::endl;
  std::cout << "time: " << last.count() << std::endl;
  std::cout << "res: " << res << std::endl;
  std::cout << std::endl;
 
  std::cout << std::endl;
     
}

int main(){
    
    std::cout << std::endl;
    
    std::random_device seed;                            // (1)
    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>");                 // (2)
    }

    
    {
      std::deque<int>myDec(randNumbers.begin(), randNumbers.end());
      sumUp(myDec,"std::deque<int>");                 // (3)
    }
    
    {
      std::list<int>myList(randNumbers.begin(), randNumbers.end());
      sumUp(myList,"std::list<int>");                 // (4)
    }
    
    {
      std::forward_list<int>myForwardList(randNumbers.begin(), randNumbers.end());
      sumUp(myForwardList,"std::forward_list<int>");  // (5)
    } 
    
}

Das Programm memoryAccess.cpp erzeugt zuerst einmal 100 Millionen Zufallszahlen zwischen 0 and 100 (1). Dann summiert es die Zahlen mit einem std::vector (2), einer std::deque (3), einer std::list (4) und einer std::forward_list (5) zusammen. Die eigentliche Arbeit findet in der Funktion sumUp (6) statt. Ich nehme an, dass Linux und Windows eine ziemlich ähnliche Implementierung des std::accumulate-Algorithmus verwenden. 

template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init)
{
    for (; first != last; ++first) {
        init = init + *first;
    }
    return init;
}

Daher ist die Zugriffszeit auf die Elemente der Container der dominante Faktor für die Gesamtperformanz.

Ich übersetzte das Programm mit maximaler Optimierung unter Linux und Windows. Mich interessiert in diesem Fall nicht der Performanzunterschied zwischen Linux und Windows, da dies ein Vergleich zwischen einem Desktop-PC und einem Laptop wäre. Mich interessiert die relative Performanz der vier Container. Hier ist sie:

Für das Gesamtbild. Dies sind meine Beobachtungen:

  • std::vector ist auf Linux 10-mal schneller als std::list oder std::forward_list; std::vector ist auf Windows 30-mal schneller als std::list oder std::forward_list.
  • std::vector ist auf Linux 1,5-mal schneller als std::deque und auf Windows 5-mal schneller als std::deque. Der Grund ist vermutlich, dass die zusammenhängenden Speicherbereiche auf Linux größer sind als auf Windows. Damit ist die Zugriffszeit auf Linux der eines std::vector sehr ähnlich.
  • std::deque ist 6-mal schneller als std::list oder std::forward_list. Dies gilt für Linux und Windows.
  • std::list und std::forward_list sind ähnlich schnell auf Linux und Windows.

Ich will meine Performanzzahlen nicht überbewerten, aber eine Beobachtung lässt sich auf jeden Fall ableiten. Je optimierter eine Datenstrukur für Cachelines ist, desto schneller ist die Zugriffszeit: std::vector > std::deque > (std::list, std::forward_list).

Wie geht's weiter?

Dies waren die Regeln zur Performanz. Mit dem nächsten Artikel werde ich beginnen, zu den Regeln zur Concurrency zu schreiben.

Weitere Informationen

Die neuen PDF-Päckchen stehen zum Download bereit:

()

Spiele

nach oben
Alle Angebote
Newsletter heise-Bot heise-Bot Push Nachrichten Push Push-Nachrichten