Forum Mjukvara Programmering och digitalt skapande Tråd

Smidig allokering av 3d-array (grid) i c++?

1
Skriv svar
Permalänk
Medlem ★
●

Smidig allokering av 3d-array (grid) i c++?

Hallå!

Tänkte höra om någon hade en snabb & smidig allokeringsteknik för 3d-grid i c++?

Går det att göra med new? Har testat men det blir alltid klagomål från kompilatorn på ett eller annat sätt. Verkar inte få använda vidare många klammor tex [], och dom verkar inte vara kompatibla med pekare & behöver konstanta nuffror för allokering osv.

Testade också med c stil, men ändra startar inte programmet av okänd anledning annars krashar det pga minne så antar att man gör fel på något sätt...

Hjälp upskattas

här var ett försök i c, är verkligen trött nu :S var ju ett tag sen man använde c allokering också...

	GridCell*** c= (GridCell***)(malloc)(sizeof (GridCell**)*w);
	for(int x=0;x<w;x++){
		c[x]=(GridCell**)(malloc)(sizeof (GridCell*)*h);
		for(int y=0;y<h;y++){
			c[x][y]=(GridCell*)(malloc)(sizeof (GridCell)*d);
		}
	}

MVH
Dalton Sleeper

Redigera
Citera flera Citera
Permalänk
Medlem
●

Att använda new på ett sätt motsvarande hur du använder malloc skulle vara:

GridCell*** c = new GridCell**[w];
for(int x = 0; x < w; x++) {
	c[x] = new GridCell*[h];
	for(int y = 0; y < h; y++) {
		c[x][y] = new GridCell[d];
	}
}

Av prestandaskäl kan det vara värt att fundera över ordningen du allokerar de olika dimensionerna, då minnesåtkomst lätt är en flaskhals nuförtiden (att hämta ny data till cache tar tid motsvarande flera hundra instruktioner). I vilken ordning kommer åtkomst att ske? Är det rad för rad kan det vara värt att allokera för h före w.

Det kan vara värt att fundera över om du skulle kunna allokera hela datamängden sekventiellt som:

GridCell* c = new GridCell[w * h * d];

Med åtkomst

c[x * (h * d) + y * d + z] = 5; // Jag tror det blir så

(Igen, fundera över vilken ordning åtkomst kommer ske.)

Visa signatur

Vill du ha svar? Citera mig gärna.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Okey tackar för din förklaring, prestandan vet jag inte riktigt, gridden kommer att användas likt i ray tracing men i detta fall picking, dvs det skall traverseras i strålars riktning vilket kan vara vilken som helst. Åtkomsten behöver vara så snabb som möjligt, dock är inte byggnadstiden så viktig i detta fall. Ska i vilket fall försöka mig på detta igen när jag blir klarare i huvudet. Det skulle vara enkalare att förstå koden & använda den om man kunde använda den på detta sätt c[x][y][z].whatever=2;... För övrigt ska gridden vara ganska stor med kanske 1000^3 eller fler celler.

Citat:

Ursprungligen inskrivet av lajnold
<Massa värt att tänka på>

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av Dalton Sleeper
Det skulle vara enkalare att förstå koden & använda den om man kunde använda den på detta sätt c[x][y][z].whatever=2;...

Väljer du att allokera minnet sekventiellt skulle du kunna ha en klass för att representera matrisen, men metod(er) för att komma åt element enkelt genom x, y och z. Det skulle kanske även kunna vara värt att skippa att sköta minnesallokeringen manuellt, och isället använda std::vector eller annan container.

class Grid {
public:
	Grid(int width, int height, int depth)
	  : width(width), height(height), depth(depth),
	    grid(width * height * depth) {}

	GridCell& get(int x, int y, int z) {
		return grid[get_index(x, y, z)];
	}

	const GridCell& get(int x, int y, int z) const {
		return grid[get_index(x, y, z)];
	}

private:
	int get_index(int x, int y, int z) const {
		return x * (height + depth) + y * depth + z;
	}

private:
	const int width, height, depth;
	std::vector<GridCell> grid;
};
Visa signatur

Vill du ha svar? Citera mig gärna.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Cellerna sitter redan i en gridklass nu ja med funktioner för lite allt möjligt, det är i stort sätt bara allokeringen & strukturen på som fattas, dock undrar jag hur effektivt det är att använda x * (height + depth) + y * depth + z väldigt många gånger per sekund, låter inte så väldigt snabbt. Celltraverseringen behöver vara så snabb det bara går och är själva flaskhalsen i programmet...picking & collision är huvudgrejen för gridden just nu.

Redigera
Citera flera Citera
Permalänk
Avstängd
●

Helt klart bör du använda lajnolds lösning om du vill ha optimal prestanda. JAg läste en kurs på KTH där vi gjorde massa numeriska beräkningar, så vi fick skriva ihop en egen array klass i C++. Lektorn sa åt oss att använda lajnolds ansats: en enda lång vektor. Och funktion som heter nåt i stil med findindex(int x, int y) som mappar om. Då kan du loopa över x och y.
data[findindex(x,y)] = 5;

EDIT: Jo, det är snabbt att göra den beräkningen.

Redigera
Citera flera Citera
Permalänk
Medlem
●
Citat:

Ursprungligen inskrivet av Dalton Sleeper
dock undrar jag hur effektivt det är att använda x * (height + depth) + y * depth + z väldigt många gånger per sekund, låter inte så väldigt snabbt.

Inte mindre effektivt än att ha på sättet ursprunliga posten föreslog.

c[x][y][z]
->
1) Beräkna c + sizeof(GridCell**) * x
2) Hämta adressen a som finns lagras på den beräknade adressen
3) Beräkna a + sizeof(GridCell*) * h
4) Hämta adressen a2 som finns lagrad på den beräknade adressen
5) Beräkna a2 + sizeof(GridCell) * z
6) Hämta önskat värde relativt den beräknade adressen (via (troligtvis) hårdkodat offset)

Jämfört med
1) Beräkna &grid[0] + (x * (height + depth) + y * depth + z) * sizeof(GridCell)
2) Hämta önskat värde relativt den beräknade adressen

Edit: Fixade till en beräkning.

Senast redigerat
Visa signatur

Vill du ha svar? Citera mig gärna.

Redigera
Citera flera Citera
Permalänk
Medlem ★
●

Se där, kanske blir att testa skillnaden på dessa två då!

Hittade buggen på min andra lösning iaf, riktigt blunderfel som jag knappt vågar posta, kollade minnesanvändningen när gridden skapades, 1.9GB! hade naturligtvis skickat in alldeles för stora värden som inte hade celloffset utan använde hela gridstorlekens värden :S, nu ligger det på 190MB med diverse grejer inladdade i programmet.

Tack så mycket för er hjälp!

Redigera
Citera flera Citera
1
Skriv svar
Senaste nyheterna
Hårdvara
Mjukvara
Övrigt
Nytt i forumet
Datorkomponenter
System
Ljud, bild och kommunikation
Spel och mjukvara