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

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

[cooky451]

@Die erinnerung
Und 8bit/8bit/8bit wäre nicht gelaufen? ^^
Wie auch immer, wenn die Welt nur halbwegs gefüllt ist, ist das eine Blöde Idee. Rechne mal nach, wie viel Platz du bei einer halbgefüllten Welt brauchst, die 128x128x128 Einheiten groß ist:
Keys: 25 * 128 * 128 * 128 / 2 / 8: 3276800 byte
Values (1 byte / Wert): 128 * 128 * 128 / 2: 1048576 byte
Machen zusammen 4325376 byte.

Ok, jetzt führen wir mal einen "Nix" Block ein, und speichern die Blockpositionen implizit durch den Index:
Values (1 byte / Wert): 128 * 128 * 128: 2097152 byte

Oh, hm. Ist ja viel weniger Speicher. Und zwar viel viel weniger. Denn man braucht keine Pointer mehr. Und den Overhead durch Bitgefrickel kann man jetzt auch vergessen.

Du siehst, manchmal lohnt es, einfach das Problem zu beschreiben.

[Die erinnerung]

Ich verstehe deine Rechnung nicht.

Wenn ein Block nicht vorhanden ist, dann verbraucht der kein Speicherplatz. Das einzige was bei einer vollkommen leeren Welt noch Speicherplatz braucht, ist sind die Übercontainer und das ist nicht viel.

Ich glaube du hast in deienr Rechnung vergessen, dass der Index in einem Container auch Speicherplatz braucht.

Und zur Frage was meine schlechten Erfahrung mit int und co sind:

Ich hatte schon einige Projekte bei denen ich mit bitweise Manipulationen arbeiten musste. Bei allen haben sich binäre Fehler eingeschlichen!!!

Ein Bespiel:

Ich wollte das ganze ursprünglich mit einem char-Array machen.

Beispiel (frei Erfunden das Problem ist aber real!):
Ich hatte zwei Werte. Einer 9 Bit der andere 7 Bit.

Beispeil:

000010110 0001011
im Char Array:
00001011 00001011

Wenn ich aber das haben
000110111 0011011
dann ist mein Chr array:
11111011 11111011

Und das ist falsch!

Mit bitset funktiniert das Fehlerfrei!