Performance-Optimierung

Übersicht

BlitzMax, BlitzMax NG

FAQs und Tutorials

	Fetze Betreff: Performance-Optimierung	Mi, Aug 24, 2005 13:36 Antworten mit Zitat
Ich habe mich in letzter Zeit recht ausgiebig mit Performance-Optimierungen beschäftigt, um noch einige versteckte FPS herausholen zu können. Hier mal ein paar Speedvergleiche, vielleicht hilft es ja dem einen oder anderen: 1. Array vs. TList Hierfür verwendete ich folgendes Testprogramm: Code: [AUSKLAPPEN] [EINKLAPPEN] Const NUM:Int = 3 Global Array :String[NUM + 1] Global LinkedList :TList = New TList Global iTempTime :Int Local iLoop :Int Local sTempString :String For iLoop = 0 To NUM sTempString = String(Rand(5)) Array[iLoop] = sTempString LinkedList.AddLast sTempString Next Delay 500 Local iLoop2 :Int FlushMem iTempTime = MilliSecs() For iLoop = 1 To 1000000 For iLoop2 = 0 To NUM 'Print Array[iLoop2] Next Next Print "Milliseconds Num-Array: " + (MilliSecs() - iTempTime) Local sLoop :String FlushMem iTempTime = MilliSecs() For iLoop = 1 To 1000000 For sLoop = EachIn Array 'Print sLoop Next Next Print "Milliseconds EachIn Array: " + (MilliSecs() - iTempTime) FlushMem iTempTime = MilliSecs() For iLoop = 1 To 1000000 For sLoop = EachIn LinkedList 'Print sLoop Next FlushMem Next Print "Milliseconds EachIn LinkedList: " + (MilliSecs() - iTempTime) Ich habe es bereits auf die jeweils höchste Geschwindigkeit optimiert, daher auch FlushMem innerhalb der LinkedList-Schleife. ................................................... Test Nr. 1 - Kleine Objektanzahlen: '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' Vier Strings, Debugmode deaktiviert: Num-Array: 7 EachIn-Arrays: 9 EachIn-List: 227 Vier Strings, Debugmode aktiviert: Num-Array: 15 EachIn-Arrays: 12 EachIn-List: 731 Acht Strings, Debugmode deaktiviert: Num-Array: 13 EachIn-Arrays: 14 EachIn-List: 325 Acht Strings, Debugmode aktiviert: Num-Array: 23 EachIn-Arrays: 18 EachIn-List: 1106 16 Strings, Debugmode deaktiviert: Num-Array: 30 EachIn-Arrays: 34 EachIn-List: 501 16 Strings, Debugmode aktiviert: Num-Array: 66 EachIn-Arrays: 37 EachIn-List: 1920 ................................................... Test Nr. 2 - Große Objektanzahlen: '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' (Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 10000) 500 Strings, Debugmode deaktiviert: Num-Array: 3 EachIn-Arrays: 8 EachIn-List: 113 500 Strings, Debugmode aktiviert: Num-Array: 16 EachIn-Arrays: 7 EachIn-List: 487 (Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 1000) 5000 Strings, Debugmode deaktiviert: Num-Array: 4 EachIn-Arrays: 7 EachIn-List: 133 5000 Strings, Debugmode aktiviert: Num-Array: 17 EachIn-Arrays: 7 EachIn-List: 495 (Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 100) 50000 Strings, Debugmode deaktiviert: Num-Array: 5 EachIn-Arrays: 7 EachIn-List: 167 50000 Strings, Debugmode aktiviert: Num-Array: 17 EachIn-Arrays: 10 EachIn-List: 537 ............................................... Test Nr. 3 - Ingame-Verbrauch: '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' Da sich Arrays sowohl bei großen Objektanzahlen als auch bei kleinen Objektanzahlen als weitaus schneller erwiesen haben, lasse ich sie hier bei der Auflistung einfach weg. Ihre Tests ergaben in diesem Durchlauf ohnehin alle "0". In diesem Testlauf entferne ich die äussere For-next-Schleife, um zu demonstrieren, wie viele Millisekunden pro Frame allein durch das durchlaufen aller Objekte verloren gehen. Es zeigten sich jedoch erst ab Objektanzahlen von 50000 erste Auswirkungen. Bei 50000 durchzulaufenden Objekten benötigt eine LinkedList 5 Millisekunden. Um 60 FPS zu erreichen, darf ein Programm insgesamt pro Frame maximal 16,6 Millisekunden verbrauchen. Da merkliche Unterschiede zwischen LinkedList und Array aber erst ab extrem großen Objektanzahlen auftreten, kann man sie denke ich vernachlässigen. *2. X X vs. X ^ 2** Wie wahrscheinlich die meisten von euch wissen, ist X * X weitaus schneller als X ^ 2. Trotzem eine Demonstration: Code: [AUSKLAPPEN] [EINKLAPPEN] Global iTempTime :Int Global iA :Int Global iB :Int Delay 500 Local iloop :Int FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iA = iB ^ 2 Next Print "Milliseconds X ^ 2: " + (MilliSecs() - iTempTime) FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iA = iB * iB Next Print "Milliseconds X * X: " + (MilliSecs() - iTempTime) FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iA = iB ^ 20 Next Print "Milliseconds X ^ 20: " + (MilliSecs() - iTempTime) FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iA = iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB Next Print "Milliseconds X * X * ... (20): " + (MilliSecs() - iTempTime) X^2, Debug deaktiviert: 223 XX, Debug deaktiviert: 20 X^20, Debug deaktiviert: 228 XX...(20), Debug deaktiviert: 212 X^2, Debug aktiviert: 602 XX, Debug aktiviert: 58 X^20, Debug aktiviert: 597 XX...(20), Debug aktiviert: 275 Fazit: Wenn man eine Zahl mit einer beliebigen, geraden anderen potenzieren will, sollte man generell das ganze mit "" ausschreiben, es sei denn, letztere Zahl liegt im Bereich über 20. Ab dort ist "^" effektiver. 3. Local vs. Global* Obwohl ohnehin jedem geraten sei, nur dann globale Variablen zu verwenden, wenn sie auch wirklich nötig sind, hier mal ein Geschwindigkeitsvergleich im Bezug auf auslesen der Variable und Zuweisen eines neues Werts: Code: [AUSKLAPPEN] [EINKLAPPEN] Global iTempTime :Int Global iA :Int Local iB :Int Local iLoop :Int Delay 500 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iB = iB + 1 Next Print "Local: " + (MilliSecs() - iTempTime) FlushMem iTempTime = MilliSecs() For iLoop = 1 To 10000000 iA = iA + 1 Next Print "Global: " + (MilliSecs() - iTempTime) Debug deaktiviert: Local: 14 Global: 27 Debug aktiviert: Local: 52 Global: 73 Witzigerweise ist der Unterschied etwas geringer, wenn ich Floats verwende. Abgesehen mal vom Debug. Debug deaktiviert, Float: Local: 58 Global: 66 Debug aktiviert, Float: Local: 65 Global: 120 4. Variable definieren vs. Mehrmals berechnen Es erscheint auf den ersten Blick logisch, natürlich eine temporäre Variable zu verwenden, um einen gerade berechneten Wert kurzzeitig abzuspeichern. Aber auch das braucht Zeit. Ich hab hier mit Durchschnittszeiten aus 100 Durchläufen gearbeitet, da das genauer ist. Tatsächlich ist es manchmal schneller, etwas mehrfach zu berechnen, als eine Variable zu verwenden: Ohne Debug: Integer, Addition, Variable: 5.07999992 Integer, Addition, Mehrfach: 4.98999977 Integer, Subtraktion, Variable: 5.13000011 Integer, Subtraktion, Mehrfach: 4.84999990 Integer, Multiplikation, Variable: 5.38999987 Integer, Multiplikation, Mehrfach: 4.61999989 Integer, Division, Variable: 5.80999994 Integer, Division, Mehrfach: 4.86999989 Float, Addition, Variable: 6.17000008 Float, Addition, Mehrfach: 5.26999998 Float, Subtraktion, Variable: 5.07999992 Float, Subtraktion, Mehrfach: 4.78999996 Float, Multiplikation, Variable: 6.38000011 Float, Multiplikation, Mehrfach: 5.73999977 Float, Division, Variable: 5.73999977 Float, Division, Mehrfach: 5.00000000 Hier der Code: Code: [AUSKLAPPEN] [EINKLAPPEN] Global iTempTime :Int Global fTempTime2 :Float Local iLoop :Int Delay 500 fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_1_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Addition, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_1_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Addition, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_2_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Subtraktion, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_2_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Subtraktion, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_3_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Multiplikation, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_3_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Multiplikation, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_4_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Division, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test1_4_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Integer, Division, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_1_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Addition, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_1_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Addition, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_2_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Subtraktion, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_2_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Subtraktion, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_3_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Multiplikation, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_3_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Multiplikation, Mehrfach: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_4_1() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Division, Variable: " + (fTempTime2 / 100.0) fTempTime2 = 0 For iLoop = 1 To 100 FlushMem iTempTime = MilliSecs() For iLoop = 1 To 100000000 Test2_4_2() Next fTempTime2:+ (MilliSecs() - iTempTime) Next Print "Float, Division, Mehrfach: " + (fTempTime2 / 100.0) Function Test1_1_1:Int() Local iX:Int = (2 + 3) Return (iX + iX) End Function Function Test1_1_2:Int() Return ((2 + 3) + (2 + 3)) End Function Function Test1_2_1:Int() Local iX:Int = (2 - 3) Return (iX + iX) End Function Function Test1_2_2:Int() Return ((2 - 3) + (2 - 3)) End Function Function Test1_3_1:Int() Local iX:Int = (2 * 3) Return (iX + iX) End Function Function Test1_3_2:Int() Return ((2 * 3) + (2 * 3)) End Function Function Test1_4_1:Int() Local iX:Int = (2 / 3) Return (iX + iX) End Function Function Test1_4_2:Int() Return ((2 / 3) + (2 / 3)) End Function Function Test2_1_1:Float() Local iX:Float = (2.0 + 3.0) Return (iX + iX) End Function Function Test2_1_2:Float() Return ((2.0 + 3.0) + (2.0 + 3.0)) End Function Function Test2_2_1:Float() Local iX:Float = (2.0 - 3.0) Return (iX + iX) End Function Function Test2_2_2:Float() Return ((2.0 - 3.0) + (2.0 - 3.0)) End Function Function Test2_3_1:Float() Local iX:Float = (2.0 * 3.0) Return (iX + iX) End Function Function Test2_3_2:Float() Return ((2.0 * 3.0) + (2.0 * 3.0)) End Function Function Test2_4_1:Float() Local iX:Float = (2.0 / 3.0) Return (iX + iX) End Function Function Test2_4_2:Float() Return ((2.0 / 3.0) + (2.0 / 3.0)) End Function Das ganze hängt aber wahrscheinlich von tausenden von Faktoren ab,weswegen man das nur bei wirklich oft genutzten Funktionen beachten kann. Wo wir gerade dabei sind: 5. Nützliche Funktionen Hier ein paar Funktionen, die man öfters mal braucht. Ich habe sie so weit ich konnte optimiert und wenn man in jeder Situation nur die einsetzt, die man auch wirklich braucht und für ein paar FPS bereit ist, etwas nicht benötigte Genauigkeit aufzugeben, können sie wirklich nützlich sein. Ich habe sie alle mehrfach in verschiedenen Varianten getestet, sie sollten also hinreichend optimiert sein. Code: [AUSKLAPPEN] [EINKLAPPEN] 'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück. Function Distance:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0) Return Sqr((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2)) End Function 'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück, ohne vorher die Wurzel zu ziehen. Ein bischen schneller, dafür nicht für alles geeignet. Function DistanceQuad:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0) Return ((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2)) End Function 'Gibt die ungefähre (Integer) Entfernung zwischen den beiden angegebenen Punkten zurück. Function IntDistance:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0) Return Sqr((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2)) End Function 'Gibt die ungefähre (Integer) Entfernung zwischen den beiden angegebenen Punkten zurück, ohne vorher die Wurzel zu ziehen. Ein bischen schneller, dafür nicht für alles geeignet. Function IntDistanceQuad:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0) Return ((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2)) End Function 'Schätzt die Distanz zwischen 2 Punkten ab. Als Parameter werden jeweils bereits die Differenzen verlangt. 'iParXD = (iParX1 - iParX2) 'iParYD = (iParY1 - iParY2) Function ApproxDistance:Int(iParXD:Int, iParYD:Int) Local iMin:Int Local iMax:Int If iParXD < 0 Then iParXD = -iParXD If iParYD < 0 Then iParYD = -iParYD If iParXD < iParYD Then iMin = iParXD iMax = iParYD Else iMin = iParYD iMax = iParXD EndIf Return (((iMax Shl 8) + (iMax Shl 3) - (iMax Shl 4) - (iMax Shl 1) + (iMin Shl 7) - (iMin Shl 5) + (iMin Shl 3) - (iMin Shl 1)) Shr 8) End Function 'Liefert den Winkel von Punkt 2 zu Punkt 1 zurück. 'Beispiel: Punkt 1 liegt bei 0,0, Punkt 2 bei 10,0 'Dann wird der Winkel 90 zurückgeliefert. Function Angle:Float(fX1:Float, fY1:Float, fX2:Float, fY2:Float) Return (ATan2(fY2 - fY1, fX2 - fX1) + 450.0) Mod 360.0 End Function 'Wie Angle, aber etwas schneller. Dafür arbeitet IntAngle nur mit Integer-Werten, folglich treten Rundungsfehler auf. Function IntAngle:Float(iX1:Int, iY1:Int, iX2:Int, iY2:Int) Return (Int(ATan2(iY2 - iY1, iX2 - iX1)) + 450) Mod 360 End Function 'Dreht und Skaliert die angegebenen Koordinaten im angegebenen Winkel um eine Mitte die Mitte 0,0. Function TransformCoord:Byte(fVarX:Float Var, fVarY:Float Var, fAngle:Float, fParCenterX:Float = 0.0, fParCenterY:Float = 0.0, fScale:Float = 1.0) Local fTempAngle:Float = Angle(fParCenterX, fParCenterY, fVarX, fVarY) + fAngle Local fTempDist:Float = Distance(fVarX, fVarY, fParCenterX, fParCenterY) * fScale fVarX = fParCenterX + Sin(fTempAngle) * fTempDist fVarY = fParCenterY - Cos(fTempAngle) * fTempDist Return True End Function 'Dreht und Skaliert die angegebenen Koordinaten im angegebenen Winkel um die Mitte 0,0. Ungenauer als die Float-Funktion, dafür aber schneller. Nur für Werte ab 10 gedacht, ansonsten extremst ungenau. Function IntTransformCoord:Byte(iVarX:Int Var, iVarY:Int Var, iAngle:Int, iParCenterX:Int = 0.0, iParCenterY:Int = 0.0, fScale:Float = 1.0) Local iTempAngle:Int = IntAngle(iParCenterX, iParCenterY, iVarX, iVarY) + iAngle Local iTempDist:Int = IntDistance(iVarX, iVarY, iParCenterX, iParCenterY) * fScale iVarX = iParCenterX + Sin(iTempAngle) * iTempDist iVarY = iParCenterY - Cos(iTempAngle) * iTempDist Return True End Function Ich hoffe, das hier bringt irgendwem was. Ich gebe keine Garantie auf Richtigkeit und würde mic hfreuen, wenn das ganze von einigen Experten bestätigt oder widerlegt werden könnte.

Fetze

Betreff: Performance-Optimierung

Mi, Aug 24, 2005 13:36
Antworten mit Zitat

Ich habe mich in letzter Zeit recht ausgiebig mit Performance-Optimierungen beschäftigt, um noch einige versteckte FPS herausholen zu können. Hier mal ein paar Speedvergleiche, vielleicht hilft es ja dem einen oder anderen:

1. Array vs. TList
Hierfür verwendete ich folgendes Testprogramm:
Code: [AUSKLAPPEN]

Const NUM:Int = 3

Global Array    :String[NUM + 1]
Global LinkedList :TList = New TList
Global iTempTime :Int

Local iLoop       :Int
Local sTempString :String
For iLoop = 0 To NUM
sTempString = String(Rand(5))
Array[iLoop] = sTempString
LinkedList.AddLast sTempString
Next

Delay 500

Local iLoop2    :Int
FlushMem
iTempTime = MilliSecs()

For iLoop = 1 To 1000000
For iLoop2 = 0 To NUM
   'Print Array[iLoop2]
Next
Next

Print "Milliseconds Num-Array: " + (MilliSecs() - iTempTime)

Local sLoop       :String
FlushMem
iTempTime = MilliSecs()

For iLoop = 1 To 1000000
For sLoop = EachIn Array
   'Print sLoop
Next
Next

Print "Milliseconds EachIn Array: " + (MilliSecs() - iTempTime)

FlushMem
iTempTime = MilliSecs()

For iLoop = 1 To 1000000
For sLoop = EachIn LinkedList
   'Print sLoop
Next
FlushMem
Next

Print "Milliseconds EachIn LinkedList: " + (MilliSecs() - iTempTime)

Ich habe es bereits auf die jeweils höchste Geschwindigkeit optimiert, daher auch FlushMem innerhalb der LinkedList-Schleife.
...................................................
Test Nr. 1 - Kleine Objektanzahlen:
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Vier Strings, Debugmode deaktiviert:
Num-Array: 7
EachIn-Arrays: 9
EachIn-List: 227

Vier Strings, Debugmode aktiviert:
Num-Array: 15
EachIn-Arrays: 12
EachIn-List: 731

Acht Strings, Debugmode deaktiviert:
Num-Array: 13
EachIn-Arrays: 14
EachIn-List: 325

Acht Strings, Debugmode aktiviert:
Num-Array: 23
EachIn-Arrays: 18
EachIn-List: 1106

16 Strings, Debugmode deaktiviert:
Num-Array: 30
EachIn-Arrays: 34
EachIn-List: 501

16 Strings, Debugmode aktiviert:
Num-Array: 66
EachIn-Arrays: 37
EachIn-List: 1920

...................................................
Test Nr. 2 - Große Objektanzahlen:
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
(Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 10000)

500 Strings, Debugmode deaktiviert:
Num-Array: 3
EachIn-Arrays: 8
EachIn-List: 113

500 Strings, Debugmode aktiviert:
Num-Array: 16
EachIn-Arrays: 7
EachIn-List: 487

(Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 1000)

5000 Strings, Debugmode deaktiviert:
Num-Array: 4
EachIn-Arrays: 7
EachIn-List: 133

5000 Strings, Debugmode aktiviert:
Num-Array: 17
EachIn-Arrays: 7
EachIn-List: 495

(Anstatt 1000000 Schleifendurchläufe, teste ich hier mit 100)

50000 Strings, Debugmode deaktiviert:
Num-Array: 5
EachIn-Arrays: 7
EachIn-List: 167

50000 Strings, Debugmode aktiviert:
Num-Array: 17
EachIn-Arrays: 10
EachIn-List: 537

...............................................
Test Nr. 3 - Ingame-Verbrauch:
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Da sich Arrays sowohl bei großen Objektanzahlen als auch bei kleinen Objektanzahlen als weitaus schneller erwiesen haben, lasse ich sie hier bei der Auflistung einfach weg. Ihre Tests ergaben in diesem Durchlauf ohnehin alle "0". In diesem Testlauf entferne ich die äussere For-next-Schleife, um zu demonstrieren, wie viele Millisekunden pro Frame allein durch das durchlaufen aller Objekte verloren gehen. Es zeigten sich jedoch erst ab Objektanzahlen von 50000 erste Auswirkungen. Bei 50000 durchzulaufenden Objekten benötigt eine LinkedList 5 Millisekunden. Um 60 FPS zu erreichen, darf ein Programm insgesamt pro Frame maximal 16,6 Millisekunden verbrauchen. Da merkliche Unterschiede zwischen LinkedList und Array aber erst ab extrem großen Objektanzahlen auftreten, kann man sie denke ich vernachlässigen.

2. X * X vs. X ^ 2
Wie wahrscheinlich die meisten von euch wissen, ist X * X weitaus schneller als X ^ 2. Trotzem eine Demonstration:
Code: [AUSKLAPPEN]

Global iTempTime :Int
Global iA       :Int
Global iB       :Int

Delay 500

Local iloop       :Int

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iA = iB ^ 2
Next
Print "Milliseconds X ^ 2: " + (MilliSecs() - iTempTime)

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iA = iB * iB
Next
Print "Milliseconds X * X: " + (MilliSecs() - iTempTime)

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iA = iB ^ 20
Next
Print "Milliseconds X ^ 20: " + (MilliSecs() - iTempTime)

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iA = iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB * iB
Next
Print "Milliseconds X * X * ... (20): " + (MilliSecs() - iTempTime)

X^2, Debug deaktiviert: 223
X*X, Debug deaktiviert: 20
X^20, Debug deaktiviert: 228
X*X*...(20), Debug deaktiviert: 212

X^2, Debug aktiviert: 602
X*X, Debug aktiviert: 58
X^20, Debug aktiviert: 597
X*X*...(20), Debug aktiviert: 275

Fazit: Wenn man eine Zahl mit einer beliebigen, geraden anderen potenzieren will, sollte man generell das ganze mit "*" ausschreiben, es sei denn, letztere Zahl liegt im Bereich über 20. Ab dort ist "^" effektiver.

3. Local vs. Global
Obwohl ohnehin jedem geraten sei, nur dann globale Variablen zu verwenden, wenn sie auch wirklich nötig sind, hier mal ein Geschwindigkeitsvergleich im Bezug auf auslesen der Variable und Zuweisen eines neues Werts:
Code: [AUSKLAPPEN]

Global iTempTime :Int
Global iA       :Int
Local iB       :Int
Local iLoop       :Int

Delay 500

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iB = iB + 1
Next
Print "Local: " + (MilliSecs() - iTempTime)

FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 10000000
iA = iA + 1
Next
Print "Global: " + (MilliSecs() - iTempTime)

Debug deaktiviert:
Local: 14
Global: 27

Debug aktiviert:
Local: 52
Global: 73

Witzigerweise ist der Unterschied etwas geringer, wenn ich Floats verwende. Abgesehen mal vom Debug.

Debug deaktiviert, Float:
Local: 58
Global: 66

Debug aktiviert, Float:
Local: 65
Global: 120

4. Variable definieren vs. Mehrmals berechnen
Es erscheint auf den ersten Blick logisch, natürlich eine temporäre Variable zu verwenden, um einen gerade berechneten Wert kurzzeitig abzuspeichern. Aber auch das braucht Zeit. Ich hab hier mit Durchschnittszeiten aus 100 Durchläufen gearbeitet, da das genauer ist. Tatsächlich ist es manchmal schneller, etwas mehrfach zu berechnen, als eine Variable zu verwenden:

Ohne Debug:
Integer, Addition, Variable: 5.07999992
Integer, Addition, Mehrfach: 4.98999977
Integer, Subtraktion, Variable: 5.13000011
Integer, Subtraktion, Mehrfach: 4.84999990
Integer, Multiplikation, Variable: 5.38999987
Integer, Multiplikation, Mehrfach: 4.61999989
Integer, Division, Variable: 5.80999994
Integer, Division, Mehrfach: 4.86999989
Float, Addition, Variable: 6.17000008
Float, Addition, Mehrfach: 5.26999998
Float, Subtraktion, Variable: 5.07999992
Float, Subtraktion, Mehrfach: 4.78999996
Float, Multiplikation, Variable: 6.38000011
Float, Multiplikation, Mehrfach: 5.73999977
Float, Division, Variable: 5.73999977
Float, Division, Mehrfach: 5.00000000

Hier der Code:
Code: [AUSKLAPPEN]

Global iTempTime :Int
Global fTempTime2 :Float
Local iLoop       :Int
Delay 500

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_1_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Addition, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_1_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Addition, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_2_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Subtraktion, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_2_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Subtraktion, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_3_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Multiplikation, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_3_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Multiplikation, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_4_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Division, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test1_4_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Integer, Division, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_1_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Addition, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_1_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Addition, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_2_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Subtraktion, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_2_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Subtraktion, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_3_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Multiplikation, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_3_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Multiplikation, Mehrfach: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_4_1()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Division, Variable: " + (fTempTime2 / 100.0)

fTempTime2 = 0
For iLoop = 1 To 100
FlushMem
iTempTime = MilliSecs()
For iLoop = 1 To 100000000
   Test2_4_2()
Next
fTempTime2:+ (MilliSecs() - iTempTime)
Next
Print "Float, Division, Mehrfach: " + (fTempTime2 / 100.0)

Function Test1_1_1:Int()
Local iX:Int = (2 + 3)
Return (iX + iX)
End Function

Function Test1_1_2:Int()
Return ((2 + 3) + (2 + 3))
End Function

Function Test1_2_1:Int()
Local iX:Int = (2 - 3)
Return (iX + iX)
End Function

Function Test1_2_2:Int()
Return ((2 - 3) + (2 - 3))
End Function

Function Test1_3_1:Int()
Local iX:Int = (2 * 3)
Return (iX + iX)
End Function

Function Test1_3_2:Int()
Return ((2 * 3) + (2 * 3))
End Function

Function Test1_4_1:Int()
Local iX:Int = (2 / 3)
Return (iX + iX)
End Function

Function Test1_4_2:Int()
Return ((2 / 3) + (2 / 3))
End Function

Function Test2_1_1:Float()
Local iX:Float = (2.0 + 3.0)
Return (iX + iX)
End Function

Function Test2_1_2:Float()
Return ((2.0 + 3.0) + (2.0 + 3.0))
End Function

Function Test2_2_1:Float()
Local iX:Float = (2.0 - 3.0)
Return (iX + iX)
End Function

Function Test2_2_2:Float()
Return ((2.0 - 3.0) + (2.0 - 3.0))
End Function

Function Test2_3_1:Float()
Local iX:Float = (2.0 * 3.0)
Return (iX + iX)
End Function

Function Test2_3_2:Float()
Return ((2.0 * 3.0) + (2.0 * 3.0))
End Function

Function Test2_4_1:Float()
Local iX:Float = (2.0 / 3.0)
Return (iX + iX)
End Function

Function Test2_4_2:Float()
Return ((2.0 / 3.0) + (2.0 / 3.0))
End Function

Das ganze hängt aber wahrscheinlich von tausenden von Faktoren ab,weswegen man das nur bei wirklich oft genutzten Funktionen beachten kann. Wo wir gerade dabei sind:

5. Nützliche Funktionen
Hier ein paar Funktionen, die man öfters mal braucht. Ich habe sie so weit ich konnte optimiert und wenn man in jeder Situation nur die einsetzt, die man auch wirklich braucht und für ein paar FPS bereit ist, etwas nicht benötigte Genauigkeit aufzugeben, können sie wirklich nützlich sein. Ich habe sie alle mehrfach in verschiedenen Varianten getestet, sie sollten also hinreichend optimiert sein.
Code: [AUSKLAPPEN]

'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück.
Function Distance:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0)
Return Sqr((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2))
End Function

'Gibt die Entfernung zwischen den beiden angegebenen Punkten zurück, ohne vorher die Wurzel zu ziehen. Ein bischen schneller, dafür nicht für alles geeignet.
Function DistanceQuad:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0)
Return ((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2))
End Function

'Gibt die ungefähre (Integer) Entfernung zwischen den beiden angegebenen Punkten zurück.
Function IntDistance:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0)
Return Sqr((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2))
End Function

'Gibt die ungefähre (Integer) Entfernung zwischen den beiden angegebenen Punkten zurück, ohne vorher die Wurzel zu ziehen. Ein bischen schneller, dafür nicht für alles geeignet.
Function IntDistanceQuad:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0)
Return ((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2))
End Function

'Schätzt die Distanz zwischen 2 Punkten ab. Als Parameter werden jeweils bereits die Differenzen verlangt.
'iParXD = (iParX1 - iParX2)
'iParYD = (iParY1 - iParY2)
Function ApproxDistance:Int(iParXD:Int, iParYD:Int)
Local iMin:Int
Local iMax:Int

If iParXD < 0 Then iParXD = -iParXD
If iParYD < 0 Then iParYD = -iParYD
If iParXD < iParYD Then
   iMin = iParXD
   iMax = iParYD
Else
   iMin = iParYD
   iMax = iParXD
EndIf

Return (((iMax Shl 8) + (iMax Shl 3) - (iMax Shl 4) - (iMax Shl 1) + (iMin Shl 7) - (iMin Shl 5) + (iMin Shl 3) - (iMin Shl 1)) Shr 8)
End Function

'Liefert den Winkel von Punkt 2 zu Punkt 1 zurück.
'Beispiel: Punkt 1 liegt bei 0,0, Punkt 2 bei 10,0
'Dann wird der Winkel 90 zurückgeliefert.
Function Angle:Float(fX1:Float, fY1:Float, fX2:Float, fY2:Float)
Return (ATan2(fY2 - fY1, fX2 - fX1) + 450.0) Mod 360.0
End Function

'Wie Angle, aber etwas schneller. Dafür arbeitet IntAngle nur mit Integer-Werten, folglich treten Rundungsfehler auf.
Function IntAngle:Float(iX1:Int, iY1:Int, iX2:Int, iY2:Int)
Return (Int(ATan2(iY2 - iY1, iX2 - iX1)) + 450) Mod 360
End Function

'Dreht und Skaliert die angegebenen Koordinaten im angegebenen Winkel um eine Mitte die Mitte 0,0.
Function TransformCoord:Byte(fVarX:Float Var, fVarY:Float Var, fAngle:Float, fParCenterX:Float = 0.0, fParCenterY:Float = 0.0, fScale:Float = 1.0)
Local fTempAngle:Float = Angle(fParCenterX, fParCenterY, fVarX, fVarY) + fAngle
Local fTempDist:Float = Distance(fVarX, fVarY, fParCenterX, fParCenterY) * fScale
fVarX = fParCenterX + Sin(fTempAngle) * fTempDist
fVarY = fParCenterY - Cos(fTempAngle) * fTempDist
Return True
End Function

'Dreht und Skaliert die angegebenen Koordinaten im angegebenen Winkel um die Mitte 0,0. Ungenauer als die Float-Funktion, dafür aber schneller. Nur für Werte ab 10 gedacht, ansonsten extremst ungenau.
Function IntTransformCoord:Byte(iVarX:Int Var, iVarY:Int Var, iAngle:Int, iParCenterX:Int = 0.0, iParCenterY:Int = 0.0, fScale:Float = 1.0)
Local iTempAngle:Int = IntAngle(iParCenterX, iParCenterY, iVarX, iVarY) + iAngle
Local iTempDist:Int = IntDistance(iVarX, iVarY, iParCenterX, iParCenterY) * fScale
iVarX = iParCenterX + Sin(iTempAngle) * iTempDist
iVarY = iParCenterY - Cos(iTempAngle) * iTempDist
Return True
End Function

Ich hoffe, das hier bringt irgendwem was. Ich gebe keine Garantie auf Richtigkeit und würde mic hfreuen, wenn das ganze von einigen Experten bestätigt oder widerlegt werden könnte.

	Firstdeathmaker	Mi, Aug 24, 2005 14:44 Antworten mit Zitat
Jaaa! Das ist eine sehr schöne Sammlung. Man braucht zwar nicht alles, aber man kann sich benötigtes einfach rauspicken, danke!
www.illusion-games.de Space War 3 \| Space Race \| Galaxy on Fire \| Razoon Gewinner des BCC #57 User posted image

Firstdeathmaker

Mi, Aug 24, 2005 14:44
Antworten mit Zitat

Jaaa! Das ist eine sehr schöne Sammlung. Man braucht zwar nicht alles, aber man kann sich benötigtes einfach rauspicken, danke!

www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

	regaa	Mi, Aug 24, 2005 17:12 Antworten mit Zitat
Boah, wieso sind Listen so langsam. Sende das mal bitte an Mark, der soll sich mal drum kümmern. Das ist ja schrecklich! Alle meine Progs basieren auf Listen .
UltraMixer Professional 3 - Download QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net

regaa

Mi, Aug 24, 2005 17:12
Antworten mit Zitat

Boah, wieso sind Listen so langsam. Sende das mal bitte an Mark, der soll sich mal drum kümmern. Das ist ja schrecklich! Alle meine Progs basieren auf Listen Confused

UltraMixer Professional 3 - Download
QB,HTML,CSS,JS,PHP,SQL,>>B2D,B3D,BP,BlitzMax,C,C++,Java,C#,VB6 , C#, VB.Net

	Dreamora	Mi, Aug 24, 2005 18:05 Antworten mit Zitat
Listen haben halt ihren Vorteil, dass man überall einfügen kann und keine reallozialisierung hat wenn man neue Elemente hinzufügt (wie es beim Array der Fall ist wenn man immer mit [..x] rumspielt) Mach doch mal ein Benchmark das mit 0 elemente startet und dann 100000 hinzufügt und danach noch ein eachin über das ganze. Dann wird der Array GANZ böse absüffeln. Array ist super für ~statische Datenmengen List ist super für dynamische Datenmengen
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

Dreamora

Mi, Aug 24, 2005 18:05
Antworten mit Zitat

Listen haben halt ihren Vorteil, dass man überall einfügen kann und keine reallozialisierung hat wenn man neue Elemente hinzufügt (wie es beim Array der Fall ist wenn man immer mit [..x] rumspielt)

Mach doch mal ein Benchmark das mit 0 elemente startet und dann 100000 hinzufügt und danach noch ein eachin über das ganze. Dann wird der Array GANZ böse absüffeln.

Array ist super für ~statische Datenmengen
List ist super für dynamische Datenmengen

Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

	Fetze	Mi, Aug 24, 2005 19:32 Antworten mit Zitat
Stimmt, sry, hab ich gar nicht berücksichtigt. Arrays sind wirklich saulahm in Sachen hinzufügen. Abgesehen davon ist es nur mit mehreren Slices möglich, ein Element aus der Mitte zu entfernen. Und SO schlimm sind Listen auch wieder nicht. Wie gesagt, Ingame würde man erste einbußen erst ab extrem hohen Objektzahlen machen. Ich schätze mal, ab 25000 gibt es die erste Millisekunde.

Fetze

Mi, Aug 24, 2005 19:32
Antworten mit Zitat

Stimmt, sry, hab ich gar nicht berücksichtigt. Arrays sind wirklich saulahm in Sachen hinzufügen. Abgesehen davon ist es nur mit mehreren Slices möglich, ein Element aus der Mitte zu entfernen. Und SO schlimm sind Listen auch wieder nicht. Wie gesagt, Ingame würde man erste einbußen erst ab extrem hohen Objektzahlen machen. Ich schätze mal, ab 25000 gibt es die erste Millisekunde.