Schlüssel für double werte - brauche kurze erklärung

Konrad Rudolph

Die Funktion ist sowieso komisch, wieso z.B. das 'memcpy'? Ein 'reinterpret_cast' wäre hier doch wohl eher angebracht.

camper

Konrad Rudolph schrieb:

Die Funktion ist sowieso komisch, wieso z.B. das 'memcpy'? Ein 'reinterpret_cast' wäre hier doch wohl eher angebracht.

Ein reinterpret_cast würde die Aliasregeln verletzen - ist also undefiniert und fliegt dir bei hohen Optimierungsstufen schnell um die Ohren. Aus Performancesicht wäre es sicherlich sinnvoll, einerseits den Parameter in eine Referenz zu verwandeln (die übliche Argumentation, darauf bei built-ins zu verzichten, greift bei inline-Funktionen nicht), andererseits ist memcpy meist performanter, wenn es auf größere Blöcke angewandt wird: eine Funktion, die auf Arrays arbeitet, würde daher effizienter arbeiten. Das hat aber alles nichts mit dem Thema zu tun.

Konrad Rudolph

camper schrieb:

Konrad Rudolph schrieb:

Die Funktion ist sowieso komisch, wieso z.B. das 'memcpy'? Ein 'reinterpret_cast' wäre hier doch wohl eher angebracht.

Ein reinterpret_cast würde die Aliasregeln verletzen - ist also undefiniert und fliegt dir bei hohen Optimierungsstufen schnell um die Ohren.

Welche Aliasregel? Die kenne ich nicht.

Aus Performancesicht wäre es sicherlich sinnvoll, einerseits den Parameter in eine Referenz zu verwandeln (die übliche Argumentation, darauf bei built-ins zu verzichten, greift bei inline-Funktionen nicht)

Wieso das? Wenn die Funktion ordentlich geinlined wird, dann kann doch hier sicherlich auch die Parameterkopie verhindert werden – oder erkennt der Compiler nicht, dass hier nirgendwo Schreibzugriff erfolgt?

Nur damit wir über's selbe reden, ich meine das hier:

inline U_Int32 H_Double(double x)
{
    U_Int32 const* const p = reinterpret_cast<U_Int32*>(&x);
    return p[0] ^ p[1];
}

U_Int32 h = H_Double(12.34);

Aus Optimierungssicht sollte es doch relativ einfach sein, hier zu erkennen, dass weder auf x noch auf ein Alias (p) jemals Schreibzugriff erfolgt, und zu Folgendem äquivalenten Code zu generieren:

double d = 12.34;
U_Int32 h =
    *reinterpret_cast<U_Int32*>(&d) ^
    *(reinterpret_cast<U_Int32*>(&d) + 1);

Fellhuhn

Ist das nicht einfacher?

inline U_int32 H_Double(double h){
  return ((U_int32*)&h)[0] ^ ((U_int32*)&h)[1];
}

Konrad Rudolph

Fellhuhn schrieb:

Ist das nicht einfacher?

inline U_int32 H_Double(double h){
  return ((U_int32*)&h)[0] ^ ((U_int32*)&h)[1];
}

Das ist im wesentlichen dasselbe wie das von mir vorgeschlagene – nur: C-Style-Casts stinken.

Fellhuhn

C++ ist nur gut wenn man alle "Features" von C nutzt.

Dein Posting war noch nicht da als ich es geschrieben hab. Daher die "Ähnlichkeit".

camper

Konrad Rudolph schrieb:

camper schrieb:

Konrad Rudolph schrieb:

Die Funktion ist sowieso komisch, wieso z.B. das 'memcpy'? Ein 'reinterpret_cast' wäre hier doch wohl eher angebracht.

Ein reinterpret_cast würde die Aliasregeln verletzen - ist also undefiniert und fliegt dir bei hohen Optimierungsstufen schnell um die Ohren.

Welche Aliasregel? Die kenne ich nicht.

3.10/15 im C++ - Standard
analog 6.3 in C90 bzw. 6.5/7 in C99
die jeweils klären, mittels welcher Art Ausdruck auf den Wert eines Objektes zugegriffen werden darf:

15 If a program attempts to access the stored value of an object through an lvalue of other than one of the following types the behavior is undefined48):
— the dynamic type of the object,
— a cv-qualified version of the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to the dynamic type of the object,
— a type that is the signed or unsigned type corresponding to a cv-qualified version of the dynamic type of the object,
— an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union),
— a type that is a (possibly cv-qualified) base class type of the dynamic type of the object,
— a char or unsigned char type.

In unserem Falle bleibt davon (abgesehen von den cv-Versionen) nur der Zugriff per char/unsigned char übrig. Wollten wir also ganz auf Kopieren verzichten, müssen wir das benutzen (und es ist durchaus denkbar, dass der Compiler das besser optimieren kann - aber die Variante per memcpy dürfte allemal verständlicher sein):

typedef unsigned int U_Int32;
template <class T>  inline U_Int32
Class<T>::H_Double(const double& x)
{
    const unsigned char (&p)[8] = reinterpret_cast< const unsigned char(&)[8] >( x );
    return U_Int32( p[0]^p[4] | (p[1]^p[5])<<8 | (p[2]^p[6])<<16 | (p[3]^p[7])<<24 );
}

Was die Eliminierung von value-Paramtern von inline-Funktionen angeht: Wenigstens einige Compiler haben damit große Schwierigkeiten, und gerade wenn Operationen wie memcpy im Spiel sind, wird es für den Compiler auch recht schwer. Daher ist es wenigstens dann sicher besser, von vornherein eine Referenz zu verwenden.

Konrad Rudolph

camper schrieb:

Konrad Rudolph schrieb:

camper schrieb:

Konrad Rudolph schrieb:

Die Funktion ist sowieso komisch, wieso z.B. das 'memcpy'? Ein 'reinterpret_cast' wäre hier doch wohl eher angebracht.

Ein reinterpret_cast würde die Aliasregeln verletzen - ist also undefiniert und fliegt dir bei hohen Optimierungsstufen schnell um die Ohren.

Welche Aliasregel? Die kenne ich nicht.

3.10/15 im C++ - Standard
analog 6.3 in C90 bzw. 6.5/7 in C99

Ach so. Klar.

Das kann man hier ja wohl aber in Kauf nehmen, da dieser Code eh nicht portabel ist und Annahmen über das Bit-Layout der Typen trifft. Oder meinst Du, dass es realistische Situationen gibt, in denen in diesem Fall die 'memcpy'-Variante funktioniert, die 'reinterpret_cast'-Variante aber nicht?

camper

Konrad Rudolph schrieb:

Das kann man hier ja wohl aber in Kauf nehmen, da dieser Code eh nicht portabel ist und Annahmen über das Bit-Layout der Typen trifft. Oder meinst Du, dass es realistische Situationen gibt, in denen in diesem Fall die 'memcpy'-Variante funktioniert, die 'reinterpret_cast'-Variante aber nicht?

Bei Aliasing geht es nicht um Layoutprobleme (natürlich können inkompatible Layouts zu undefinierten Verhalten führen, wenn es nicht schon am aliasing scheitert). Es geht im Kern um die Identität von Objekten. Kleines sinnfreies Beispiel:

template<typename T, typename U>
T f(const T& foo, U* bar)
{
    T baz = foo;
    *bar = 0;
    return baz ^ foo;
}

T sei irgendein integertyp.
wenn U hier von T verschieden und kein char/unsigned char oder der zu T korrespondiernde vorzeichenlose/-behaftete Typ ist, kann und darf der Compiler hier annehmen, dass f stets 0 zurückgibt. In anderen Fällen wäre es denkbar, dass die Zuweisung an *bar den Wert von foo ändert - diese Möglichkeit erschwert offensichtlich Optimierungen, denn solange Aliase existieren können - und der Compiler diesen nicht folgen kann (was bei Pointern regelmäßig der Fall sein wird, Referenzen sind da manchmal einfacher) - darf sich der Speicherplatz der Variablen (im kompilierten Code - ob das nun ein Register oder ein Hauptspeicherplatz ist, ist erst mal egal) nicht ändern. Denn ein auf einen Zugriff über ein Alias erfolgender Zugriff muss eine evtl. Änderung des Wertes reflektieren. Die (strengen) Aliasregeln erleichtern dem Compiler die Arbeit, indem sie die Fällen einschränken, in denen Aliasing auftreten darf.

double d = 12.34;
U_Int32 h =
    *reinterpret_cast<U_Int32*>(&d) ^
    *(reinterpret_cast<U_Int32*>(&d) + 1);

Da die Typen völlig inkompatibel sind, darf der Compiler annehmen, dass der Zugriff über die Pointer nicht vom Wert den d abhängt, also nicht auf d zugegriffen wird. Falls das der EInzige Zugriff auf d sein sollte, hindert nichts den Compiler, d komplett wegzuoptimieren - und die Pointer die beim Cast gebildet werden zeigen möglicherweise nicht irgendwohin (sondern dahin wo d sein würde, wenn der Compiler nicht auf die Initialisierung verzichtet hätte) und das Ergebnis ist einfach nur Müll. Und zu dieser Optimierung sind moderne Compiler durchaus fähig.

Und schließlich - das kannst du nicht wissen - ist der präsentierte Code das Ergebnis eines vorherigen Postings (1-2 Monate her), weil eine Variante mit Cast plötzlich (nach einem Compilerupdate) nicht mehr funktionierte.

Also ohne irgendjemandem wiedersprechen zu wollen und nur so falls es jemanden interessiert:

Ich hatte vorher tatsächlich einen reinterpret_cast drin und das lief auch ohne Probleme auf meinem gcc 3.3 damals.

Nachdem ich dann mit meinem gcc 4.1.* gemerkt habe dass die Funktion plötzlich inkorrekt arbeitet wurde sie auf das vorliegende geändert.

Nur soviel dazu.
Danke für die rege beteiligung.

Konrad Rudolph

Hi Camper, vielen Dank für die Erläuterung. Mir war nicht bewusst, dass der Compiler hier so weitreichende Optimierungs„erlaubnis“ besitzt.