Arraydurchlauf "langsam"

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

 

PhillipK

Betreff: Arraydurchlauf "langsam"

BeitragMi, Apr 24, 2013 10:50
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Smile
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

BeitragMi, Apr 24, 2013 11:15
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 11:28
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 11:44
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 13:08
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 14:45
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 14:54
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 14:56
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Apr 24, 2013 15:03
Antworten mit Zitat
Benutzer-Profile anzeigen
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.
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

BeitragMi, Apr 24, 2013 16:06
Antworten mit Zitat
Benutzer-Profile anzeigen
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

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group