3. Hash_Key aus double-vector möglichst schnell: Ideen gesucht

Hash_Key aus double-vector möglichst schnell: Ideen gesucht

  • M

    Hallo,

    ich habe eine Funktion die mir aus einem double-vector einen möglichst kollisionsfreien Schlüssel generiert. Das funktioniert auch einwandfrei - nur laut meinem Profiling wird da ziemlich viel Zeit verbraten (~5-8%).

    Die Berechnung dieser schlüssel läuft innerhalb von for-schleifen, d.h sie kann unter umständen mehrere 10000-mal aufgerufen werden.

    Was ich bisher verwendet habe war das folgende:

    typedef unsigned int U_Int32;

template <>	U_Int32 
Cache<double>::Compute_Key(	const double* vec, 
							size_t size) const
{                    
	U_Int32 ret = 0;
	U_Int32 mix = Hash_Double(0.13);
	while(size--)
	{
		ret = (ret * 31) + mix + Hash_Double(*vec);
		vec++;
	} 
	return ret;
}

template <class T>	inline U_Int32 
Cache<T>::Hash_Double(double x)
{ 
	// 	U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
	// 	return *p ^ (*p >> 32); 

	U_Int32 p[2];
	memcpy( p, &x, sizeof p );
	return p[0] ^ p[1];
}

    Was dort passiert: Ich iteriere über jeden wert des vectors und ver-XODERe die oberen 32 Bit mit den unteren.

    Also eine Iteration über alle Elemente ist ja schon mal zwingend....obs noch schneller geht?

    0
  • C
    Mod 

    typedef unsigned int U_Int32;

template <>    U_Int32
Cache<double>::Compute_Key(    const double* vec,
                            size_t size) const
{                    
    U_Int32 ret = 0;
    U_Int32 mix = Hash_Double(0.13);
    while(size--)
    {
        ret = (ret * 31) + mix + Hash_Double(*vec);
        vec++;
    }
    return ret;
}

template <class T>    inline U_Int32
Cache<T>::Hash_Double(const double& x) // const double& bei inlining evtl. effizienter
{
    //     U_Int64* p = reinterpret_cast< U_Int64* > (&x);
    //     return *p ^ (*p >> 32);
    struct Helper
    {
        U_Int32 p[2];
    };
    const Helper& h = *new(const_cast<void*>(&x)) Helper; // tut eigentlich nichts, müsste aber unerlaubtes aliasing verhindern
    U_Int32 result = h.p[0] ^ h.p[1];
    new(const_cast<void*>(&x)) double;
    return result;
}

    Ich bin mir noch nicht ganz sicher ob das wirklich legal ist, aber ein Feldversuch kann nicht schaden.

    0
  • B

    Warum nicht einfach so?

    Hash_Double(const double& x)
{
    struct Helper
    {
        U_Int32 a, b;
    };
    const Helper& h = (const Helper&)x;
    return h.a ^ h.b;
}
    0
  • C
    Mod

    Badestrand schrieb:

    Warum nicht einfach so?

    Hash_Double(const double& x)
{
    struct Helper
    {
        U_Int32 a, b;
    };
    const Helper& h = (const Helper&)x;
    return h.a ^ h.b;
}

    weil das Layout von Helper nicht hinreichend genau festgelegt ist (deshalb muss es mit einem Array sein). Was schwerer wiegt, ist die Verletzung der Aliasregeln. Seit Urzeiten werden Programme geschrieben, die diese Regeln verletzen, nicht zuletzt deshalb, weil die Compiler lange nicht in der Lage waren, das Optimierungspotential, das in diesen Regeln liegt, zu nutzen. Viele der Probleme, die bei hohen Optimierungsstufen auftreten, sind - abgesehen von echten Compilerfehlern - auf solche subtilen Fehler zurückzuführen.

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

    1. The intent of this list is to specify those circumstances in which an object may or may not be aliased.
    0
  • ?
     

    Hash_Double(const double& x)
{
    U_Int32* a = reinterpret_cast< U_Int32* > (&x);
    return *a ^ *(a+1);
}

    so?

    0
  • B

    camper schrieb:

    Badestrand schrieb:

    ...

    weil das Layout von Helper nicht hinreichend genau festgelegt ist (deshalb muss es mit einem Array sein). Was schwerer wiegt, ist die Verletzung der Aliasregeln.

    Kannst du das evtl ein wenig genauer erklären? Und wie meinst du das mit den Aliasregeln? Dass a und b auch 8-Byte-Aligned sein könnten?

    0
  • M

    Danke vielmals für eure Hilfe - leider schreit mein compiler gcc 4.1.3 mit der version von camper mehrmals nach einem ungültigen cast:

    Fehler: ungültiges const_cast von Typ »double*« in Typ »void*«

    Ändere ich die cast von void* nach double* klappt natürlich. Und ich glaube auch dass es korrekt arbeitet - bemerke aber dass ich etwas langsamer bin mit dieser funktion...

    Der reinterpret_cast ist zwar schneller liefert aber inkorrekte ergebnisse...

    0
Anmelden zum Antworten