Unions oder doch Bit-Shift und Bit-Operationen



  • @hustbaer So ist es eben wenn man anfängt sich in den Fuß zu schießen. Zuerst mit der kleinkalibrigen Pistole ... und ehe man es merkt hat man eine Panzerfaust in der Hand ...



  • @Netzschleicher sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Sorry wenn die Codeformatierung fehlt. Schreibe aus der Arbeit, und im Browser hier funzt das nicht. 😫

    Du brauchst bloß drei Backticks (```) in eine Zeile vor und in eine Zeile nach Deinem Code schreiben.



  • Ich weiss nicht mehr genau welcher Vortrag es war, ich erinnere mich allerdings noch vage daran, dass Chandler Carruth auf die Frage, wie diese Problematik denn am besten zu lösen sei, mit memcpy geantwortet hat, das würde gut optimiert.

    memcpy-Ansatz

    Ich war neugierig und habe mal geschaut, was die Compiler da so generieren: https://godbolt.org/z/FsYGAb

    Für seinen Compiler, Clang, hat Carruth auf jeden Fall nicht zu viel versprochen. Aus

    r2 = set_hi(r2, get_lo(r1));
    r2 = set_lo(r2, get_hi(r1));
    

    wird hier einfach nur

    rol     ax, 8
    

    Eine simple Linksrotation des 16-Bit AX-Registers, bei der die Einsen und Nullen, die links herausgeschoben werden wieder rechts hineingeschoben werden.
    Wie geil ist das denn, was der da aus diesem Funktionsgeschachtel und den memcpy-Aufrufen macht? 😉

    Des weiteren arbeitet der Code, der für die Funktionen erzeugt wird, ausschliesslich auf Registern und kommt ohne Speicherzigriffe aus (Das lea eax, [rdi + rsi] in set_lo ist nur eine Adressberechnung, kein Speicherzugriff!).

    Leider erzeugen GCC und MSVC hier unnötige Speicherzugriffe in den set-Funktionen und somit auch im main-Code. Es scheint, als könnten diese das memcpynicht so gut wegoptimieren. Gut ist jedoch, dass diese bei den get-Funktionen ebenfalls nur auf Registern arbeiten.

    union-Ansatz

    Hier dasselbe mit union: https://godbolt.org/z/F1F96h

    Clang erzeugt hier identischen Code 👍, GCC kommt hierbei jezt ohne die zusätzlichen Speicherzugriffe aus (gut!), berechnet das Ergebnis aber auf anderem Wege, unter Verwendung von ah/al etc., der "hi"/"lo"-8-Bit-Register, welche die x86-Architektur zur Verfügung stellt (Das ist auch gut!). MSVC leidet hierbei leider immer noch unter zu vielen Speicherzugriffen... Schade.

    shift-Ansatz

    ... und nochmal mit Shift und Bitweisen Operationen: https://godbolt.org/z/EmW1aX

    Wieder identischer Code mit Clang - schon beeindruckend wie gut dieser Compiler hier begreift, dass dieser ganze Code äquivalent ist 👍. GCC erzeugt hier den selben Code wie beim union-Ansatz, auch gut! MSVC baut mir hier wieder zu viele Speicherzugriffe ein, auch wenn es auf den ersten Blick ebenfalls nach identischem Code aussieht.

    Fazit

    Zumindest für meinen Testfall hier, scheinen die Shift- und union-Ansätze gleichwertigen Code zu erzeugen. Mit memcpy glänzte hier leider nur Clang.

    Alles in allem ist dennoch Vorsicht angebracht: Mein Test ist nicht sonderlich umfangreich und ist daher nicht geeignet, ein vollständiges Bild zu liefern... ich denke man bekommt aber schon so ein paar Ideen.

    @TGGC Die verscheidenen Tests zeigen auch ein wenig, was ich mit Astraktion meine und warum man nicht "tausende Bitshifts" überall im Code benötigt. Meine "riesige main()-Codebase" musste ich hier gar nicht anfassen, ich habe für jeden Testfall lediglich die Abstraktion angepasst 😉


  • Mod

    So wirklich interessant würde das aber erst bei Code für einen 8-Bit Prozessor. Oder wenn du statt 16 Bit in 2x8 zu zerlegen, du bei dem hier benutzten 64-Bit Zielprozessor 128 Bit in 2x64 zerlegst. Dann ist das mit den Optimierungen nämlich vermutlich nicht mehr so einfach.

    PS: Das ist mir selber aber gerade im Moment zu viel Aufwand, Finnegans Programme darauf umzuschreiben, da es keinen nativen 128-Bit Typen gibt. Aber wenn jemand Zeit und Lust hat, würde mich das Ergebnis sehr interessieren.
    PPS: Oder wenn man -m32/-m16 benutzt und dann das "Register" auf 64 bzw. 32 Bit setzt, sollte das den gleichen Effekt haben, oder?



  • @Finnegan sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    @TGGC Die verscheidenen Tests zeigen auch ein wenig, was ich mit Astraktion meine

    Du hast aber auch nur einen absolutes Minimum an Funktionalität eingebaut. Der Compiler kann Unions aus beliebig vielen structs, die wiederum beliebig viele uints mit einer beliebiger Bitzahl enthalten können. Folgen wir deinem Schema musst du im allgemeinen Fall für jeden der Member zwei Funktionen mit jeweils einem Shift und einem And und den zwei Magical Values programmieren.

    Ich schaue gerade auf eine struct mit 24 Member, das wären 48 Funktionen und 96 Operationen und 96 Magical Values. Noch nicht eingerechnet, wie oft sich diese Sachen im Laufe der Entwicklung geändert hätten, weil man die Member ordnet erweitert oder entfernt. Für eine einzige Struct. Diese Variante ist für mich daher komplett praxisfremd.



  • @SeppJ sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    da es keinen nativen 128-Bit Typen gibt

    GCC, Clang, ICC: __int128



  • @SeppJ sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Aber wenn jemand Zeit und Lust hat, würde mich das Ergebnis sehr interessieren.

    https://godbolt.org/z/O7GROY


  • Mod

    @hustbaer sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    @SeppJ sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    da es keinen nativen 128-Bit Typen gibt

    GCC, Clang, ICC: __int128

    Ausgezeichnet.

    Shift-Variante:
    https://godbolt.org/z/w7jKTb

    Union-Variante:
    https://godbolt.org/z/EoCE41

    Gleiche Beobachtung wie von Finnegan bei 8-Bit gemacht: Die Shift-Variante ist genau so gut wie die Union-Variante, d.h. es wird alles maximal optimiert zu zwei simplen mov. Beim GCC ist die memcpy-Variante etwas schlechter, CLang kann auch diese optimieren. Beeindruckend. Insbesondere da man die Bitmaske für das High-Word gar nicht mehr als Literal hinschreiben kann, aber selbst mit der Zwischenrechnung wurde alles perfekt optimiert.

    Swordfishs Vorschalg kann man natürlich nicht mehr zum Vergleich ranziehen, weil seine überlegene Variante nicht mehr für > 8 Bit funktioniert.



  • @hustbaer sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    https://godbolt.org/z/O7GROY

    Das geht nun wirklich nicht besser, ohne die Aufrufkonvention zu verletzen. Nice 😉

    Warum hingegen GCC die Parameter-Register erst auf den Stack schreibt, nur um sie dann direkt wieder in die Rückgabe-Register einzulesen verstehe ich wirklich nicht: https://godbolt.org/z/vpyYQY
    Da sieht man mal wieder dass Optimierung oft derart ausgeklügelt ist, dass sie bei so simplen Dingen versagt. Etwas superkomplexes hätte er vielleicht brilliant gelöst 😉

    @SeppJ sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Shift-Variante:
    https://godbolt.org/z/w7jKTb

    Union-Variante:
    https://godbolt.org/z/EoCE41

    Interessanterweise bekommt der GCC hierbei auch das simple mov hin. Nur bei memcpy verschluckt er sich, was mich wieder in der vermutung bestärkt, dass die Empfehlung von Chandler Carruth doch sehr "clang-spezifisch" war 😉

    @TGGC sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Ich schaue gerade auf eine struct mit 24 Member, das wären 48 Funktionen und 96 Operationen und 96 Magical Values.

    Das sieht mir schon nach einem massiveren Einsatz von Type Punning via union aus. Vielleicht ist das ja gut handhabbar ein deinem Code, aber wenn ich das so lese, wäre mir dabei etwas unwohl, dass ich nicht irgendwo einen Union-Zugriff einbaue, der trotzdem vor die Wand läuft.
    Was passiert da? Irgendein Zusammenbau von Datenpaketen oder Speicherblöcken für eine Hardware?



  • In dem Fall wird eine Anzahl int Werte speichereffizient abgespeichert und später aus dem Speicher gelesen, verglichen etc.

    Ich hab auch noch ein anderes Real World Beispiel, nur Variablennamen angepasst, sonst rauskopiert.

    /*!
        0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0
        ^  ^  ^                                ^  ^                                                   ^  ^                                                                                                 ^
        |    | |_____________     ___________|  |_____________________   __________________________|  |____________________________________   ________________________________________________________|
        |  |                 12 Bit                                    16 Bit                                                                32 Bit
        |  |                   |                                        |                                                                    |
        |  |                 Wert A                                   Wert B                                                            Wert C
        |    Flag B
        Flag A
    */
    	union
    	{
    		struct
    		{
    			uint32		WertC : 32;
    			AndereID	WertB;
    			uint16		Unused : 2;
    			uint16		WertA : 12;
    			uint16		FlagB : 1;
    			uint16		FlagA : 1;
    		};
    
    		uint64			Data;
    	};
    
    

    Hier wird das ganze sogar verschachtelt benutzt. AndereID ist wieder ein solcher Datentyp. Data wird zum schnellen vergleichen benutzt, zum Einordnen in Hashmaps, zum sortieren um Reihenfolgeprobleme zu lösen. Eins der Flags ist z.B. nötig um zu sagen, welchen ID nur auf dem Rechner gültig ist und welche global im Netzwerk gültig sind. Andere Teile damit Threads oder gar verschiedenen User an verschiedenen PCs unabhängig IDs generieren können, die nicht kollidieren. Früher hatten wir nur Data und damit rumgeshiftet, seit dem die Komplexität höher wurde und wir von 32 auf 54 gingen, haben wir das gelassen.

    Der Code ist übersichtlicher und genauer als der Kommentar, zumindest für mich. Zur Compilezeit sind einige Basics durch static asserts abgesichert, die vor den größten Dummheiten schützen sollen, aber nicht wirklich relevant sind aus meiner Sicht. Probleme gabs noch nie, würden aber sofort auffallen, da quasi alles darauf aufbaut. In der täglichen Arbeit kann ich mich darauf verlassen, das der Code simpel aussieht, lesbar ist und verlässlich und effizient tut, was wir wollen.

    Und zu Chandler Carruth bei einem verwandten Thema: https://www.youtube.com/watch?v=vElZc6zSIXM&t=3235
    "Its terrifying [...] But use them, its less terrifying than writing math yourself and hope to get it right"



  • Seh ich jetzt erst:

    @Th69 sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Ab C++20 gibt es dafür dann std::bit_cast<To, From>.

    Wie hilft das bei vorliegendem Problem?



  • @Swordfish Naja mit bit_cast kannst du memcpy ohne memcpy machen. D.h. du kannst damit z.B. nen uint64_t in einen gleich grossen (trivialen) struct konvertieren. Siehe https://en.cppreference.com/w/cpp/numeric/bit_cast

    Der Vorteil dabei ist: das kann zwar über memcpy implementiert sein, es muss aber nicht. Damit können die Jungs die die Standard-Library schreibseln es so schreibseln dass der Compiler versteht dass hier nichts "in den Speicher gezwungen" werden muss sondern bloss bytes "uminterpretiert" werden.

    EDIT: den/dem Fehler korrigiert 🤦♂ . Naja, ich sag mal die Hitze is schuld 🙂



  • @hustbaer sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Naja mit bit_cast kannst du memcpy ohne memcpy machen. D.h. du kannst damit z.B. nen uint64_t in einen gleich grossen (trivialen) struct konvertieren.

    Ach so, ja. Ich dachte ständig an einen kleineren Typ für High and Low. Mit einer struct wird da schon ein Schuh draus.



  • @TGGC sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    Ich hab auch noch ein anderes Real World Beispiel, nur Variablennamen angepasst, sonst rauskopiert. [...]

    Mit solchen kompakten Datenstrukturen habe ich auch immer wieder mal zu tun gehabt und bevorzuge diese auch vor allem aus Cache-Gründen, wenn die Performance wichtig ist. Ich bin auch so verwegen und speichere in meiner Freizeit auch schonmal Flags in den Bits von Pointern, die wegen des Alignments immer 0 sind (manchmal gehe ich sogar so weit und nutze bei Pointern selbst die obeneren ungenutzen Bits 😉 ).

    Auf die Idee, das mit dem Data über ein Union zu lösen, bin ich allerdings noch nicht gekommen, deshalb konnte ich mir auch nur schwer vorstellen, wann man sowas wirklich braucht. Ich habe mal eine Trie-basierte Datenstruktur geschrieben, in der ich auch so etwas ähnliches die dieses Data benötigte. Dort habe ich allerdings das struct als char-Array (re-)interpretiert und mir dann das Data mit Shift-Operationen aus den einzelnen char-Bytes zusammengestoppelt. Diesen Code braucht man auch nicht anzupassen, wenn sich die Zusammensetzung des struct ändert, höchstens wenn es dann irgendwann nicht mehr in einen uint64 passt.

    Und zu Chandler Carruth bei einem verwandten Thema: https://www.youtube.com/watch?v=vElZc6zSIXM&t=3235
    "Its terrifying [...] But use them, its less terrifying than writing math yourself and hope to get it right"

    Ja, ich stimme da zu. Wenn sich diese Berechnungen redundant durch die Ganze Codebase ziehen, dann sind sie gewiss eine nervige Fehlerquelle. Bitfields halte ich auch für okay, wenn man aufpasst und sich der Konsequenzen bewusst ist, dass sich hier mehrere Variablen eine Speicheradresse teilen können. Dennoch: Ich denke, dass sich fehlerträchtige Berechnungen immer irgendwie zentralisieren lassen, so dass man nur eine problematische Stelle im Code hat, anstatt hunderte. Das sollte einem der Mehraufwand für eine Abstraktion wert sein.



  • @hustbaer sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    bit_cast
    ...
    Der Vorteil dabei ist: das kann zwar über memcpy implementiert sein, es muss aber nicht.

    Nach den Beobachtungen hier im Thread rate ich mal ins Blaue, dass das Clang-Team wahrscheinlich wenig Mühe haben wird, das zu implementieren und das wohl einfach nur als memcpy-Wrapper umsetzt 😉



  • @Finnegan sagte in Unions oder doch Bit-Shift und Bit-Operationen:

    @TGGC sagte in Unions oder doch Bit-Shift und Bit-Operationen:
    Dennoch: Ich denke, dass sich fehlerträchtige Berechnungen immer irgendwie zentralisieren lassen, so dass man nur eine problematische Stelle im Code hat, anstatt hunderte.

    Diese Stelle gibt es und die ist im Kompiler drin. Daher meine Meinung: nicht neu machen. Ausserdem ist ja schön wenn du alles zentralisierst, aber wenn hunderte Member eine Position und Länge innerhalb ihrer Parentstruct brauchen, dann musst du eben diese hundertem Werte eben angeben. Wie zentralisiert das ist, ändert nichts an der Menge der Daten und der Schwierigkeit Inkonsistenzen zu vermeiden. Und daher nehme ich da soviel Unterstützung und Error Checking vom Compiler mit, wie ich nur kann anstatt das alles neu zu designen.


Anmelden zum Antworten