Schneller speichern und laden

SeppJ

Hast du eigentlich auch mal dein ursprüngliches Programm mit Optimierungen ausprobiert? Ich kann mir nämlich nicht vorstellen, dass put an sich so furchtbar langsam ist.

headmyshoulder

Die erinnerung schrieb:

ich will ja auch nicht nach jedem byte flushen, aber wie mache ich das am besten?

Edit:

Kleiner Fortschritt: Nur noch 78 sec mit folgendem Code:

void World::save(std::ofstream& file)
{
	unsigned int tmp;
	Block_Container* block;
	Chunk* chunk;
	vector<char> buf(196608);
	
	for(unsigned int ci = 0; ci < 64; ci++)
	{
		for(unsigned int cj = 0; cj < 64; cj++)
		{
			for(unsigned int ck = 0; ck < 16; ck++)
			{
				chunk = &this->chunks[ci][cj][ck];

				for(unsigned int i = 0; i < 8; i++)
				{
					for(unsigned int j = 0; j < 8; j++)
					{
						for(unsigned int k = 0; k < 8; k++)
						{
							block = &chunk->blocks[i][j][k];
				
							tmp = block->get_ID();
				
							file.put((unsigned char) (tmp >> 8));
							file.put((unsigned char) tmp);
							file.put((unsigned char) ((block->get_Sub_ID() << 2) | block->get_direction()));
						}
					}
				}
			}
		}
	}
}

this->chunks[ci][cj][ck] machts langsam. Diese Dereferenzierung kann stark beschleunigt werden, in dem Du in den Schleifen davor schon die Unterblöcke berechnest:

// Achtung: Pseudo-Code, subchunk1 und subchunk2 müssen richtig definiert werden...
for( ci )
{
   subchunk1 = this->chunks[ci];
   for( cj )
   {
      subchunk2 = subchunk1[ci];
      for( ck )
      {
         chunk = subchunk2[ck];
      }
   }
}

Das gilt natürlich auch für chunk->blocks[i][j][k]

Die erinnerung

Nein, habe ich nicht, aber ich vermute es würde ca. 10 Sekunden dauern, da ich durch das optimieren ca. um den Faktor 10 schneller bin.

Ich verstehe aber auch nicht, warum der Aufruf so lange dauert.
Ich sammele mal den Code zusammen:

get-Id-Funktion mit Infos:

//========== Klasse: ==========

class Block_Container
{
private:
	static std::map<Block_ID, Block*> BLOCKS;
	unsigned short direction;

	Block* block;

public:
	Block_Container();
	~Block_Container();

	void set_ID(unsigned short ID);
	void set_ID(unsigned short ID, unsigned short Sub_ID);
	void set_ID(unsigned short ID, unsigned short Sub_ID, unsigned short direction);
	void set_ID(Block_ID ID);
	void set_ID(Block_ID ID, unsigned short direction);
	void set_direction(unsigned short direction);

	unsigned short get_ID() const;
	unsigned short get_Sub_ID() const;
	Block_ID get_Block_ID() const;
	unsigned short get_direction() const;

	friend std::ostream& operator<<(std::ostream& Stream, const Block_Container block);
	friend std::ostream& operator<<(std::ostream& Stream, const Block_Container* block);

	friend World;
};

//========== Funktion: ==========

unsigned short Block_Container::get_ID() const
{
	return this->block->get_ID().ID;
}

Das get_ID (Hierbei handelt es sich um Polymorphie!)

//========== Klasse: ==========

class Block
{
public:
	Block(void);
	~Block(void);

	virtual Block* clone();

	virtual Block_ID get_ID();
};

//========== Funktion: ==========

Block_ID Block::get_ID()
{
	return Block_ID(0);
}

Und noch Block_ID:

class Block_ID
{
public:
	unsigned short ID;
	unsigned short Sub_ID;

	Block_ID();
	Block_ID(unsigned short ID);
	Block_ID(unsigned short ID, unsigned short Sub_ID);

	~Block_ID();

	bool operator< (Block_ID data) const;
	bool operator== (Block_ID data) const;
	bool operator!= (Block_ID data) const;

	friend std::ostream& operator<<(std::ostream& Stream, const Block_ID Block);
	friend std::ostream& operator<<(std::ostream& Stream, const Block_ID* Block);
};

Block_ID::Block_ID()
{
	Block_ID::ID = 0;
	Block_ID::Sub_ID = 0;
}

Block_ID::Block_ID(unsigned short ID)
{
	if((ID < 0) || (ID > 65535))
	{
		throw(BF_Error(1, 4));
	}

	Block_ID::ID = ID;
	Block_ID::Sub_ID = 0;
}

Block_ID::Block_ID(unsigned short ID, unsigned short Sub_ID)
{
	if((ID < 0) || (ID > 65535))
	{
		throw(BF_Error(1, 4));
	}

	if((Sub_ID < 0) || (Sub_ID > 63))
	{
		throw(BF_Error(1, 5));
	}

	Block_ID::ID = ID;
	Block_ID::Sub_ID = Sub_ID;
}

Block_ID::~Block_ID()
{
}

bool Block_ID::operator< (Block_ID data) const
{
	if(Block_ID::ID == data.ID)
	{
		return Block_ID::Sub_ID < data.Sub_ID;
	}

	return Block_ID::ID < data.ID;
}

bool Block_ID::operator== (Block_ID data) const
{
	return (Block_ID::ID == data.ID) && (Block_ID::Sub_ID == data.Sub_ID);
}

bool Block_ID::operator!= (Block_ID data) const
{
	return (Block_ID::ID != data.ID) || (Block_ID::Sub_ID != data.Sub_ID);
}

std::ostream& operator<<(std::ostream& Stream, const Block_ID Block)
{
	if(Block.Sub_ID == 0)
	{
		return Stream << Block.ID;
	}

	return Stream << Block.ID << ":" << Block.Sub_ID;
}

std::ostream& operator<<(std::ostream& Stream, const Block_ID* Block)
{
	if(Block->Sub_ID == 0)
	{
		return Stream << Block->ID;
	}

	return Stream << Block->ID << ":" << Block->Sub_ID;
}

Ich verstehe nicht, wieso das so lange dauert...

Edit:

@headmyshoulder:

Wie definiere ich die richtig?
(So gehts nicht: Chunk* (chunk_2d[64][16]); , wie sonst? (Ohne die Klammer gehts auch nicht!)

pyhax

Was ist den der Typ von World::chunks?

Athar

Na gut, damit sind die vier Sekunden nicht mehr verwunderlich.

Erst einmal, wenn du Funktionen nicht in der gleichen Übersetzungseinheit definierst, wird dir das ohne WPO/LTO nicht geinlined. Simple Funktionen wie Getter sollte man in den Header verlagern, sofern das möglich und sinnvoll ist.
Die Indirektion in Block_Container und der virtuelle Funktionsaufruf wird der Sache den Rest geben. Müssen deine Blöcke wirklich polymorph sein?
Falls ja, würde ich es einfach dabei belassen.

Die erinnerung

Ja sie müssen polymorph sein! Ja, aber trotzdem danke, 4 im Vergleich zu über 100 ist riesig!

Und der Datentyp von World::chunks ist Chunk[64][64][16];

headmyshoulder

Dann sollte es so funktionieren:

// Achtung: Pseudo-Code, subchunk1 und subchunk2 müssen richtig definiert werden...
for( ci )
{
   Chunk **subchunk1 = this->chunks[ci];
   for( cj )
   {
      Chunk *subchunk2 = subchunk1[ci];
      for( ck )
      {
         chunk = subchunk2[ck];
      }
   }
}

Die erinnerung

Nein, geht nicht.

Athar

Das zu optimieren ist ohnehin eher die Aufgabe des Compilers.

headmyshoulder

Die erinnerung schrieb:

Nein, geht nicht.

Funktioniert das:

for( ci )
{
   Chunk (*subchunk1)[16] = this->chunks[ci];
   for( cj )
   {
      Chunk *subchunk2 = subchunk1[ci];
      for( ck )
      {
         chunk = subchunk2[ck];
      }
   }
}

Natürlich müssen die for-Schleifen noch ausgeschrieben werden ...

hustbaer

headmyshoulder schrieb:

this->chunks[ci][cj][ck] machts langsam.

Wieso sollte das was langsam machen? Compiler können sowas schön optimieren.

headmyshoulder

hustbaer schrieb:

headmyshoulder schrieb:

this->chunks[ci][cj][ck] machts langsam.

Wieso sollte das was langsam machen? Compiler können sowas schön optimieren.

this->chunks[ci][cj][ck] sind drei Aufrufe des []-Operators, subchunk[ck] ist ein Aufruf. Im ersten Fall treten N1*N2*N3*3 dieser Aufrufe auf, im zweiten Fall N1+N1*N2+N1*N2*N3, was knapp ein drittel ist. Wenn der Compiler das Optimieren will muss er Logik in die Schleifen über cj und ci ziehen. Drauf würde ich mich nicht verlassen. Es kann sein, dass das hier klappt da das Arrays sind. Ist chunk aber ein vector< vector< vector< T > > > wird man dadurch ganz sicher Performance verlieren.

hustbaer

headmyshoulder schrieb:

hustbaer schrieb:

headmyshoulder schrieb:

this->chunks[ci][cj][ck] machts langsam.

Wieso sollte das was langsam machen? Compiler können sowas schön optimieren.

this->chunks[ci][cj][ck] sind drei Aufrufe des []-Operators, subchunk[ck] ist ein Aufruf. Im ersten Fall treten N1*N2*N3*3 dieser Aufrufe auf, im zweiten Fall N1+N1*N2+N1*N2*N3, was knapp ein drittel ist. Wenn der Compiler das Optimieren will muss er Logik in die Schleifen über cj und ci ziehen.

Ja, tut er auch.

Drauf würde ich mich nicht verlassen.

Ich schon, weil ich häufig gesehen habe dass es funktioniert. Und eigentlich noch keinen derart einfachen Fall wo es nicht funktioniert hätte.

Es kann sein, dass das hier klappt da das Arrays sind. Ist chunk aber ein vector< vector< vector< T > > > wird man dadurch ganz sicher Performance verlieren.

Selbst da wäre ich mir nicht sicher dass der Compiler es nicht optimiert.
Compiler sind recht gut darin konstante Ausdrücke aus Schleifen rauszuziehen. Auch wenn diese erst durch inlining diverser Funktionen entstehen.

Natürlich schadet es nichts, ich würde aber trotzdem erstmal gucken ob es was bringt.
Jede Optimierung macht den Code schwerer nachzuvollziehen/schwerer auf Fehler zu untersuchen etc. Jede unnötige Optimierung ist daher mMn. als schlechter Code zu werten.

Wobei ich in dem (hypothetischen) Fall mit verschachtelten Vektoren es noch als OK ansehen würde hier die optimierte Schleife zu verwenden. Weil da viele Dinge mit reinspielen, von denen man oft nicht erwartet dass sie einen Unterschied machen können. D.h. eine ganz harmlos aussehende Änderung kann dazu führen dass der Compiler die Optimierung auf einmal nicht mehr packt.

headmyshoulder

hustbaer schrieb:

Drauf würde ich mich nicht verlassen.

Ich schon, weil ich häufig gesehen habe dass es funktioniert. Und eigentlich noch keinen derart einfachen Fall wo es nicht funktioniert hätte.

Es kann sein, dass das hier klappt da das Arrays sind. Ist chunk aber ein vector< vector< vector< T > > > wird man dadurch ganz sicher Performance verlieren.

Selbst da wäre ich mir nicht sicher dass der Compiler es nicht optimiert.
Compiler sind recht gut darin konstante Ausdrücke aus Schleifen rauszuziehen. Auch wenn diese erst durch inlining diverser Funktionen entstehen.

Natürlich schadet es nichts, ich würde aber trotzdem erstmal gucken ob es was bringt.
Jede Optimierung macht den Code schwerer nachzuvollziehen/schwerer auf Fehler zu untersuchen etc. Jede unnötige Optimierung ist daher mMn. als schlechter Code zu werten.

Wobei ich in dem (hypothetischen) Fall mit verschachtelten Vektoren es noch als OK ansehen würde hier die optimierte Schleife zu verwenden. Weil da viele Dinge mit reinspielen, von denen man oft nicht erwartet dass sie einen Unterschied machen können. D.h. eine ganz harmlos aussehende Änderung kann dazu führen dass der Compiler die Optimierung auf einmal nicht mehr packt.

Ich hab durch genau diese Art von Optimierung die Laufzeit eines Programmes schon um mehrere Faktoren verbessert. Ist aber schon ein Weile her (ca. 7 Jahre) und wahrscheinlich können moderne Compiler jetzt viel besser optimieren. Ich vermute auch stark dass alle linearen Algebra-Packages sowas machen. Ok, man muss da auch nicht lange rumrätseln. Ich werd einen Testfall schreiben und das Ergebniss hier posten. Mal sehn was rauskommt.

Die erinnerung

Eigentlich sind 4 Sekunden vollkommen ok und ich glaube nicht, dass ich damit nochmals Sekunden raushole und dann lohnt es sich nicht.

Ich vertraue mal meinem Compiler...

hustbaer

headmyshoulder schrieb:

Ich werd einen Testfall schreiben und das Ergebniss hier posten. Mal sehn was rauskommt.

Wenn es dir die Sache wert ist, immer her damit.

tntnet

Ich wollte mal anmerken, dass ofstream ein puffernder Stream ist. Es ist also fast egal, ob man da byteweise oder in grösseren Blöcken schreibt. Der ofstream übergibt die Daten in der Regel in 8k Blöcken an das Betriebssystem.

Und einer hat hier Locking erwähnt. Die put-Methode ist nicht thread-safe und wird nicht locken. Auch das macht nichts aus.

Dann hat noch einer erwähnt, dass std::vector mit Sicherheit langsamer wäre, als arrays. Auch das stimmt nicht. Der Compiler sieht die komplette Implementierung des std::vector und kann daher genau die selben Optimierungen durchführen, wie mit arrays. std::vector ist ja gewissermaßen "nur" syntactic sugar (wobei ich darauf nicht verzichten will).

Aber das Resümee hier sollte sein, dass eine Performancemessung ohne Optimierung nichts bringt.

Ach ja - die Aussagen bezüglich ofstream gelten nicht für den xlC-Compiler. Da sind die iostreams indiskutabel langsam. Aber ich bezweifle, dass hier jemand mit dem xlC arbeitet.

Die erinnerung

Das ostream bufferd habe ich gewusst, ich dachte deshalb ja anfangs auch, dass das mit dem Vekto sinnlos ist. Hat ja auch nur 2 Sekunden rausgeholt...

Athar

tntnet schrieb:

std::vector ist ja gewissermaßen "nur" syntactic sugar

Naja, es ist syntactic sugar für mit new[] angelegte Arrays, was hier allerdings nicht der Fall ist.
Von der Natur her entspricht einem multidimensionalen Array wie Block blocks[8][8][8]; grob eher ein solches Konstrukt:

vector<Block> blocks;
    Chunk() : blocks(8*8*8) {}
    Block& getBlock(int x,int y,int z) {return blocks[x*64+y*8+z];}

Und in der Tat, auch mit vector bleibt die Laufzeit bei mir weitgehend unverändert (0.20s statt 0.18s).

@Die erinnerung
Selbst mit deinen Klassen läuft das bei mir noch in 0.45s. Irgendwie habe ich das Gefühl, dass da immer noch nicht alles optimal läuft (es sei denn, du hast noch einen Pentium II oder ähnliches).
Aber wenn du schon zufrieden bist, dann ist ja gut.

TyRoXx

Athar schrieb:

tntnet schrieb:

std::vector ist ja gewissermaßen "nur" syntactic sugar

Naja, es ist syntactic sugar für mit new[] angelegte Arrays, was hier allerdings nicht der Fall ist.

Nö, ist er nicht.