Geschwindigkeit von Pow

Anfängerfragen zum Programmieren mit PureBasic.
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Geschwindigkeit von Pow

Beitrag von diceman »

Hallo liebe Leute,
Mir ist aufgefallen, daß die Pow()-Funktion (Potenzieren) ziemlich langsam arbeitet. Ziel des folgenden Beispiel-Snippets ist es, die Distanz von 2 Punkten mit dem Satz des Pythagoras zu berechnen. Dabei nutze ich drei Methoden

- grobe Schätzung über x/y-Achsen, kein SdP
- Satz des Pythagoras mit Pow()
- Satz des Pythagoras ohne Pow(), also ausgeschrieben

Jede Methode rechnet 100000000 (= 100 Millionen) mal dieselbe Formel durch, und gibt danach die Zeit aus, die benötigt wurde. Ich habe den Test sowohl mit Debugger als auch ohne Debugger durchgeführt:

Code: Alles auswählen

EnableExplicit

Define x0,y0,x1,y1
Define distance.f
Define i
Define timer

x0 = 2
y0 = 2
x1 = 7
y1 = 8

OpenConsole("")

timer = ElapsedMilliseconds()
For i = 1 To 100000000
	distance = Abs(x0-x1)+Abs(y0-y1)
Next
PrintN("Schätzung: "+distance)
PrintN("Millisecs: "+Str(ElapsedMilliseconds()-timer))



PrintN("")

timer = ElapsedMilliseconds()
For i = 1 To 100000000
	distance = Sqr(Pow((x0-x1),2)+Pow((y0-y1),2))
Next
PrintN("Satz des Pythagoras: "+distance)
PrintN("Millisecs: "+Str(ElapsedMilliseconds()-timer))



PrintN("")

timer = ElapsedMilliseconds()
For i = 1 To 100000000
	distance = Sqr(((x0-x1)*(x0-x1))+((y0-y1)*(y0-y1)))
Next
PrintN("ohne Pow(): "+distance)
PrintN("Millisecs: "+Str(ElapsedMilliseconds()-timer))



PrintN("")
PrintN("Press ENTER") : Input()
Schätzung:
Ergebnis (mit Debugger): ~ 6208 ms
Ergebnis (ohne Debugger): ~ 338 ms

SdP mit Pow():
Ergebnis (mit Debugger): ~ 20307 ms
Ergebnis (ohne Debugger): ~ 13231 ms

SdP ohne Pow():
Ergebnis (mit Debugger): ~ 7144 ms
Ergebnis (ohne Debugger): ~ 813 ms

Auffällig an diesem Ergebnis ist, daß die ohne Pow() ausgeschriebene Variante nicht nur 3x so schnell läuft, sondern die Berechnung ohne Debugger mit den Varianten ohne Pow() einen rund 10-20fachen Geschwindigkeitsboost erfährt, die Pow()-Variante ohne Debugger aber gerade mal ein Drittel schneller läuft.




Und falls es jemanden interessiert, hier derselbe Test in Blitzbasic/Blitz3D (das Potenzieren erledigt in BB der ^-Operator):

Code: Alles auswählen

Global x0,y0,x1,y1
Global distance#
Global i
Global timer

x0 = 2
y0 = 2
x1 = 7
y1 = 8

timer = MilliSecs()
For i = 1 To 100000000
	distance = Abs(x0-x1)+Abs(y0-y1)
Next
Print "Schätzung: "+distance
Print "Millisecs: "+(MilliSecs()-timer)

Print
timer = MilliSecs()
For i = 1 To 100000000
	distance = Sqr(((x0-x1)^2)+((y0-y1)^2))
Next
Print "Satz des Pythagoras: "+distance
Print "Millisecs: "+(MilliSecs()-timer)

Print
timer = MilliSecs()
For i = 1 To 100000000
	distance = Sqr(((x0-x1)*(x0-x1))+((y0-y1)*(y0-y1)))
Next
Print "ohne ^: "+distance
Print "Millisecs: "+(MilliSecs()-timer)

Print
Print "Press ENTER"
WaitKey()
Schätzung:
Ergebnis (mit Debugger): ~ 4782 ms
Ergebnis (ohne Debugger): ~ 547 ms

SdP mit Pow():
Ergebnis (mit Debugger): ~ 19324 ms
Ergebnis (ohne Debugger): ~ 14975 ms

SdP ohne Pow():
Ergebnis (mit Debugger): ~ 4801 ms
Ergebnis (ohne Debugger): ~ 540 ms
Zuletzt geändert von diceman am 10.02.2018 13:34, insgesamt 1-mal geändert.
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
mk-soft
Beiträge: 3695
Registriert: 24.11.2004 13:12
Wohnort: Germany

Re: Geschwindigkeit von Pow

Beitrag von mk-soft »

Liegt an ASM Code der erzeugt wird. Dieser ist länger da erst der Aufruf zur POW Funktion erfolgt
Ausserdem berücksichtigt die Pow-Funktion den Exponent
...
; distance = Sqr(Pow((x0-x1),2)+Pow((y0-y1),2))
PUSH qword [D2]
FILD qword [v_x0]
FILD qword [v_x1]
FSUBP st1,st0
FADD qword [D1]
SUB rsp,8
FSTP qword [rsp]
MOVSD xmm0,qword [rsp]
ADD rsp,8
MOVSD xmm1,qword [rsp]
ADD rsp,8
CALL _PB_Pow_DOUBLE
MOVSD [rsp-8],xmm0
FLD qword [rsp-8]
SUB rsp,8
FSTP qword [rsp+0]
SUB rsp,8
PUSH qword [D2]
FILD qword [v_y0]
FILD qword [v_y1]
FSUBP st1,st0
FADD qword [D1]
SUB rsp,8
FSTP qword [rsp]
MOVSD xmm0,qword [rsp]
ADD rsp,8
MOVSD xmm1,qword [rsp]
ADD rsp,8
CALL _PB_Pow_DOUBLE
ADD rsp,8
MOVSD [rsp-8],xmm0
FLD qword [rsp-8]
FLD qword [rsp+0]
FXCH st1
ADD rsp,8
FADDP st1,st0
FADD qword [D1]
FSQRT
FSTP dword [v_distance]
...
; distance = Sqr(((x0-x1)*(x0-x1))+((y0-y1)*(y0-y1)))
FILD qword [v_x0]
FILD qword [v_x1]
FSUBP st1,st0
FADD qword [D1]
FILD qword [v_x0]
FILD qword [v_x1]
FSUBP st1,st0
FADD qword [D1]
FMULP st1,st0
FILD qword [v_y0]
FILD qword [v_y1]
FSUBP st1,st0
FADD qword [D1]
FILD qword [v_y0]
FILD qword [v_y1]
FSUBP st1,st0
FADD qword [D1]
FMULP st1,st0
FADDP st1,st0
FADD qword [D1]
FSQRT
FSTP dword [v_distance]
;
Kannst dir mit ein Macro behelfen

Code: Alles auswählen

Macro Pow2(Value)
  ((Value) * (Value))
EndMacro

Macro Pow3(Value)
  ((Value) * (Value) * (Value))
EndMacro
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Geschwindigkeit von Pow

Beitrag von diceman »

Sehr interessant, in der Tat!
Habe mich nie damit beschäftigt, bin halt gerademit der Nase darauf gestoßen worden, als ich meine superfixe A*-Pfadsuche von Blitzbasic nach Purebasic übersetzt habe - unter anderem arbeitet man mit "Pfadkosten":

G-Kosten = exakte Kosten der bislang bekannten Strecke
H-Kosten - geschätzte Kosten der noch zurückzulegenden Strecke
F-Kosten = G+H

H habe ich immer mit (Abs(x0-x1)+Abs(y0-y1)) * 10 (bzw. 14 für Diagonalen) berechnet, was auch gut funktioniert.

Hatte dann zum Spaß stattdessen den Satz des Pythagoras (mit Pow()) verwendet, und war schon nicht wenig erschrocken, wie die Berechnungszeit auf einmal exponentiell in die Höhe schnellte. :o



Das mit den Makros ist sicherlich eine gute Idee (weniger Schreibarbeit). :)
Wie ich das verstehe, sind Makros vorgefertige Programmzeilen, welche beim Compilieren automatisch in den Code eingefügt werden, also anders als Prozedur-Verweise keine Rechenzeit kosten, richtig?
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
juergenkulow
Beiträge: 188
Registriert: 22.12.2016 12:49
Wohnort: :D_üsseldorf-Wersten

Re: Geschwindigkeit von Pow

Beitrag von juergenkulow »

Hallo diceman,

es wird bei dem Test nur 1 CPU-Kern benutzt, was zu einer geringen CPU-Auslastung führt.
Lohnt es sich die Rechenaufgabe auf mehrere Threads zu verteilen?
Lohnt es sich die Rechenaufgabe an die GPU der Grafikkarte zu geben?
Gruß
Bitte stelle Deine Fragen, denn den Erkenntnisapparat einschalten entscheidet über das einzig bekannte Leben im Universum.

Jürgen Kulow Wersten :D_üsseldorf NRW D Europa Erde Sonnensystem Lokale_Flocke Lokale_Blase Orion-Arm
Milchstraße Lokale_Gruppe Virgo-Superhaufen Laniakea Sichtbares_Universum
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Geschwindigkeit von Pow

Beitrag von diceman »

Tut mir Leid, ich verstehe nicht was du meinst. :)
Mir ist klar, daß das nur ein kleines, nicht optimiertes Snippet ist.
openConsole() habe ich verwendet, um den Test auch ohne Debugger durchführen zu können.
Auch ist mir klar, daß man in lauffähigen Programmen Schleifen nicht einfach so durchrattern lassen sollte und zumindest ein Delay(1) einfügen sollte um die CPU zu entlasten.
Allerdings wollte ich hier das Test-Ergebnis (= Rechendauer) nicht verfälschen.
Mit Threads (ich denke mal, du meinst hier die Aufteilung von Rechendauer auf mehrere Kerne?) habe ich mich leider nie (noch nicht) beschäftigt; ich bin erst seit knapp einer Woche in PureBasic unterwegs.
Zuletzt geändert von diceman am 10.02.2018 14:44, insgesamt 3-mal geändert.
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
mk-soft
Beiträge: 3695
Registriert: 24.11.2004 13:12
Wohnort: Germany

Re: Geschwindigkeit von Pow

Beitrag von mk-soft »

@Diceman
Das mit den Macros hast du richtig verstanden.

Das mit den Threads schauen wir uns etwas später an. Mit Threads und Semaphores zu arbeiten ist eigentlich keine Problem.
Aber man kann da einiges falsch machen was zum Beispiel zum Deadlock führen kann.
Alles ist möglich, fragt sich nur wie...
Projekte ThreadToGUI / EventDesigner V3 / OOP-BaseClass-Modul
Downloads auf MyWebspace / OneDrive
Benutzeravatar
diceman
Beiträge: 347
Registriert: 06.07.2017 12:24
Kontaktdaten:

Re: Geschwindigkeit von Pow

Beitrag von diceman »

Wtf, habe gerade den Test mit Pow2-Macro und einmal mit Pow2-Prozedur-Aufruf ausgeführt ...
Die Macro-Version läuft fast 7x mal schneller, und die Prozedur-Variante ist ungefähr 2.5x langsamer als der reguläre Pow()-Operator-Aufruf.
:o :o :o

//EDIT:
Aber nur wenn man's mit Debugger laufen lässt. :D
Ohne Debugger macht's knapp 50 Millisekunden aus (bei 100 mio. Durchläufen, wohlgemerkt).
Was natürlich Macros nicht weniger cool macht - schneller coden, FTW!
Zuletzt geändert von diceman am 10.02.2018 15:49, insgesamt 3-mal geändert.
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.
Benutzeravatar
Bisonte
Beiträge: 2427
Registriert: 01.04.2007 20:18

Re: Geschwindigkeit von Pow

Beitrag von Bisonte »

diceman hat geschrieben:Das mit den Makros ist sicherlich eine gute Idee (weniger Schreibarbeit). :)
Wie ich das verstehe, sind Makros vorgefertige Programmzeilen, welche beim Compilieren automatisch in den Code eingefügt werden, also anders als Prozedur-Verweise keine Rechenzeit kosten, richtig?
Richtig. Makros sind eingentlich Platzhalter.

Aus dem Code :

Code: Alles auswählen

Macro Hey()
  Print("Hallo Du Da")
EndMacro

Hey()
Hey()
Hey()
Setzt der Compiler vor dem kompilieren den entsprechenden Code einfach nur ein.

Code: Alles auswählen

Print("Hallo Du Da")
Print("Hallo Du Da")
Print("Hallo Du Da")
Daher entfällt der Prozedur Aufruf, Stackvorbereitung, StackNachbereitung, Freigeben von Resourcen etc.
Also schneller ;)
PureBasic 6.04 LTS (Windows x86/x64) | Windows10 Pro x64 | Asus TUF X570 Gaming Plus | R9 5900X | 64GB RAM | GeForce RTX 3080 TI iChill X4 | HAF XF Evo | build by vannicom​​
Benutzeravatar
ts-soft
Beiträge: 22292
Registriert: 08.09.2004 00:57
Computerausstattung: Mainboard: MSI 970A-G43
CPU: AMD FX-6300 Six-Core Processor
GraKa: GeForce GTX 750 Ti, 2 GB
Memory: 16 GB DDR3-1600 - Dual Channel
Wohnort: Berlin

Re: Geschwindigkeit von Pow

Beitrag von ts-soft »

@diceman

Zeittests immer ohne Debugger (disabledebugger reicht nicht) messen. Bei den Tests mit Debugger kannst Du Dir die Zeitmessungen sparen, die stehen nicht in bezug zu dem Code, sondern eher in bezug zu dem "DebuggerCode", haben also keinerlei Relevanz. Es ist also vollkommen uninteressant, ob der Code mit Debugger 2x, 10x oder 1000x solange benötigt, es kommt nur der Code ohne Debugger in der Exe zum tragen.

Testen mit Debugger:okay, Zeit messen mit Debugger: nicht okay! (der Wert hast keinerlei Beziehung zum Code ohne Debugger).

Gruß
Thomas
PureBasic 5.73 LTS | SpiderBasic 2.30 | Windows 10 Pro (x64) | Linux Mint 20.1 (x64)
Nutella hat nur sehr wenig Vitamine. Deswegen muss man davon relativ viel essen.
Bild
Benutzeravatar
NicknameFJ
Beiträge: 324
Registriert: 03.06.2007 14:36
Wohnort: Von der Sonne aus gesehen der dritte Planet

Re: Geschwindigkeit von Pow

Beitrag von NicknameFJ »

@diceman

Wenn es dir nicht auf die wirkliche Distanz ankommt sondern es nur darum geht zwei Distanzen zu vergleichen dann kannst du in diesem Fall auf das Wurzelziehen innerhalb der Berechnung Pythagoras verzichten
PS: Alle im Text enthaltenen Schreibfehler sind beabsichtigt und dienen der Belustigung aller

Bild
Antworten