hash_map: insert operation sehr teuer? Warum?



  • Hallo,

    ich habe einen algorithmus mit einer hash_map am laufen. Mein erwarteter speedup mittels hash-map ist leider überhaupt nicht zustandegekommen - leider bekomme ich viel schlechtere laufzeiten (profiling).

    An der Hash funktion liegt es nicht - auch wenn ich diese auf nur eine anweisung vereinfache ändert sich da nix.

    struct HASH_DATA
    {
        std::vector<double> a;
        std::vector<double> b;
        std::vector<double> c;
        int d;
        int e;   
    };
    
    typedef std::pair< std::vector< double >, HASH_DATA> Hash_Pair;
    ...
     hash_map<std::vector<double>, HASH_DATA, HASH_FUNCTION> m_hash_map;
    
    ...
    
    void
    Hash::Insert_Hash_Data(const std::vector< double >& a
                           const std::vector< double >& b
                           const std::vector< double >& c
                           const std::vector< double >& d
                           const int e
                           const int f
    {
        struct HASH_DATA hd;
        hd.a = b;
        hd.b = c;
        hd.c = d;
        hd.d = e;
        hd.e = f;   
        m_hash_map.insert(Hash_Pair(a, hd));
    }
    

    jetzt weiß ich nicht ob es evtl. an der speicherung von den ganzen vektoren liegen kann - diese können nämlich ziemlich groß werden (dimension 2000).
    Ich habe probeweiser mal einfach gar nichts in das hash schreiben lassen - das hat fast gar nichts an dem laufzeitproblem geändert. Natürlich hat er zwar immer an ne andere stelle "nichts" reingeschrieben aber es änderte nichts....kann es sein dass im vergleich die zeit um dinge in die hash_map zu inserten einfach sehr lange arbeiten?

    Wenn ja, wäre es performanter das hashing nicht auf basis der stl-extensions zu benutzen sondern zu versuchen selber was zu schreiben? Ich bezweifle dass das speedup bringen könnte...

    Für ratschläge bin ich sehr dankbar!



  • Äh. Vektoren kopieren ist vielleicht sehr teuer?
    Vielleicht verstehe ich aber auch nicht genau was du meinst.
    Nen std::vector<double> als Key zu verwenden ist auch etwas... seltsam & unüblich.

    Was tut denn das Programm inetwa?

    Und: eine hash-map ist nicht notwendigerweise sehr schnell beim Einfügen (kommt auf die Implementierung drauf an - sie *kann* auch schnell beim Einfügen sein), sondern eher beim Lookup.



  • Mati schrieb:

    ich habe einen algorithmus mit einer hash_map am laufen. Mein erwarteter speedup mittels hash-map ist leider überhaupt nicht zustandegekommen - leider bekomme ich viel schlechtere laufzeiten (profiling).

    jo, das kommt öfter mal vor. hauptursache ist eine schlechte hash-funktion.

    An der Hash funktion liegt es nicht - auch wenn ich diese auf nur eine anweisung vereinfache ändert sich da nix.

    "bringt sie zu viele kollissionen" ist die frage. die hash_map von dir ist vermutlich ein array mit vielen zeigern auf verkette listen. wenn die hashfunktion immer den gleichen arrayindex erzeugt, dann kollabiert die hash_map zu einer einzigen verketten liste und du hast schreckliche suchzeiten aber noch prima einfügezeiten.

    void
    Hash::Insert_Hash_Data(const std::vector< double >& a
                           const std::vector< double >& b
                           const std::vector< double >& c
                           const std::vector< double >& d
                           const int e
                           const int f
    {
        struct HASH_DATA hd;
        hd.a = b;
        hd.b = c;
        hd.c = d;
        hd.d = e;
        hd.e = f;   
        m_hash_map.insert(Hash_Pair(a, hd));
    }
    

    schade, daß das viele kopieren sein muß. aber egal, du machst eh viel mehr suchoperationen als einfügungen, gell?

    jetzt weiß ich nicht ob es evtl. an der speicherung von den ganzen vektoren liegen kann - diese können nämlich ziemlich groß werden (dimension 2000).

    klar ist das lahm, 5 vectoren zu kopieren, sogar zweimal zu kopieren, einmal in deiner insert-funktion und einmal in der der hash_map (und noch einmaln im ctor von Hash_Pair?). vielleicht ist es besser, sich erst ein leeres datenelement zu holen und dann dort reinzukopieren.

    Ich habe probeweiser mal einfach gar nichts in das hash schreiben lassen - das hat fast gar nichts an dem laufzeitproblem geändert. Natürlich hat er zwar immer an ne andere stelle "nichts" reingeschrieben aber es änderte nichts....kann es sein dass im vergleich die zeit um dinge in die hash_map zu inserten einfach sehr lange arbeiten?

    ca. 100 bis 200 takte, schätze ich. halt einmal den op new aufrufen für die private verkettete liste.

    Wenn ja, wäre es performanter das hashing nicht auf basis der stl-extensions zu benutzen sondern zu versuchen selber was zu schreiben? Ich bezweifle dass das speedup bringen könnte...

    ich auch.

    Für ratschläge bin ich sehr dankbar!

    kannste dir erlauben, zeiger auf vector zu verwalten statt der daten selbst?

    außerdem kopierungen sparen.

    //völlig ungetestet. nur mal so ne anregung. 
    void Hash::Insert_Hash_Data(const std::vector< double >& a
                           const std::vector< double >& b
                           const std::vector< double >& c
                           const std::vector< double >& d
                           const int e
                           const int f
    {
        pair<iterator,bool>& insertResult=m_hash_map.insert(a);
        if(insertResult.second==false) return;
        HASH_DATA& hd=(*insertResult.first).second;
        hd.a = b;
        hd.b = c;
        hd.c = d;
        hd.d = e;
        hd.e = f;   
    }
    


  • danke euch...
    habe jetzt meinen algorithmus auf pointer umgeschrieben...
    jetzt würde ich gern meine hash klasse komplett auf pointer verlegen...nur habe ich damit enorme probleme....:(

    Ich poste mal den ursprung ohne pointer (NEBENBEI: Das Hashing ist zum großteil mit volkards Hilfe entstanden 🙂 )

    //======HEADER==================
    #if __GNUC__ < 3
    #include <hash_map.h>
    #else
    #include <ext/hash_map>
    using __gnu_cxx::hash_map;
    #endif
    
    typedef unsigned int U_Int32;
    typedef unsigned long long U_Int64; 
    
    struct HASH_FUNCTION
    {
    
        U_Int32 
        operator()(const std::vector<double> vec) const
        {        
    
            U_Int32 ret = 0; 
            for(uint i = 0; i < vec.size(); i++)
                ret = (ret * 31) + hash_d(vec[i]);
    
            return ret;
        }
    
        inline U_Int32 
        hash_d(double x) const
        { 
            U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
            return *p ^ (*p >> 32); 
        }
    };
    
    class Hash
    {
    
        public:
            Hash();
    
            ~Hash();
    
            //Methods
    
            void        Insert_Hash_Data(const std::vector< double >& vec_key, 
                                         const std::vector< double >& A_hat_qr, 
                                         const std::vector< double >& tau,
                                         const std::vector< double >& m_k_hat, 
                                         const int unit_vec_size = -1, 
                                         const int unit_vec_row = -1);
    
            const       hash_map<std::vector< double >, HASH_DATA, HASH_FUNCTION>& Get_Hash_Map() const;
    
            const int   Get_Hash_Size();
    
        private:
            hash_map<std::vector<double>, HASH_DATA, HASH_FUNCTION> m_hash_map;
    };
    
    //========================
    void
    Hash::Insert_Hash_Data(const std::vector< double >& vec_key, 
                           const std::vector< double >& A_hat_qr, 
                           const std::vector< double >& tau,
                           const std::vector< double >& m_k_hat, 
                           const int unit_vec_size, 
                           const int unit_vec_row)
    {
        struct HASH_DATA hd;
        hd.A_hat_qr = A_hat_qr;
        hd.tau = tau;
        hd.m_k_hat = m_k_hat;
        hd.unit_vec_row = unit_vec_row;
        hd.unit_vec_size = unit_vec_size;   
        m_hash_map.insert(Hash_Pair(vec_key, hd));
    }
    
    const hash_map<std::vector<double>, HASH_DATA, HASH_FUNCTION>& 
    Hash::Get_Hash_Map() const
    {
        return m_hash_map;   
    }
    
    const int
    Hash::Get_Hash_Size()
    {
        return m_hash_map.size();    
    }
    

    vielleicht hat jemand eine Hilfestellung - ich arbeite daran 🙂

    Danke



  • sorry war doppelpost



  • operator()(const std::vector<double> vec) const
    

    soll sicherlich

    operator()(const std::vector<double>& vec) const
    

    heißen.

    und

    inline U_Int32 
        hash_d(double x) const
    

    bestimmt

    static inline U_Int32 
        hash_d(double x) const
    


  • jo...danke...werds ausbessern

    mein etwas schneller laufende variante jetzt die auf pointern beruht - zumindest hoffe ich das das so jetzt passt...ergebnisse stimmen...
    die aber immer noch meiner meinung nach zu langsam ist hat ca. 5% boost gebracht:
    EDIT!!!!: Ne sorry - der boost ist anscheinend grösser aber das gesamtergebnis ist nur um 5% schneller geworden....hmm. Vorhin frass die insert operation 40% der gesamtzeit - jetzt sind es nur noch 5 %. Also doch deutlicher wachstum 🙂

    //=========HEADER==========
    //hash_map is no C++ standard - 
    //so include the extensions due to gcc version
    #if __GNUC__ < 3
    #include <hash_map.h>
    #else
    #include <ext/hash_map>
    using __gnu_cxx::hash_map;
    #endif
    
    typedef unsigned int U_Int32;
    typedef unsigned long long U_Int64; 
    
    typedef std::pair<double*, size_t> Key_Pair;
    
    struct HASH_FUNCTION
    {
    
        U_Int32 
        operator()(const Key_Pair kp) const
        {        
    
            U_Int32 ret = 0;
            size_t dim = kp.second;
            const double* vec = kp.first;
            while(dim--)
            {
                ret = (ret * 31) + hash_d(*vec);
                vec++;
            } 
    
            return ret;
        }
    
        inline U_Int32 
        hash_d(double x) const
        { 
            U_Int64* p = reinterpret_cast< U_Int64* > (&x); 
            return *p ^ (*p >> 32); 
        }
    };
    
    struct HASH_DATA
    {
        double* A_hat_qr;
        double* tau;
        double* m_k_hat;
        int unit_vec_size;
        int unit_vec_row;   
    };
    
    typedef std::pair< Key_Pair, HASH_DATA> Hash_Pair;
    
    class Hash
    {
    
        public:
    
            Hash();
            ~Hash();
    
            void        Insert_Hash_Data(double* vec_key, 
                                         size_t size,
                                         double* A_hat_qr, 
                                         double* tau,
                                         double* m_k_hat, 
                                         const int unit_vec_size = -1, 
                                         const int unit_vec_row = -1);
    
            const       hash_map<Key_Pair, HASH_DATA, HASH_FUNCTION>& Get_Hash_Map() const;
    
            const int   Get_Hash_Size();
    
        private:
    
            hash_map<Key_Pair, HASH_DATA, HASH_FUNCTION> m_hash_map;
    };
    
    //===========================
    
    ....
    
    void
    Hash::Insert_Hash_Data(double* vec_key, 
                           size_t size,
                           double* A_hat_qr, 
                           double* tau,
                           double* m_k_hat, 
                           const int unit_vec_size, 
                           const int unit_vec_row)
    {
         struct HASH_DATA hd;
         hd.A_hat_qr = A_hat_qr;
         hd.tau = tau;
         hd.m_k_hat = m_k_hat;
         hd.unit_vec_row = unit_vec_row;
         hd.unit_vec_size = unit_vec_size;   
         m_hash_map.insert(Hash_Pair(Key_Pair(vec_key, size), hd));
    }
    
    ....
    


  • Naja....
    anscheinend findet er obwohl der key identisch ist nicht den entry in der hash_map...

    EDIT: scheiße....irgendwie wenn ich die pointer übergebe gehts also net...wenn ich den gleichen pointer übergebe dann schon....aber warum? der pointer zeigt doch einfach nur auf einen speicherbereich in dem dann die gleichen zahlen stehen - und der key ist ja derselbe....???

    folgendes habe ich als input :

    Hash h;
    
        double* A_hat = (double*)calloc(4, sizeof(double));
        A_hat[0] = 0.2;
        A_hat[1] = 0.5;
        A_hat[2] = 0.6;
        A_hat[3] = 0.44;
        double* tau = (double*)calloc(1, sizeof(double));
        tau[0] = 9.9;    
        double* m_k_hat = (double*)calloc(1, sizeof(double));
        m_k_hat[0] = 1.1;
    
        double* v = (double*)calloc(2, sizeof(double));
        v[0] = 1.44;
        v[1] = 1.1;
    
        size_t size = 2;
    
        h.Insert_Hash_Data(v, size, A_hat, tau, m_k_hat, 3,9);
    
        //h.Print_Specific_Hash_Data(Key_Pair(v, size));
        //h.Print_Full_Hash();
        std::cout << "Anzahl: " << h.Get_Hash_Size() << std::endl;
    
        hash_map<Key_Pair, HASH_DATA, HASH_FUNCTION>::const_iterator it;
    
        double* t = (double*)calloc(2, sizeof(double));
        t[0] = 1.44;
        t[1] = 1.1;
    
        size_t s = 2;
        Key_Pair kp(t, s);
    
        it = h.Get_Hash_Map().find(kp);
    
        if(it == h.Get_Hash_Map().end())
            std::cout << "nicht gefunden" << std::endl;
        else
            std::cout << "gefunden" << std::endl;
    

    da sollte er eigentlich gefunden ausgeben - die schlüssel sind absolut identisch also die Hash-funktion arbeitet korrekt ...nur warum läuft er über das element drüber? Kann es sein dass das Key_Pair probleme macht?



  • *grmpf....ich versteh das net....hat jemand ne Ahnung warum des so net richtig funzt?



  • Ich weiss, unter Linux debuggen ist Nicht Lustig (tm), aber kannst du mal durchsteppen und gucken wo etwas schief geht und was? Wäre wohl am einfachsten 😉



  • hmm...mal ne blöde frage jetzt...meinst du mim durchsteppen das durchsteppen der stl-extensions der hash_map.* oder was? Weil die find operation ist ja net mein code.....
    also nur nochmal kurz in diesem zusammenhang: wenn ich denselben pointer übergebe dann gehts - nur wenn ich einen anderen poitner der auf ein anderes array zeigt (was aber völlig identisch ist) - dann gehts eben net....vielleicht ist auch meine implemenierung einfach mist? Wenn jemand andere vorschläge hat - sehr gern - zumindest was die schlüsselstruktur betrifft.

    Danke



  • also jetzt werden die richtigen ergebnisse - zumindest mittels hash-funktion.

    Ich frage mich jetzt ob die daten die im hash drin sind so auch nicht überschrieben werden? Ich übergebe ja nur pointer in die funktion und speichere doch so nur die pointer in der hash-Map. wenn ich außerhalb dann die array verändere müssten sich nicht dann auch die daten in der map verändern? Weil drin sind ja nur pointer die auf das erste element zeigen? Wäre sehr nett wenn mir diesbezüglcih jemand helfen könnte....


Log in to reply