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

Hallo,

ich verstehe etwas nicht. Folgende Funktion berechnet mir für meine
double werte über eine XOR-Operation der oberen und unteren 32 Bit
einen schlüssel.

typedef unsigned int U_Int32;
template <class T>  inline U_Int32 
Class<T>::H_Double(double x)
{ 
    U_Int32 p[2];
    memcpy( p, &x, sizeof p );
    return p[0] ^ p[1];
}

Ich würde erwarten, dass wenn ich der funktion einen U_Int32 übergebe
dass einfach nix passiert, da einfach die 32 Bit Zahl verXODERT wird mit
lauter NUllern.

Für normale Inputs geschieht das auch.

Übegebe ich aber sowas

U_Int32 hd_x = H_Double(4);
        U_Int32 hd_y = H_Double(5);  
        U_Int32 test = hd_x^hd_y;
        std::cout << "hdx^hdy: " << test << std::endl;

        test = H_Double(test);
        std::cout << "H_Double(hdx^hdy)" << test << std::endl;

kommen unterschiedliche werte dabei raus. Warum beeinflusst denn die
XOR-Operation die Ausgabe? Ich übergebe doch mit dem U_Int32 einen 32 Bit wert der eigentlich nicht verändert werden sollte....oder wo ist mein denkfehler?

Danke

CStoll

Die Funktion erwartet einen double - wenn du dort einen int übergibst, wird der nicht 1:1 übernommen, sondern in einen (soweit möglich) wertgleichen double konvertiert - und der hat dann ein anderes Bitmuster.

Danke CStoll - leider bräuchte ich noch ein wenig Hilfe weil mich das jetzt etwas wundert.

Wenn ich jetzt z.B 0000 0100 für die Zahl 4 habe, ich dachte sozusagen dass dann vorne einfach Nuller angehängt werden. Bzw. wie wird denn die Darstellung geändert?

Seltsam ist auch dass wenn ich ja z.B nur 4 übergebe, die Schlüssel identisch sind.
Gebe ich aber z.B 4 xor 5 , dann sind sie es nicht?

Also irgendwie versteh ich da was nicht.....

Ich danke für noch ein weni Hilfe....

CStoll

testo schrieb:

Wenn ich jetzt z.B 0000 0100 für die Zahl 4 habe, ich dachte sozusagen dass dann vorne einfach Nuller angehängt werden. Bzw. wie wird denn die Darstellung geändert?

Wenn du die Ganzzahl 4 an deine Funktion übergibst, wird diese umgerechnet in die Gleitkommazahl 4.0 - und von diesem Wert wird dein Schlüssel berechnet - daß dort wieder 4 rauskommt, ist vermutlich Zufall.

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.