Performance Frage

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

Firstdeathmaker

Betreff: Performance Frage

 BeitragMo, Jan 26, 2009 17:44
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,


Es geht hauptsächlich um die Zeile 88 und 107ff.

Wenn man bei Zeile 88 ein sqr vor den Ausdruck auf der rechten Seite setzt, dann wird meine Quicksort-Funktion extrem langsamer (Wenn man es startet, sieht man jeweils die Zeit für einen Aufruf der Funktion TQuicksort_sort()).

Das seltsame ist jetzt aber, das die Berechnung aus Zeile 88 garnicht im Aufruf von TQuicksort_sort() geschieht, sondern vorher. Eigentlich dürfte sich das also garnicht auf die Geschwindigkeit der Funktion auswirken. Hat jmd eine Idee weshalb es das trotzdem tut?



Test.bb
Code: [AUSKLAPPEN]
Include "Includes\Spannbaum.bb"
Include "Includes\QuicksortQueue.bb"

TNode_InitAll()


For i=0 To 100
TConnection_InitAll()
For c.TConnection = Each TConnection
Delete c
Next
Next



;TConnection_CreateSpanningTree(First TNode)


WaitKey()
End


Includes\Spannbaum.bb
Code: [AUSKLAPPEN]




Const NODES%=100
Global NODES_XDIST# = 100 / 2
Global NODES_YDIST# = 100 / 2
Global NODES_ZDIST# = 100 / 2

Global CurrentConnections_counter% = 0
Dim CurrentConnectionsArray.TConnection(NODES-1)

Dim NODE_ARRAY.TNode(NODES)
Type TNode
    Field id%
    Field entity%
    Field pos#[3]
   Field connected%
End Type

Function TNode_getDistanceBetween(n1.TNode,n2.TNode)
   Return Sqr(n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2])
End Function

Type TConnection
   Field node.TNode[2]
   Field dist#
   Field valid%
   Field entity%
End Type

Global CONNECTIONS% = TConnection_calcConnCount%()
Dim CONNECTION_ARRAY.TConnection(CONNECTIONS)

Function TConnection_calcConnCount%()
   Return (NODES*(NODES+1)/2) - NODES; See http://de.wikipedia.org/wiki/Der_kleine_Gau%C3%9F
End Function

Function minInt(c1%,c2%)
   If c1<=c2 Return c1
   Return c2
End Function

Function maxInt(c1%,c2%)
   If c1>=c2 Return c1
   Return c2
End Function

Function TConnection_getConnection.TConnection(n1%,n2%)
   If n1=n2 Return Null
   Return CONNECTION_ARRAY(TConnection_getArrayPos(n1,n2))
End Function

Function TConnection_getArrayPos%(n1%,n2%)
   Local na% = minInt(n1,n2)
   Local nb% = maxInt(n1,n2)
   Local pos% = 0
   For i% = 1 To na
      pos = pos + Sgn((na-i)) * (NODES - i)
   Next
   pos = pos + (nb-na) - 1
   Return pos
End Function

Function TConnection_getConnectionTest()
For i% = 5000 To 5005
Local c2.TConnection = TConnection_getConnection((i/1000)+1,(i Mod 1000)+1)
If c2<>Null
   Print ((i/1000)+1)+"/"+((i Mod 1000)+1) + " = "+c2\node[0]\id + "/"+c2\node[1]\id
EndIf
Next
End Function


Function TNode_InitAll()
   DebugLog "Init Nodes"
   For i% = 1 To NODES
      Local n.TNode = New TNode
      n\id = i
      n\pos[0] = Rnd(-NODES_XDIST,NODES_XDIST)
      n\pos[1] = Rnd(-NODES_YDIST,NODES_YDIST)
      n\pos[2] = Rnd(-NODES_ZDIST,NODES_ZDIST)
      NODE_ARRAY(i-1) = n
   Next
End Function

Function TConnection_Create.TConnection(n1.TNode,n2.TNode)
   Local c.TConnection = New TConnection
   c\node[0] = n1
   c\node[1] = n2
   ;c\dist = TNode_getDistanceBetween(n1,n2)
   c\dist = (n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2])
   Return c
End Function

Function TConnection_InitAll()
   DebugLog "Init Connections"
   Local stmp% = NODES-1
   Local c% = 0
   TQuicksort_Clear()
   For i1% = 0 To stmp
      For i2% = i1 To stmp
         If i1<>i2
            CONNECTION_ARRAY(c) = TConnection_Create(NODE_ARRAY(i1),NODE_ARRAY(i2))
            TQuicksortLink_create.TQuicksortLink(CONNECTION_ARRAY(c)\dist,Handle(CONNECTION_ARRAY(c)))
            c = c + 1
         EndIf
      Next
   Next
   DebugLog "sorting connections: ..."
   Local time% = MilliSecs()
   TQuicksort_sort()
   DebugLog "sorting connections: finished within "+(MilliSecs()-time)+" ms"
End Function



Function TConnection_CreateSpanningTree(startNode.TNode)
   DebugLog "Reset"
   CurrentConnections_counter = 0
   For n.TNode = Each TNode
      n\connected = False
   Next
   For c.TConnection = Each TConnection
      c\valid = False
   Next

   DebugLog "calculating min spanning tree"
   startNode\connected = True
   For i% = 1 To NODES
      TConnection_CreateSpanningTree_Sub()
   Next
   
   DebugLog "cleaning up"
   ;For qsl.TQuicksortLink = Each TQuicksortLink
   ;   Local c.TConnection = Object.TConnection(qsl\objHandle)
   ;   If c\node[0]\connected And c\node[1]\connected
   ;      Local pos% = TConnection_getArrayPos%(c\node[0]\id,c\node[1]\id)
   ;      If CONNECTION_ARRAY(pos)<>Null Delete CONNECTION_ARRAY(pos)
   ;      CONNECTION_ARRAY(pos) = Null
   ;   EndIf
   ;Next
   TQuickSort_clear()
   
   DebugLog "finished calc spanning tree"
   For i% = 0 To NODES-1
      c.TConnection = CurrentConnectionsArray(i)
      If c<>Null DebugLog "c "+c\node[0]\id+" <--> "+c\node[1]\id+" dist:"+c\dist
   Next
End Function

Function TConnection_CreateSpanningTree_Sub()
   ;Kleinste Kante wählen die Graph mit noch nicht verb. Knoten verbindet.
   For qsl.TQuicksortLink = Each TQuicksortLink
   
      Local c.TConnection = Object.TConnection(qsl\objHandle)
      
      If c\node[0]\connected Xor c\node[1]\connected
         c\node[0]\connected = True
         c\node[1]\connected = True
         c\valid = True
         
         CurrentConnectionsArray(CurrentConnections_counter) = c
         CurrentConnections_counter = CurrentConnections_counter + 1
         
         Delete qsl
         Return
      EndIf
   Next
End Function


Includes\QuickSortQueue.bb
Code: [AUSKLAPPEN]
;QuickSortQueue.bb
;version 1.0
;by Christian Geißler
;24.1.2009


Type TQuicksortLink
   Field value#
   Field objHandle%
End Type

Function TQuicksortLink_create.TQuicksortLink(value#,objectHandle%)
   Local pl.TQuicksortLink = New TQuicksortLink
   pl\value = value
   pl\objHandle = objectHandle
   Return pl
End Function

Function TQuicksortLink_removeFirst%()
   Local l.TQuicksortLink = First TQuicksortLink
   If l<>Null
      Local h% = l\objHandle
      Delete l
      Return h
   EndIf
End Function

Function TQuicksortLink_removeLast%()
   Local l.TQuicksortLink = Last TQuicksortLink
   If l<>Null
      Local h% = l\objHandle
      Delete l
      Return h
   EndIf
End Function

Function TQuicksort_clear()
   For ql.TQuicksortLink = Each TQuicksortLink
      Delete ql
   Next
End Function

Function TQuicksort_sort()
   TQuicksort_sortPart(First TQuicksortLink,Last TQuicksortLink)
End Function

Function TQuicksort_sortPart(f.TQuicksortLink,l.TQuicksortLink)
   If f = l Return
   If l = Null Return
   If f = Null Return
   
   p.TQuicksortLink = f
   e.TQuicksortLink = l
   ;p = pivot element
   this.TQuicksortLink = f
   enum.TQuicksortLink = After this
   
   While this<>e And enum<>Null
      this = enum
      enum = After enum

      
      If this\value < p\value
         Insert this Before f
         f = this
      Else
         Insert this After l
         l = this
      EndIf
   Wend
   
   TQuicksort_sortPart(f,p)
   TQuicksort_sortPart(After p,l)
End Function
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Who

 BeitragMo, Jan 26, 2009 21:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi!

Es ist mir unerklärlich, wie fehlende Klammern so viel Extrazeit beanspruchen Shocked

auskommentiert (Zeile 88):
Code: [AUSKLAPPEN]
Abstand = x1^2 + x2^2 + x3^2
Zeit: 35 ms pro Dings

mit Formel (Zeile 87):
Code: [AUSKLAPPEN]
Abstand = Sqrx1^2 + x2^2 + x3^2
Zeit: 1000 ms

richtig:
Code: [AUSKLAPPEN]
Abstand = Sqr(x1^2 + x2^2 + x3^2)
Zeit: 80 ms


trotzdem kommt mir das sehr lahm vor, nur die eine Wurzel will doppelt so viel Zeit haben...

MFG
Who

hectic

Sieger des IS Talentwettbewerb 2006

BeitragMo, Jan 26, 2009 21:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn man in der Schule gelernt hat wie man Wurzeln zieht ohne Hilfe eines Taschenrechners und weiß, dass der Rechner kaum andere Möglichkeiten anwendet. Dann leuchtet einem auch ein, dass bestimmte Rechenweisen eben viel mehr Rechenzeit benötigen.

Beispiele:

Addition kann der Rechner fast direkt mit AND-Operatoren durchführen. Daher kann der Rechner mit nur wenigen Taktzyklen eine Addition ausrechnen. Soweit ich informatiert bin, nach etwa 3 Takten ist das Ergebnis berechnet.

Multiplikation muß dagegen internt bereits mehrfach aufgeteilt werden. Das ganze benötigt dann etwa 15 bis 30 Taktzyklen.

Wurzel muß komplett aufgelöst und jede Ziffer einzelnd berechnet werden. Dabei müßen verschiedene Regeln eingehalten werden. Das ganze benötigt dann im Schnitt 90 bis etwa 130 Taktzyklen eines Prozessors.

-

Meine Angaben können mitlerweile überholt sein. Meine Angaben stützen sich auf Rechern die etwa 10 jahre alt sind. Neuere Rechner können sicherlich das eine oder andere schon schneller ausrechnen. Das Verhältnis aller sollte aber denoch nahezu gleich sein.
Download der Draw3D2 V.1.1 für schnelle Echtzeiteffekte über Blitz3D

Firstdeathmaker

 BeitragMo, Jan 26, 2009 21:16
Antworten mit Zitat
Benutzer-Profile anzeigen
Ähm, um das nochmal klar zu stellen:

Mir geht es nicht darum, dass Sqr so viel Zeit verbraucht (das ist schließlich klar) oder dass x1*x1 nunmal schneller als x1^2 ist, sondern darum, dass ich in meinem code ungefähr folgendes mache (Pseudocode):
(Da der gepostete Quicksort auch nur eine absolute Ordnung braucht, kann ich mir das berechnen der Quadratwurzel sogar sparen).

Code: [AUSKLAPPEN]
COUNT = 1000
dim arr#[COUNT]

for i=0 to COUNT-1
 arr[i] = ;komplexe Berechnung
next

time = millisecs()
for i=0 to COUNT-1
 ;verarbeite arr[i]
next
debuglog (time - millisecs())


Sprich, die komplexe Berechnung dürfte überhaupt keine Zeitliche Auswirkung auf die gestoppte Zeit haben, weil sie vor dem starten der Stoppuhr stattfindet. Leider hat sie dass aber in meinem im vorherigen geposteten Code.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

hectic

Sieger des IS Talentwettbewerb 2006

BeitragMo, Jan 26, 2009 21:21
Antworten mit Zitat
Benutzer-Profile anzeigen
Nach jeden Programmstart eines Blitzprogrammes wird nach etwa 0.5 bis 1.0 Sekunden noch einmal eine Optimierung durchgeführt. Diese Optimierung lässt das Programm stocken. Ob diese Optimierung von Blitz oder Windows durchgeführt wird, kann ich nicht sagen. Aber ich habe dieses Verhalten schon immer beobachten können. Daher sind auch Geschwindigkeitstest ohne mindestens 2 Sekunden Pause vor dem eigendlichem Test fast nicht zu gebrauchen, was viele hier im Forum immer wieder gerne vernachlässigen. die Optimierungen könnten auch zusätzliche Speicherplatzreservierungen oder sonstiges sein, die für ein Programm benötigt werden. Wer es weiß, kann es ja gerne mal erläutern. Mich würde es schon interessieren.

Edit1: Worauf ich hinaus will. Vielleicht misst du einfach nur genau dieses stocken, und nicht irgendwelche Berechnungen die bereits durchgeführt wurden.
Download der Draw3D2 V.1.1 für schnelle Echtzeiteffekte über Blitz3D

Firstdeathmaker

 BeitragMo, Jan 26, 2009 21:31
Antworten mit Zitat
Benutzer-Profile anzeigen
Hmm, das klingt schon logisch, allerdings sprechen die Zeiten total dagegen:

Wenn ich die langsamere Vorberechnung wähle, bekomme ich beim Quicksort Zeiten von 38 Sekunden raus, im Gegensatz zu vllt. 2 Sekunden die man anders bekommt.

Es liegt also definitiv nicht an einem 2-Sekunden Ruckler.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Who

 BeitragMo, Jan 26, 2009 21:47
Antworten mit Zitat
Benutzer-Profile anzeigen
Das ist wirklich mysteriös, hoffentlich kann das noch jemand klären.
Ein ausgiebiges Delay bevor die Uhr läuft ändert nichts.

Nebenbei: Deine Felder sind alle 1 zu groß Wink

MFG

Meoqan

 BeitragMo, Jan 26, 2009 23:32
Antworten mit Zitat
Benutzer-Profile anzeigen
hi!

nach einigen tests und dem herausfinden das bei deiner "alten" rechenart ein bug von blitz zugrundeliegt, kann ich dir sagen das manche floats nur "NaN"(not a number) zurückgeben.


das kommt davon:

Code: [AUSKLAPPEN]

If Sqr(-1) = 0 And Sqr(-1) = 12345 Then Print "unmoeglich"
WaitKey()
End


und hier aus einem forum ein paar funktionen die dem problem vorbeugen:

Code: [AUSKLAPPEN]

Function isNaN(n#)
   Return n = 0 And n = 12345
End Function

Function isInf(n#)
   Return n / 1000 = n And (Not isNaN(n))
End Function

Function isPosInf(n#)
   Return isInf(n) And Sgn(n) = 1
End Function

Function isNegInf(n#)
   Return isInf(n) And Sgn(n) = -1
End Function



have phun, Meoqan
meine codes sind die essenz des bössen. nicht du veränderst meine codes sondern meine codes verändern dich!

Jan_

Ehemaliger Admin

BeitragDi, Jan 27, 2009 9:40
Antworten mit Zitat
Benutzer-Profile anzeigen
Nimm, die Zeit, mal bevor du loslegst, und dann nochmal, beim richtigen loslegen.
Ich bin der Meinung, das verschiedene Befehle bei der Erstnutzung erst initialisiert werden.
Hatte da auch schon einmal was.
between angels and insects

Firstdeathmaker

 BeitragDi, Jan 27, 2009 11:14
Antworten mit Zitat
Benutzer-Profile anzeigen
@ Meoqan:

Die Werte die ich bekomme sind aber niemals negativ wenn ich sie in sqr reinstopfe. Schließlich ist
x*x >= 0

Ich hab trotzdem mal mit deinen Funktionen überprüft ob die Werte vielleicht NaN ergeben, dies ist aber nicht der Fall.


@ Jan_:
Ich lasse in meinem Test die Berechnung 100x durchführen und nehme immer wieder die Zeit. Es hat also nichts mit Erstnutzung und Initialisierung oder 2 Sekunden Lag zu tun. Die Zeiten bleiben konstant schlecht oder gut.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Meoqan

 BeitragDi, Jan 27, 2009 13:49
Antworten mit Zitat
Benutzer-Profile anzeigen
hi

deine alte schreibweisse:

c\dist = (n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2])

plus deinem satz: "Wenn man bei Zeile 88 ein sqr vor den Ausdruck auf der rechten Seite setzt, dann wird meine Quicksort-Funktion extrem langsamer"

c\dist = Sqr(n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2])

das ergibnis ist das nicht alles "NaN" ist sondern nur welche wo n1\pos[0] kleiner ist als n2\pos[0]

wenn ich das ganze jetzt in klammernsetze dann ist wieder alles normal:

c\dist = Sqr((n1\pos[0]-n2\pos[0])*(n1\pos[0]-n2\pos[0])+(n1\pos[1]-n2\pos[1])*(n1\pos[1]-n2\pos[1])+(n1\pos[2]-n2\pos[2])*(n1\pos[2]-n2\pos[2]))

und zur überprüfung des ganzen:

c\dist = Sqr(-1)

oder

c\dist = 0

mehr schreib ich jetzt mal nicht dazu Smile mfg meoqan
meine codes sind die essenz des bössen. nicht du veränderst meine codes sondern meine codes verändern dich!

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group