1 Tick schnelleres atan2

Hier kann alles mögliche diskutiert werden. Themen zu Purebasic sind hier erwünscht.
Flames und Spam kommen ungefragt in den Mülleimer.
Benubi
Beiträge: 186
Registriert: 22.10.2004 17:51
Wohnort: Berlin, Wedding

1 Tick schnelleres atan2

Beitrag von Benubi »

Hallo Leute!

folgender Code ist zu simpel um unter Tipps & Tricks gepostet zu werden, und es handelt sich auch nicht direkt um ein Bug, nur indirekt um ein Feature request. Ich habe die atan2 von PureBasic mit der internen von Lua 5.4 DLL (mit PellesC kompiliert) verglichen; Lua ist "viel" schneller, meistens ca. 7-15% in den vorigen Tests. Ich habe also versucht die atan2 nachzuschreiben, wie bei wikipedia angegeben. Das Ergebnis ist ein Tick schneller als die PB interne Procedure. Aber es ist immer noch langsamer als die C atan2 funktion welche Lua intern benutzt. Ich habe das nur auf meiner alten XP Möhre getestet, 32bit. Mit PB 6 beta ist es sogar ein bißchen schneller, aber immer noch ist die pb Funktion etwas langsamer. Ich denke die PB Funktion kann optimiert werden.

Code: Alles auswählen

#HalfPi = #PI / 2

ProcedureC.d WAtan2(x.d,y.d) 
  If x>0
    ProcedureReturn ATan(y/x)
  ElseIf x<0 And y>=0
    ProcedureReturn ATan(y/x) + #PI
  ElseIf x<0 And y<0

    ProcedureReturn ATan(y/x) - #PI
  ElseIf x=0 And y>0
    ProcedureReturn #HalfPi
  ElseIf x=0 And y<0
    ProcedureReturn -#HalfPi
  EndIf 
  ProcedureReturn 0
EndProcedure
Vergleich: C lua (math lib), und 2 implementierungen wmath = obige funktion, und pbmath ist nur die pb atan2 funktion "direkt" gewrappt. Ich habe eine alternative "wmath" lib geschrieben welche memos benutzt um einige Kalkulationen zu beschleunigen, nach außen aber die selben Befehle ausweist wie die original. atan2 ließ sich leider nicht memoizieren, jedenfalls nicht mit meinem Erbsenhirn. Daher erstmal nur so ein Ergebnis. Die Reihenfolge der Überprüfungen ist vermutlich nur etwas anders in PB gestaltet, ich hatte nämlich einmal 100% identische Werte; ich hatte atan2 Varianten die auch langsamer waren als die von PB. Leider weisen die Tests jetzt den "großen" Unterschied nicht wirklich nach, aber ein kleiner Unterschied wird schon zu messen sein:

(siehe weiter unten, neue Ergebnisse nach Bugfix und neuem Test code)


PureBasic Test Code
Update: mit ATan() Approximation + Negativwerte werden geprüft

Code: Alles auswählen

; Faster atan2() procedures
#HalfPi = #PI / 2


ProcedureC.d atan_scalar_approximation(x.d)
  ; Source: 
  ; https://mazzo.li/posts/vectorized-atan2.html
  ; inline float atan_scalar_approximation(float x) {
;   float a1  =  0.99997726f;
;   float a3  = -0.33262347f;
;   float a5  =  0.19354346f;
;   float a7  = -0.11643287f;
;   float a9  =  0.05265332f;
;   float a11 = -0.01172120f;
; 
;   float x_sq = x*x;
;   return
;     x * (a1 + x_sq * (a3 + x_sq * (a5 + x_sq * (a7 + x_sq * (a9 + x_sq * a11)))));
; }
  
  #a1  =  0.99997726;
  #a3  = -0.33262347;
  #a5  =  0.19354346;
  #a7  = -0.11643287;
  #a9  =  0.05265332;
  #a11 = -0.01172120;
  Protected x_sq.d = x * x
  
  ProcedureReturn    x * (#a1 + x_sq * (#a3 + x_sq * (#a5 + x_sq * (#a7 + x_sq * (#a9 + x_sq * #a11)))));
EndProcedure


ProcedureC.d XAtan2(x.d,y.d)
  If x>0
    ProcedureReturn atan_scalar_approximation(y/x)
  ElseIf x<0 And y>=0

    ProcedureReturn atan_scalar_approximation(y/x) + #PI
  ElseIf x<0 And y<0

    ProcedureReturn atan_scalar_approximation(y/x) - #PI
  ElseIf x=0 And y>0
    ProcedureReturn #HalfPi
  ElseIf x=0 And y<0
    ProcedureReturn -#HalfPi
  EndIf 
  ProcedureReturn 0
EndProcedure




ProcedureC.d WAtan2(x.d,y.d) 
  If x>0
    ProcedureReturn ATan(y/x)
  ElseIf x<0 And y>=0

    ProcedureReturn ATan(y/x) + #PI
  ElseIf x<0 And y<0

    ProcedureReturn ATan(y/x) - #PI
  ElseIf x=0 And y>0
    ProcedureReturn #HalfPi
  ElseIf x=0 And y<0
    ProcedureReturn -#HalfPi
  EndIf 
  ProcedureReturn 0
EndProcedure



Define pe,ps, we,ws , xe, xs
Define max = 10000000
Define.d angleresult 

Delay(1)
ps = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = ATan2(Random(10000)-5000,Random(10000)-5000  )
Next 
pe =ElapsedMilliseconds()

Delay(1)

ws = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = WATan2(Random(10000)-5000,Random(10000)-5000 )  
Next 
we = ElapsedMilliseconds()

Delay(1)

xs = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = XATan2(Random(10000)-5000,Random(10000)-5000)  
Next 
xe = ElapsedMilliseconds()




msg$ = "Ergebnis" +#CRLF$
msg$ + "loops: "+Str(max)+#CRLF$
msg$ + "atan2 (PB intern):"+Str(pe-ps)+"ms"+#CRLF$
msg$ + "atan2 (WAtan2):"+Str(we-ws)+"ms"+#CRLF$
msg$ + "atan2 (XAtan2, Approximation):"+Str(xe-xs)+"ms"+#CRLF$

CompilerIf #PB_Compiler_Debugger
  msg$+#CRLF$+"Hey, der Debugger ist AN. Das ist Schummelei!"+#CRLF$+"Probiere es bitte ohne Debugger."+#CRLF$
CompilerEndIf 
SetClipboardText(msg$)
MessageRequester("Leistungsvergleich",msg$)


Die Unterschiede sind minimal, aber im Vergleich dazu ist die C atan2 prozedure welche Lua benutzt doch immer ein wenig schneller. 10-15% Leistungssteigerung sind "nicht der Burner", aber "Kleinvieh macht auch Mist".

Lua Skript zur Vollständigkeit (Update)

Code: Alles auswählen


require "wmath"
require "clock"
require "math"

local max = 10000000
local i
local ms,me
local ws,we
local ps,pe
local xs,xe
local tick = clock.tick
local aatan2	= math.atan2
local watan2	= wmath.atan2
local xatan2	= wmath.atan2_2
local patan2      	= wmath.pbatan2
local random	= wmath.random
local angleresult

ms = tick()
for i=1,max,1 do
	angleresult = aatan2(random(10000)-5000,random(10000)-5000)
end
me = tick()

ws = tick()
for i=1,max,1 do
	angleresult = watan2(random(10000)-5000,random(10000)-5000)
end

we = tick()

xs = tick()
for i=1,max,1 do
	angleresult = xatan2(random(10000)-5000,random(10000)-5000)
end
xe = tick()

ps = tick()
for i=1,max,1 do
	angleresult = patan2(random(10000)-5000,random(10000)-5000)
end
pe = tick()

print("performance","loops:",max)
print("lua math",me-ms,"ms")
print("wmath xatan2 (approximation)",we-ws,"ms")
print("wmath watan2",xe-xs,"ms")
print("wmath pb atan2",pe-ps,"ms")
Ich würde gerne wissen ob ihr auch meßbare unterschiede habt, besonders Neugierig bin ich ob da unterschiede zwischen den 32/64 bit Versionen von PB auftauchen.
Zuletzt geändert von Benubi am 24.12.2021 17:18, insgesamt 2-mal geändert.
ST4242
Beiträge: 42
Registriert: 29.10.2011 16:54

Re: 1 Tick schnelleres atan2

Beitrag von ST4242 »

Hallo,
folgendes Ergebnis bei mir:

Pure Basic 5.73 LTS 64 Bit
Ergebnis
loops: 10000000
atan2 (PB intern):300ms
atan2 (WAtan2):339ms


Pure Basic 5.73 LTS 32 Bit
Ergebnis
loops: 10000000
atan2 (PB intern):1548ms
atan2 (WAtan2):560ms

Rechner
Window 10 64 Bit

AMD ZEN 3900X

Grüsse
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: 1 Tick schnelleres atan2

Beitrag von STARGÅTE »

Kleiner Hinweis zu deinem Test-Code:
Du übergibst gar keine negativen Werte mit deinen Zufallszahlen, daher trifft praktisch immer gleich die erste If-Abfrage zu und die Geschwindigkeitsmessung ist nicht repräsentativ. Außerdem sollten beide Schleifen die selben Zahlen erzeugen.

Mit RandomSeed(1) und (Random(10000)-5000, Random(10000)-5000), kommt
bei mir übrigens folgendes raus:
x64 hat geschrieben:Ergebnis
loops: 10000000
atan2 (PB intern):332ms
atan2 (WAtan2):423ms
x86 hat geschrieben:Ergebnis
loops: 10000000
atan2 (PB intern):1544ms
atan2 (WAtan2):609ms
ATan2 ist unter x64 schneller. Warum ATan2 unter x86 so viel langsamer ist macht mich etwas stutzig.
Allerdings bin ich mir auch unsicher, was bei ATan2() überhaupt übergeben wird, wenn man eine Integer übergibt?
Wird die in eine Float oder Double umgewandelt?
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benubi
Beiträge: 186
Registriert: 22.10.2004 17:51
Wohnort: Berlin, Wedding

Re: 1 Tick schnelleres atan2

Beitrag von Benubi »

:allright:
Vielen Dank für den wichtigen Hinweis, ich habejetzt beide Test codes (PB + Lua) ge-updated. Die Ergebnisse finde ich auch merkwürdig. Die Funktionen benutzen alle Doubles; ich habe probiert das ganze mit floats zu machen, auf meinem System (32bit) gab es aber keine Leistungsunterschiede. Ich denke die mathematischen Funktionen benutzen dann auch alle Doubles.

Zwischendurch habe ich 1) versucht zu optimieren mit FPTAN - bin aber schlecht in Assembler. Als die Funktion "halb fertig" war verbrauchte sie schon mehr Zeit als alle anderen Varianten. Ich habe weiter zum Befehl gesucht und bin auf eine codeoverflow Seite gestoßen die darauf hindeutete, daß "Software Lösungen" schneller seien. In dem Beispiel wurde im desassemblierten Beispielcode auf eine Hashmap verwiesen oder sowas; aber ich habe dann 2) eine Approximations-Funktion für ATan() gefunden, und das umgesetzt. Das läuft "viel" schneller. Lua benutzt nur 64bit Quads und Doubles als native Datentypen (auf fast allen Platformen), daher habe ich mich dafür entschieden. Die Geschwindigkeitsunterschiede sind aber marginal oder inexistent bei allen Versuchen die ich unternommen habe. Waren aber auch nicht sehr viele. Man kann ja auf der PB Seite alles so machen wie man will, und floats haben keinen oder kaum meßbaren Unterschied gemacht bei sin,cos,atan2 etc.

Hier noch die Quelle für die neue Funktion (habe nur die ATan übernommen)
https://mazzo.li/posts/vectorized-atan2.html

Code update (PB) mit neuer Approximations-Funktion XATan2()

Code: Alles auswählen

; Faster atan2() procedures
#HalfPi = #PI / 2


ProcedureC.d atan_scalar_approximation(x.d)
  ; Source: 
  ; https://mazzo.li/posts/vectorized-atan2.html
  ; inline float atan_scalar_approximation(float x) {
;   float a1  =  0.99997726f;
;   float a3  = -0.33262347f;
;   float a5  =  0.19354346f;
;   float a7  = -0.11643287f;
;   float a9  =  0.05265332f;
;   float a11 = -0.01172120f;
; 
;   float x_sq = x*x;
;   return
;     x * (a1 + x_sq * (a3 + x_sq * (a5 + x_sq * (a7 + x_sq * (a9 + x_sq * a11)))));
; }
  
  #a1  =  0.99997726;
  #a3  = -0.33262347;
  #a5  =  0.19354346;
  #a7  = -0.11643287;
  #a9  =  0.05265332;
  #a11 = -0.01172120;
  Protected x_sq.d = x * x
  
  ProcedureReturn    x * (#a1 + x_sq * (#a3 + x_sq * (#a5 + x_sq * (#a7 + x_sq * (#a9 + x_sq * #a11)))));
EndProcedure


ProcedureC.d XAtan2(x.d,y.d)
  If x>0
    ProcedureReturn atan_scalar_approximation(y/x)
  ElseIf x<0 And y>=0

    ProcedureReturn atan_scalar_approximation(y/x) + #PI
  ElseIf x<0 And y<0

    ProcedureReturn atan_scalar_approximation(y/x) - #PI
  ElseIf x=0 And y>0
    ProcedureReturn #HalfPi
  ElseIf x=0 And y<0
    ProcedureReturn -#HalfPi
  EndIf 
  ProcedureReturn 0
EndProcedure




ProcedureC.d WAtan2(x.d,y.d) 
  If x>0
    ProcedureReturn ATan(y/x)
  ElseIf x<0 And y>=0

    ProcedureReturn ATan(y/x) + #PI
  ElseIf x<0 And y<0

    ProcedureReturn ATan(y/x) - #PI
  ElseIf x=0 And y>0
    ProcedureReturn #HalfPi
  ElseIf x=0 And y<0
    ProcedureReturn -#HalfPi
  EndIf 
  ProcedureReturn 0
EndProcedure



Define pe,ps, we,ws , xe, xs
Define max = 10000000
Define.d angleresult 

Delay(1)
ps = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = ATan2(Random(10000)-5000,Random(10000)-5000  )
Next 
pe =ElapsedMilliseconds()

Delay(1)

ws = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = WATan2(Random(10000)-5000,Random(10000)-5000 )  
Next 
we = ElapsedMilliseconds()

Delay(1)

xs = ElapsedMilliseconds()
For i=1 To max Step 1
  angleresult = XATan2(Random(10000)-5000,Random(10000)-5000)  
Next 
xe = ElapsedMilliseconds()




msg$ = "Ergebnis" +#CRLF$
msg$ + "loops: "+Str(max)+#CRLF$
msg$ + "atan2 (PB intern):"+Str(pe-ps)+"ms"+#CRLF$
msg$ + "atan2 (WAtan2):"+Str(we-ws)+"ms"+#CRLF$
msg$ + "atan2 (XAtan2, Approximation):"+Str(xe-xs)+"ms"+#CRLF$

CompilerIf #PB_Compiler_Debugger
  msg$+#CRLF$+"Hey, der Debugger ist AN. Das ist Schummelei!"+#CRLF$+"Probiere es bitte ohne Debugger."+#CRLF$
CompilerEndIf 
SetClipboardText(msg$)
MessageRequester("Leistungsvergleich",msg$)

Merkwürdige Ergebnisse, weil jetzt negative Werte geprüft werden die ich wohl ausgelassen hatte - PB liegt wieder vorn, die neue Approximation braucht am Wenigsten Zeit ist aber nicht so schnell wie erhofft.

PB 5,73 WinXP 32bit
Ergebnis
loops: 10000000
atan2 (PB intern):923ms
atan2 (WAtan2):950ms
atan2 (XAtan2, Approximation):593ms
---------------------

Lua lib mit PB 5,73 WinXP 32bit
performance loops: 10000000
lua math 2911 ms
wmath xatan2 (approximation) 2815 ms
wmath watan2 3203 ms
wmath pb atan2 3373 ms
---------------------

PB 6 beta WinXP 32bit
Ergebnis
loops: 10000000
atan2 (PB intern):922ms
atan2 (WAtan2):943ms
atan2 (XAtan2, Approximation):591ms
---------------------

Lua lib mit PB 6 beta WinXP 32bit
performance loops: 10000000
lua math 2890 ms
wmath xatan2 (approximation) 2785 ms
wmath watan2 3193 ms
wmath pb atan2 3289 ms

Ich habe übrigens zuvor auch geprüft, daß Lua und die PB interne atan2 identische Werte zurrückgeben und das tun sie. Habe mein "game" auch mit der Approximation problemlos spielen können, aber erwartungsgemäß kaum Fortschritte bei der FPS Zahl erzielt... :lol:
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: 1 Tick schnelleres atan2

Beitrag von STARGÅTE »

Benubi hat geschrieben: 24.12.2021 16:34 Die Funktionen benutzen alle Doubles;
Deine eigenen schon, aber was nutzt PureBasic bei ATan2(), schließlich sind beide Varianten (float und double) definiert. Was nutzt PB wenn du eine ganze Zahl übergibst statt einer Float- oder Double-Variable?
Benubi hat geschrieben: 24.12.2021 16:34 aber ich habe dann 2) eine Approximations-Funktion für ATan() gefunden, und das umgesetzt. Das läuft "viel" schneller.
Dir ist aber sicherlich klar, dass du hier (wie es auch im auskommentierten Code steht) mit float-genauigkeit approximierst, aber "dreißt" einfach n double zurück gibst? Außerdem stimmen die Werte nicht, denn du musst vorher fragen, ob x <= 1 ist, ansonsten musst du "flippen", also atan(x) = pi/2 - atan(1/x)

Code: Alles auswählen

Debug StrD(atan_scalar_approximation(0.1)) + " vs " + StrD(ATan(0.1))
Debug StrD(atan_scalar_approximation(0.5)) + " vs " + StrD(ATan(0.5))
Debug StrD(atan_scalar_approximation(1.0)) + " vs " + StrD(ATan(1.0))
Debug StrD(atan_scalar_approximation(2.0)) + " vs " + StrD(ATan(2.0))
Debug StrD(atan_scalar_approximation(4.0)) + " vs " + StrD(ATan(4.0))
Benubi hat geschrieben: 24.12.2021 16:34 ich habe weiter zum Befehl gesucht und bin auf eine codeoverflow Seite gestoßen die darauf hindeutete, daß "Software Lösungen" schneller seien.
Das stimmt. Auch ich habe ich damals über mein ASM - Log2() gewundert, was langsamer war als das PB Log10 oder Log.
ASM - fyl2x langsammer als Log10 oder Log ?
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Benubi
Beiträge: 186
Registriert: 22.10.2004 17:51
Wohnort: Berlin, Wedding

Re: 1 Tick schnelleres atan2

Beitrag von Benubi »

So die Approximation ist leider unbrauchbar. Nächstes mal vielleicht.

Ich habe ein Test Programm geschrieben zu deiner Integer Frage. Im Assembler Code gibt es die ATan2 nur einmal:

extrn _PB_ATan2@8

Sie wird sie mit FILD für longs, quads und integer "gefüttert."

Code: Alles auswählen

(...) ; qx, qy = quad .q
; result = ATan2(qx,qy)  
  FILD   qword [v_qy]
  SUB    esp,4
  FSTP   dword [esp]
  FILD   qword [v_qx]
  SUB    esp,4
  FSTP   dword [esp]
  CALL  _PB_ATan2@8
  SUB    esp,8
  FISTP  qword [esp]
  POP    dword [v_result]
  POP    dword [v_result+4]
(...) ; ix, iy = integer .i
; result = ATan2(ix,iy)  
  PUSH   dword [v_iy]
  FILD   dword [esp]
  FSTP   dword [esp]
  PUSH   dword [v_ix]
  FILD   dword [esp]
  FSTP   dword [esp]
  CALL  _PB_ATan2@8
  SUB    esp,8
  FISTP  qword [esp]
  POP    dword [v_result]
  POP    dword [v_result+4]
(...)

Test Code - ATan2() mit den wichtigsten Datentypen vergleichen :

Code: Alles auswählen

Define dx.d,dy.d
Define fx.f,fy.f
Define lx.l,ly.l
Define qx.q,qy.q
Define ix,iy

Define ds,de
Define fs,fe
Define ls,le
Define qs,qe
Define is,ie

Define max  = 1000000

Define result.q

Define i



Delay(1)
ds = ElapsedMilliseconds()
For i=1 To max 
  dx = Random(10000)-5000
  dy = Random(10000)-5000
  result = ATan2(dx,dy)  
Next 
de = ElapsedMilliseconds()


Delay(1)
fs = ElapsedMilliseconds()
For i=1 To max 
  fx = Random(10000)-5000
  fy = Random(10000)-5000
  result = ATan2(fx,fy)  
Next 
fe = ElapsedMilliseconds()


Delay(1)
ls = ElapsedMilliseconds()
For i=1 To max 
  lx = Random(10000)-5000
  ly = Random(10000)-5000
  result = ATan2(lx,ly)  
Next 
le = ElapsedMilliseconds()


Delay(1)
qs = ElapsedMilliseconds()
For i=1 To max 
  qx = Random(10000)-5000
  qy = Random(10000)-5000
  result = ATan2(qx,qy)  
Next 
qe = ElapsedMilliseconds()

Delay(1)
is = ElapsedMilliseconds()
For i=1 To max 
  ix = Random(10000)-5000
  iy = Random(10000)-5000
  result = ATan2(ix,iy)  
Next 
ie = ElapsedMilliseconds()



msg$="Ergebnisse"+#CRLF$
msg$+"Loops:"+Str(max)+#CRLF$
msg$+"double:"+Str(de-ds)+"ms"+#CRLF$
msg$+"float:"+Str(fe-fs)+"ms"+#CRLF$
msg$+"long:"+Str(le-ls)+"ms"+#CRLF$
msg$+"quad:"+Str(qe-qs)+"ms"+#CRLF$
msg$+"integer:"+Str(ie-is)+"ms"+#CRLF$


SetClipboardText(msg$)
MessageRequester("Ergebnis",msg$)
Antworten