Stress für B-Baum
-
So, ich habe den B-Baum nun fertiggestellt und ausgiebig getestet (mit 5.000.000 Elementen erfolgreich). Jetzt habe ich ein anderes Problem: die Geschwindigkeit. Der Suchalgorithmus ist wirklich sehr schnell, aber das Inserten von 100.000 Elementen dauert 10-12 Sekunden. Ich habe bzgl. der Optimierung noch kaum Ahnung, bin jetzt aber so vorgegangen:
Ich schaute, was so jeder einzelne Insert an Zeit frisst.
Ergebnis:
Die meisten Inserts dauerten 0ms. Es sind insgesamt jedoch immer ca. 11 Sekunden. Um die 750 Einzelfälle dauert ein Insert von 14 - 16ms. Die Summe dieser Einzelfälle ist tatsächlich die gesamte Insert-Laufzeit. Ich lasse mir anschließend aus der Schleife die Werte ausgeben, wo die Laufzeit nicht 0ms betrug.
Die ausgegebenen Werte finde ich interessant. Sie sind jedesmal andere, aber meistens durch 3 teilbar, und wenn nicht, sind sie nur +/- 1 entfernt. 3 war auch die Ordnung des Baumes. Zufall? Ich bild mir da bestimmt nur was ein...DWORD total = 0; std::vector<DWORD> notnull; std::vector<double> pos; for(double i = 0; i < 100000; i++) { DWORD begin = GetTickCount(); db.insert(std::make_pair(i, "Database")); DWORD end = GetTickCount(); total += end - begin; if(end - begin != 0) { notnull.push_back(end - begin); pos.push_back(i); } } std::cout << "Total: " << total << std::endl; std::cout << notnull.size() << " von 100000 Insertions dauerten laenger als 0ms." << std::endl; std::cout << "Durchschnittlich brauchten diese Insertions je " << std::accumulate(notnull.begin(), notnull.end(), 0) / notnull.size() << "ms, zusammen: " << std::accumulate(notnull.begin(), notnull.end(), 0) << "ms." << std::endl; std::cout << "Auswahl an Positionen der langsamen Insertions:" << std::endl; for(std::size_t n = 0; n < notnull.size() / 3; n++) std::cout << pos[n] << std::endl;Ich weiß nur nicht, wo ich am Algorithmus nun optimieren könnte. Anhand der Zahlen erkenne ich (noch) kein konsistentes Muster, worauf ich schließen könnte. Das ist bestimmt nur hardwareabhängiges Zeug, worauf ich mir hier einen Reim machen will. Wie kann ich Engpässe in meinem Algorithmus finden?
-
sag mal du baust da einen ganz normalen b-tree, kann der nicht iwie ausarten also ich meine das du am ende eine linked list hast, und dir im schlimmsten fall 100.000 knoten anschauen mußt bis du deine einfüge stelle gefunden hast? auch wenn da das einfügen nicht schneller ist, so ist bei einem avl-tree die höhe auf 1,44*log2(n) limitiert, wär doch mal ein versuch wert, oder einen red-black tree der hat auch eine maximale höhe von 2*log2(n) und ist beim einfügen etwas schneller
lg lolo
-
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden. Das Balancieren erfolgt schon beim Inserten. Der allgemeine Algorithmus des B-Trees ist ja vollkommen in Ordnung, nur habe ich bestimmt bei der Umsetzung irgendwas verbasselt oder schlecht umgesetzt. Ich meine, der binäre Baum der std::map ist um Längen schneller beim Inserten, ich würde gerne den Flaschenhals in meinem Code finden, weiß aber nicht, wie ich beim Suchen von sowas anfangen soll. Diese 80-20-Regel würde ich da gerne mal anwenden, nur, wie finde ich diese 20% Code, die 80% der Laufzeit fressen?
-
du hast mal von nem Vektor geredet. schau mal, ob dir der nicht voll läuft und er dann auf einmal deine ganze schöne Struktur umkopiert...
-
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Ad aCTa schrieb:
der binäre Baum der std::map ist um Längen schneller beim Inserten
das ist auch kein std. binary tree
stl map schrieb:
Implemented using a self-balancing binary search tree.
also eher rb oder avl tree
-
-
> du hast mal von nem Vektor geredet.
Jap, der genannte Vektor beinhaltet die Zeiger zu den Childnodes.
> schau mal, ob dir der nicht voll läuft und er dann auf einmal deine ganze schöne Struktur umkopiert...
Wie kann ich das verstehen? Bisher habe ich die Elemente, die ich anfüge, immer mit
push_backneu alloziiert. An sich habe ich nur 2 Stellen im Code, an denen ich den Vektor beeinflusse:// Diese Stelle entscheidet, ob beim Teilen eines Knotens der zu teilende Knoten selber Children hat. Die müssen dann auf die neuen beiden Teilnodes verteilt werden. /* Simuliertes Beispiel: Baum der Ordnung 2, Node voll bei 2*2-1 = 3 Schlüsseln: 2 5 <---------- Ich befinde mich in diesem Knoten und sehe: / | \ | / | \ | \ \|/ 7 9 11 <---------- voll, muss geteilt werden und Children / | | \ müssen verteilt werden, denn Knoten hat / | | \ auch noch Childnodes 6 8 10 12 14 2 5 9 / | | \ | \ 7 11 /\ / \ 6 8 10 12 14 */ //children ist der Vektor mit Zeigern auf Kindknoten // left und right sind die neuen Teilnodes, auf die die Zeiger nun verteilt werden if(children[position]->children.size() > 0) for(unsigned i = 0; i < children[position]->children.size(); i++) { if(i < order) left->children.push_back(children[position]->children[i]); else right->children.push_back(children[position]->children[i]); }Voller als 2 * Ordnung wird der Vektor nicht. Die Reihenfolge behalte ich ja eigentlich auch immer bei.
-
noobLolo schrieb:
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Dann wartet http://de.wikipedia.org/wiki/B-Baum auf deine Korrektur:
-
Bashar schrieb:
noobLolo schrieb:
Ad aCTa schrieb:
Der B-Baum ist immer balanciert und kann nicht (wirklich nie) zur Liste werden.
ein normaler b-tree ist nicht balanciert...
Dann wartet http://de.wikipedia.org/wiki/B-Baum auf deine Korrektur:
sry dachte das b-tree steht als abkürzung für einen binary-tree
-
wikipedia schrieb:
Die häufigste Interpretation ist, dass B für balanciert steht. Weitere Interpretationen sind B für Bayer, Barbara (nach seiner Frau), Broad, Bushy, oder Boeing, da Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat.
-
So, ich habe mir das noch mal mit 1000 Elementen bei einer std::map angeschaut. Die Map brauchte 1mal 15ms. Diese Zahl kommt mir verdächtig vor, könnte das nicht die Zeit sein, die der Scheduler vom OS mein Programm warten lässt? Wenn dem so ist, dann brauchen meine Insertions einfach ingesamt länger, und umso mehr Takte ich benötige, desto mehr Wartezeiten bekommt mein Programm.
Toll, das war jetzt ein Schuss für den Ofen, jetzt weiß ich das, was ich vorher wusste: mein Insert ist langsam.
Weiß jemand, wie ich den Flaschenhals in einem Code finden kann? Es sind ca. 100 Zeilen.
-
Hast du's mal mit einem Profiler versucht?
-
Hm... mit denen habe ich keine Erfahrnung. Kannst du mir einen empfehlen?
-
Nö, aber für den Anfang reicht ja irgendeiner.
-
Ich habe mir jetzt mal einen gesucht, der sehr schön mit meiner IDE arbeiten kann. Ganz nette Sache, er zeigt mir also an, wie oft welche Funktionen aufgerufen wurden. Er sagt mir, dass insert() oft aufgerufen wurde. Schön, das weiß ich schon. Aber richtig Auskunft kann er mir nicht geben. Ohne jetzt genau den Algorithmus verstehen zu müssen, sieht jemand in diesem Code irgendeine Art "no-go"?
template <unsigned order, typename key_t, typename payload_t, typename compare_t, typename allocator_t> std::pair<typename node<order, key_t, payload_t, compare_t, allocator_t>::iterator, bool> node<order, key_t, payload_t, compare_t, allocator_t>::insert(const std::pair<key_t, payload_t>& dp) { // greater_equal, smaller_equal search: typename std::list<pointer>::iterator key = std::find_if(payload.begin(), payload.end(), bind2nd(compare_t(), dp.first)); if(!children.empty()) { // it's an inner node if(key != payload.end()) { // there is a key with those condition if((*key)->first != dp.first) { // key is not equal to the needle typename std::list<pointer>::difference_type position = std::distance(payload.begin(), key); // is the child candidate full? if(children[position]->payload.size() == 2 * order - 1) { position = split(dp, position); // then split it and get new position to search } return children[position]->insert(dp); // map position on childnodes and search in subtree } else return std::make_pair(iterator(this, key), false); // found in inner node } else {// there is not such a position if(children.back()->payload.size() == 2 * order - 1) { // is the node full? typename std::list<pointer>::difference_type position = payload.size(); position = split(dp, position); // split it and return new position to continue searching return children[position]->insert(dp); } return children.back()->insert(dp); // the very right subtree may contain the key } } else { if(key == payload.end() || (*key)->first != dp.first) { // key does not exist or is too big --> we can insert pointer n = allocate(1); construct(n, dp); std::list<pointer>::iterator pos = payload.insert(payload.end(), n); // insert at the end payload.sort(cmp()); // sort the payload list return std::make_pair(iterator(this, pos), true); } else return std::make_pair(iterator(this, key), false); // found in leave node } }Nur von Seiten der Performance. Ich habe den Algorithmus einfach mal umgesetzt, und wüsste nicht, wie ich das ummodeln sollte, damit es schneller wird.
-
Ad aCTa schrieb:
Ich habe mir jetzt mal einen gesucht, der sehr schön mit meiner IDE arbeiten kann. Ganz nette Sache, er zeigt mir also an, wie oft welche Funktionen aufgerufen wurden. Er sagt mir, dass insert() oft aufgerufen wurde.
Eigentlich sollte er auch anzeigen, welche Anweisung wie oft durchlaufen wurde und wieviel Zeit darin verbracht wurde.
Schön, das weiß ich schon. Aber richtig Auskunft kann er mir nicht geben. Ohne jetzt genau den Algorithmus verstehen zu müssen, sieht jemand in diesem Code irgendeine Art "no-go"?
Naja no-go vielleicht nicht, aber ein paar Sachen fallen mir schon auf.
- Warum eine Liste und kein Vektor?
- Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
- Du fügst unten einfach mal ein und sortierst die Liste dann. Zum Einfügen in eine sortierte Liste gibt's aber effizientere Verfahren.Ich muss aber zugeben, dass ich den Code nur kurz überflogen habe.
-
> - Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
Weil diese Objekte von einem Allokator kommen. Der gibt mir nur Pointer.
> Warum eine Liste und kein Vektor?
> Du fügst unten einfach mal ein und sortierst die Liste dann. Zum Einfügen in eine sortierte Liste gibt's aber effizientere Verfahren.Ich hab da lange rumüberlegt. Ich wollte gerne einen Container haben, bei dem Einfügen in der Mitte günstig ist, am besten gleich sortierend einfügt. Ich verstehe nicht, warum es in der Standardbibliothek nicht eine automatisch sortierende Liste gibt, der einzige Container, der das kann ist std::set. Außerdem fand ich die splice()-Methode recht nett auf mein Problem zugeschnitten, die Liste zu teilen und automatisch zu löschen. Zuletzt hielt ich list::sort() dem std::sort für überlegen, in der Hoffnung, dort am meisten Performance raus zu holen. Dem ist scheinbar nicht so.
Zugegeben, was gescheites, wie man auf n Elemente n + 1 andere draufmappen kann, ist mir noch nicht eingefallen. Bis jetzt taten es vector und list.
-
Ad aCTa schrieb:
> - Wenn schon Liste, warum enthält sie dann Pointer und nicht Objekte?
Weil diese Objekte von einem Allokator kommen. Der gibt mir nur Pointer.
Ich kenn mich mit Allokatoren nicht aus, aber warum ist das so? Die STL-Container arbeiten mit dem Standard-Allokator-Interface und enthalten Objekte.
-
> Die STL-Container arbeiten mit dem Standard-Allokator-Interface und enthalten Objekte.
Ne, das glaub ich nicht. Schließlich werden ja die Elemente, die du in einen Container packst, kopiert. Der Allokator ist eigentlich nur das:
T* memory = allocator.allocate(1); allocator.construct(memory, T()); // ... allocator.destroy(memory); allocator.deallocate(memory);z.B. ein malloc() mit einem placement-new.
Bzgl. dieser Vektor-Liste-Angelegenheit: Vielleicht regele ich es einfach so, dass es einen Payload-Typen gibt, der immer einen Zeiger auf den Nächsten Node hat. Dieser Payload-Typ kommt in einen Vektor. Das allererste Element hat zwar einen Next-Zeiger, ist aber sonst leer. Dann muss ich vielleicht nicht mehr so mit diesen 2 Vektoren/Listen rumhantieren.