C++Guns – RoboBlog blogging the bot

Von der Compiler Optimierung O3 habe ich mir keine weiteren Geschwindigkeitsgewinn erhofft, aber dass das Programm doppelt so langsam! wurde, da stand mir dann doch der Mund offen ;)
Das ist btw. auch das erste mal in meinem Programmiererleben, dass O3 die Laufzeit wirklich deutlich verschlechtert. Bisher hatte ich nur davon gehört. Ein schneller Blick in den Profiler zeigt auch warum. Gab es bei O2 und der innersten Schleife ein paar 100k Branch Mispredicts, waren es bei O3 auf einmal ein paar Millionen! Die Stelle im Code war auch im ersten Teil schon etwas verwirrend. Anscheinend gibt es eine Code Optimierung, welche die Verzweigung in der min() Funktion entfernt, ganz ohne Bithacks.
Nun war es schon spät am Abend, aber die Sache musste unbedingt untersucht werden! Also habe ich dem vom Compiler erzeugten Assembler Code studiert und konnte die Sache auf ein Minimalbeispiel runter brechen.

Betrachtet werden muss nur die innerste Schleife, da nur hier die min() Funktion vorkommt.

#include <string>
#include <vector>

void func(size_t N) {
    std::vector<int> v0(N+1), v1(N+1);

    for(size_t i=0; i < N; ++i) {   
        v1[i+1] = std::min(v0[i], v0[i+1]);
    }
}

Es wird paarweise das Minimum gesucht. Wird der Eingangs Array mit Zufallszahlen gefüllt, so muss die spekulative Ausführung der min() Funktion, also Branch Mispredict 50% betragen. Der Compiler erkennt dies irgendwie, und produziert folgenden Assembler Code ohne spekulative min() Funktion.

  mov ecx, DWORD PTR [rbx]             ecx = v0[0]
  xor edx, edx                         i = 0
.L10:                                  for()
  add rdx, 1                           ++i
  mov esi, DWORD PTR [rbx+rdx*4]       esi = v0[i+1]
  cmp esi, ecx                         v0[i+1] <= ecx ?
  cmovle ecx, esi                      Wenn true: ecx = esi  Hier passiert die Magie.
  cmp rdx, rbp                         i < N
  mov DWORD PTR [rdi+rdx*4], ecx       v1[i+1] = ecx
  mov ecx, esi                         ecx = v0[i+1]
  jb .L10

Der Code ist nicht weiter schwer. Ich habe eine grobe Übersetzung in die rechte Spalte geschrieben. In der ersten Zeile wird das erste Element von v0 in das Register ecx kopiert. Und in der zweiten Zeile das Register edx, also die Laufvariable i, auf 0 gesetzt. Danach beginnt in Zeile 3 der Schleifenkörper.
Variable i wird um eins erhöht und Zeile fünf erfolgt der lesende Zugriff auf v0[i+1] und der Wert wird in das Register esi geladen.
In den Register esi und ecx stehen jetzt die beiden Werte die verglichen werden sollen. Dabei steht in ecx immer der Wert der Vorherigen Schleifeniteration. Damit wird nur ein RAM Zugiff pro Iteration benötigt.
Verglichen werden die Werte in Zeile 6 und das Ergebnis des Vergleichs wird in Zeile 7 ausgewertet. Nur wenn der neue Wert an Stelle i+1 kleiner oder gleich als der alte ist, wird mit dem neuen Wert der alte überschrieben.
Das Ergebnis wird in Zeile 9 nach v1[i+1] kopiert und in Zeile 10 wird ecx für die nächste Iteration vorbereitet. Zeile 8 und 11 entspricht noch dem Schleifenkopf mit dem Rücksprung zum Label L10.

Die Magie passiert bei der Assembler Instruktion cmovle. Hier wird ein Kopiervorgang nur dann ausgeführt, wenn das Ergebnis des Vergleichs eine Zeile weiter oben ergeben hat, dass die Zahl kleiner ist. Es gibt also keine Verzweigung im Programmablauf und keine spekulative Ausführung. Daher auch kein Branch Mispredict. Der Code kann mit voller CPU Power laufen. Besser geht es nur noch mit SSE und prefetch.

Dies erklärt also warum die min() Funktion keine Branch Mispredicts erzeugt. Aber warum läuft der O3 Optimierte Code nicht schneller. Auch die Assembler Code hab ich untersucht und der Grund ist unter anderem tree vectorize und andere Schleifen Optimierungen die der Compiler vornimmt. Aber die Schleife ist so super einfach, dass jegliche Optimierung nur eine Verschlechterung verursacht. Auch Loop unroll, welches per default nicht mit O3 aktiviert wird, wird die Laufzeit nicht verbessern. Da der Compiler nicht wissen kann, wie oft die innerste Schleife laufen wird. Daher müssen alle Möglichkeiten betrachtet werden und dies führt zu ein paar mehr Jumps im Code. Und schon führt die verlangsamte spekulative Code Ausführung wieder zu.

Was haben wir gelernt? Optimierung O2 ist gut. O3 bringt in der Summe genauso viel wie sie wieder zerstört. Bei HPC macht es keinen Sinn immer mit O3 zu kompilieren. Vielmehr muss der Algorithmus und die Arbeitsweise der Ziel CPU bis ins Detail verstanden werden. Danach kann die passende Compiler Optimierung ausgewählt werden.

Getestet mit GNU GCC 7.3

Funktionen können Funktionen als Rückgabe Type/Wert haben, solange sie die selbe Signatur vorweisen. Also z.B. alles Binary Funktionen mit Argumenten von Type double.

#include <iostream>
#include <vector>
#include <functional>

double add(const double lhs, const double rhs) {
    return lhs+rhs;
}

double mul(const double lhs, const double rhs) {
    return lhs*rhs;
}

// does not work
double PI() {
    return 3.14;
}

enum class Operator { add, mul, PI };

auto parse(Operator op) {
    switch(op) {
    case Operator::add: {
        return add;
    }
    case Operator::mul: {
        return mul;
    }
    case Operator::PI: {
        // error: inconsistent deduction for auto return type: ‘double (*)(double, double)’ and then ‘double (*)()’
        // return PI;
    }
    }
}

int main() {
    auto l = parse(Operator::add);
    auto result = l(1,2);
    std::cout << result << "\n";
}

Wen hat es nicht schon einmal gestört, dass std::sort() so transparent arbeitet? Manchmal muss man wissen welche Elemente beim Sortieren wohin verschoben werden. Sozusagen eine Permutation.
Manchmal ist es möglich, den zu sortierenden Daten eine ID mitzugeben. Aber oft nicht. Zum Beispiel arbeite ich mit 2D Punkten. Diese liegen natürlich schön dicht gepackt im std::vector, und die ID ist implizit durch die Position im vector gegeben. Durch das Sortieren würde sich auch die ID ändern, was aber nicht geht, da sie mit andern Daten noch verknüpft ist. Und die ID explicit abspeichern ist auch nicht gut, da dann die x/y Koordinaten vom Punkt im Speicher nicht mehr optimal ausgerichtet sind. Das Speicherlayout ändert sich zu meinen Ungunsten.

Zumindest in meinem Anwendungsfall brauche ich die sortierten Daten auch nur kurzzeitig, und die original Daten sollen unverändert bleiben. Es würde teilweise auch vollkommen langen, wenn die sort Funktion nur ein vector mit neuen IDs in der sortierten Reihenfolge zurück gibt.

Mein erster Ansatz ist, eine sort() Funktion zu schreiben, welche als zusätzliches Argument einen Visitor akzeptiert. Diese Funktion ruft die eigentlich std::sort() Funktion auf, so dass alles vom Standard noch eingehalten wird und sich auch nichts an der asymptotischen Laufzeit ändert.
Um eine ID zu erhalten, werte ich die Adresse der Elemente im std::vector aus. Damit die original Daten (erst einmal) in ihrer ursprünglichen Reihenfolge bleiben, wird ein zweiter std::vector mit Referenz Wrappern erstellt. Dies kostet pro Element den Speicherplatz einer Referenz, also 8byte. Dies ist, denke ich, nie ein Problem.

Nach der eigentlichen Sortierung mit std::sort ist so feststellbar, wie die Elemente im vector getauscht wurden. Damit wird das Visitor Objekt aufgerufen, so dass der Anweder den Permutationsvektor erstellen kann. Und die eigentlichen Daten werden durch swap sortiert.

Hier der Code der ersten Implementierung:

template<typename T, typename Allocator, typename Visitor>
inline void sort(std::vector<T,Allocator>& data,  Visitor&& vis) {
    std::vector<std::reference_wrapper<const T>> sorted;
    sorted.reserve(data.size());
    for(const auto& x : data) {
        sorted.push_back(std::cref(x));
    }

    std::sort(sorted.begin(), sorted.end());
    // ptrdiff_t is the signed equivalent to size_t
    for(size_t i=0; i < sorted.size(); ++i) {
        // get the address of an item in data, not sorted.
        const size_t idx1 = std::addressof(sorted[i].get()) - data.data();
        if(i < idx1) {
            std::swap(data[i], data[idx1]);
            vis(i, idx1);
        }
    }
}

//////

    struct Visitor {
        void operator()(size_t i, size_t j) {
            std::cout << "Swap idx " << i << " with idx " << j << "\n";
        }
    };

    std::vector<int> v {3,2,1,0};
    cpl::sort(v, Visitor());
    QVERIFY(std::is_sorted(v.begin(), v.end()));

Swap idx 0 with idx 3
Swap idx 1 with idx 2

Das Problem von impliziten Konversionen in C/C++ ist nicht neu. Wenn integer in floats und floats in integer kopiert werden und dabei die Werte der Zahlen verändert werden, kann das in wissenschaftlichen Anwendungen katastrophale Auswirkungen haben. Es müssen verschiedene Szenarien beachtet werden. So ist z.b. das kopieren eines 32bit integer in ein 64bit float kein Problem. Hingegen kann ein 32bit integer nicht ohne Verlust in ein 8bit integer gespeichert werden. Außer, es ist vom Algorithmus her unmöglich, dass sich die Wertebereiche überlappen.

Ich werde versuchen das Thema an Hand von Beispielen zu verdeutlichen. Sowohl für Funktions-Parameter als auch für Rückgabe Typen. Diverse Compilerparameter die man immer nutzen sollte, sowie ob Concepts hier helfen können.

Beispiel 1:
Drei Member Funktionen die jeweils ein bool übergeben, und bool zurück geben sollen. Aber der Programmierer hat sich vertan und übergibt einmal ein integer und float. Im zweiten Fall wird ein Integer zurück gegeben und im dritten Fall ist der Return Type falsch gewählt, aber es wird dennoch ein bool zurück gegeben.

Da eine implizite Umwandlung zwischen bool und integer/float erlaubt ist, erwarte ich nicht, dass der Compiler hier Fehlermeldungen wirft. Möglicherweise nur ein paar Warnings. Compiliert wird mit -Wall -Wextra -Wconversion

#include <cassert>
  
bool b_good(bool b) { 
  assert(b);
  return true;     
};

bool b_bad(bool b) { 
  assert(b);
  return 2;     
};

float b_bad2(bool b) {
  assert(b);
  return true; 
};

int main() {
  assert(b_good(true)); // okay
  assert(b_bad(4));     // bad but works. pass int ->   bool return int -> bool -> bool
  assert(b_bad2(2.0));  // bad but works. pass float -> bool return bool-> float -> bool
}

Der Compiler schweigt und das Programm läuft sauber durch. Salopp gesagt, alles was nicht 0 ist, ist wahr. Das funktioniert, aber fördert nicht die Fehlerfreiheit des Programms.

Mit narrowing conversion / brace initialization / list initialization, mit den geschweiften Klammern gibt es immerhin Warnungen bzw. gleich ein Fehler für Konstanten:

assert(b_bad({4})); 
...
return {2};

error: narrowing conversion of ‘4’ from ‘int’ to ‘bool’ inside { } [-Wnarrowing]
assert(b_bad({4}));

error: narrowing conversion of ‘2’ from ‘int’ to ‘bool’ inside { } [-Wnarrowing]
return {2};

Aber überall jetzt noch mehr Klammern einbauen kann nicht die Lösung sein. Beim return kann ich es mir noch vorstellen, aber nicht bei jedem Funktionsparameter.

Wie sieht es aus wenn statt dem Typ bool das Konzept Boolean genutzt wird? Nun, meine Variante dieses Konzept ist nicht wirklich eins, es gleicht mehr einem constraint. Ein Konzept soll ja auch möglichst vielen constrain bestehen. Aber es funktioniert. Ersetzt man die Funktionsparameter Typen durch das Konzept Boolean, kommen gute Fehlermeldungen, wie gewünscht.

template <class B> concept bool Boolean = std::is_same<B, bool>::value;

error: cannot call function ‘auto b_bad(auto:2) [with auto:2 = int]’
note: constraints not satisfied
Boolean b_bad(Boolean b) {
note: within ‘template concept const bool Boolean [with B = int]’
template concept bool Boolean = std::is_same::value;
‘std::is_same::value’ evaluated to false

error: cannot call function ‘float b_bad2(auto:3) [with auto:3 = double]’
note: constraints not satisfied
float b_bad2(Boolean b) {
note: within ‘template concept const bool Boolean [with B = double]’
template concept bool Boolean = std::is_same::value;
note: ‘std::is_same::value’ evaluated to false

#include <type_traits>

// Forcing a concept to be a fixed type. Is this a good concept or misuse?
template<typename B>
concept bool BoolType = std::is_same<B,bool>::value;

template< typename ObjectType>
concept bool ObjectInterface = requires (ObjectType obj, int a) {
  // Compound Requirements

  // does not work. 
  // 4) trailing-return-type that names a type that does not use placeholders: 
  // 4a) the type named by trailing-return-type is valid (type constraint)
  // 4b) the result of the expression is implicitly convertible to that type (implicit conversion constraint)
  // {obj.u1(a)} -> bool;  
  
  // works
  // 3) trailing-return-type that names a type that uses placeholders,
  // the type must be deducible from the type of the expression (argument deduction constraint)  
  {obj.u1(a)} -> BoolType;
};

void f(ObjectInterface obj) {
  obj.u1(1);
}

struct MyType {
  auto u1(int a) { return false; }
//  auto u1(int a) { return 1; } // error
};

int main () {
  f(MyType());
}