uni8_t Vector in eine einzige unit32_t variable schreiben

SeppJ

@john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Das ist maximal am Thema vorbei.

Ja, an deinem Fantasiethema, von dem niemand sonst redet.

*john 0

@Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Hat SeppJ nicht gerade aufgezeigt, dass das casten dieser Zeiger garantiert funktionieren muss?

Nein, hat er nicht. Die Norm garantiert, dass man Zeiger auf Felder die man als uint32_t anlegt in einen Zeiger von Typ uint8_t casten kann. Die Norm garantiert aber nicht, dass man das auch umgekehrt kann. Da diese Felder nicht so ausgerichtet sein müssen, dass der Zeiger auf einer Modulo 4 Adresse liegt. Oftmals ist das der Fall, und zwar dann, wenn die Feldgröße ein Vielfaches von sizeof(uint32_t) ist. malloc alloziert nach diesem Muster den Speicher, und richtet ihn so aus dass das für größere Typen passt. Das Problem hier an der Stelle ist, dass Du nicht weißt, welche Allokationsstrategie der Container std::vector<uint8_t> nutzt. Er darf hier Speicher so anfordern, dass er mehr Speicher als die vier uint8_tanfordert. Wenn er eine Größe anfordert, die nicht ein Vielfaches von sizeof(uint32_t) ist, kann es knallen. Ja, das ist unwahrscheinlich, aber es ist eben nicht garantiert, dass das auch funktioniert.

Finnegan

@john-0 sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Das Problem hier an der Stelle ist, dass Du nicht weißt, welche Allokationsstrategie der Container std::vector<uint8_t> nutzt. Er darf hier Speicher so anfordern, dass er mehr Speicher als die vier uint8_tanfordert. Wenn er eine Größe anfordert, die nicht ein Vielfaches von sizeof(uint32_t) ist, kann es knallen. Ja, das ist unwahrscheinlich, aber es ist eben nicht garantiert, dass das auch funktioniert.

Alle Allokationen des Default-Allocator basieren letztendlich auf std::malloc und haben ein Alignment von mindestens alignof(std::max_align_t).

Für die Signatur uint32_t to_uint32(const std::vector<uint8_t> &v) bindet v auch nur an std::vector-Typen, welche std::allocator<uint8_t> verwenden, daher halte ich den reinterpret_cast bezüglich Alignment in diesem Fall für unproblematisch, solange man nicht anfängt, bei irgendwelchen krummen Vector-Indizes zu casten.

Ich denke auch, die Diskussion driftet hier zu weit in Bereiche ab, die derzeit nicht das aktuelle Problem sind, auch wenn all diese Apsekte durchaus irgendwann mal relevant sein könnten. Für mich ist die Frage eher, ob die im OP genannte Byte-Reihenfolge wichtig ist und auf jedem System die selbe sein sollte (Netzwerkpakete, portable Dateiformate), oder ob einfach nur die Bytes in Maschinen-Reihenfolge in den Speicher geschreiben werden sollen. Ersteres ist ein starkes Argument für Shift&Add, bei letzterem bitte gerne auch reinterpret_cast. Ich vermute stark letzteres, so wie die Frage gestellt wurde.

hustbaer

@SeppJ sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Da braucht man auch nix zu erzählen vonwegen "es ist technisch gesehen undefiniert". Auch da gilt: Gerade deswegen programmieren wir doch in einer maschinennahen Sprache, eben damit wir unser höheres Wissen anwenden können, dass dies hier eine völlig harmlose Operation ist, mit der wir unnöitge Rechnungen einsparen können.

Finde ich den falschen Zugang. In diesem speziellen Fall müsste es mMn. sogar - fast - vom Standard abgedeckt sein. Also fast wegen der Annahme dass uint8_t entweder char oder unsigned char ist - was der Standard AFAIK nicht garantiert. Sobald die Aliasing-Ausnahme aber nicht mehr gilt, ... oops.
https://godbolt.org/z/1YbacbKdq

Columbo

@john-0 vector<T> alloziert mit std::allocator, welches auf operator new basiert, was wiederum garantiert fuer alle normalen Objekte ausgerichteten Speicher ergibt. Da das interne Array mindestens sizeof(uint32_t) bytes haben muss, damit das type punning ueberhaupt Sinn ergibt, ist es folglich auch fuer ein Objekt vom Typ uint32_t ausgerichtet.

Wenn man ganz paranoid ist kann man auch static_assert(alignof(uint32_t) <= __STDCPP_DEFAULT_NEW_ALIGNMENT__) schreiben.

@hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Finde ich den falschen Zugang. In diesem speziellen Fall müsste es mMn. sogar - fast - vom Standard abgedeckt sein. Also fast wegen der Annahme dass uint8_t entweder char oder unsigned char ist - was der Standard AFAIK nicht garantiert. Sobald die Aliasing-Ausnahme aber nicht mehr gilt, ... oops.

Dann kopierst Du halt mit memcpy? Oder schreibst einen static_assert mit Deiner Bedingung, der auf 0% der existierenden Platformen feuert. Klingt jetzt nicht nach nem deal breaker.

hustbaer

@Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

@hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Finde ich den falschen Zugang. In diesem speziellen Fall müsste es mMn. sogar - fast - vom Standard abgedeckt sein. Also fast wegen der Annahme dass uint8_t entweder char oder unsigned char ist - was der Standard AFAIK nicht garantiert. Sobald die Aliasing-Ausnahme aber nicht mehr gilt, ... oops.

Dann kopierst Du halt mit memcpy?

Mir ist klar dass es mit memcpy geht. Ist aber ziemlich egal was mit memcpy geht, wenn hier speziell reinterpret_cast diskutiert wurde, oder?

Und was memcpy vs. Shiften + Addieren angeht: da kommt's halt drauf an was man braucht. Wenn die Byte-Order fix und unabhängig von der Maschine ist, dann ist mMn. Shiften + Addieren angesagt. Wenn die Byte-Order dagegen garantiert die der Maschine ist, dann nimmt man memcpy. Nicht nur weil es die jeweils einfachere Variante ist, sondern weil es mMn. auch die jeweils "logischere" Variante ist.

Und da der OP die Frage so formuliert hat dass man annehmen muss dass die Byte Order fix und unabhängig von der Maschine ist => Shiften + Addieren.

Oder schreibst einen static_assert mit Deiner Bedingung, der auf 0% der existierenden Platformen feuert. Klingt jetzt nicht nach nem deal breaker.

Ich wollte nur darauf hinweisen dass das ganze nur auf Grund der speziellen, im Standard verankerten Ausnahme für char, unsigned char und std::byte funktioniert. Weil ich glaube dass das viele Leute die solchen Code schreiben nicht wissen. Und wenn man denen dann ohne diese Ausnahme zu erwähnen sagt "reinterpret_cast ist OK", dann ist das schlecht. Weil sie dann vermutlich auch annehmen würden dass reinterpret_cast auch OK ist wenn's z.B. um ein uint32_t Array geht wo man uint64_t rauslesen will.

Finnegan

@hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Ich wollte nur darauf hinweisen dass das ganze nur auf Grund der speziellen, im Standard verankerten Ausnahme für char, unsigned char und std::byte funktioniert. Weil ich glaube dass das viele Leute die solchen Code schreiben nicht wissen. Und wenn man denen dann ohne diese Ausnahme zu erwähnen sagt "reinterpret_cast ist OK", dann ist das schlecht.

Ja, das habe ich hier auch verbockt. Irgendwie tendiere ich bei groben Überfliegen intuitiv öfter mal dazu, std::uint8_t ebenfalls zu diesem erlauchten Kreis der Strict-Aliasing-Ausnahmen zu zählen. Passiert mir nicht zum ersten Mal, und das nehme ich hiermit zurück

std::memcpy sollte eigentlich auch ziemlich gut optimiert werden, auch wenn das im C++-Code erstmal relativ schwergewichtig aussieht - selbst für einzelne Bytes. Obwohlich mich vage erinnern kann, dass Clang das im Vergleich zu GCC oder gar MSVC in einigen Fällen besser gemacht hat. Ist aber schon ne Weile her. Auf jeden Fall den generierten Code anschauen, wenn Effizienz wichtig ist (sowieso immer).

Columbo

@Finnegan sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Auf jeden Fall den generierten Code anschauen, wenn Effizienz wichtig ist (sowieso immer).

Einfach Geschwindigkeit messen. Vom Assembly (bspw. dessen Länge) auf die Geschwindigkeit zu schliessen ist per se Unsinn.

@hustbaer
Ich wollte im Gegenzug darauf hinweisen, dass man keine Angst davor haben braucht, den Code optimal so hinzuschreiben, wenn man befaehigt ist, die noetigen Vorbedingungen zu erkennen und pruefen. C++ ist nicht umsonst maechtig.

Finnegan

@Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

@Finnegan sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Auf jeden Fall den generierten Code anschauen, wenn Effizienz wichtig ist (sowieso immer).

Einfach Geschwindigkeit messen. Vom Assembly (bspw. dessen Länge) auf die Geschwindigkeit zu schliessen ist per se Unsinn.

Ja, das stimmt, allerdings hatte ich hier eher sowas wie ein call memcpy vs ein simples mov im Sinn. Es dürfte leichter sein zu schauen, ob memcpy und reinterpret_cast exakt den selben Code generienen als Performanceunterschiede im Nanosekundenbereich präzise zu messen

hustbaer

@Columbo sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Einfach Geschwindigkeit messen. Vom Assembly (bspw. dessen Länge) auf die Geschwindigkeit zu schliessen ist per se Unsinn.

In vielen einfachen Fällen reicht es durchaus den Assembler-Code zu lesen. Wenn da bloss ein mov eax, dword ptr [ecx] steht, dann weiss ich dass das memcpy perfekt optimiert wurde.

Wobei Benchmarken gerade bei dem Thema vielleicht doch nicht ganz doof ist. Weil es halt auch darauf ankommt wie und wann der Wert den man da liest geschrieben wurde. Wenn der direkt zuvor geschrieben wurde, dann kann es sein dass er noch in den Store-Buffern steht -- und die meisten CPUs implementieren Store-Forwarding nur wenn die Operanden gleich gross sind. D.h. wenn man byteweise reinschreibt und dann gleich 1-2 Zyklen später nen 32 Bit Wert rausliest, dann zahlt man Strafe weil man darauf warten muss dass die Store-Buffer in den Cache geschrieben wurden.

Der 32 Bit Load an und für sich ist dann zwar schon optimal, aber der Code als ganzes halt nicht. Von daher: ja, vielleicht lieber doch Benchmarken. Und wenn möglich grössere Blöcke und keine realitätsfremden Mikrobenchmarks.

Finnegan

@hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Wobei Benchmarken gerade bei dem Thema vielleicht doch nicht ganz doof ist. Weil es halt auch darauf ankommt wie und wann der Wert den man da liest geschrieben wurde. Wenn der direkt zuvor geschrieben wurde, dann kann es sein dass er noch in den Store-Buffern steht -- und die meisten CPUs implementieren Store-Forwarding nur wenn die Operanden gleich gross sind. D.h. wenn man byteweise reinschreibt und dann gleich 1-2 Zyklen später nen 32 Bit Wert rausliest, dann zahlt man Strafe weil man darauf warten muss dass die Store-Buffer in den Cache geschrieben wurden.

Man kann sich den Assembler-Code auch nur aus dem Grund anschauen um zu sehen, ob der Compiler überhaupt erkannt hat, dass sich das memcpy zu einem simplen mov optimieren lässt und eben kein plumpes call memcpy generiert. Oder wie vor einiger Zeit das vertauschen der High- und Low-Bits eines Integers via memcpy und verschachtelten Funktionaufrufen, dass zu einer simplen rol-Instruktion optimiert wurde.

Wenn ich weiss, dass der Compiler das Optimierungspotential richtig erkannt hat, habe ich auch mehr Vertrauen darin, dass er bei den von dir angesprochenen Load/Store-Besonderheiten das Richtige macht und die Instruktionen eventuell entsprechend umsortiert. Das kann man dann immer noch zusammen mit dem ganzen Code drumeherum benchmarken.

Ich würde auch vermuten, dass es sich bei diesen Teilen um verscheidene Verarbeitungsschritte des Compilers handelt. Das Optimieren von memcpy zu mov würde ich eher den Optimierungen auf der SSA-IR zuordnen, während ich die Load/Store-Sachen eher beim Code-Generator verorte. Ist aber nur ein Bauchgefühl, bin kein Compiler-Experte

hustbaer

@Finnegan
Ich kann nur sagen dass GCC 9.1 mit -O2 bei uns nicht schlau genug war das zu optimieren, obwohl keine "inlining-barrier" dazwischen war. Das Schreiben war direkt in der "äusseren" Funktion und das Lesen war ne kleine inline Hilfsfunktion mit bloss ein bisschen Magic um sich um Alignment und Aliasing zu kümmern (so GCC __attribute__ Zeugs halt). Trotzdem hat GCC munter ne Byteschleife zum Schreiben und direkt danach nen 64 Bit Load zum Lesen generiert.

Mich hätte es auch ehrlich gesagt gewundert wenn GCC das besser optimiert hätte, also mit Rücksicht auf Store-Forwarding.

Der Code war inetwa so:

uint64_t hash(char const* data, size_t size) {
    uint64_t h = init(size);
    while (size >= 8) {
        h = combine(h, load64(data));
        data += 8;
        size -= 8;
    }

    // Schreiben in 8 Bit Stücken
    char remaining[8];
    for (int i = 0; i < size; i++)
        remaining[i] = data[i];
    for (; i < 8; i++)
        remaining[i] = 0;

    // Lesen als 64 Bit => Strafe
    h = combine(h, load64(remaining));
    return h;
}

Hatte ich erst so geschrieben weil ich den Ball flach halten wollte. Die load64 Funktion (reinterpret_cast) wurde an beiden Stellen zu nem einzigen 64 Bit Load kompiliert.

Benchmark hat aber gezeigt dass die neue Version der Funktion bei kleinen Blöcken auf einmal deutlich langsamer war als was wir davor verwendet hatten. Hab mich dann erinnert vor vielen Jahren mal was über Store-Forwarding gelesen zu haben und den "remaining" Teil zu ner Shift+Add Schleift umgeschrieben. Und damit war die neue Funktion dann wie geplant für alle Grössen schneller als die alte.

Finnegan

@hustbaer sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Hab mich dann erinnert vor vielen Jahren mal was über Store-Forwarding gelesen zu haben und den "remaining" Teil zu ner Shift+Add Schleift umgeschrieben. Und damit war die neue Funktion dann wie geplant für alle Grössen schneller als die alte.

Mir ist auch aufgefallen, dass die Compiler mit simplel ausformuliertem Lehrbruch-C++-Algorithmen (wie Shift+Add) nicht selten besser klarkomen als mit Code, den man mit einem "Assembler-Mindset" (reinterpret_cast) geschrieben hat.

Ich kann nur vermuten, dass solcher Code mehr Freiheitgerade für diejenigen Teile des Compilers bietet, die am intelligentesten optimieren können. Das würde ich eher auf dem Graphen der Intermediate Representation vermuten und dass ein Shift+Add dort einfach mehr "Knoten" generiert, mit denen der Compiler spielen kann. Just a hunch.

Wenn das so zutrifft, dann ist das eigentlich ne gute Sache, weil das bedeutet, dass mit einfachem* Code, den man so auch Anfängern lehren würde, oft auch sehr effizienter Code erzeugt wird.

Ein bisschen wie einfach return string; anstatt "oh mein Gott, bloss keine Kopie anlegen!" und generiere_string(string&), während ein Anfänger nichtmal weiss, was ein Kopier-Konstruktor ist und dennoch den besseren Code schreibt. Da ist schon was dran, dass wie Stroustrup sagt, in C++ eine simplere Sprache steckt, die gerne herauskommen möchte

* Einfach nicht im Sinne von kürzer, sodern höherleveliger und lediglich mit C++-Grundlagen zu verstehen.

Edit: Oh warte mal, deine Shift+Add-Schliefe war schneller, weil du uint64_t damit zusammengebaut und gechrieben hast? Also nicht unbedingt Optimizer-Magie? Jetzt hab ich hier viel spekuliert und sehe gerade, dass du den Compiler möglicherweise doch bezüglich Load+Store "an der Hand geführt" hast. Dennoch nicht ganz falsch, was ich gechrieben habe, nur nicht unbedingt für dieses Beispiel zutreffend.Ist echt ne Schwäche von mir zu früh ne ausführliche Antwort zu schreiben und dann beim Korrekturlesen ne wichtige Erkenntnis zu bekommen

hustbaer

@Finnegan sagte in uni8_t Vector in eine einzige unit32_t variable schreiben:

Mir ist auch aufgefallen, dass die Compiler mit simplel ausformuliertem Lehrbruch-C++-Algorithmen (wie Shift+Add) nicht selten besser klarkomen als mit Code, den man mit einem "Assembler-Mindset" (reinterpret_cast) geschrieben hat.

Möglich. Aber in dem Fall war der Grund einfach dass die Shift+Add Schleife keinen temporären Puffer verwendet hat auf den mit unterschiedlichen Grössen zugegriffen wurde, und daher auch kein Warten auf die Store-Buffer anfallen konnte.

Edit: Oh warte mal, deine Shift+Add-Schliefe war schneller, weil du uint64_t damit zusammengebaut und gechrieben hast? Also nicht unbedingt Optimizer-Magie? Jetzt hab ich hier viel spekuliert und sehe gerade, dass du den Compiler möglicherweise doch bezüglich Load+Store "an der Hand geführt" hast.

Genau