std::map build - Warum dauert das so lange?

happystudent

Hallo,

ich verwende in einem meiner Projekte eine std::map welche ich zum Programmstart mit einigen Werten vorinitialisieren will. Bei sehr wenigen Werten ist das auch kein Problem.

Wenn ich allerdings mehrere Werte hinzufügen will habe ich das Gefühl dass die Compile-Zeit exponentiell (oder zumindest super-linear) ansteigt was ich mir nicht erklären kann. Besonders im Release-Mode dauert so ein Build bereits bei relativ wenig Werten ewig.

Anbei ein vollständiges Minimalbeispiel welches das Problem verdeutlicht:

#include <iostream>
#include <string>
#include <map>

struct Data
{
	Data() {};
	Data(int number_, std::string text1_, std::string text2_) : number(number_), text1(text1_), text2(text2_) {};

	std::string text1;
	std::string text2;
	int number;
};

int _tmain(int argc, _TCHAR* argv[])
{
	std::map<std::string, Data> my_map;

	// Um diese Zeile geht es
	my_map["mein test-string-key"] = Data(1, "mein erster test string, noch kurz", "mein zweiter test string, schon länger aber immer noch nicht extrem lang");
}

Obiger Code alleine macht noch keinerlei Probleme. Vervielfältige ich jetzt aber die Zeile mit der Zuweisung von my_map, dann steigt die Compile-Zeit im Release-Modus extrem an. Ich hab hier mal ein paar Tests gemacht (unter Visual Studio 2010 und 2013, jeweils kein nennenswerter Unterschied):

// 200 Zeilen:	2 Sekunden
// 500 Zeilen:	8 Sekunden
// 1000 Zeilen: 50 Sekunden
// 2000 Zeilen: 6 Minuten
// 4000 Zeilen: 42 Minuten

Dabei heißt "200 Zeilen" dass die obige Zeile mit der Zuweisung 200 mal kopiert wurde, also eine Initialisierung der map mit 200 Werten simuliert. Bereits ab einer sehr geringen Zahl von nur 1000 Zeilen benötigt die Code-Generierung bereits 50 Sekunden. Bei 4000 Zeilen sind es bereits 42 Minuten(!!!).

Jemand eine Idee woran das liegt? Unter diesen Vorraussetzungen ist effektives Arbeiten qausi nicht möglich

Oder mache ich irgendwo einen kapitalen Fehler?

volkard

happystudent schrieb:

Jemand eine Idee woran das liegt? Unter diesen Vorraussetzungen ist effektives Arbeiten qausi nicht möglich

4000 Befehle in einer Funktion müssen halt bestraft werden.

Ist es schneller, wenn Du eine Schleife bis 4000 laufen läßt?

MFK

happystudent schrieb:

Bei 4000 Zeilen sind es bereits 42 Minuten(!!!).

Kann ich nicht reproduzieren. Mit Visual C++ 2010 und 2012 dauern 4000 Zeilen nur wenige Sekunden.

Vielleicht läuft da ein Plug-In Amok?

happystudent

volkard schrieb:

4000 Befehle in einer Funktion müssen halt bestraft werden.

Aber wie soll ich die map denn sonst initialisieren können? 4000 Befehle find ich jetzt auch nicht viel um ehrlich zu sein...

volkard schrieb:

Ist es schneller, wenn Du eine Schleife bis 4000 laufen läßt?

Ja, dann läuft der Build-Vorgang innerhalb Sekundenbruchteilen, selbst wenn ich noch viel mehr Einträge erstelle. Problem ist aber dass ich keine Schleife verwenden kann, da die Einträge individuell und einzigartig sind.

MFK schrieb:

Kann ich nicht reproduzieren. Mit Visual C++ 2010 und 2012 dauern 4000 Zeilen nur wenige Sekunden.

Vielleicht läuft da ein Plug-In Amok?

Hm das ist seltsam. Habs extra an zwei komplett verschiedenen Rechnern getestet, auf beiden tritt das Problem auf...

volkard

happystudent schrieb:

volkard schrieb:

4000 Befehle in einer Funktion müssen halt bestraft werden.

Aber wie soll ich die map denn sonst initialisieren können? 4000 Befehle find ich jetzt auch nicht viel um ehrlich zu sein...

Array!

hustbaer

@happystudent
Der Optimizer versucht die ganze Funktion zu optimieren.
Wenn die 1000 Zeilen hat, von der jede Zeile ein Template instanziert, und die aufgerufenen Funktionen eindeutig Inlining-Kandidaten sind...
Der Compiler hat da einfach viel zu viele Möglichkeiten wie er optimieren könnte. z.B. den Aufruf in der ersten Zeile inlinen, den in der zweiten nicht usw. - macht theoretisch 2^N Möglichkeiten (und das nur für eine der vielen Optimierungen die er machen kann).
Die kann er natürlich bei N=1000 sowieso nicht alle untersuchen -- aber dass er sich mehr Zeit lässt je grösser die Funktion ist, finde ich nicht wirklich verwunderlich.

=> Dauert halt.

Und?
1000 solche Zeilen brauchst du netmal in generiertem Code. Generier dir ein static const Array wo die Daten drin sind und loop' da drüber.

Bzw. wenns anders nicht geht, dann pack ein #pragma optimize() drumrum, mit dem du lokal die Optimierungen deaktivierst.

MFK

happystudent schrieb:

Hm das ist seltsam. Habs extra an zwei komplett verschiedenen Rechnern getestet, auf beiden tritt das Problem auf...

Es tritt nur auf, wenn Optimierungen eingeschaltet sind.

Daher: Siehe hustbaer. Füll deine Map aus einem Array.

happystudent

Ok, habs jetzt mit einem Array versucht. Damit geht es jetzt, Build-Zeit sind damit 25 Sekunden. Ist zwar immernoch recht viel aber erträglich, da man ja nicht so oft Release-Build macht.

Danke auf jeden Fall

JulianH

Und bitte übergebe Referenzen.

happystudent

Mr.Long schrieb:

Und bitte übergebe Referenzen.

Wo meinst du jetzt, im Konstruktor? Die strings müssen da doch eh kopiert werden, ist dass da nicht egal?

Hab übrigens ein neues Problem mit der Array Technik. Und zwar ist folgendes extrem nervig:

struct Data
{
	Data() {};
	Data(int number_, std::string text1_, std::string text2_) : number(number_), text1(text1_), text2(text2_) {};

	std::string text1;
	std::string text2;
	int number;
};

// Daten Array mit den 4000 Einträgen
const int DATA_SIZE = 2;
Data const data_array[] = { Data(0, "kurzer test string", "langer test string"),
							Data(0, "kurzer test string", "langer test string") };

int _tmain(int argc, _TCHAR* argv[])
{

	std::map<std::string, Data> my_map;

	for (unsigned int i = 0; i < DATA_SIZE; i++) {
		my_map["?"] = data_array[i]; // <- Wie komm ich jetzt hier an den zugehörigen key?
	}

	return 0;
}

Zwar kann ich meine Daten jetzt in das const array reinschmeissen, allerdings hab ich dann ja nicht den benötigten key für die map zur Verfügung, da der Schlüssel nicht in der struct Data gespeichert werden soll.

Einzige Lösung die mir bis jetzt einfällt um das zu lösen wäre ein zweites Array mit den keys mitzuschleifen. Das ist aber extrem nervig, da die Übersicht dann noch mehr leidet. Vor allem wenn man dann mal eine Zeile löschen/hinzufügen will muss man dann genau aufpassen dass man das alles manuell richtig macht.

Daher ist ein zweites array wohl keine gute Lösung. Wie könnte man das sonst machen? Muss ja irgendwie möglich sein eine map vernünftig und ohne massiven manuellen Aufwand zu initialisieren?

Da hätte ich auch gleich noch eine Frage. Die lange Build-Zeit bei Initialisierung ohne array resultiert wohl aus den 4000 Konstruktor-Aufrufen in der Funktion. Wenn ich keine eigene Datenstruktur einfüge sondern direkt strings ist die Build-Zeit sehr kurz - was macht die std::string Klasse hier anders dass deren Konstruktoren soviel effektiver gebuildet werden können?

hustbaer

std::pair<std::string, Data> const data_array[] = {
    std::pair<std::string, Data>("key1", Data(0, "kurzer test string", "langer test string")),
    std::pair<std::string, Data>("key2", Data(0, "kurzer test string", "langer test string")),
    // ...
    }; 

size_t const data_size = sizeof(data_array)/sizeof(data_array[0]);

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    std::map<std::string, Data> my_map(&data_array[0], &data_array[data_size]); // <- Das wäre eine Möglichkeit
    return 0; 
}

// oder gleich so -----------------------V
std::map<std::string, Data> const my_global_map(&data_array[0], &data_array[data_size]);

Martin Richter

Und warum soll das schneller sein. Ich finde es aleine schon problematisch wieviele Allocationen hier durchgeführt werden müssen.
Bei Programmstart, dann nochmal muss das ganze Zeugs kopiert werden...

Nimm z.B. Smart-Pointer und lass die Daten nur einmal erzeugen, was natürlich einen weitere indirekten Zugriff bedeutet, aber damit würden die Objekte nicht kopiert. Oder wenn das statisch ist arbeite mit const Zeigern.

Wie oft ändern sich denn die Einträge in die Maß?

Wenn das relativ statisch ist, dann könnte man das Befüllen der Map auch in eine eigene Objektdatei packen und die nicht bei jeder kleinen Änderung am eigentlichen Programm neu kompiliert werden müsste.

hustbaer

Martin Richter schrieb:

Und warum soll das schneller sein.

Was ist in letzter Zeit immer mit den unpassenden "warum soll das {xxx} sein" Fragen
Ich hab' nie behauptet dass es "schneller" sein soll (schneller als was übrigens?).

Die Frage war

happystudent schrieb:

Zwar kann ich meine Daten jetzt in das const array reinschmeissen, allerdings hab ich dann ja nicht den benötigten key für die map zur Verfügung, da der Schlüssel nicht in der struct Data gespeichert werden soll.

Einzige Lösung die mir bis jetzt einfällt um das zu lösen wäre ein zweites Array mit den keys mitzuschleifen. Das ist aber extrem nervig, da die Übersicht dann noch mehr leidet. Vor allem wenn man dann mal eine Zeile löschen/hinzufügen will muss man dann genau aufpassen dass man das alles manuell richtig macht.

Daher ist ein zweites array wohl keine gute Lösung. Wie könnte man das sonst machen? Muss ja irgendwie möglich sein eine map vernünftig und ohne massiven manuellen Aufwand zu initialisieren?

happystudent

hustbaer schrieb:

std::map<std::string, Data> my_map(&data_array[0], &data_array[data_size]); // <- Das wäre eine Möglichkeit

Ah, das ist schon viel besser

Morle schrieb:

Wie oft ändern sich denn die Einträge in die Maß?

Wenn das relativ statisch ist, dann könnte man das Befüllen der Map auch in eine eigene Objektdatei packen und die nicht bei jeder kleinen Änderung am eigentlichen Programm neu kompiliert werden müsste.

Die Einträge ändern sich eigentlich ziemlich selten. Macht es dann einen Unterschied ob man eine fertig kompilierte .cpp Datei hat (die ja beim kompilieren dann auch nicht mehr angefasst wird) oder eine eigene Objektdatei?

Martin Richter schrieb:

Und warum soll das schneller sein. Ich finde es aleine schon problematisch wieviele Allocationen hier durchgeführt werden müssen.
Bei Programmstart, dann nochmal muss das ganze Zeugs kopiert werden...

Ist der Compiler nicht schlau genug das selbst zu checken? Weil das Daten-Array würde ich nur lokal in der Funktion befüllen, die dann auch die map befüllt.

EDIT: Hm, nach dem Verlagern der Initialisierung in eine eigene Funktion erhalte ich einen Stack-Overflow... Wenn ich das array global deklariere allerdings nicht. Wie kann das jetzt sein, ich will das Daten-Array ja nicht die Ganze Zeit im Speicher mitschleifen, daher würde ich es gerne lokal in einer extra Funktion haben dass es nach befüllen der map wieder freigegeben werden kann...

Martin Richter

Dein lokaler Heap ist eben begrenzt. Und Du schleppst dennoch den Code und den Speicher mit Dir rum. Spätestens in der EXE...

happystudent

Ok, und was mache dann jetzt am besten? Kann ja nicht sein dass es so kompliziert ist eine map effizient zu befüllen...

Martin Richter

Nimm einen Statischen Array als POD.
Verwende in der MAP nur const Zeiger auf diesen Array.

SideWinder

...oder lies den Kram aus einer Datei ein. Kann ja nicht sein, dass diese 4000 Key-Value-Pairs so statisch sind, dass sie unbedingt in der exe sein müssen.

MfG SideWinder