Interesting speed test

BlitzMax Forums/BlitzMax Programming/Interesting speed test

Jake L.

(Posted 2007) [#1]

I've tested two different versions of LinesCollide. The method is pretty the same (solving line-equatations). Version 1 (LinesCollide) calculates everything and then finally determine if the lines collide.

Version 2 (LinesCollide2) tries to calculate only the neccessary to leave the function as fast as possible before everything is calculated. Less calculation, more if-then-else.

I've called both versions with 500k random lines (same seed for both), and LinesCollide (=calc everything, only one if) was always faster (750ms against 790ms for LinesCollide2). That's with debug off.

I personally thought that version 2 would be faster, at least with debug off.

If you want to try by yourself:

superstrict
'graphics 800,600

global _x1#,_x2#,_x3#,_x4#
global _y1#,_y2#,_y3#,_y4#

global time1%,count1%
global time2%,count2%

seedrnd (123456)
delay(2000)
time1=millisecs()
for local i%=1 to 500000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	if LinesCollide(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) then count1:+1
Next
time1=millisecs()-time1
print "Method 1: "+count1+" colisions found in "+time1+" ms"

seedrnd (123456)
time2=millisecs()
for local i%=1 to 500000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	if LinesCollide2(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) then count2:+1
Next
time2=millisecs()-time2
print "Method 2: "+count2+" colisions found in "+time2+" ms"
delay(1000)
end


function LinesCollide%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	local dpx#= x3 - x1 + x4 - x2
	local dpy#= y3 - y1 + y4 - y2
	local qax#= x2 - x1
	local qay#= y2 - y1
	local qbx#= x4 - x3
	local qby#= y4 - y3
	
	local d#= qay*qbx - qby*qax
	local la# = qbx*dpy - qby*dpx
	local lb# = qax*dpy - qay*dpx
	
	if abs(la)<=abs(d)  and abs(lb) <=abs(d) then return true
	return false
End Function

function LinesCollide2%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	local LowerX#,UpperX#,LowerY#,UpperY#
	local Ax#,Ay#,Bx#,By#,Cx#,Cy#,d#,e#,f#
  	
	Ax# = x2 - x1
  	Bx# = x3 - x4
	if Ax<0.0
		LowerX = x2
		UpperX = x1
	else
		UpperX = x2
		LowerX = x1
	end if

	if Bx>0.0
		if UpperX<x4 or x3<LowerX then return false
	elseif (UpperX<x3 or x4<LowerX)
		return false
	endif
  
	Ay = y2 - y1
	By = y3 - y4

	if Ay<0.0
		LowerY = y2
		UpperY = y1
	else
		UpperY = y2
		LowerY = y1
	end if

	if By>0.0
		if UpperY<y4 or y3<LowerY then return false
	elseif UpperY<y3 or y4<LowerY
		return false
	endif

	Cx = x1 - x3
	Cy = y1 - y3
  	d  = (By * Cx) - (Bx * Cy)
  	f  = (Ay * Bx) - (Ax * By)

	if f>0.0
		if d<0.0 or d>f then return false
	elseif d>0.0 or d<f
		return false
	endif

 	e = (Ax * Cy) - (Ay * Cx)

	if f>0.0 then
		if e<0.0 or e>f then return false
	elseif e>0.0 or e<f then
		return false
	endif

  	return true
end function

ImaginaryHuman

(Posted 2007) [#2]

Interesting. I guess sometimes in order to implement a special case of something requires extra overhead. Sometimes it takes longer to ask yourself `if` and to take a branch, than to just do something straight away. Your second line program is obviously quite a bit larger.

H&K	(Posted 2007) [#3]

Deleted. Full code posted later

Derron

(Posted 2007) [#4]

Don't blame the methods...
Most of the time is spend on randomizing the numbers...

So the code posted above isn't really usable to compare effectivity.

bye
MB

Perturbatio

(Posted 2007) [#5]

SuperStrict
'graphics 800,600

Global _x1#,_x2#,_x3#,_x4#
Global _y1#,_y2#,_y3#,_y4#

Global time1%,count1%
Global time2%,count2%

SeedRnd (123456)
Delay(2000)
time1=MilliSecs()
For Local i%=1 To 50000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	If LinesCollide(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) Then count1:+1
Next
time1=MilliSecs()-time1
Print "Method 1: "+count1+" colisions found in "+time1+" ms"

SeedRnd (123456)
time2=MilliSecs()
For Local i%=1 To 50000
	_x1=Rnd(0,800)
	_x2=Rnd(0,800)
	_x3=Rnd(0,800)
	_x4=Rnd(0,800)
	_y1=Rnd(0,600)
	_y2=Rnd(0,600)
	_y3=Rnd(0,600)
	_y4=Rnd(0,600)
	If LinesCollide2(_x1,_y1,_x2,_y2,_x3,_y3,_x4,_y4) Then count2:+1
Next
time2=MilliSecs()-time2
Print "Method 2: "+count2+" colisions found in "+time2+" ms"
Delay(1000)
End


Function LinesCollide%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	Local dpx#= x3 - x1 + x4 - x2
	Local dpy#= y3 - y1 + y4 - y2
	Local qax#= x2 - x1
	Local qay#= y2 - y1
	Local qbx#= x4 - x3
	Local qby#= y4 - y3
	
	Local d#= qay*qbx - qby*qax
	Local la# = qbx*dpy - qby*dpx
	Local lb# = qax*dpy - qay*dpx
	
	If Abs(la)<=Abs(d)  And Abs(lb) <=Abs(d) Then Return True
	Return False
End Function

Function LinesCollide2%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	Local LowerX#,UpperX#,LowerY#,UpperY#
	Local Ax#,Ay#,Bx#,By#,Cx#,Cy#,d#,e#,f#
  	
	Ax# = x2 - x1
  	Bx# = x3 - x4
	If Ax<0.0
		LowerX = x2
		UpperX = x1
	Else
		UpperX = x2
		LowerX = x1
	End If

	If Bx>0.0
		If UpperX<x4 Or x3<LowerX Then Return False
	ElseIf (UpperX<x3 Or x4<LowerX)
		Return False
	EndIf
  
	Ay = y2 - y1
	By = y3 - y4

	If Ay<0.0
		LowerY = y2
		UpperY = y1
	Else
		UpperY = y2
		LowerY = y1
	End If

	If By>0.0
		If UpperY<y4 Or y3<LowerY Then Return False
	ElseIf UpperY<y3 Or y4<LowerY
		Return False
	EndIf

	Cx = x1 - x3
	Cy = y1 - y3
  	d  = (By * Cx) - (Bx * Cy)
  	f  = (Ay * Bx) - (Ax * By)

	If f>0.0
		If d<0.0 Or d>f Then Return False
	ElseIf d>0.0 Or d<f
		Return False
	EndIf

 	e = (Ax * Cy) - (Ay * Cx)

	If f>0.0 Then
		If e<0.0 Or e>f Then Return False
	ElseIf e>0.0 Or e<f Then
		Return False
	EndIf

  	Return True
End Function

Method 1 is always faster for me, H&K's occasionally is slower, but never faster than method 2

H&K	(Posted 2007) [#6]

Don't blame the methods...
Most of the time is spend on randomizing the numbers...

You are of course correct

SuperStrict
Graphics 800,600

Global _x1#,_x2#,_x3#,_x4#
Global _y1#,_y2#,_y3#,_y4#
Global Seed:Int

Global time1%,count1%
Global time2%,count2%
Global time3%,Count3%
Global Array:Int[,] = New Int[500000,8]

While Not KeyDown (Key_Space)
Count1=0
Count2=0
Count3=0

Seed = Rnd (0,MilliSecs())

SeedRnd (Seed)
For Local i%=1 To 500000
	array [i-1,0]=Rnd(0,800)
	array [i-1,1]=Rnd(0,600)
	array [i-1,2]=Rnd(0,800)
	array [i-1,3]=Rnd(0,600)
	array [i-1,4]=Rnd(0,800)
	array [i-1,5]=Rnd(0,600)
	array [i-1,6]=Rnd(0,800)
	array [i-1,7]=Rnd(0,600)

Next

Delay(20)
time1=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count1:+1
Next
time1=MilliSecs()-time1

Delay(20)
time2=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide2(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count2:+1
Next
time2=MilliSecs()-time2

Delay(20)
time3=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide3(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count3:+1
Next
time3=MilliSecs()-time3
Print "Method 1: "+count1+" colisions found in "+time1+" ms"
Print "Method 2: "+count2+" colisions found in "+time2+" ms"
Print "Method 3: "+count3+" colisions found in "+time3+" ms"
Wend

End


Function LinesCollide%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	Local dpx#= x3 - x1 + x4 - x2
	Local dpy#= y3 - y1 + y4 - y2
	Local qax#= x2 - x1
	Local qay#= y2 - y1
	Local qbx#= x4 - x3
	Local qby#= y4 - y3
	
	Local d#= qay*qbx - qby*qax
	Local la# = qbx*dpy - qby*dpx
	Local lb# = qax*dpy - qay*dpx
	
	If Abs(la)<=Abs(d)  And Abs(lb) <=Abs(d) Then Return True
	Return False
End Function

Function LinesCollide3%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	  
  	If Max (x2,x1)<Min (X3,x4) Or Max (x3,x4)<Min (x2,x1) Or Max (y2,y1)<Min (y3,y4) Or Max (y3,y4)<Min (y2,y1) Then Return False
	
	Local Ay# = y2 - y1
	Local By# = y3 - y4
	Local Ax# = x2 - x1
  	Local Bx# = x3 - x4
	Local Cx# = x1 - x3
	Local Cy# = y1 - y3
  	Local d#  = (By# * Cx#) - (Bx# * Cy#)
  	Local f#  = (ay# * Bx#) - (Ax# * By#)
	Local e# = (Ax#* Cy#) - (ay# * Cx#)

	If (f>0.0 And (d<0.0 Or d>f Or e<0.0 Or e>f)) Or (F<=0.0 And (d>0.0 Or d<f Or e>0.0 Or e<f)) Then Return False

  	Return True
End Function

Function LinesCollide2%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	
  		Local LowerX#,UpperX#,LowerY#,UpperY#
	Local Ax#,Ay#,Bx#,By#,Cx#,Cy#,d#,e#,f#
  	
	Ax# = x2 - x1
  	Bx# = x3 - x4
	If Ax<0.0
		LowerX = x2
		UpperX = x1
	Else
		UpperX = x2
		LowerX = x1
	End If

	If Bx>0.0
		If UpperX<x4 Or x3<LowerX Then Return False
	ElseIf (UpperX<x3 Or x4<LowerX)
		Return False
	EndIf
  
	Ay = y2 - y1
	By = y3 - y4

	If Ay<0.0
		LowerY = y2
		UpperY = y1
	Else
		UpperY = y2
		LowerY = y1
	End If

	If By>0.0
		If UpperY<y4 Or y3<LowerY Then Return False
	ElseIf UpperY<y3 Or y4<LowerY
		Return False
	EndIf

	Cx = x1 - x3
	Cy = y1 - y3
  	d  = (By * Cx) - (Bx * Cy)
  	f  = (Ay * Bx) - (Ax * By)

	If f>0.0
		If d<0.0 Or d>f Then Return False
	ElseIf d>0.0 Or d<f
		Return False
	EndIf

 	e = (Ax * Cy) - (Ay * Cx)

	If f>0.0 Then
		If e<0.0 Or e>f Then Return False
	ElseIf e>0.0 Or e<f Then
		Return False
	EndIf

  	Return True

End Function

Method 1 is always faster for me, H&K's occasionally is slower, but never faster than method 2

Well on mine, mine is twice as fast as method 2, but never faster than method 1
The Rnds were the major bottle neck. Test the one Ive just posted. It runs until "Space Down"

Perturbatio

(Posted 2007) [#7]

Method 1: 93866 colisions found in 62 ms
Method 2: 93866 colisions found in 87 ms
Method 3: 93866 colisions found in 96 ms
Method 1: 93773 colisions found in 60 ms
Method 2: 93773 colisions found in 87 ms
Method 3: 93773 colisions found in 96 ms
Method 1: 93680 colisions found in 60 ms
Method 2: 93680 colisions found in 87 ms
Method 3: 93680 colisions found in 96 ms
Method 1: 93500 colisions found in 63 ms
Method 2: 93500 colisions found in 87 ms
Method 3: 93500 colisions found in 96 ms
Method 1: 93566 colisions found in 61 ms
Method 2: 93566 colisions found in 87 ms
Method 3: 93566 colisions found in 96 ms
Method 1: 93830 colisions found in 60 ms
Method 2: 93830 colisions found in 87 ms
Method 3: 93830 colisions found in 96 ms
Method 1: 93749 colisions found in 62 ms
Method 2: 93749 colisions found in 87 ms
Method 3: 93749 colisions found in 96 ms
Method 1: 94207 colisions found in 62 ms
Method 2: 94207 colisions found in 87 ms
Method 3: 94207 colisions found in 96 ms

H&K	(Posted 2007) [#8]

Method 1: 116225 colisions found in 221 ms
Method 2: 116225 colisions found in 455 ms
Method 3: 116225 colisions found in 264 ms

Method 1: 115406 colisions found in 238 ms
Method 2: 115406 colisions found in 470 ms
Method 3: 115406 colisions found in 270 ms

Method 1: 115792 colisions found in 220 ms
Method 2: 115792 colisions found in 453 ms
Method 3: 115792 colisions found in 263 ms

Method 1: 115383 colisions found in 219 ms
Method 2: 115383 colisions found in 466 ms
Method 3: 115383 colisions found in 271 ms

Method 1: 115599 colisions found in 220 ms
Method 2: 115599 colisions found in 453 ms
Method 3: 115599 colisions found in 265 ms

Method 1: 115614 colisions found in 221 ms
Method 2: 115614 colisions found in 461 ms
Method 3: 115614 colisions found in 277 ms

Method 1: 115886 colisions found in 219 ms
Method 2: 115886 colisions found in 448 ms
Method 3: 115886 colisions found in 272 ms

Method 1: 115507 colisions found in 225 ms
Method 2: 115507 colisions found in 467 ms
Method 3: 115507 colisions found in 278 ms

HUmmmmmm. Can we have a few more

Acer Aspire 3000 winXP Home SP2

grable

(Posted 2007) [#9]

Method 1: 115783 colisions found in 46 ms
Method 2: 115783 colisions found in 79 ms
Method 3: 115783 colisions found in 74 ms

Method 1: 115762 colisions found in 48 ms
Method 2: 115762 colisions found in 70 ms
Method 3: 115762 colisions found in 85 ms

Method 1: 115269 colisions found in 47 ms
Method 2: 115269 colisions found in 67 ms
Method 3: 115269 colisions found in 76 ms

Method 1: 115647 colisions found in 48 ms
Method 2: 115647 colisions found in 69 ms
Method 3: 115647 colisions found in 78 ms

Method 1: 115558 colisions found in 47 ms
Method 2: 115558 colisions found in 68 ms
Method 3: 115558 colisions found in 76 ms

Method 1: 115874 colisions found in 48 ms
Method 2: 115874 colisions found in 68 ms
Method 3: 115874 colisions found in 75 ms

Method 1: 115545 colisions found in 48 ms
Method 2: 115545 colisions found in 69 ms
Method 3: 115545 colisions found in 75 ms

Method 1: 115689 colisions found in 47 ms
Method 2: 115689 colisions found in 70 ms
Method 3: 115689 colisions found in 79 ms

Athlon64 3400+ Windows XP SP2 (32bit)

SpaceAce

(Posted 2007) [#10]

Method 1: 115153 colisions found in 47 ms
Method 2: 115153 colisions found in 66 ms
Method 3: 115153 colisions found in 74 ms
Method 1: 115393 colisions found in 47 ms
Method 2: 115393 colisions found in 66 ms
Method 3: 115393 colisions found in 74 ms
Method 1: 115747 colisions found in 46 ms
Method 2: 115747 colisions found in 67 ms
Method 3: 115747 colisions found in 74 ms
Method 1: 116007 colisions found in 47 ms
Method 2: 116007 colisions found in 67 ms
Method 3: 116007 colisions found in 74 ms
Method 1: 115949 colisions found in 51 ms
Method 2: 115949 colisions found in 67 ms
Method 3: 115949 colisions found in 74 ms
Method 1: 116075 colisions found in 46 ms
Method 2: 116075 colisions found in 68 ms
Method 3: 116075 colisions found in 74 ms
Method 1: 115516 colisions found in 46 ms
Method 2: 115516 colisions found in 69 ms
Method 3: 115516 colisions found in 74 ms
Method 1: 115772 colisions found in 46 ms
Method 2: 115772 colisions found in 68 ms
Method 3: 115772 colisions found in 74 ms
Method 1: 115824 colisions found in 46 ms
Method 2: 115824 colisions found in 67 ms
Method 3: 115824 colisions found in 74 ms
Method 1: 115375 colisions found in 47 ms
Method 2: 115375 colisions found in 66 ms
Method 3: 115375 colisions found in 75 ms

AMD Athlon 64 X2 4600+, 2 gigs of RAM, Windows XP Home Edition with Service Pack 2

SpaceAce

Torrente

(Posted 2007) [#11]

Method 1: 115909 colisions found in 55 ms
Method 2: 115909 colisions found in 80 ms
Method 3: 115909 colisions found in 88 ms
Method 1: 115636 colisions found in 56 ms
Method 2: 115636 colisions found in 79 ms
Method 3: 115636 colisions found in 87 ms
Method 1: 115657 colisions found in 55 ms
Method 2: 115657 colisions found in 79 ms
Method 3: 115657 colisions found in 88 ms
Method 1: 115406 colisions found in 56 ms
Method 2: 115406 colisions found in 79 ms
Method 3: 115406 colisions found in 87 ms
Method 1: 115461 colisions found in 55 ms
Method 2: 115461 colisions found in 79 ms
Method 3: 115461 colisions found in 88 ms
Method 1: 115402 colisions found in 55 ms
Method 2: 115402 colisions found in 79 ms
Method 3: 115402 colisions found in 87 ms
Method 1: 115741 colisions found in 56 ms
Method 2: 115741 colisions found in 79 ms
Method 3: 115741 colisions found in 88 ms
Method 1: 116169 colisions found in 56 ms
Method 2: 116169 colisions found in 79 ms
Method 3: 116169 colisions found in 88 ms
Method 1: 115926 colisions found in 55 ms
Method 2: 115926 colisions found in 78 ms
Method 3: 115926 colisions found in 87 ms
Method 1: 115758 colisions found in 57 ms
Method 2: 115758 colisions found in 78 ms
Method 3: 115758 colisions found in 87 ms
Method 1: 116293 colisions found in 55 ms
Method 2: 116293 colisions found in 78 ms
Method 3: 116293 colisions found in 88 ms

AMD Athlon 64 X2 3800+, 1G RAM, Windows XP Service Pack 2

Oh, btw, you spelled collisions wrong ;)

Jake L.

(Posted 2007) [#12]

Sure, Rnd takes the most time, but that doesn't matter as it should need the same time for both methods, so the result is compareable again.

Jake

PS: Torrente, you're right, here's the missing letter: l ;)

LarsG

(Posted 2007) [#13]

Method 1: 116066 colisions found in 52 ms
Method 2: 116066 colisions found in 79 ms
Method 3: 116066 colisions found in 109 ms

Method 1: 115853 colisions found in 52 ms
Method 2: 115853 colisions found in 81 ms
Method 3: 115853 colisions found in 112 ms

Method 1: 115801 colisions found in 51 ms
Method 2: 115801 colisions found in 79 ms
Method 3: 115801 colisions found in 111 ms

Method 1: 116252 colisions found in 53 ms
Method 2: 116252 colisions found in 80 ms
Method 3: 116252 colisions found in 110 ms

Method 1: 115178 colisions found in 51 ms
Method 2: 115178 colisions found in 80 ms
Method 3: 115178 colisions found in 109 ms

Method 1: 115494 colisions found in 53 ms
Method 2: 115494 colisions found in 81 ms
Method 3: 115494 colisions found in 111 ms

Method 1: 115880 colisions found in 52 ms
Method 2: 115880 colisions found in 79 ms
Method 3: 115880 colisions found in 110 ms

Method 1: 116172 colisions found in 52 ms
Method 2: 116172 colisions found in 80 ms
Method 3: 116172 colisions found in 109 ms

Method 1: 115674 colisions found in 51 ms
Method 2: 115674 colisions found in 80 ms
Method 3: 115674 colisions found in 111 ms

Method 1: 115286 colisions found in 51 ms
Method 2: 115286 colisions found in 80 ms
Method 3: 115286 colisions found in 110 ms

with a fair amount of apps running on the compy..

H&K	(Posted 2007) [#14]

Sure, Rnd takes the most time, but that doesn't matter as it should need the same time for both methods, so the result is compareable again.

Well, I was going to post an answer like that, but then I realised that it does make a differance. For wereas the results are comparible, the % differance is greater.
So I agree with you that the fastest will still be the fastest, but it will be by a greater amount. eg You had Method1 as about 6% faster. With the edited program is it not now closer to 80% faster? (LarsG Has it as 120%Faster)

Jake L.

(Posted 2007) [#15]

Who cares about how much faster one method is about another? No offense, but unless I (or anyone) finds a method faster than method 1 (which seems to be the fastest at the moment), this is the method to use, right?

Well, maybe it could be interesting to have a general guide which basic operations (+-*/, if-then-else, select-case, etc..) takes more time than others. With such a guide one could code faster functions more easy. On the other side I don't profile most highlevel-functions. Linechecking and other essential stuff called a hundred times each frame are very special cases and the only ones worth for optimization imho.

In fact I'm excited how fast this little function is. I thought about splitting concave polygons into convex ones for faster collision checking. Now I see no need for this step. Should be fast enough for my project when doing AABB-check prior. More time for other things...

Jake

PS: What about starting a competition for "usual tasks"-functions like different collisions, basic physics-calculations and such? I'm sure we find a lot of common functions everyone of us use, so having a FAQ/Howto with the fastest way to do it in BM would be nice, wouldn't it?

H&K	(Posted 2007) [#16]

Who cares about how much faster one method is about another?

Well you. As proven by

No offense, but unless I (or anyone) finds a method faster than method 1 (which seems to be the fastest at the moment), this is the method to use, right?

What was interesting is that Method 2 is only 50% of the speed of Method three in DEBUG, but about 110% of the speed in release. Somthing which I didnt think would happen.

Jake L.

(Posted 2007) [#17]

That's indeed interesting, not to say a little bit weird.

P.S: I meant the %-difference with "how much faster than another"...

zzz	(Posted 2007) [#18]

Some results from me.

Method 1: 115838 colisions found in 46 ms
Method 2: 115838 colisions found in 65 ms
Method 3: 115838 colisions found in 72 ms

Method 1: 115824 colisions found in 45 ms
Method 2: 115824 colisions found in 65 ms
Method 3: 115824 colisions found in 72 ms

Method 1: 115908 colisions found in 46 ms
Method 2: 115908 colisions found in 66 ms
Method 3: 115908 colisions found in 72 ms

Method 1: 115016 colisions found in 45 ms
Method 2: 115016 colisions found in 65 ms
Method 3: 115016 colisions found in 72 ms

Thats not enough code in the linescollide function(s) to justify branching for optimization at all, and the use of abs/max/min slows it down even more.

Having said that, im not sure if you can manage without the latter.

zzz	(Posted 2007) [#19]

Shaved of a few milliseconds.

Method 1: 116235 colisions found in 45 ms
Method 2: 116235 colisions found in 66 ms
Method 3: 116235 colisions found in 77 ms
Method 4: 116235 colisions found in 41 ms

Method 1: 115877 colisions found in 46 ms
Method 2: 115877 colisions found in 66 ms
Method 3: 115877 colisions found in 77 ms
Method 4: 115877 colisions found in 41 ms

Method 1: 115740 colisions found in 45 ms
Method 2: 115740 colisions found in 67 ms
Method 3: 115740 colisions found in 73 ms
Method 4: 115740 colisions found in 41 ms

Method 1: 115597 colisions found in 45 ms
Method 2: 115597 colisions found in 66 ms
Method 3: 115597 colisions found in 75 ms
Method 4: 115597 colisions found in 42 ms

And the code.

SuperStrict
Graphics 800,600

Global _x1#,_x2#,_x3#,_x4#
Global _y1#,_y2#,_y3#,_y4#
Global Seed:Int

Global time1%,count1%
Global time2%,count2%
Global time3%,Count3%
Global time4%,count4%
Global Array:Int[,] = New Int[500000,8]

While Not KeyDown (Key_Space)
Count1=0
Count2=0
Count3=0
Count4=0

Seed = Rnd (0,MilliSecs())

SeedRnd (Seed)
For Local i%=1 To 500000
	array [i-1,0]=Rnd(0,800)
	array [i-1,1]=Rnd(0,600)
	array [i-1,2]=Rnd(0,800)
	array [i-1,3]=Rnd(0,600)
	array [i-1,4]=Rnd(0,800)
	array [i-1,5]=Rnd(0,600)
	array [i-1,6]=Rnd(0,800)
	array [i-1,7]=Rnd(0,600)

Next

Delay(20)
time1=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count1:+1
Next
time1=MilliSecs()-time1

Delay(20)
time2=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide2(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count2:+1
Next
time2=MilliSecs()-time2

Delay(20)
time3=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide3(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count3:+1
Next
time3=MilliSecs()-time3

Delay(20)
time4=MilliSecs()
For Local i%=1 To 500000
	If LinesCollide4(array [i-1,0],array [i-1,1],array [i-1,2],array [i-1,3],array [i-1,4],array [i-1,5],array [i-1,6],array [i-1,7]) Then count4:+1
Next
time4=MilliSecs()-time4
Print "Method 1: "+count1+" colisions found in "+time1+" ms"
Print "Method 2: "+count2+" colisions found in "+time2+" ms"
Print "Method 3: "+count3+" colisions found in "+time3+" ms"
Print "Method 4: "+count4+" colisions found in "+time4+" ms"
Print ""
Wend

End


Function LinesCollide%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	Local dpx#= x3 - x1 + x4 - x2
	Local dpy#= y3 - y1 + y4 - y2
	Local qax#= x2 - x1
	Local qay#= y2 - y1
	Local qbx#= x4 - x3
	Local qby#= y4 - y3
	
	Local d#= qay*qbx - qby*qax
	Local la# = qbx*dpy - qby*dpx
	Local lb# = qax*dpy - qay*dpx
	
	If Abs(la)<=Abs(d)  And Abs(lb) <=Abs(d) Then Return True
	Return False
End Function

Function LinesCollide4%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	Local dpx#= x3 - x1 + x4 - x2
	Local dpy#= y3 - y1 + y4 - y2
	Local qax#= x2 - x1
	Local qay#= y2 - y1
	Local qbx#= x4 - x3
	Local qby#= y4 - y3
	
	Local d#= qay*qbx - qby*qax
	Local la# = qbx*dpy - qby*dpx
	Local lb# = qax*dpy - qay*dpx
	
	local ad# = d*d
	Local ala# = la*la
	local alb# = lb*lb
	
	Return (alb <= ad) & (ala <= ad)

End Function

Function LinesCollide3%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	  
  	If Max (x2,x1)<Min (X3,x4) Or Max (x3,x4)<Min (x2,x1) Or Max (y2,y1)<Min (y3,y4) Or Max (y3,y4)<Min (y2,y1) Then Return False
	
	Local Ay# = y2 - y1
	Local By# = y3 - y4
	Local Ax# = x2 - x1
  	Local Bx# = x3 - x4
	Local Cx# = x1 - x3
	Local Cy# = y1 - y3
  	Local d#  = (By# * Cx#) - (Bx# * Cy#)
  	Local f#  = (ay# * Bx#) - (Ax# * By#)
	Local e# = (Ax#* Cy#) - (ay# * Cx#)

	If (f>0.0 And (d<0.0 Or d>f Or e<0.0 Or e>f)) Or (F<=0.0 And (d>0.0 Or d<f Or e>0.0 Or e<f)) Then Return False

  	Return True
End Function

Function LinesCollide2%(x1#,y1#,x2#,y2#,x3#,y3#,x4#,y4#)
	
  		Local LowerX#,UpperX#,LowerY#,UpperY#
	Local Ax#,Ay#,Bx#,By#,Cx#,Cy#,d#,e#,f#
  	
	Ax# = x2 - x1
  	Bx# = x3 - x4
	If Ax<0.0
		LowerX = x2
		UpperX = x1
	Else
		UpperX = x2
		LowerX = x1
	End If

	If Bx>0.0
		If UpperX<x4 Or x3<LowerX Then Return False
	ElseIf (UpperX<x3 Or x4<LowerX)
		Return False
	EndIf
  
	Ay = y2 - y1
	By = y3 - y4

	If Ay<0.0
		LowerY = y2
		UpperY = y1
	Else
		UpperY = y2
		LowerY = y1
	End If

	If By>0.0
		If UpperY<y4 Or y3<LowerY Then Return False
	ElseIf UpperY<y3 Or y4<LowerY
		Return False
	EndIf

	Cx = x1 - x3
	Cy = y1 - y3
  	d  = (By * Cx) - (Bx * Cy)
  	f  = (Ay * Bx) - (Ax * By)

	If f>0.0
		If d<0.0 Or d>f Then Return False
	ElseIf d>0.0 Or d<f
		Return False
	EndIf

 	e = (Ax * Cy) - (Ay * Cx)

	If f>0.0 Then
		If e<0.0 Or e>f Then Return False
	ElseIf e>0.0 Or e<f Then
		Return False
	EndIf

  	Return True

End Function

I noticed that between blitzmax 118 and 124, method 2 and 3 were one or two milliseconds faster on 124, but method 4 was 10! milliseconds faster on 118.

H&K	(Posted 2007) [#20]

Ok bare in mind that Im rubbish at C++, but I had a go anyway, just Method1

#include "DarkGDK.h" 


int time1;

bool LinesCollide (int x1,int y1, int x2, int y2, int x3,int y3,int x4,int y4)
{
	int dpx = x3 - x1 + x4 - x2;
	int dpy= y3 - y1 + y4 - y2;
	int qax= x2 - x1;
	int qay= y2 - y1;
	int qbx= x4 - x3;
	int qby= y4 - y3;
	
	int d= qay*qbx - qby*qax;
	int la = qbx*dpy - qby*dpx;
	int lb = qax*dpy - qay*dpx;
	
	if (dbABS (float (la))<=dbABS(float (d)) && dbABS(float (lb))<=dbABS(float (d))) return true;
	
	return false;
}


void DarkGDK ( void )
{ 
	dbRandomize (dbTimer());
	dbSyncOn ( );
	dbSync();
	
	int TheArray [500000][8] = {0};
	
	for (int g = 0;g<6;g++)
	{
		int Count1 = 0;
	
		for(int i = 0; i < 500000; i++)
		{
			TheArray [i][0]=dbRND ( 799 ) ;
			TheArray [i][1]=dbRND ( 599 ) ;
			TheArray [i][2]=dbRND ( 799 ) ;
			TheArray [i][3]=dbRND ( 599 ) ;
			TheArray [i][4]=dbRND ( 799 ) ;
			TheArray [i][5]=dbRND ( 599 ) ;
			TheArray [i][6]=dbRND ( 799 ) ;
			TheArray [i][7]=dbRND ( 599 ) ;
		}

	
		dbWait (20);
		time1=dbTimer();	
		for(int i = 1; i < 500000; i++)
		{
			if (LinesCollide (TheArray [i-1][0],TheArray [i-1][1],TheArray [i-1][2],TheArray [i-1][3],TheArray [i-1][4],TheArray [i-1][5],TheArray [i-1][6],TheArray [i-1][7])) Count1++;
		}
		time1 = dbTimer()-time1;
		dbText (10,20*g,dbStr(Count1));
		dbText (90,20*g,dbStr(time1));
		dbSync ();
	}
		dbWaitKey ();
}

Note 1: As you may be able to tell, its using DarkGDK, and The free VC8 express. And possibly someone who know what they are doing could improve it.
Note 2:I got it going with a Low Array size, and then it stopped working with the larger size. Ok so it was just nessesary to increase the Stack size, but Ive never had to do anything like that with BMax
Note 3:I dont think that I compiled it as Managed C++, and am almost certain that I ran it as core C++

DeBug

116109     211
115805     223
115598     198
115891     199
115433     199
115914     204

Max, 271,274,276,270,269

Release

115598     161
115878     156
116235     159
116088     157
115766     157
115657     158

Max, 70,65,65,65,64

I dont think Ive made the code any differently in the C version, but if anyone want to point out a bottleneck Ive introduced please do.