C++Guns – RoboBlog blogging the bot

24.09.2017

C++ Guns - Settings class

Filed under: Allgemein — Tags: — Thomas @ 11:09

Für das nächste große Projekt will ich Einstellungen aus einer Datei lesen und in Performance kritischen Codeabschnitt nutzen.
Die Variablen sollen read-only, also const, sein. So wird ein versehentlichen verändern der Einstellungen verhindert und der Compileroptimierer freut sich auch. Auf getter-Funktionen möchte ich wegen unnötigen Code verzichten.
Wenige Variablen werden besonders häufig benutzt, daher soll keine zusätzliche Tipparbeit entstehen, um erst auf das Einstellungs-Objekt zuzugreifen, und dann auf die eigentliche Variable. Statt

if(settings.L1)

einfach gleich

if(L1)

Also wird es Shortcut Variablen geben.
Um die Lesbarkeit des performance kritischen Codes nicht zu verschlechtern, sollen einige Einstellungs Variablen zur Compilezeit ausgewertet werden, aber erst zur Laufzeit gesetzt. Dies gelingt mittels Code Vervielfältigung. Der Compiler erstellt für jede Variante speziell optimierten Code.

Erste Implementierung:

#ifndef __cpp_if_constexpr
    #error "You need an actual C++17 compiler with feature P0292R2 'constexpr if' for this example"
#endif

#include <iostream>

using namespace std;

struct Settings {
    bool L1 = false;
    bool L2 = false;
};

template<bool L2>
class Algo {
public:
    Algo(const Settings& s)
        : s(s)
    {
    }

    void run() {
        cout << "SWE Settings:\n";
        cout << "L1          " << s.L1 << "\n";
        cout << "shortcut L1 " << L1   << "\n";
        cout << "L2          " << s.L2 << "\n";
        // s.L2 = true; // error. read only

        if constexpr(L2) {
            cout << "L2 template " << L2   << "\n";
        } else {
            cout << "L2 template " << L2   << "\n";
        }
    }

private:
    const Settings s;
    const bool L1 = s.L1;
};


Settings readSettings() {
    Settings s;
    s.L1 = true;
    return s;
}

template<bool L2>
void func(const Settings& s) {
    Algo<L2> swe(s);
    swe.run();
}

int main() {
    cout << boolalpha;

    Settings s = readSettings();

    cout << "Runtime L2 setting: " << s.L2 << "\n";
    if(s.L2) {
        func<true>(s);
    } else {
        func<false>(s);
    }

    s.L2 = !s.L2;
    cout << "\nRuntime L2 setting: " << s.L2 << "\n";
    if(s.L2) {
        func<true>(s);
    } else {
        func<false>(s);
    }
}


12.09.2017

C++ Guns - Missed optimizations

Filed under: Allgemein — Tags: , — Thomas @ 02:09

Compiler sind nicht perfekt. Gerade das Optimieren von Code ist so komplex, dass es keinen Algorithmus dafür gibt. Ehr werden Heuristiken dafür benutzt. So kommt es schon mal vor, dass bei banal aussehenden Code die Compiler Optimierung versagt hat und es möglich ist, von Hand schnelleren Assembler Code zu schreiben.

In [1] wurde viele solcher fehlerhaften Optimierungen gezeigt. Mit "Fehlerbeschreibung", Assembercode und teils sogar Patches für den Compiler. Leider nur für die ARM Architektur.

Ich möchte nun einige Beispiele aufgreifen und versuchen sie auf X86 64bit Plattformen nachzuahmen. Getestet wird mit g++ 64bit 4.9.2, 7.1.0, 32bit 6.3.0. Compileraufruf:
g++ -save-temps -O3 -g -fverbose-asm -march=native -c 1.cpp -Wa,-adhln=test.s

Compiler passedfailed
gcc 8.0.0 ARM 0 2
g++ 7.1.0 x86-642 0
g++ 6.0.0 x86-321 1
g++ 4.9.2 x86-642 0

Useless initialization of struct passed by value

struct S0 {
  int f0;
  int f1;
  int f2;
  int f3;
};

int f1(struct S0 p) {
    return p.f0;
}

ARM:

The struct is passed in registers, and the function's result is already in r0, which is also the return register. The function could return immediately, but GCC first stores all the struct fields to the stack and reloads the first field.

X86:

11:1.cpp         ****     return p.f0;
71   	         movl	%edi, %eax	# p,
72               ret

Ja, nur eine Assembler Instruktion.

float to char type conversion goes through memory

char fn1(float p1) {
  return (char) p1;
}

ARM:

the result of the conversion in s15 is stored to the stack and then reloaded into r0 instead of just copying it between the registers

X86-64:

 2:2.cpp         ****   return (char) p1;
78         vcvttss2si      %xmm0, %eax     # p1

VCVTTSS2SI: Convert one single-precision floating-point value from xmm1/m32 to one signed doubleword integer in r32 using truncation.

Ja, mit AVX zwischen den Register kopiert.

X86-32:

78               subl    $4, %esp        #,
 2:2.cpp         ****   return (char) p1;
81               flds    8(%esp) # p1
82               fisttps 2(%esp) #
83               movzwl  2(%esp), %eax   #

FISTTP: Store Integer with Truncation

Nein, die Variable wird vom Stack in ein floating point Register geladen und dort convertiert. Danach zurück auf den Stack gespeichert und zum Schluss in das Rückgaberegister geladen.

[1] https://github.com/gergo-/missed-optimizations/blob/master/README.md

08.09.2017

C&P Bug of the Day

Filed under: Allgemein — Tags: — Thomas @ 15:09

Keine Ahnung wie das passiert ist. git diff zeigte es dann. Ich wusste garnicht, dass so etwas überhaupt compiliert. FORTRAN ist scheiße :D


-      ContAdvection(1) = NABLA_U(1,2) + NABLA_U(2,3)
+      ContAdvection(1) =  (1,2) + NABLA_U(2,3)

04.09.2017

C++ Guns - Semantik und concepts - Part 3

Filed under: Allgemein — Tags: — Thomas @ 17:09

Kommen wir nun zu den concepts. Wie anfangs erwähnt, las ich das Paper [1].
Ich erlaube mir hier ein paar Ausschnitte davon zu kommentieren, um meine Motivation zu begründen.

A concept has semantics; it means something; it is not just a
set of unrelated operations and types. Without an idea of what operations mean and how they relate to each other we cannot write generic code that works for all appropriate types.

Ein Konzept bedeutet also irgendetwas. Wenn man sich hinsetzt und irgendetwas programmiert, hat man irgendetwas im Kopf, was es bedeuten soll. Aber diese Bedeutung können wir nur schwer in Code formulieren. Das liegt erfahrungsgemäß nicht nur an der Sprache und ihre Mittel, hauptsächlich ist es der Programmierer, der nicht weiß was er will.
So wird viel ausprobiert und viel Code umgeschrieben. Und dabei ein Haufen Bugs eingebaut, die vermeidbar gewesen wären, hätte man sich nur mal kurz überlegt, was man überhaupt will.

It follows that a guarantee that all types accepted by concept checking
will work correctly is impossible: they may have exactly the syntactic properties required, but have the wrong semantics. This is nothing new: Similarly, a function taking a double can
interpret it differently from what the caller expects. Consider set_speed(4.5). What does this mean? Is 4.5 supposed to be in m/s or maybe miles/hour? Is 4.5 an absolute value, a delta to the current speed, or possibly a factor of change?

Genau hier will ich ansetzen und widersprechen.
Der Programmierer der Funktion set_speed hat in seinem Kopf gewusst, was die Funktion machen soll, und was der Funktionsparameter bedeutet. Das muss so sein, sonst hätte er sie nicht programmieren können. Er hat diese Dinge aber nicht in Code formuliert. Wenn zum Beispiel die Funktion set_speed als Argument kein double entgegen nimmt, sondern ein Type namens Speed, welcher intern auf den Physikalischen Einheiten Meter pro Sekunde definiert ist, dann ist es nicht möglich aus versehen eine Geschwindigkeit in miles/hours zu übergeben, ohne dass der Compiler aktiv wird.
Selbes gilt für eine Geschwindigkeitsänderung welche z.B. durch den Typ DeltaSpeed ausgedrückt werden könnte, oder eine Änderung durch Skalierung.

Genau darum geht es. Um die Bedeutung von Variablen. Um die Bedeutung des Variablentypes, der mittels concepts zur Compilezeit überprüft werden kann.

I suspect that perfect checking for all code will forever elude us;

Hier bin ich vom Gegenteil überzeugt. Sobald alle Informationen ohne Fehler für den Compiler in auswertbarer Form vorliegen, muss der Compiler immer ein Fehler liefern, sobald man Schwachsinn programmiert hat.
Es macht in keinem Universum Sinn, Geschwindigkeit und Abstand zu addieren. Hier wird der Compiler sofort aktiv.
Auch Algorithmen müssen vom Compiler überprüfbar sein. Wenn alle Ein- und Ausgabedaten durch Prädikate beschrieben werden, muss der Compiler Fehler im Algorithmus finden.

Wenn aber jemand den Abstand Erde-Sonne in Millimeter berechnen will, ist das natürlich kein Compilezeitfehler.

Im nächsten Teil gibt es wieder C++ Code.

[1] Concepts: The Future of Generic Programming or How to design good concepts and use them well - Bjarne Stroustrup

C++ Guns - Semantik und concepts - Part 2

Filed under: Allgemein — Tags: , — Thomas @ 14:09

Im letzten Post wollte ich deutlich machen, welche Art von Fehler passieren, wenn zwischen den TypenPoint3D und Vector3D keinen semantischen Unterschied gemacht wird. Also, wenn ein Rechenergebnis von der Bedeutung ein Vektor ist, es aber in einem Punkt Datentyp gespeichert wird.

Die erste Lösung war, einen zusätzlichen Datentyp Vector3D zu erstellen, welcher sich genau wie ein Point3D verhält, aber von der Bedeutung eine andere hat. Dies lässt sich auch noch ohne concepts realisieren. Dazu das selbe Beispiel von Part1 diesmal in FORTRAN. Und im nächsten Teil gibts dann das erste concept.

Da ich nicht weiß ob es in FORTRAN möglich ist, von einem Array zu erben, noch ob man operator()() überladen kann, hier eine Version mit etwas mehr Tipparbeit.

Wichtig ist aber erstmal nur, dass die selbe Art von Fehlermeldung erzeugt werden kann.

conceptpart2.F90
normal = normalenVector(tri)
1
Error: Can't convert TYPE(vector3d_t) to TYPE(point3d_t) at (1)

conceptpart2.F90.gz

module test_m
 implicit none
 
  type Point3D_t
    real(8) :: xyz(3)
  end type

  type Vector3D_t
    real(8) :: xyz(3) 
  end type


  type Triangle_t
      type(Point3D_t) :: points(3)
  end type

  interface operator(-)
    module procedure minus1
  end interface
  
  contains

  function minus1(p1, p2) result(p3)
    implicit none
    type(Point3D_t), intent(in) :: p1, p2
    type(Point3D_t) :: p3

    p3 = Point3D_t( (/ p1%xyz(1)-p2%xyz(1), p1%xyz(2)-p2%xyz(2), p1%xyz(3)-p2%xyz(3) /) )
  end function

  function normalenVector(tri) result(normal)
    implicit none
    type(Triangle_t), intent(in) :: tri
    type(Point3D_t) :: vec1, vec2
    type(Vector3D_t) :: normal
    
      vec1 = tri%points(2)-tri%points(1)
      vec2 = tri%points(3)-tri%points(1)

      normal = Vector3D_t( (/ vec1%xyz(2)*vec2%xyz(3)-vec1%xyz(3)*vec2%xyz(2), &
&                  vec1%xyz(3)*vec2%xyz(1)-vec1%xyz(1)*vec2%xyz(3), &
&                  vec1%xyz(1)*vec2%xyz(2)-vec1%xyz(2)*vec2%xyz(1) /) )
  end function
 
end module

program main
  use test_m
  implicit none
  type(Triangle_t) :: tri
  type(Point3D_t) :: normal
    
  tri = Triangle_t((/ Point3D_t((/0, 0, 0/)), Point3D_t((/10, 0, 0/)), Point3D_t((/10, 10, 0/)) /))
  normal = normalenVector(tri)
end program


01.09.2017

C++ Guns - C++17 Extension to aggregate initialization

Filed under: Allgemein — Thomas @ 14:09

C++17 bringt ein paar tolle Sachen mit. Mit der Erweiterten Aggregat Initialisierung kann ich nun endlich meinen Lieblings Point3D Datentyp zusammenbauen.
Dieser soll mit den Funktionen x(), y() z() Zugriff auf die einzelnen Skalare bieten, aber gleichzeitig ein Array fester Länge sein. Damit der Compiler besser optimieren kann. Der Typ selbst soll ein Array sein, und nicht ein Array als Membervariable enthalten, um weniger tippen zu müssen. Gleichzeitig soll aber eine Initialisierung ohne selbst geschriebenen Konstruktor möglich sein. Der Typ muss für die Performance natürlich POD sein, darf aber niemals uninitialisiert sein. Der interne Type der Skalare muss per Templates austauschbar sein. Um Einheiten wie z.B. Meter oder Grad zu verwenden. Es sollen mit Point3D Berechnungen zur Compilezeit möglich sein, also constexpr. Eine Ausgabe über cout und Standard Operatoren wie + - * / sollen zur Verfügung stehen.

Ganz schön viele Sachen. Aber das lässt sich alles realisieren:

Getestet mit gcc 7.1.0 und clang-4.
Point3D.cpp.gz

#include <iostream>
#include <array>
#include <type_traits>

template<typename T>
struct Point3D : public std::array<T,3> // Typ selbst ist ein Array fester Laenge
{
    using value_type = T;

    Point3D() = delete;

    constexpr const T& x() const {
        return this->at(0);
    }

    constexpr T& x() {
        return this->at(0);
    }

    constexpr const T& y() const {
        return this->at(1);
    }

    constexpr T& y() {
        return this->at(1);
    }

    constexpr const T& z() const {
        return this->at(2);
    }

    constexpr T& z() {
        return this->at(2);
    }
};

// interner Type austauschbar
using Point3Dd = Point3D<double>;
using Point3Df = Point3D<float>;
using Point3Di = Point3D<int>;

static_assert(std::is_pod<Point3Dd>::value, "Point3D is not POD");

template<typename T>
std::ostream& operator<<(std::ostream& s, const Point3D<T>& p) {
    s << '(' << p[0] << ' ' << p[1] << ' ' << p[2] << ')';
    return s;
}

template<typename T, typename T2>
constexpr auto operator+(const Point3D<T>& p1, const Point3D<T2>& p2) {
    using Internal = decltype(T() + T2());
    return Point3D<Internal> {p1[0]+p2[0], p1[1]+p2[1], p1[2]+p2[2]};
}

template<typename T, typename T2>
constexpr auto operator-(const Point3D<T>& p1, const Point3D<T2>& p2) {
    using Internal = decltype(T() - T2());
    return Point3D<Internal> {p1[0]-p2[0], p1[1]-p2[1], p1[2]-p2[2]};
}

// Rest fuer dich

int main() {
    // niemals uninitialisiert
    // error: use of deleted function ‘Point3D<T>::Point3D()
    //Point3Dd p;

    // Initialisierung ohne selbst geschriebenen Konstruktor
    constexpr Point3Di p1{1, 2, 3};

    // Ausfuerung zur Compilezeit
    static_assert(p1.x() + p1.y() + p1.z() == 6, "Oh oh");

    std::cout << p1 << "\n";

    // (Physikalische) Einheiten nutzbar (kommt bald)
    //Point3D<SI::Meter> p2 {1_m, 100_cm, 0.001_km);

    constexpr Point3Dd p3{1.0, 2.0, 3.0};
    // int + double = ? Der Compiler weis es
    constexpr auto p4 = p1+p3;

    static_assert(std::is_same<decltype(p4)::value_type, double>::value, "int+double should be double. right?");
}

C++ Guns - Semantik und concepts - Part 1

Filed under: Allgemein — Tags: — Thomas @ 10:09

Ich lese gerade das Paper
Concepts: The Future of Generic Programming
or
How to design good concepts and use them well
von Bjarne Stroustrup

http://www.stroustrup.com/good_concepts.pdf

und muss sagen, ich bin restlos begeistert! Die Idee dahinter wird sehr toll beschrieben. Das ist mir am wichtigsten, so dass es möglich ist, die Idee auch bei anderen Programmiersprachen anzuwenden. Natürlich mehr oder weniger schlecht, da die Sprachmittel fehlen. Ich arbeite gerade an einem Beispiel aus meiner Domain welche mit concepts realisiert ist, aber das dauert noch etwas.

Deswegen gibt es heute nur ein einfaches Beispiel aus der angewandten Mathematik, welche den Begriff der Semantik verdeutlichen soll.

Ein Dreieck hat bekanntlich drei Ecken. Also drei Punkte. Auch wenn es nervt, dieser Witz ist sehr treffend. Viele Computerformate bilden ein Dreick als Polygonlinie mit vier Punkten ab! Deren Computer würde explodieren, würde sie C++ mit concepts nutzen ;)

Also, ein Dreieck im 3D Raum hat drei Punkte und jeder Punkt hat drei Skalare: x, y, und z. Es soll der Normalenvector zu einem Dreieck berechnet werden. Dieser steht senkrecht zur Fläche, welche die drei Punkte aufspannen.

Punkte und Dreieck kann man sich leicht vorstellen und anfassen. Wir können sie also schnell als Typen in C++ implementieren:

#ifndef __cpp_aggregate_bases
    #error "You need an actual C++17 compiler with feature P0017R0 'Extension to aggregate initialization' for this example"
#endif
#include <iostream>
#include <array>

using namespace std;

struct Point3D : public array<double, 3> {
};

struct Triangle {
    array<Point3D, 3> points;
};

auto operator-(const Point3D& p1, const Point3D& p2) {
    return Point3D{ p1[0]-p2[0], p1[1]-p2[1], p1[2]-p2[2] };
}

Laut Internet berechnet sich der Normalvekor so:

Das Kreuz-Produkt zweier Vektoren steht senkrecht auf der Fläche, das die beiden Vektoren aufspannen.

Das Kreuzprodukt schütteln wir natürlich im Schlaf aus dem Ärmel. Das haben wir in der Schule rauf und runter geübt. Also los:

auto normalenVector(const Triangle& tri) {
    const auto vec1 = tri.points[1]-tri.points[0];
    const auto vec2 = tri.points[2]-tri.points[0];

    return Point3D{ vec1[1]*vec2[2]-vec1[2]*vec2[1],
                vec1[2]*vec2[0]-vec1[0]*vec2[2],
                vec1[0]*vec2[1]-vec1[1]*vec2[0] };
}

Das ist immer etwas Tipparbeit aber einmal implementiert, immer anwendbar. Oder?

Jetzt fehlt nur noch das Hauptprogramm mit einem kleinen Test:

ostream& operator<<(ostream& s, const Point3D& p) {
    s << "(" << p[0] << " " << p[1] << " " << p[2] << ")";
    return s;
}

int main() {
    Triangle tri{ Point3D{0, 0, 0}, Point3D{10, 0, 0}, Point3D{10, 10, 0} };
    Point3D normal = normalenVector(tri);
    cout << normal << '\n';
}

Compilieren und Ausführen...

Starting part1...
(0 0 100)

Alles klar. Das Ergebnis ist auch richtig. Sind wir fertig? Wo sind die Concepts? Nagut die kommen noch. Aber wo ist der Semantik Fehler? Die Funktion normalenVector() soll einen Vektor zurück geben. Aber wir haben als Rückgabetyp ein Punkt implementiert. Technisch lassen sich sowohl Punkt als auch Vector als drei Skalare implementieren. Aber ihre Bedeutung ist eine ganz andere! Ein Punkt ist eine Position im Raum. Ein Vektor zeigt in eine Richtung.

Jetzt kommt der erste Schritt hin zu Concepts. Die eben erkannte Bedeutung formulieren wir nun im Code. Dazu erstellen wir einen neuen Typ der einen Vektor repräsentiert und die Funktion normalenVector() gibt einen Vektortyp zurück:

struct Vector3D : public array<double, 3> {
};
...
return Vector3D{ ... };

Das neue Programm wäre funktional gleich dem alten. Sogar der Assembler und Binärcode wäre 100% identisch. Das Rechenergebnis natürlich auch. Der Unterschied besteht darin, dass der Compiler nun prüfen kann, ob das, was wir in unserem Programm zum Ausdruck bringen wollen, auch wirklich implementiert haben. Haben wir nicht:

main.cpp: In function ‘int main()’:
main.cpp: error: conversion from ‘Vector3D’ to non-scalar type ‘Point3D’ requested
Point3D normal = normalenVector(tri);

Na, das schaut für den Anfang gar nicht mal so schlecht aus. Das ist nur ein kleiner Schritt Richtung concepts, der sogar in FORTRAN realisierbar ist.

Im nächsten Teil portiere ich diese Idee nach FORTRAN um zu zeigen, wo die Grenze dieser Sprache liegt. Um dann im übernächsten Teil endlich Richtung concepts zu starten.

conceptpart1.gz

Powered by WordPress