Arraydurchlauf "langsam"

Übersicht

BlitzMax, BlitzMax NG

Allgemein

	PhillipK Betreff: Arraydurchlauf "langsam"	Mi, Apr 24, 2013 10:50 Antworten mit Zitat
Huhu Forum! Ich benötige mal eure hilfe, ich habe scheinbar nen brett vorm kopf. Im moment versuche ich, eine art "lichteinfluss" zu berechnen. Hierbei geht es um eine 2d Tilemap, sidescrolling. Meine map ist im moment 8192x2048 tiles groß - also doch nicht wenig. Ich verwende insgesamt 2x einen kompletten durchlauf. Der eine stellt fest, wo "skyblöcke" sind, der 2te berechnet den lichteinfluss der gefundenen skyblöcke. Klar, ich könnte das ganze zusammenlegen, um Rechenzeit zu sparen, aber mich wurmt etwas anderes Der Erste durchlauf braucht so ~ 2.500ms, dabei geht er jeden block durch und, wenn dieser ein skyblock ist, schaut die anliegenden blöcke links,rechts,oben,unten durch, ob diese ein Solid block sind. Wenn ja, stempel ich diesen block (den skyblock!) als lichtemitter. Der 2te durchlauf braucht grademal 1.000ms, zugegeben, das ist immernoch langsam, aber das ist erstmal egal. Der 2te durchlauf checkt jeden block und, wenn dieser ein Skyblock mit lichtemitter flag ist, prüft 30x30 blöcke drumrum und rechnet eine manhatten distanz aus. Ausserdem setzt es ein paar bits eines Shorts neu, falls der neue lichtwert höher ist. Allerdings finde ich, das der 2te durchlauf wesentlich komplexer ist, aber dennoch ist er schneller: warum? Hier mal die methode, um die es geht: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Method CreateLightData() Local ms:Int = MilliSecs() Print("Beginne lichtblock bestimmung") Local x1:Int, y1:Int, x2:Int, y2:Int Local dirX:Int[] = [- 1, 0, 1, 0] Local dirY:Int[] = [0, -1, 0, 1] Local i:Int '//Jeden block durchgehen: Wenn er ein skyblock ist, umgebung prüfen For x1 = 0 Until sizeX For y1 = 0 Until sizeY If GetValue(x1, y1) = 0 Then '->Ist skyblock SetSkyLight(x1, y1, 15) '-> Lichtwert für diesen block setzen (bits 5-8 in einem short) For i = 0 Until 4 '-> Eckenprüfung If GetValue(x1 + dirX[i], y1 + dirY[i]) > 0 Then '->Ist solidblock lightData[x1, y1] = lightData[x1, y1] \| SKY_WITH_BORDER_FLAG '-> Diesen block als lichtemitter festlegen Exit End If Next EndIf Next Next Print("Ende - Dauer: " + (MilliSecs() - ms)) Local ms2:Int = MilliSecs() Print("Beginne mit lichtberechnung") '//Wieder jeden block durcgehen. Diesmal für alle lichtemitter die umgebung prüfen. For x1 = 0 Until sizeX For y1 = 0 Until sizeY If lightData[x1, y1] & SKY_WITH_BORDER_FLAG Then '-> Dieser block ist ein Skyblock, welcher neben mindestens einem Solidblock sitzt. Lichtberechnung For x2 = -15 To 15 For y2 = -15 To 15 i = Clamp(15 - ManhattenI(x1, y1, x2 + x1, y2 + y1), 0, 15) '->Manhatten distanz. Je weiter weg, desto kleiner wird i. Wert liegt zwischen 0 und 15. If i > GetSkylight(x1 + x2, y1 + y2) '-> Vorhandenes licht prüfen SetSkyLight(x1 + x2, y1 + y2, i) '-> und eventuell höheren lichteinfluss setzen. End If Next Next End If Next Next Print("Dauer lichtberechnung: " + (MilliSecs() - ms2)+" - Dauer insgesamt: "+(MilliSecs()-ms)) End Method Und hier, der sauberkeit halber, noch die 3 methoden zum setten/getten: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Method SetSkyLight(x:Int, y:Int, val:Byte) x = (x + sizeX) Mod sizeX y = Clamp(sizeY - y, 0, sizeY - 1) Local l:Short = lightData[x, y] Local result:Short = (l & $F0FF) + (val Shl 8) lightData[x, y] = result End Method Method GetSkylight:Byte(x:Int, y:Int) x = (x + sizeX) Mod sizeX y = Clamp(sizeY - y, 0, sizeY - 1) Return ((lightData[x, y] & SKY_ILLUM_FLAG) Shr 8) End Method Method GetValue:Byte(x:Int, y:Int) y = Clamp(sizeY - y, 0, sizeY - 1) x = (x + sizeX) Mod sizeX Return blockdata[x, y] End Method Also.. hm ManhattenI macht btw nichts anderes wie eine manhatten distanz, also abs(x2-x1)+abs(y2-y1). das I am ende steht für integer - es nimmt integer an und gibt integer zurück (um internes casten zu verhindern, speedboost). Hat jemand ne idee, wie man den ersten durchlauf umschreiben könnte, um die geschwindigkeit zu erhöhen? Zwar passiert das ganze exakt einmal pro mapload, aber schneller wäre trotzdem cool :> EDIT: Um genau zu sein, braucht es sogar noch länger, wenn ich die beiden methoden zusammenfüge. Dort, wo EXIT im ersten durchlauf vorkommt, lässt sich rein logisch betrachtet direkt der 2te durchlauf zum lichteinfluss der umgebung berechnen einfügen. DH der for x2 = -15 to 15... part. ERgebniss-> 300ms mehr. Ich verzweifel

PhillipK

Betreff: Arraydurchlauf "langsam"

Mi, Apr 24, 2013 10:50
Antworten mit Zitat

Huhu Forum!

Ich benötige mal eure hilfe, ich habe scheinbar nen brett vorm kopf.

Im moment versuche ich, eine art "lichteinfluss" zu berechnen. Hierbei geht es um eine 2d Tilemap, sidescrolling.
Meine map ist im moment 8192x2048 tiles groß - also doch nicht wenig.

Ich verwende insgesamt 2x einen kompletten durchlauf. Der eine stellt fest, wo "skyblöcke" sind, der 2te berechnet den lichteinfluss der gefundenen skyblöcke.
Klar, ich könnte das ganze zusammenlegen, um Rechenzeit zu sparen, aber mich wurmt etwas anderes Smile

Der Erste durchlauf braucht so ~ 2.500ms, dabei geht er jeden block durch und, wenn dieser ein skyblock ist, schaut die anliegenden blöcke links,rechts,oben,unten durch, ob diese ein Solid block sind.
Wenn ja, stempel ich diesen block (den skyblock!) als lichtemitter.

Der 2te durchlauf braucht grademal 1.000ms, zugegeben, das ist immernoch langsam, aber das ist erstmal egal.
Der 2te durchlauf checkt jeden block und, wenn dieser ein Skyblock mit lichtemitter flag ist, prüft 30x30 blöcke drumrum und rechnet eine manhatten distanz aus.
Ausserdem setzt es ein paar bits eines Shorts neu, falls der neue lichtwert höher ist.

Allerdings finde ich, das der 2te durchlauf wesentlich komplexer ist, aber dennoch ist er schneller: warum?

Hier mal die methode, um die es geht:
BlitzMax: [AUSKLAPPEN]

	Method CreateLightData()

		Local ms:Int = MilliSecs()
		Print("Beginne lichtblock bestimmung")
		
		Local x1:Int, y1:Int, x2:Int, y2:Int
		Local dirX:Int[] = [- 1, 0, 1, 0]
		Local dirY:Int[] = [0, -1, 0, 1]
		
		Local i:Int
		
		
		'//Jeden block durchgehen: Wenn er ein skyblock ist, umgebung prüfen
		For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If GetValue(x1, y1) = 0 Then '->Ist skyblock
				SetSkyLight(x1, y1, 15) '-> Lichtwert für diesen block setzen (bits 5-8 in einem short)
				
				For i = 0 Until 4 '-> Eckenprüfung
					If GetValue(x1 + dirX[i], y1 + dirY[i]) > 0 Then '->Ist solidblock 
						lightData[x1, y1] = lightData[x1, y1] | SKY_WITH_BORDER_FLAG '-> Diesen block als lichtemitter festlegen
						Exit
					End If
				Next
			EndIf
		Next
		Next
		
		
		Print("Ende - Dauer: " + (MilliSecs() - ms))
		Local ms2:Int = MilliSecs()
		Print("Beginne mit lichtberechnung")
		
		'//Wieder jeden block durcgehen. Diesmal für alle lichtemitter die umgebung prüfen.
		For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If lightData[x1, y1] & SKY_WITH_BORDER_FLAG Then '-> Dieser block ist ein Skyblock, welcher neben mindestens einem Solidblock sitzt. Lichtberechnung
				For x2 = -15 To 15
				For y2 = -15 To 15
					i = Clamp(15 - ManhattenI(x1, y1, x2 + x1, y2 + y1), 0, 15) '->Manhatten distanz. Je weiter weg, desto kleiner wird i. Wert liegt zwischen 0 und 15.
					If i > GetSkylight(x1 + x2, y1 + y2) '-> Vorhandenes licht prüfen
						SetSkyLight(x1 + x2, y1 + y2, i) '-> und eventuell höheren lichteinfluss setzen.
					End If
				Next
				Next
			
			End If
		Next
		Next
		
		Print("Dauer lichtberechnung: " + (MilliSecs() - ms2)+" - Dauer insgesamt: "+(MilliSecs()-ms))
	End Method

Und hier, der sauberkeit halber, noch die 3 methoden zum setten/getten:
BlitzMax: [AUSKLAPPEN]

	Method SetSkyLight(x:Int, y:Int, val:Byte)
		x = (x + sizeX) Mod sizeX
		y = Clamp(sizeY - y, 0, sizeY - 1)
		
		Local l:Short = lightData[x, y]
		Local result:Short = (l & $F0FF) + (val Shl 8)
		
		lightData[x, y] = result
	End Method
	Method GetSkylight:Byte(x:Int, y:Int)
		x = (x + sizeX) Mod sizeX
		y = Clamp(sizeY - y, 0, sizeY - 1)
		Return ((lightData[x, y] & SKY_ILLUM_FLAG) Shr 8)
	End Method
	Method GetValue:Byte(x:Int, y:Int)
		y = Clamp(sizeY - y, 0, sizeY - 1)
		x = (x + sizeX) Mod sizeX
		Return blockdata[x, y]
	End Method

Also.. hm

ManhattenI macht btw nichts anderes wie eine manhatten distanz, also abs(x2-x1)+abs(y2-y1). das I am ende steht für integer - es nimmt integer an und gibt integer zurück (um internes casten zu verhindern, speedboost).

Hat jemand ne idee, wie man den ersten durchlauf umschreiben könnte, um die geschwindigkeit zu erhöhen?
Zwar passiert das ganze exakt einmal pro mapload, aber schneller wäre trotzdem cool :>

EDIT:
Um genau zu sein, braucht es sogar noch länger, wenn ich die beiden methoden zusammenfüge.
Dort, wo EXIT im ersten durchlauf vorkommt, lässt sich rein logisch betrachtet direkt der 2te durchlauf zum lichteinfluss der umgebung berechnen einfügen.
DH der for x2 = -15 to 15... part.

ERgebniss-> 300ms mehr. Ich verzweifel Smile

	aMul Sieger des Minimalist Compo 01/13	Mi, Apr 24, 2013 11:15 Antworten mit Zitat
Der Geschwindigkeitsunterscheid zwischen den beiden Teilen liegt vermutlich daran, dass deine Tilemap relativ große gefüllte und leere Gebiete hat. Damit ist die Dichte der Blöcke dir in der ersten Schleife markiert werden sehr gering, was diese langsamer macht(Da die innere Schleife selten abgebrochen wird). Der zweite Teil hingegen profitiert hiervon, da der innere Teil der Schleife nur für sehr wenige Blöcke ausgeführt wird. Dass es langsamer wird wenn du den inneren Teil der zweiten Schleife in die erste legst kann daran liegen, dass der Compiler nicht mehr so gut optimieren kann und du potenziell deinen CPU Cache verwirrst damit. (Spekulation) Einen Weg den ersten Teil schneller zu machen sehe ich leider nicht. Die zweite Schleife hingegen scheint mir weniger optimiert. Zum Beispiel musst du nicht den gesammten 31x31 Bereich bearbeiten, da dein Licht sich in einer Rauten-Form ausbreitet. Weiterhin wäre es vielleicht schneller, wenn auch komplizierter(weshalb es dass vielleicht nicht wert ist), eine Art Floodfill zu benutzen, welches sich von den Lichtquellen ausbreitet, und nur weiter rekursiv/iterativ aufgerufen wird, wenn die Helligkeit des aktuellen Blocks sich verändert hat. Oh, und btw: Code: [AUSKLAPPEN] [EINKLAPPEN] ManhattenI(x1, y1, x2 + x1, y2 + y1) == Abs(x2) + Abs(y2)
Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben! advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans! Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! \| RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 \| Stereoskopie in Blitz3D \| Teleport-Animation Screensaver

aMul

Sieger des Minimalist Compo 01/13

Mi, Apr 24, 2013 11:15
Antworten mit Zitat

Der Geschwindigkeitsunterscheid zwischen den beiden Teilen liegt vermutlich daran, dass deine Tilemap relativ große gefüllte und leere Gebiete hat. Damit ist die Dichte der Blöcke dir in der ersten Schleife markiert werden sehr gering, was diese langsamer macht(Da die innere Schleife selten abgebrochen wird). Der zweite Teil hingegen profitiert hiervon, da der innere Teil der Schleife nur für sehr wenige Blöcke ausgeführt wird.

Dass es langsamer wird wenn du den inneren Teil der zweiten Schleife in die erste legst kann daran liegen, dass der Compiler nicht mehr so gut optimieren kann und du potenziell deinen CPU Cache verwirrst damit. (Spekulation)

Einen Weg den ersten Teil schneller zu machen sehe ich leider nicht.

Die zweite Schleife hingegen scheint mir weniger optimiert. Zum Beispiel musst du nicht den gesammten 31x31 Bereich bearbeiten, da dein Licht sich in einer Rauten-Form ausbreitet. Weiterhin wäre es vielleicht schneller, wenn auch komplizierter(weshalb es dass vielleicht nicht wert ist), eine Art Floodfill zu benutzen, welches sich von den Lichtquellen ausbreitet, und nur weiter rekursiv/iterativ aufgerufen wird, wenn die Helligkeit des aktuellen Blocks sich verändert hat.

Oh, und btw:
Code: [AUSKLAPPEN]

ManhattenI(x1, y1, x2 + x1, y2 + y1) == Abs(x2) + Abs(y2)

Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben!
advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans!
Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! | RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 | Stereoskopie in Blitz3D | Teleport-Animation Screensaver

	DAK	Mi, Apr 24, 2013 11:28 Antworten mit Zitat
In BlitzMax kosten Funktionsaufrufe unglaublich viel. Ich hab mal etwas herumgespielt: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] For x1 = 0 Until sizeX For y1 = 0 Until sizeY If blockdata[x, y]=0 Then EndIf Next Next dauert unter 200 ms. (Eher gegen 150 ms) BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] For x1 = 0 Until sizeX For y1 = 0 Until sizeY If GetValue(x1, y1) = 0 Then EndIf Next Next mit BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Method GetValue:Byte(x:Int, y:Int) Return blockdata[x, y] End Method kostet über eine Sekunde! Ohne den Funktionsaufruf bist du 5-10 mal schneller! Deine erste Funktion ruft in Schleife eine Funktion auf. Das sind 16777216 teure Funktionsaufrufe. Die zweite Schleife vergleicht nur Daten. Allein hier fällt schon viel raus. Außerdem ruft deine GetValue-Funktion noch die Clamp()-Funktion auf (zwei Funktionen = 10-20 mal langsamer als keine Funktion) und verwendet den teuren Mod-Operator ziemlich grundlos (der kostet dich auch rund 3 Sekunden, von den 15-20, die der volle Lauf bei mir dauert). Versuche also reine Getter und Setter komplett zu vermeiden, und wenn möglich, Funktionen in Schleifen, die eine lange Laufzeit haben, zu vermeiden. Ich weiß, das geht gegen alle guten Coding-Practices, aber hier geht's um Geschwindigkeit. Edit: Was du noch machen kannst, ist beim ersten Laden der Map (wo blockData und lightData befüllt werden) eine Liste aller SkyBlocks zu erstellen. Eine echte Liste (im Sinne von LinkedList) wäre für so große Datenmengen aber wohl etwas langsam. Am besten wär wohl ein Array nach diesem Schema: x1, x2, x3, x4, x5, ... y1, y2, y3, y4, y5, ... Also, dass der x-Index eine Laufvariable ist und der y-Index zum Unterscheiden von X- und Y-Koordinate da ist. Dann bräuchtest du nicht mehr alle Blöcke überprüfen, sondern nur noch die, die du brauchst. Sollte dir je nach der Anzahl an Skyblocks die du hast, einen bis zu doppelten Geschwindigkeitsboost geben.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mi, Apr 24, 2013 11:28
Antworten mit Zitat

In BlitzMax kosten Funktionsaufrufe unglaublich viel. Ich hab mal etwas herumgespielt:

BlitzMax: [AUSKLAPPEN]


For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If blockdata[x, y]=0 Then
			EndIf
		Next
Next

dauert unter 200 ms. (Eher gegen 150 ms)

BlitzMax: [AUSKLAPPEN]


For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If GetValue(x1, y1) = 0 Then
			EndIf
		Next
Next

mit
BlitzMax: [AUSKLAPPEN]


	Method GetValue:Byte(x:Int, y:Int)
		Return blockdata[x, y]
	End Method

kostet über eine Sekunde!

Ohne den Funktionsaufruf bist du 5-10 mal schneller!
Deine erste Funktion ruft in Schleife eine Funktion auf. Das sind 16777216 teure Funktionsaufrufe.
Die zweite Schleife vergleicht nur Daten. Allein hier fällt schon viel raus.
Außerdem ruft deine GetValue-Funktion noch die Clamp()-Funktion auf (zwei Funktionen = 10-20 mal langsamer als keine Funktion) und verwendet den teuren Mod-Operator ziemlich grundlos (der kostet dich auch rund 3 Sekunden, von den 15-20, die der volle Lauf bei mir dauert).

Versuche also reine Getter und Setter komplett zu vermeiden, und wenn möglich, Funktionen in Schleifen, die eine lange Laufzeit haben, zu vermeiden.

Ich weiß, das geht gegen alle guten Coding-Practices, aber hier geht's um Geschwindigkeit.

Edit: Was du noch machen kannst, ist beim ersten Laden der Map (wo blockData und lightData befüllt werden) eine Liste aller SkyBlocks zu erstellen. Eine echte Liste (im Sinne von LinkedList) wäre für so große Datenmengen aber wohl etwas langsam. Am besten wär wohl ein Array nach diesem Schema:
x1, x2, x3, x4, x5, ...
y1, y2, y3, y4, y5, ...

Also, dass der x-Index eine Laufvariable ist und der y-Index zum Unterscheiden von X- und Y-Koordinate da ist.
Dann bräuchtest du nicht mehr alle Blöcke überprüfen, sondern nur noch die, die du brauchst. Sollte dir je nach der Anzahl an Skyblocks die du hast, einen bis zu doppelten Geschwindigkeitsboost geben.

Gewinner der 6. und der 68. BlitzCodeCompo

	PhillipK	Mi, Apr 24, 2013 11:44 Antworten mit Zitat
Wow Oo So hatte ich das noch garnicht gegengecheckt. Nunja, ganz grundlos sind die setter/getter nicht. Nur wesentlich öfters als benötigt. Ich die daten sollen border-übergreifend sein, dh alles was bei x-1 ist, liegt praktisch gesehen auf der anderen seite der map (-> Mod) Clamp ist eine reine vorsichtsmaßnahme. Ich wollte damit eigentlich nur die checks (if y >= 0 and y < sizeY) vermeiden. Aber okay, ich baus mal direkt ein, dh mit abfragen (modulus nur wenn nötig, clamp hardcoded) und probiers erneut. Ich melde mich gleich. danke DAK (das war wohl das brett vorm kopf, was du entfernst hast^^) EDIT: Alter schwede, DAK du bist mein Held ^^ Ich habe hier mal die überarbeitete version. Dort wo es wahrscheinlich nötig war, habe ich abfragen eingebaut um Modulus und "clamping" nur dann zu verwenden, wenns wirklich gebraucht wird. Die alten codestücke habe ich dringelassen, um den vergleich zu zeigen. Generell ist es wesentlich unleserlicher, aber trotzdem sau schnell oO BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Method CreateLightData() Local ms:Int = MilliSecs() Print("Beginne lichtblock bestimmung") Local x1:Int, y1:Int, x2:Int, y2:Int Local dirX:Int[] = [- 1, 0, 1, 0] Local dirY:Int[] = [0, -1, 0, 1] Local i:Int Local tmpX:Int Local tmpY:Int '//Jeden block durchgehen: Wenn er ein skyblock ist, umgebung prüfen For x1 = 0 Until sizeX For y1 = 0 Until sizeY If blockdata[x1, (sizeY - y1) - 1] = 0 Then 'If GetValue(x1, y1) = 0 Then '->Ist skyblock lightData[x1, (sizeY - y1) - 1] = (lightData[x1, (sizeY - y1) - 1] & $F0FF) + $F00 ' SetSkyLight(x1, y1, 15) '-> Lichtwert für diesen block setzen (bits 5-8 in einem short) For i = 0 Until 4 '-> Eckenprüfung tmpX = x1 + dirX[i] tmpY = (sizeY - y1 + dirY[i]) - 1 If tmpX < 0 Or tmpX >= sizeX Then tmpX = (tmpX + sizeX) Mod sizeX If tmpY < 0 Then tmpY = 0 If tmpY >= sizeY Then tmpY = sizeY - 1 If blockdata[tmpX, tmpY] > 0 Then 'If GetValue(x1 + dirX[i], y1 + dirY[i]) > 0 Then '->Ist solidblock lightData[x1, y1] = lightData[x1, y1] \| SKY_WITH_BORDER_FLAG '-> Diesen block als lichtemitter festlegen Exit End If Next EndIf Next Next Print("Ende - Dauer: " + (MilliSecs() - ms)) Local ms2:Int = MilliSecs() Print("Beginne mit lichtberechnung") '//Wieder jeden block durcgehen. Diesmal für alle lichtemitter die umgebung prüfen. For x1 = 0 Until sizeX For y1 = 0 Until sizeY If lightData[x1, y1] & SKY_WITH_BORDER_FLAG Then '-> Dieser block ist ein Skyblock, welcher neben mindestens einem Solidblock sitzt. Lichtberechnung For x2 = -15 To 15 For y2 = -15 To 15 i = 15 - (Abs(x2) + Abs(y2)) If i < 0 Then i = 0 If i > 15 Then i = 15 'i = Clamp(15 - ManhattenI(x1, y1, x2 + x1, y2 + y1), 0, 15) '->Manhatten distanz. Je weiter weg, desto kleiner wird i. Wert liegt zwischen 0 und 15. tmpX = x1 + x2 tmpY = (sizeY - y1 + y2) - 1 If tmpX < 0 Or tmpX >= sizeX Then tmpX = (tmpX + sizeX) Mod sizeX If tmpY < 0 Then tmpY = 0 If tmpY >= sizeY Then tmpY = sizeY - 1 If i > (lightData[tmpX, tmpY] & SKY_ILLUM_FLAG) Shr 8 Then 'If i > GetSkylight(x1 + x2, y1 + y2) '-> Vorhandenes licht prüfen lightData[tmpX, tmpY] = (lightData[tmpX, tmpY] & $F0FF) + (i Shl 8) 'SetSkyLight(x1 + x2, y1 + y2, i) '-> und eventuell höheren lichteinfluss setzen. End If Next Next End If Next Next Print("Dauer lichtberechnung: " + (MilliSecs() - ms2)+" - Dauer insgesamt: "+(MilliSecs()-ms)) End Method Hier noch der print-output: Code: [AUSKLAPPEN] [EINKLAPPEN] Beginne lichtblock bestimmung Ende - Dauer: 395 Beginne mit lichtberechnung Dauer lichtberechnung: 257 - Dauer insgesamt: 652 aufruf an alle, die ähnlich wie ich verzweifeln: Wenns schnell sein soll, spart nicht an kommentaren, sondern an funktionsaufrufen.. ist echt unmenschlich, was dabei rumkommt :O Dauer lichtblockbestimmung vorher: 2.200- 2.500 ms. Dauer lichtberechnung vorher: ~800 - 1.000 ms. Insgesamt zwischen 3.000 und 3.500ms Verbesserung, selbe logik, nur ganz ohne funktionsaufrufe: Dauer lichtblockbestimmung: 370-410ms Dauer lichtberechnung: 250-260ms

PhillipK

Mi, Apr 24, 2013 11:44
Antworten mit Zitat

Wow Oo

So hatte ich das noch garnicht gegengecheckt.

Nunja, ganz grundlos sind die setter/getter nicht. Nur wesentlich öfters als benötigt. Smile

Ich die daten sollen border-übergreifend sein, dh alles was bei x-1 ist, liegt praktisch gesehen auf der anderen seite der map (-> Mod)
Clamp ist eine reine vorsichtsmaßnahme. Ich wollte damit eigentlich nur die checks (if y >= 0 and y < sizeY) vermeiden.
Aber okay, ich baus mal direkt ein, dh mit abfragen (modulus nur wenn nötig, clamp hardcoded) und probiers erneut.
Ich melde mich gleich. danke DAK Smile

(das war wohl das brett vorm kopf, was du entfernst hast^^)

EDIT:

Alter schwede, DAK du bist mein Held ^^

Ich habe hier mal die überarbeitete version.
Dort wo es wahrscheinlich nötig war, habe ich abfragen eingebaut um Modulus und "clamping" nur dann zu verwenden, wenns wirklich gebraucht wird.
Die alten codestücke habe ich dringelassen, um den vergleich zu zeigen.
Generell ist es wesentlich unleserlicher, aber trotzdem sau schnell oO

BlitzMax: [AUSKLAPPEN]

	Method CreateLightData()

		Local ms:Int = MilliSecs()
		Print("Beginne lichtblock bestimmung")
		
		Local x1:Int, y1:Int, x2:Int, y2:Int
		Local dirX:Int[] = [- 1, 0, 1, 0]
		Local dirY:Int[] = [0, -1, 0, 1]
		
		Local i:Int
		
		Local tmpX:Int
		Local tmpY:Int
		
		
		'//Jeden block durchgehen: Wenn er ein skyblock ist, umgebung prüfen
		For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If blockdata[x1, (sizeY - y1) - 1] = 0 Then
			'If GetValue(x1, y1) = 0 Then '->Ist skyblock
			
				lightData[x1, (sizeY - y1) - 1] = (lightData[x1, (sizeY - y1) - 1] & $F0FF) + $F00
			'	SetSkyLight(x1, y1, 15) '-> Lichtwert für diesen block setzen (bits 5-8 in einem short)
				
			
				For i = 0 Until 4 '-> Eckenprüfung
					tmpX = x1 + dirX[i]
					tmpY = (sizeY - y1 + dirY[i]) - 1
					
					If tmpX < 0 Or tmpX >= sizeX Then tmpX = (tmpX + sizeX) Mod sizeX
					If tmpY < 0 Then tmpY = 0
					If tmpY >= sizeY Then tmpY = sizeY - 1
					
					If blockdata[tmpX, tmpY] > 0 Then
					'If GetValue(x1 + dirX[i], y1 + dirY[i]) > 0 Then '->Ist solidblock 
						lightData[x1, y1] = lightData[x1, y1] | SKY_WITH_BORDER_FLAG '-> Diesen block als lichtemitter festlegen
						Exit
					End If
				Next
			EndIf
		Next
		Next
		
		
		Print("Ende - Dauer: " + (MilliSecs() - ms))
		Local ms2:Int = MilliSecs()
		Print("Beginne mit lichtberechnung")
		
		'//Wieder jeden block durcgehen. Diesmal für alle lichtemitter die umgebung prüfen.
		For x1 = 0 Until sizeX
		For y1 = 0 Until sizeY
			If lightData[x1, y1] & SKY_WITH_BORDER_FLAG Then '-> Dieser block ist ein Skyblock, welcher neben mindestens einem Solidblock sitzt. Lichtberechnung
				For x2 = -15 To 15
				For y2 = -15 To 15
					i = 15 - (Abs(x2) + Abs(y2))
					If i < 0 Then i = 0
					If i > 15 Then i = 15
					'i = Clamp(15 - ManhattenI(x1, y1, x2 + x1, y2 + y1), 0, 15) '->Manhatten distanz. Je weiter weg, desto kleiner wird i. Wert liegt zwischen 0 und 15.
					
					
					tmpX = x1 + x2
					tmpY = (sizeY - y1 + y2) - 1
					
					If tmpX < 0 Or tmpX >= sizeX Then tmpX = (tmpX + sizeX) Mod sizeX
					If tmpY < 0 Then tmpY = 0
					If tmpY >= sizeY Then tmpY = sizeY - 1
					
					If i > (lightData[tmpX, tmpY] & SKY_ILLUM_FLAG) Shr 8 Then
					'If i > GetSkylight(x1 + x2, y1 + y2) '-> Vorhandenes licht prüfen
						
						lightData[tmpX, tmpY] = (lightData[tmpX, tmpY] & $F0FF) + (i Shl 8)
						'SetSkyLight(x1 + x2, y1 + y2, i) '-> und eventuell höheren lichteinfluss setzen.
					End If
				Next
				Next
			
			End If
		Next
		Next
		
		Print("Dauer lichtberechnung: " + (MilliSecs() - ms2)+" - Dauer insgesamt: "+(MilliSecs()-ms))
	End Method

Hier noch der print-output:
Code: [AUSKLAPPEN]

Beginne lichtblock bestimmung

Ende - Dauer: 395

Beginne mit lichtberechnung

Dauer lichtberechnung: 257 - Dauer insgesamt: 652

aufruf an alle, die ähnlich wie ich verzweifeln:
Wenns schnell sein soll, spart nicht an kommentaren, sondern an funktionsaufrufen.. ist echt unmenschlich, was dabei rumkommt :O

Dauer lichtblockbestimmung vorher: 2.200- 2.500 ms.
Dauer lichtberechnung vorher: ~800 - 1.000 ms.
Insgesamt zwischen 3.000 und 3.500ms

Verbesserung, selbe logik, nur ganz ohne funktionsaufrufe:
Dauer lichtblockbestimmung: 370-410ms
Dauer lichtberechnung: 250-260ms
Smile

	DAK	Mi, Apr 24, 2013 13:08 Antworten mit Zitat
Freut mich, dass es so gut geklappt hat! Falls du noch etwas Optimierung willst, schau, ob das was ich vorhin im Edit geschrieben hab, dir was hilft. Mit etwas Glück kannst du damit deine Geschwindigkeit noch mal verdoppeln. Edit: So schaut das Ergebnis bei mir aus: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] ###ALT Ende - Dauer: 13453 Beginne mit lichtberechnung Dauer lichtberechnung: 179 - Dauer insgesamt: 13632 ###NEU Beginne lichtblock bestimmung Ende - Dauer: 3263 Beginne mit lichtberechnung Dauer lichtberechnung: 169 - Dauer insgesamt: 3432 Gut gemacht! Der große Unterschied war hald, dass du bei der ersten Schleife für jeden Block zwei Funktionen aufgerufen hast, und bei der zweiten Schleife nur direkte Vergleiche verwendet hast.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mi, Apr 24, 2013 13:08
Antworten mit Zitat

Freut mich, dass es so gut geklappt hat!

Falls du noch etwas Optimierung willst, schau, ob das was ich vorhin im Edit geschrieben hab, dir was hilft. Mit etwas Glück kannst du damit deine Geschwindigkeit noch mal verdoppeln.

Edit: So schaut das Ergebnis bei mir aus:
BlitzMax: [AUSKLAPPEN]


###ALT
Ende - Dauer: 13453
Beginne mit lichtberechnung
Dauer lichtberechnung: 179 - Dauer insgesamt: 13632

###NEU
Beginne lichtblock bestimmung
Ende - Dauer: 3263
Beginne mit lichtberechnung
Dauer lichtberechnung: 169 - Dauer insgesamt: 3432

Gut gemacht!

Der große Unterschied war hald, dass du bei der ersten Schleife für jeden Block zwei Funktionen aufgerufen hast, und bei der zweiten Schleife nur direkte Vergleiche verwendet hast.

Gewinner der 6. und der 68. BlitzCodeCompo

	PhillipK	Mi, Apr 24, 2013 14:45 Antworten mit Zitat
Mir ist leider ein großer fehler in meiner Denkweise aufgefallen: Die ursprüngliche version hat bisher keinerlei verwendung mehr. grund: Es war geplant, das es auch Halbsolide blocks und nicht-licht-emitter-airblocks gibt. Heißt im klartext: Es gibt blöcke die an den hintergrund angrenzen (Die airblocks), sowie welche, die zwar luft sind aber von einem 2ten layer vom himmel abgeschnitten sind, oder aber auch glassblöcke, welche zwar licht absorbieren und solid sind, aber eben nicht in dem maße, wie es ein wirklich fester block tun würde. Das lässt sich nicht über die pure distanz regeln, was bedeutet, das eine art floodfill her muss. Aber, gelernt habe ich doch einiges (blöde funktionsaufrufe) und für andere bereiche ist die funktion sicher extrem hilfreich. Mit hilfe von AMul wurde diese btw noch weiter verfeinert. Extrem unleserlich, aber der check auf i wurde ausgemerzt und er hat mir einen pseudocode geliefert, die eine rautenform durchläuft, und nicht wie in meiner ursprünglichen version eine rechteck funktion. Diese micro-optimierungen haben am ende nochmal 100ms eingespart, was schon ziemlich krass ist. 400 ms um insgesamt 8192x2048 blöcke zu durchlaufen und eine richtig coole lichtsache einzubauen :> Im moment arbeite ich an der floodfill version, die leider etwa so lahm ist wie meine erste version mit unnötigen funktionsaufrufen. Aber ich optimiere weiterhin...

PhillipK

Mi, Apr 24, 2013 14:45
Antworten mit Zitat

Mir ist leider ein großer fehler in meiner Denkweise aufgefallen:
Die ursprüngliche version hat bisher keinerlei verwendung mehr. grund:
Es war geplant, das es auch Halbsolide blocks und nicht-licht-emitter-airblocks gibt.
Heißt im klartext: Es gibt blöcke die an den hintergrund angrenzen (Die airblocks), sowie welche, die zwar luft sind aber von einem 2ten layer vom himmel abgeschnitten sind, oder aber auch glassblöcke, welche zwar licht absorbieren und solid sind, aber eben nicht in dem maße, wie es ein wirklich fester block tun würde.

Das lässt sich nicht über die pure distanz regeln, was bedeutet, das eine art floodfill her muss.

Aber, gelernt habe ich doch einiges (blöde funktionsaufrufe) und für andere bereiche ist die funktion sicher extrem hilfreich.
Mit hilfe von AMul wurde diese btw noch weiter verfeinert. Extrem unleserlich, aber der check auf i wurde ausgemerzt und er hat mir einen pseudocode geliefert, die eine rautenform durchläuft, und nicht wie in meiner ursprünglichen version eine rechteck funktion.

Diese micro-optimierungen haben am ende nochmal 100ms eingespart, was schon ziemlich krass ist.
400 ms um insgesamt 8192x2048 blöcke zu durchlaufen und eine richtig coole lichtsache einzubauen :>

Im moment arbeite ich an der floodfill version, die leider etwa so lahm ist wie meine erste version mit unnötigen funktionsaufrufen. Aber ich optimiere weiterhin... Smile

	DAK	Mi, Apr 24, 2013 14:54 Antworten mit Zitat
Mit Floodfill ist jetzt hald die Sache, dass der meist rekursiv arbeitet, was heißt, du hast haufenweise Funktionsaufrufe.
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mi, Apr 24, 2013 14:54
Antworten mit Zitat

Mit Floodfill ist jetzt hald die Sache, dass der meist rekursiv arbeitet, was heißt, du hast haufenweise Funktionsaufrufe.

Gewinner der 6. und der 68. BlitzCodeCompo

	PhillipK	Mi, Apr 24, 2013 14:56 Antworten mit Zitat
AMul sei dank, ist version eins keine rekursive sache. Eine simple linked list wo einträge von vorne entfernt und evtl andere hinten angefügt werden. Ich vermeide für die lichtberechnung grade jegliche form von funktionsaufruf Du hast mir die augen geöffnet. ^^

PhillipK

Mi, Apr 24, 2013 14:56
Antworten mit Zitat

AMul sei dank, ist version eins keine rekursive sache. Eine simple linked list wo einträge von vorne entfernt und evtl andere hinten angefügt werden.

Ich vermeide für die lichtberechnung grade jegliche form von funktionsaufruf Razz

Du hast mir die augen geöffnet. ^^

	aMul Sieger des Minimalist Compo 01/13	Mi, Apr 24, 2013 15:03 Antworten mit Zitat
Psst, bei Benutzung der BMax internen Listen sind hinzufügen und entfernen Funktionen. Aber ich hab keine Ahnung wie die von der Geschwindigkeit sind. Ich hab noch nie ersthaft in BM gearbeitet. Aber generell lässt sich mit einem Queue ein recht effizienter Floodfill Algo schreiben. Insbesondere auch einer wie dieser, wo der Füllwert mit jedem Schritt abnimmt, da die Einträge im Queue dadurch automatisch sortiert sind.
Panic Pong - ultimate action mashup of Pong and Breakout <= aktives Spiele-Projekt, Downloads mit vielen bunten Farben! advASCIIdraw - the advanced ASCII art program <= aktives nicht-Spiele-Projekt, must-have für ASCII/roguelike/dungeon-crawler fans! Alter BB-Kram: ThroughTheAsteroidBelt - mit Quelltext! \| RGB-Palette in 32²-Textur / Farbige Beleuchtung mit Dot3 \| Stereoskopie in Blitz3D \| Teleport-Animation Screensaver

aMul

Sieger des Minimalist Compo 01/13

Mi, Apr 24, 2013 15:03
Antworten mit Zitat

Psst, bei Benutzung der BMax internen Listen sind hinzufügen und entfernen Funktionen. Mr. Green

Aber ich hab keine Ahnung wie die von der Geschwindigkeit sind. Ich hab noch nie ersthaft in BM gearbeitet.

Aber generell lässt sich mit einem Queue ein recht effizienter Floodfill Algo schreiben. Insbesondere auch einer wie dieser, wo der Füllwert mit jedem Schritt abnimmt, da die Einträge im Queue dadurch automatisch sortiert sind.

	DAK	Mi, Apr 24, 2013 16:06 Antworten mit Zitat
Da der FloodFill sowieso eine Maximalreichweite hat, und du somit eine Obergrenze hast, wie viele Felder gefüllt werden können, nimm statt der Liste doch lieber ein Array mit einer Laufvariable. Dann hast du da gar keine Funktionen. Und ums noch billiger zu machen, erstell nicht bei jedem neuen Floodfill ein eigenes Array sondern setz in dem einen Array manuell jeden Eintrag auf 0 (oder besser -1, da 0 ja verwendet werden kann). So sparst du dir die Kosten fürs Allozieren vom Speicher. Edit: Ein klein wenig Offtopic, aber ich hab das mal in Java nachgestellt: Code: [AUSKLAPPEN] [EINKLAPPEN] private static int i = 50; public static void main(String[] args) { for (int t=0;t<50;t++) { long ms = System.currentTimeMillis(); for (int x=0;x<8192;x++) { for (int y=0;y<2048;y++) { if (i==x && i==y) { i = i+1; } } } System.out.println("direct took "+(System.currentTimeMillis()-ms)+" ms."); i = 50; ms = System.currentTimeMillis(); for (int x=0;x<8192;x++) { for (int y=0;y<2048;y++) { if (getI()==x && getI()==y) { setI(getI()+1); } } } System.out.println("method took "+(System.currentTimeMillis()-ms)+" ms.\n"); } } private static int getI() { return i; } private static void setI(int _i) { i = _i; } Dieses Programm testet nur, wie schnell Funktionsaufrufe und direkter Zugriff ist. Dabei ist es hier aber so, dass der Zugriff über Funktionen sogar schneller (!!) ist, als der direkte Zugriff. Scheint also wirklich nur ein Blitz Problem zu sein (B3D hatte das gleiche Problem auch, nehme mal an, dass B+ und B2D da auch nicht anders drauf waren). EDIT 2: Da ist ein Wurm drinnen gewesen. Hab ihn behoben, jetzt braucht auch in Java der Funktionsaufruf ziemlich genau 4 mal so lange wie ohne Funktionsaufruf (3ms Direkt, 12ms per Funktionsaufruf). Danke Thunder!
Gewinner der 6. und der 68. BlitzCodeCompo

DAK

Mi, Apr 24, 2013 16:06
Antworten mit Zitat

Da der FloodFill sowieso eine Maximalreichweite hat, und du somit eine Obergrenze hast, wie viele Felder gefüllt werden können, nimm statt der Liste doch lieber ein Array mit einer Laufvariable. Dann hast du da gar keine Funktionen. Und ums noch billiger zu machen, erstell nicht bei jedem neuen Floodfill ein eigenes Array sondern setz in dem einen Array manuell jeden Eintrag auf 0 (oder besser -1, da 0 ja verwendet werden kann). So sparst du dir die Kosten fürs Allozieren vom Speicher.

Edit: Ein klein wenig Offtopic, aber ich hab das mal in Java nachgestellt:

Code: [AUSKLAPPEN]

private static int i = 50;

public static void main(String[] args) {
for (int t=0;t<50;t++) {
long ms = System.currentTimeMillis();
for (int x=0;x<8192;x++) {
for (int y=0;y<2048;y++) {
if (i==x && i==y) {
i = i+1;
}
}
}
System.out.println("direct took "+(System.currentTimeMillis()-ms)+" ms.");
i = 50;
ms = System.currentTimeMillis();
for (int x=0;x<8192;x++) {
for (int y=0;y<2048;y++) {
if (getI()==x && getI()==y) {
setI(getI()+1);
}
}
}
System.out.println("method took "+(System.currentTimeMillis()-ms)+" ms.\n");
}
}

private static int getI() {
return i;
}
private static void setI(int _i) {
i = _i;
}

Dieses Programm testet nur, wie schnell Funktionsaufrufe und direkter Zugriff ist. Dabei ist es hier aber so, dass der Zugriff über Funktionen sogar schneller (!!) ist, als der direkte Zugriff. Scheint also wirklich nur ein Blitz Problem zu sein (B3D hatte das gleiche Problem auch, nehme mal an, dass B+ und B2D da auch nicht anders drauf waren).

EDIT 2: Da ist ein Wurm drinnen gewesen. Hab ihn behoben, jetzt braucht auch in Java der Funktionsaufruf ziemlich genau 4 mal so lange wie ohne Funktionsaufruf (3ms Direkt, 12ms per Funktionsaufruf).
Danke Thunder!

Gewinner der 6. und der 68. BlitzCodeCompo

Übersicht

BlitzMax, BlitzMax NG

Allgemein

Nach Oben

BlitzBasic Portal

Arraydurchlauf "langsam"

Betreff: Arraydurchlauf "langsam"