Unions oder doch Bit-Shift und Bit-Operationen

hustbaer

@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.

SeppJ

@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.

Finnegan

@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?

TGGC

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"

Swordfish

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?

hustbaer

@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

Swordfish

@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.

Finnegan

@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.

Finnegan

@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

TGGC

@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.