Stress für B-Baum

[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?

[Bashar]

Nö, aber für den Anfang reicht ja irgendeiner.

[Ad aCTa]

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.

[Bashar]

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.

[Ad aCTa]

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

[Bashar]

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.

[Ad aCTa]

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