3. Hashtable debuggen

Hashtable debuggen

  • E

    Hoi,
    meine Debugging-Skills sind recht bescheiden. Meistens benutze ich einen Debugger um mir einen Stacktrace bei Crashes anzeigen zu lassen. Viel Debugging mache ich mit der Methode Stringausgaben in den Quellcode einzufügen. Das wars irgendwie aber schon fast.

    Jetzt habe ich eine Hashtable programmiert und stehe vor einem mysteriösen Problem:

    int main()
{
    std::vector<std::string> words;
    std::ifstream in("wordsEn.txt");
    std::string curWord;
    while(in >> curWord)
        words.push_back(curWord);
    std::cout << words.size() << " words read\n";

    {
        StringHashtable<char, int> ht(0);
        for(std::string const& word : words)
            ht[word] = 1;

        std::cout << ht.size() << " pushed into StringHashtable\n";

        for(std::string const& word : words)
            if(!ht.contains(word))
                std::cout << word << " not in StringHashtable!\n";

        for(std::string const& word : words)
            if(ht[word] != 1)
                std::cout << word << " fail! (" << ht[word] << ") ";
        std::cout << std::endl;

        ht["octavo"] = 1;
        std::cout << "octavo in StringHashtable: " << (ht.contains("octavo") ? "yes" : "no") << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
        std::cout << "octavo: " << &ht["octavo"] << "(" << ht["octavo"] << ")" << std::endl;
    }
}

    Zuerst erzeuge ich bei meinem Test für jedes englische Wort einen Eintrag und mappe ihn auf 1. Dann überprüfe ich bei jedem Eintrag ob er vorhanden ist. Bei der Überprüfung ob auch jeder Eintrag auf 1 gemappt ist fällt nur "octavo" durch - die anderen 109581 Einträge sind korrekt. Setze ich "octavo" nachträglich auf 1 dann stimmt alles:

    109582 words read
    109582 pushed into StringHashtable
    octavo not in StringHashtable!
    octavo fail! (0)
    octavo in StringHashtable: yes
    octavo: 0x1100750(1)
    octavo: 0x1100750(1)
    octavo: 0x1100750(1)
    octavo: 0x1100750(1)
    octavo: 0x1100750(1)

    Wie debugge ich das am Besten? Aus irgendeinem Grund scheint "octavo" beim Füllen der Hashtable mal gelöscht zu werden, ich kann mir aber nicht erklären warum.

    Hier ist der Quellcode falls es jemanden interessiert: http://pastebin.com/30FhSFzX
    Recht hacky aber ich bin dabei etwas hinzufrickeln was für mein Einsatzgebiet maximal optimiert ist und was ich individuell verändern kann.

    Danke & Grüße,
    Ethon

    0
  • ?

    Müsstest du nach einem rehash nicht den Bucket-Index neu ausrechnen?

    template<bool Rehash = true>
    void insertEntry(Entry* entry, size_t bucketIndex)
    {
        if(Rehash && float(_size) / bucketCount() > detail::HASHTABLE_MAX_LOADFACTOR)
            rehash();

        if(!_buckets[bucketIndex])
        {
            _buckets[bucketIndex] = entry;
            _buckets[bucketIndex]->next = nullptr;
        }
        else
        {
            Entry* old = _buckets[bucketIndex];
            _buckets[bucketIndex] = entry;
            _buckets[bucketIndex]->next = old;
        }
        ++_size;
    }
    0
  • E

    Volltreffer! Kann garnicht in Worte fassen wie dankbar ich dir bin, hab mir schon fast jedes Haar ausgerupft! 👍 👍 👍 🙂

    0
  • E

    So, ich hätte mal noch ein paar theoretische Fragen nachdem schon ein Thread da ist. 🙂
    Vorneweg, der aktuelle Code etwas aufgeräumter: http://pastebin.com/xj3chfpc

    Ich teste den Code mit einer Wörterliste die knapp 4,5 Millionen Wörter enthält und ziehe einen Vergleich zwischen einer Lösung die Malloc für jede Allokation verwendet, einer Lösung die eine Arena verwendet und einer klassischen unordered_map<string, int>.

    Zum Glück war der Arbeitsaufwand nicht ganz umsonst, die unordered_map braucht 1600ms um die Hashtable aufzubauen, meine Implementierung mit malloc 1300ms und mit der Arena 1100ms. Frage #1: Gibt es noch irgendwelche Optimierungstricks als die Hashtable einfach als array von linked lists zu implementieren und den Hash per Modulo darauf zu mappen?

    Was ich jetzt interessant finde: Die Überprüfung ob alle Wörter in der Hashtable sind dauert bei meinen Implementierungen etwas über 400ms, bei der unordered_map aber über 1000ms! Frage #2: Hat jemand eine Erklärung warum count bei der unordered_map so viel langsamer ist als bei meiner Implementierung?
    (gcc-Version 4.8.3 20140624 (Red Hat 4.8.3-1) (GCC))

    Zu guter letzt: Wie ist es zu erklären dass meine Implementierung mit malloc 452MB Heapspeicher insgesamt benötigt und die unordered_map nur 444MB ?
    Ich wäre davon ausgegangen dass ich da weniger benötige da a.) nur eine Allokation pro Eintrag und b.) die Allokationen kleiner sind da kein Speicher verschenkt wird. (Edit: Ah jo, vermutlich bin ich vor dem Ende nochmal gewachsen und unordered_map nicht da andere Primzahlen)

    Danke & Grüße,
    Ethon

    0
  • ?

    Ist das nicht ein bisschen unfair, wenn du fnv1a verwendest und unordered_map den default-hash?

    Was noch optimiert werden könnte ist, den Hash zu cachen:

    struct Entry
{
    std::size_t hash = fnv1a<std::size_t>(data, data + keyLength * sizeof(CharT));
    std::size_t keyLength;
    Entry* next;
    ValueT value;
    CharT key[1];
};

    Das macht einerseits das rehash() schneller, viel wichtiger ist aber, dass der Vergleich in der verlinkten Liste schneller wird, weil du statt std::memcmp aufzurufen einfach die beiden Hashes vergleichen kannst.

    Ansonsten am besten ein vollständig lauffähiges Vergleichsprogramm posten.

    0
Anmelden zum Antworten