Stress für B-Baum

Ad aCTa

Hallo,
ich habe für einen B-Baum Suchen und Einfügen implementiert. Jetzt wollte ich den mal in eine Stress-Situation bringen, indem er 10000 Elemente speichern und durchsuchen soll. Dabei legt das Programm ein merkwürdiges Verhalten zu Tage. Wenn ich manche Elemente suchen will, z.B. 5892, scheitert er. Ich weiß, das ist echt viel RAM, der damit belegt wird, aber er müsste doch eine bad_alloc werfen, wenn er keinen Heap-Speicherplatz bekommt?!
Jetzt habe ich in der Schleife, in der ich im Baum jedes Element suche, Ausgaben hingestellt. Abgesehen davon, dass er mittendrin irgendwann abstürzt (sprich: Prozess reagiert nicht mehr), gibt er mir beim Durchlauf mit double-Werten immer nur jeden 4. Wert aus. z.B.:

std::cout << "Finden...";
for(double i = 0; i < 10000; i++) {
	if(!db.find(i))
		std::cerr << '\a';
	else
		std::cout << i << " da\n";
}

Ausgabe:

...
4096
4100
4104
4108
...

Ich hoffe, dass das nichts mit meinem Algorithmus zu tun hat, sondern nur mit der Hardware. Was konkret könnte da passieren?

Bashar

10000 Elemente sind jetzt nicht so wahnsinnig viel, hättest du 100000000 gesagt, aber so? Da wird wohl in deinem Algorithmus was nicht stimmen.

Ad aCTa

Ich habe es jetzt ein klitzekleines bisschen plattformabhängig gemacht:

tree<3, double, std::string> db;
std::cout << "Elemente werden eingefuegt..." << std::endl;
for(double i = 0; i < 40000; i++) {
	std::cout << i << std::endl;
	Sleep(1);
	db.insert(std::make_pair(i, "Database"));
}

std::cout << "Finden...";
for(double i = 0; i < 40000; i++) {
	Sleep(1);
	if(!db.find(i))
		std::cerr << '\a';
	else
		std::cout << i << " da\n";
}

In der Hoffnung, dass die CPU nur eine kleine Pause durch Sleep() braucht. Ich würde 10000 nicht unterschätzen: dazu gehören ja ein double-Wert, ein String, der intern den 9-Byte-große C-String hat; eine std::list, ein std::vector mal 10.000 plus einen Wert an 4-Byte-Zeigern, auch irgendwo in den hundertern/tausendern.
Die erste Schleife gibt hintereinanderweg die Zahlen von 0 - 39999 aus. In der cmd.exe kann ich die Ausgabe durch "Auswahl" auch kurz stoppen. In der zweiten Schleife kann ich das nicht, und die Double-Werte sehen so aus:

3er oder 4er-Schritte?! Dann bricht er irgendwann in der Schleife ab. (Diesmal bei 1718). Es kommt auch vor, dass er ganz durchkommt, am Ende dann aber einfach einfriert, wenn die letzte Zeile der main() erreicht wurde. Wahrscheinlich ist das deleten in den Destruktoren sehr aufwändig. Alles etwas mysteriös...

Edit: nehme ich beim Suchen das Sleep() raus, kommt ich sogar in höhere Gefile, ca. um 3000. Was ist da los? Kann das überhaupt mit meinem Algo zusammen hängen?

Bashar

Das mit dem '\a' seh ich jetzt erst. Piepst es denn jedesmal, wenn ein Element nicht gefunden wird? Das muss ja der Fall sein, wenn bei der Ausgabe in Dreierschritten vorgegangen wird. Wenn nein, würde ich tippen, dass dein Rechner mit dem Abspielen unhörbarer Piepstöne beschäftigt ist.

Ad aCTa

Allerdings, die Piepse sind unhörbar. Ich dachte, mit Sleep() hat er evtl. dafür Zeit. Naja, jetzt weiß ich, dass der Algorithmus irgendwo spinnen muss. Ab 28 Elementen fängt er an zu spinnen. Ich mach mich dann mal auf die Suche.

JaykopX

Hast du die Klasse tree selber geschrieben? Wie sieht die denn aus?
Ein double als Schleifenvariable sieht komisch aus, mach lieber ein int draus wenn es sowieso ganzzahlig ist. Es wird umgecastet falls nötig.

1. Die viererschritte sehen verdächtig nach Addresssrpüngen aus, könnte sein das du mit Pointer statt den tatsächlichen Werten arbeitest und der crash wegen unerlauben RAM zugriff auftaucht.

2. Taucht kein Crash auf sondern friert es einfach ein tippe ich auf eine Endlosschleife, die durch verändern von i in db.find(i) stattfinden(Was natürlich auf keinen fall passieren sollte!) -> Das kannst du überprüfen indem du das mal probierst:

std::cout << "Finden...";
for(unsigned int i = 0; i < 10000; i++) {
    //Kopieren der Schleifenvariable, um manipulation auszuschließen
    unsigned int tmp = i;
    if(!db.find(tmp))
        std::cerr << '\a';
    else
        std::cout << tmp << " da\n";
}

Insgesamt fehlt aber noch Quellcode von der tree Klasse um genaueres zu sagen.
Ob der wirklich auf dem Heap erstellt oder new zum reservieren von RAM verwendet kann man auch nicht erkennen.

EDIT: Hab den C/C++ Code tag gefunden. Ist jetzt alles bunt bunt....

Ad aCTa

Ich glaube das nicht. Ich bin meinen Algorithmus genauestens durchgegangen und habe den Übeltäter vmtl. gefunden. Die Klasse habe ich selber geschrieben.

Für die, die es interessieren sollte, was Ursache war: Beim Spalten eines vollen Nodes, der noch Childnodes besitzt, ist das Problem, dass die Childs nicht verteilt wurden. Demnach hatte der Node keine Children, die eigentlichen Children gehen verloren (Memory Leak), der Node ist offiziell Blattknoten (obwohl er ein innerer Node ist) und neue Elemente werden falsch inserted. Der Suchalgorithmus findet den Schlüssel dann nicht mehr. Ich muss jetzt also noch prüfen, ob der zu teilende Node Children hat, denn falls ja, muss ich diese auf die resultierenden beiden neuen Nodes verteilen. (Gratulation an die, die das jetzt verstanden haben. )

PS: Das ist mit Abstand das komplizierteste, was ich mit C++ je gemacht habe.

Ad aCTa

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

Ad aCTa

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?

otze

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

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Ad aCTa

> 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_back neu 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.

Bashar

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

Ad aCTa

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.

Ad aCTa

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.

Bashar

Hast du's mal mit einem Profiler versucht?

Ad aCTa

Hm... mit denen habe ich keine Erfahrnung. Kannst du mir einen empfehlen?