C++Guns – RoboBlog blogging the bot

14.03.2019

C++ Guns: floating point bit round - p0476r2 Bit-casting object representations

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

C++20

Low-level code often seeks to interpret objects of one type as another: keep the same bits, but obtain an object of a different type. Doing so correctly is error-prone: using reinterpret_cast or union runs afoul of type-aliasing rules yet these are the intuitive solutions developers mistakenly turn to.

Attuned developers use aligned_storage with memcpy, avoiding alignment pitfalls and allowing them to bit-cast non-default-constructible types.

This proposal uses appropriate concepts to prevent misuse. As the sample implementation demonstrates we could as well use static_assert or template SFINAE, but the timing of this library feature will likely coincide with concept’s standardization.

Furthermore, it is currently impossible to implement a constexpr bit-cast function, as memcpy itself isn’t constexpr. Marking the proposed function as constexpr doesn’t require or prevent memcpy from becoming constexpr, but requires compiler support. This leaves implementations free to use their own internal solution (e.g. LLVM has a bitcast opcode).

We should standardize this oft-used idiom, and avoid the pitfalls once and for all.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0476r2.html
https://github.com/jfbastien/bit_cast/

Solange wir noch kein C++20 haben um Bit Manipulationen an Gleitkommazahlen vorzunehmen, muss memcpy herhalten.

  double value;

  // float -> integer 
  std::uint64_t n;
  std::memcpy(&n, &value, sizeof(value)); // no aliasing violation

  // Bit Manipulation an Variable 'n'
  // ...

  // integer -> float
  std::memcpy(&value, &n, sizeof(n));

06.03.2019

Profiler read/write miss Gedanken

Filed under: Allgemein — Tags: — Thomas @ 16:03

Profiler read/write miss Gedanken

write miss: unterscheiden zwischen permanenten und temporäre Daten:
Permanente Daten: wohl unausweichlich, denn die neuen Daten MÜSSEN ja vom Chache in den Hauptspeicher geschrieben werden.
Temporäre Daten: eventuell vermeidbar, wenn man sie an einer späteren Stelle im Code erstellt. Wann immer Daten in den Cache geschrieben werden, fliegen andere Daten raus die eventuell gerade erst aufwendig geladen wurden.

read miss: Unterscheiden zwischen permanent und temporären Daten:
Permanente Daten: wohl unausweichlich. wenn man über einen Datensatz iteriert der größer als der Cache ist, MÜSSEN die Daten vom Hauptspeicher in den Cache geladen werden.
Temporäre Daten: eventuell vermeidbar. Selbe Argumentation wie bei write miss.

Eine temporäre/local scope Variable wird erstellt und in den Cache geschrieben. Dabei fallen eventuell wichtige Daten aus dem Cache. Nun passieren andere Berechnungen die auch in den Cache geschrieben werden. Dabei kann die temp. Variable in den Hauptspeicher ausgelagert werden. Später muss sie wieder vom Hauptspeicher wieder in den Cache geladen werden.

Cache misses auf temporäre Daten womöglich vermeidbar. Auf permanente Daten wohl unvermeidlich. Sso kann es vorkommen, dass das Laden der Daten mehr Zeit kostet als die eigentlichen arithmetischen Berechnungen damit. Profiler die nur Zeiten anzeigen, können nicht benutzt werden um zu Entscheiden ob etwas optimiert werden kann.
Die Addressberechnung und das Laden der Daten in den Cache ist teuer. Vorallem wenn die Daten nicht hintereinander im RAM liegen.
Wenn 10 Werte aus 10 Container geladen werden, sind 10 Cache Zeilen belegt. Da immer Cachezeilen-Byte viele Daten geladen werden (64byte??)
Wenn ein struct a 10 Member geladen wird, geschieht nur Speicherzugriff an einer Stelle im RAM und es wird auch nur eine (oder wenige) Cache Zeilen belegt.
Cache Zeilen sind wertvoll. es gibt nur wenige davon (CPU abhängig).
Ganz schlimm ist es, wenn in der nächsten Iteration an ganz anderer Stelle im Array zugegriffen wird. Dann sind alle geladenen Cachezeilen ungültig. Auch bei kontinuierlicher RAM Benutzung.
(Das ist DAS Problem bei Dreiecksnetzten)
Faustformel: arithmetische Operation +-*/ kostet 1-40. Main RAM read kostet 100-500

02.03.2019

C++ Guns: A Sorted Data Type

Filed under: Allgemein — Tags: — Thomas @ 18:03

Mit dem C++ Typsystem ist es möglich Informationen und Algorithmen in das Programm zu codieren, die schon vor der Compilezeit fest stehen.

Wie würdet ihr folgendes Problem lösen:
Ein Algorithmus, zum Beispiel die binäre Suche, benötigt einen bereits sortieren Datensatz. Den Datensatz zu sortieren und danach die Suche anzuwenden ist trivial. Aber in einem anderen Teil des Programms muss danach noch einmal die binäre Suche angewendet werden. Nur kann dieser andere Programm Teil nicht annehmen, dass der übergebene Datensatz sortiert ist. Noch einmal die Sortierung angewandt kostet viel Laufzeit. Zu testen ob die Daten bereit sortiert sind, ist immer noch ein linearer Algorithmus.
Der Programmierer könnte auch eine bool Variable mit geben, die aussagt ob die Daten bereits sortiert sind. Das ist immerhin nur ein konstanter Mehraufwand. Der Datensatz muss stark mit dieser Statusvariable gekoppelt sein, damit keine Inkonsistenz entsteht. Also kommen beide zusammen in einem neuen Datentyp. Wenn man den sortierten Datensatz noch read-only macht, muss man kein Aufwand treiben festzustellen, ob der Datensatz durch ein Schreibzugriff nun nicht mehr sortiert ist. Damit ist auch die Statusvariable konstant.

Jetzt passiert etwas besonderes. Die Statusvariable wird von einer Funktion erzeugt und hat immer den selben Wert. Nämlich true, für "sortiert". Damit ist es möglich, diese Idee auch zur Compilezeit auszuführen und einen neuen Datentype Sorted einzuführen, der nur von einer sort() Funktion erzeugt werden kann und IMMER sortierte Daten enthält. Die bool Variable fällt komplett weg. Ihre Semantik ist im neuen Datentyp kodiert.

Wie sieht diese Idee in der Praxis aus? Es braucht eine sorted() Funktion welche die Daten sortiert und einen Sorted Typ zurück gibt. Damit, bei Bedarf, keine unnötigen Kopien erstellt werden, ist es auch möglich mit moveOwnership() die Daten in den Sorted Typ zu verschieben.

Jeder Algorithmus welcher sortiere Daten benötigt, soll nur Datensätze von Typ Sorted akzeptieren. Damit ist zur Compilezeit sichergestellt, dass nie aus Versehen unsortierte Daten übergeben werden und es wird nur einmal der Datensatz sortiert. Und alles kommt dank statischer Typisierung mit zero-overhead.

std::vector<int> vec {3,2,1};
// sort and move ownership to Sorted
Sorted sortedVec = sorted(acpl::moveOwnership(vec));

// can be used with the strong typed binary_search function
binary_search(sortedVec, valueToSearch);

Der Type Sorted implementiert nur ein read-only Interface und ist ein Wrapper um einen beliebigen Container. Der Konstruktor ist privat, damit nur die spezielle sorted Funktion diesen Typen erstellen kann.

auto nope = Sorted<std::vector<int>>{vec}; // error: ‘Sorted<Container>::Sorted(Container&&) is private within this context

Für bestehende Algorithmen können leicht Wrapper geschrieben werden. Wie beispielsweise für die binäre Suche:

template<typename Container, typename T>
bool binary_search(const Sorted<Container>& data, const T& value) {
    return std::binary_search(data.begin(), data.end(), value);
}

Die Implementierung der sorted() Funktion ist relativ einfach, wenn die Sache mit Universal Referenz geklärt ist

template<typename Container>
Sorted<std::remove_reference_t<Container>> sorted(Container&& data) {
    // variable data is a univeral reference. pattern: "deducted type&&" so we use forward
    std::remove_reference_t<Container> sorted(std::forward<Container>(data));
    std::sort(sorted.begin(), sorted.end());
    // variable sorted is not a universal reference so we use move
    return {std::move(sorted)};
}

Natürlich gibt es auch einen overload für die Funktion isSorted() diese gibt trivialierweise immer true zurück.

template<typename Container>
bool isSorted(const Sorted<Container>&) {
    return true;
}

Und die Implementierung des Typ Sorted selbst

template<typename Container>
// requires Sequence container
class Sorted {


    Sorted(Container&& data)
        : c(std::forward<Container>(data))
    {  }

public:
    using value_type = typename Container::value_type;
    using const_iterator = typename Container::const_iterator;
    using const_reference = typename Container::const_reference;

    auto size() const {
        return std::size(c);
    }

    const_iterator begin() const {
        return c.begin();
    }

    const_iterator end() const {
        return c.end();
    }

    const_reference at(const auto& i) const {
        return c.at(i);
    }

    const_reference operator[](const auto& i) const {
        return c[i];
    }

    const_reference front() const {
        return c.front();
    }

    template<typename C>
    friend Sorted<std::remove_reference_t<C>> sorted(C&& data);

    const Container c;
};

Powered by WordPress