Programm hängt sich in einer For-Schleife beim Erzeugen von Objekten auf.

[Die erinnerung]

Hallo.
Ich weiß, der Titel hört sich komisch an, aber das ist das Problem.
Ich erzeugen in einer For-Schleife Objekte, die ich in einer unordered_map speichere.
Bei genau 32.768 bleibt das Programm einige Sekunden stehen und bei 262.144 bleibt es vollständig hängen!

Mein Code: (Auf mehre Datein verteilt!)

main.cpp:

//Codeauschnitt: (wird aber ausgefürht!)
		World welt;

		for(int i = 0; i < 16777000; i++)
		{
			welt.add((Bit25) i);        //"Bit25" ist "std::bitset<25>"
		}
//Ende

World.cpp:

//Codeauschnitt: (das ist die Funktion, die aufgerufen wird)
void World::add(Bit25 pos)
{
	WorldIter it = Welt.find(pos);        //"WorldIter" ist "std::tr1::unordered_map<Bit25, Block_Container*>::iterator"

	if(it == Welt.end())
	{
		 World::Welt[pos] = new Block_Container(pos, (Bit20) 0, *this);
                 //"Bit20" ist "std::bitmap<20>"
                 //World::Welt ist vom Datentyp "std::tr1::unordered_map<Bit25, Block_Container*>"
	}
	else
	{
		throw(BF_Error(2)); //Fehlerfall (wird hier nicht aufgerufen!)
	}
}
//Ende

Block_Container.cpp:

//Codeauschnitt: (das ist der Konstruktor, der aufgerufen wird)
Block_Container::Block_Container(Bit25 pos, Bit20 data, World &welt)
{
	Block_Container::pos = pos;        //Datentyp "Bit25"

	Block_Container::data = data;      //Datentyp "Bit20"

	Block_Container::world = &welt;    //Datentyp "World*"
}
//Ende

Ich verstehe nicht, warum das Programm nicht weiterspeichert.

Bei Bedarf an mehr Code, einfach schreiben!

Ich muss korrigieren! Ein Freund sagte, dass das Programm nach 20 min weiter macht und dann zwischen 2.097.000 und 2.097.999 anhält. Ich vermute, jetzt müsste man noch länger warten und dann kommt nochmal viel weiter!

[knivil]

Was ist das: .. (Bit25) i .. Du castest einen Int nach einen zusammengesetzten typ? Oder std::bitmap, ich habe bis jetzt nur mit std::bitset gearbeitet.

[Die erinnerung]

Mein Fehler!!!!! Es ist nicht bit ** map **, sondern bit ** set **!!!

Ich korrigiere den Code

[Die erinnerung]

Wäre ein Möglichkeit, dass ich im Prinzip mehre unordered_map s anlege und die dann über eine Zentrale Klasse verwalte?

[cooky451]

Warum forderst du den BlockContainer mit new an? Scheint mir nicht so sinnvoll. Und wenn du mit .insert() arbeitest, kannst du am Rückgabewert feststellen ob überschrieben wurde oder nicht, das dürfte performanter sein. Und was dieser Cast von int nach bitset soll hast du auch noch nicht beantwortet.

[ScottZhang]

Vllt einfach ma abschätzen wieviel Speicher du da brauchst. vermutlich wird einfach nur heftig geswapt ?

[Die erinnerung]

Ich mache das mit new, weil die map als Datentyp Block_Container ** * **nimmt. Und das mit dem casten:

ganz einfach! Mein Key ist aus Speicherplatzgründen ein bitset und da ich bitsets nicht inkremetiren kann, caste ich einfach!

[cooky451]

Die erinnerung schrieb:

Ich mache das mit new, weil die map als Datentyp Block_Container ** * **nimmt.

Haha LOL, ja, super Begründung. Und warum machst du die map nicht zu einer unordered_map<Bit25, Block_Container>?

Die erinnerung schrieb:

ganz einfach! Mein Key ist aus Speicherplatzgründen ein bitset und da ich bitsets nicht inkremetiren kann, caste ich einfach!

bitset hat nicht umsonst to_ulong und Konstruktoren. Arbeite damit.

[RedPuma]

Kann es sein dass du irgendwo einen relativ aufwändigen Copy-Constructor hast welcher aufgerufen wird wenn der von der map reservierte Speicherplatz nicht mehr ausreicht und re-allokiert werden muss? Diese re-allokation ist der einzige Grund der mir einfällt damit die Ausführung bei bestimmten Grenzen auf einmal scheinbar anhält.

Noch eine Anmerkung: Ein Bitset mit 25 Elementen benötigt 4 Byte, da kannst du also genausogut einen unsigned int verwenden. Ein Computer kann nunmal nur Byteweise adressieren. Ein Bitset mit 20 Elementen benötigt 3 Byte, ich vermute aber mal das dein new Operator auf ein Alignment von 4 Byte eingestellt ist was deine Bitset-Speicherspaar-Idee komplett zunichte macht.

Und noch eine Anmerkung: warum benutzt du unordered_map? Wegen dem (ohnehin sinnlosen) Bitset eine Map zu benutzen ist die reinste Verschwendung. Erstell per new[] den ganzen Batzen an Blöcken, weise ihnen hinterher in ner Schleife ihre Position zu und benutz zur Adressierung der Blöcke einfache unsigned int. Das ist schätzungsweise 1000 mal schneller und benötigt im Endeffekt den selben Speicherplatz. Wenn du bei STL Typen bleiben willst dann benutze std::vector<Block_Container> Welt(16777000).

[Die erinnerung]

Einen solchen Konstruktor habe ich nicht (oder besser gesagt: nicht das ich wüsste). Aber wenn du das ansprichst: Kann man einer (unordered_)map im Vor-raus eine Größe zuweisen?

Der Grund warum ich eine (unordered_)map verwnde ist ganz einfach.
Ich möchte nicht jede Zahl von 0 bis ca. 16.777.000 belegen. Es sind lücken enthalten. Und der bitset als Key gibt die Position an!

[knivil]

Mein Key ist aus Speicherplatzgründen ein bitset und da ich bitsets nicht inkremetiren kann, caste ich einfach!

Das ist wahrscheinlich undefiniertes Verhalten.

Ich möchte nicht jede Zahl von 0 bis ca. 16.777.000 belegen. Es sind lücken enthalten. Und der bitset als Key gibt die Position an!

Und warum benutzt du keinen int? Was kann bitset<25>, was nicht genauso einfach mit Int erreicht wird? ... wenn du sowieso staendig castest.

[Die erinnerung]

Ich persönlich habe schon (sehr) viele schlechte erfahrungen gemacht, was Bitweise-manipulationen von int, short, long und char Werten. Deshalb bin ich (ursprünglich auch aus Speicherplatzgründen) auf Bitset umgestiegen, weil hier alles Funktioniert, so wie es sein sollte.

mit unsigned int und co habe ich nocht nicht gearbeitet (außer mit unsigned char. Da hat auch nichts geklappt!)

[pyhax]

Welche schlechte Erfahrungen hast du den mit bitweisen Manipulationen bei int, short, ... gemacht? Und std::bitset spart kein einziges Byte, denke ich. Das ist intern auch nur ein array von unsigned chars.
EDIT: Warum machst du bitweise Manipulationen auf den Ḱeys ein map Was soll das bringen?

[SeppJ]

pyhax schrieb:

Und std::bitset spart kein einziges Byte, denke ich. Das ist intern auch nur ein array von unsigned chars.

Auch wenn es vom Standard nicht erzwungen wird, so liegt die interne Datenspeicherung in einer gepackten Form a la vector<bool> aufgrund der bitset-Schnittstelle doch sehr nahe. Mindestens die GCC-Implementierung verwendet daher intern ein unsigned long Array (dessen Länge nur bei sehr vielen Bits größer als 1 wird). Bitset zu benutzen ist daher äquivalent zum Bits selber manipulieren^*, außer dass jemand anderes für einen schon die Fleißarbeit übernommen hat.

^*: Egal ob Bitset oder Eigenbau: Die Technik hat Vor- und Nachteile!

[pyhax]

SeppJ schrieb:

Mindestens die GCC-Implementierung verwendet daher intern ein unsigned long Array.

Das heißt, ein bitset hat mindestens die Größe (beim GCC) sizeof(unsigned long)?

[otze]

*weißt darauf hin, dass Vergrößern des Speicherbereichs in einer unordererd map im worst case O(n^2) ist und verzieht sich dann wieder aus dem Thread*

//edit http://www.youtube.com/watch?v=R2Cq3CLI6H8

[knivil]

Es gibt keine Garantien, aber ausprobieren kann das jeder selbst.

int main(int argc, char** argv) 
{
  std::bitset<1> bt;
  int t;

  std::cout << sizeof(bt) << "   " << sizeof(t) << std::endl;
}

[SeppJ]

pyhax schrieb:

Das heißt, ein bitset hat mindestens die Größe (beim GCC) sizeof(unsigned long)?

Zumindest auf meinem 64-Bit System. Die Kommentare im Quelltext deuten darauf hin, dass die natürliche Wortbreite des Prozessors benutzt wird (was irgendwie naheliegend ist), jedoch ist da andererseits das unsigned long fest eingebaut. Da müsste man mal mit einem 32-Bit System vergleichen.

[cooky451]

SeppJ schrieb:

unsigned long

unsigned long ist ja auch nur mindestens 32 bit breit, erst long long ist auch auf 32 bit Systemen 64 bit breit.

[Die erinnerung]

Zur Frage was bitweise manipulationen mit dem Key zu tun haben:

Der Key ist eine 3-dimensionale Koordinate, die aus x, y und z-Wert besteht. um Speicher zu sparen, komprimiere ich diese Informationen in einer Zahl, die als eindeutige Position dient. Damit ich aber aus den Koordinaten einen einzigen Wert machen kann, muss ich die Bitweise Manipulation anwenden. Denn ich schneide die einzel Koordinaten zurecht und verschiebe sie an die richtige Stelle.

x-Koordinate hat 9 Bit
y-Koordinate hat 9 Bit
z-Koordinate hat 7 Bit

===>

Eindeutige Position hat 25 Bit

Ursprünglich waren bei allen jeweils ein Bit mehr geplant, ist dann aber zu groß!

Ich werde mein problem jetzt ganz einfach lösen:

ich lege mir Überquadrate an, die eine gewisse Menge von Blöcken in sich tragen und die Welt verwaltet diese Überquadrate (Chunks) dann.

Vielen Dank für eure Hilfe!

Und vielen, vielen Dank an otze. ich hatte sowas schon vermutet, aber war mir nicht sicher!