faster nested loops

This code has been declared by its author to be Public Domain code.

faster nested loops by Nate the Great

2009

well this is a little type I put together to improve the speed of my physics engine which uses many nested loops... lists in general slow down nested loops a lot more than arrays do so I decided to make my own little type to do the array stuff behind the scenes so its almost like your using a tlist without the slowdown if you have a lot of objects. speed example posted below, on my pc, the arrays take about two thirds of the time the tlists do... which is a lot when trying to shave off a few milliseconds

edit: all known bugs fixed! see examples for how to delete things from an array, it is a little hard to get why but it is the only way to keep the array system fast and flexible and error proof... you must also loop through them backwards if you want to delete everything in one fowl swoop... but you may delete in any order going one at a time

Type Array		'array to act like tlist except a million times faster
	Field a:Object[10]	'starts off with 100 objects...
	Field last:Int
		
	Function Create:Array(Length:Int)
		Local a:array = New array
		a.a = a.a[..length]
		Return a:array
	End Function
	
	Method length:Int()
		Return (last-1)
	End Method
	
	Method add:Int(obj:Object)
		a[last] = obj
		If a.length < last+2 Then
			a = a[..(a.length+1000)]
		EndIf
		last :+ 1
		Return (last-1)
	End Method
	
	Method Getbyindex:Object(in:Int)
		Return a[in]
	End Method
	
	Method remove:Object(index:Int)
		a[index] = a[last-1]
		a[last-1] = Null
		last :- 1
		Return a[index]
	End Method
End Type

Comments

Nate the Great

2009

example using arrays

SuperStrict

Print "Creating foo's"

Local i:Int = MilliSecs()
Local j:Int
Local k:Int
For j = 0 To 10000
	foo.Create(j)
Next

Print MilliSecs()-i

Local f:foo
Local ff:foo
Local blah:Int

Print "Looping through all foo's"

i = MilliSecs()


For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	For k = 0 To foo.fooarray.length()
		ff:foo = foo(foo.fooarray.getbyindex(k))
		ff.blah = f.blah	'do somethin...
	Next
Next

Print MilliSecs()-i
Print "Removing foo's"
i = MilliSecs()

For j = foo.fooarray.length() To 0 Step -1
	f:foo = foo(foo.fooarray.getbyindex(j))
	f.remove()
Next

Print MilliSecs()-i


Type foo
	Global fooarray:Array = Array.Create(1000)
	
	Field blah:Int
	Field index:Int
	
	Function Create:foo(blah:Int)
		Local f:foo = New foo
		f.blah = blah
		f.index = fooarray.add(f:foo)
		Return f:foo
	End Function
	
	Method remove()
		Local f:foo = foo(foo.fooarray.remove(index))		
		If f:foo Then f.index = index
	End Method
End Type


Type Array		'array to act like tlist except a million times faster
	Field a:Object[10]	'starts off with 100 objects...
	Field last:Int
		
	Function Create:Array(Length:Int)
		Local a:array = New array
		a.a = a.a[..length]
		Return a:array
	End Function
	
	Method length:Int()
		Return (last-1)
	End Method
	
	Method add:Int(obj:Object)
		a[last] = obj
		If a.length < last+2 Then
			a = a[..(a.length+1000)]
		EndIf
		last :+ 1
		Return (last-1)
	End Method
	
	Method Getbyindex:Object(in:Int)
		Return a[in]
	End Method
	
	Method remove:Object(index:Int)
		a[index] = a[last-1]
		a[last-1] = Null
		last :- 1
		Return a[last]
	End Method
End Type

example using tlists instead

SuperStrict

Print "Creating foo's"

Local i:Int = MilliSecs()
Local j:Int
For j = 0 To 10000
	foo.Create(j)
Next

Print MilliSecs()-i

Local f:foo
Local ff:foo
Local blah:Int

Print "Looping through all foo's"

i = MilliSecs()


For f:foo = EachIn foo.foolist
	For ff:foo = EachIn foo.foolist
		ff.blah = f.blah	'do somethin...
	Next
Next

Print MilliSecs()-i
Print "Removing foo's"
i = MilliSecs()

For f:foo = EachIn foo.foolist
	foo.foolist.remove(f:foo)
Next

Print MilliSecs()-i


Type foo
	Global foolist:TList = New TList	
	Field blah:Int
		
	Function Create:foo(blah:Int)
		Local f:foo = New foo
		f.blah = blah
		foolist.addlast(f:foo)
		Return f:foo
	End Function
End Type

if you modify the examples not to use nested loops they are almost the same but using 3 nested loops will increase the difference in the time it takes

BlitzSupport

2009

Great idea, and the examples certainly showed the difference here. (About a second slower with lists -- 1300 ms vs 2200 ms.)

TaskMaster

2009

I think I see a problem with your array type.

If somebody is holding on to the indexes into the array of their objects for fast reference, and then remove an object, your are moving the last one to the place in the list where the removed one was. Which means the index the user is holding for that object is wrong...

TaskMaster

2009

Also, I just noticed for your length method, you might want to return last, not last-1. With nothing in the list, do you want the length to be -1 or 0. I would think 0.

outsider

2009

Hi Nate the Great, there is error in your example using arrays. I'm using BM 1.36, and there

For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	foo.fooarray.remove(f:foo,f.index)
Next

I have a message:
"Unhandled Exception: Attempt to acces field or method of Null object".
I do that:

For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	DebugLog "index: "+f.index
	DebugLog "foo.length: "+foo.fooarray.length()
	foo.fooarray.remove(f:foo,f.index)
Next

and my output looks like that:

DebugLog:index: 0
DebugLog:foo.length: 1000
DebugLog:index: 1
DebugLog:foo.length: 999
DebugLog:index: 2
DebugLog:foo.length: 998
DebugLog:index: 3
...
DebugLog:index: 498
DebugLog:foo.length: 502
DebugLog:index: 499
DebugLog:foo.length: 501
DebugLog:index: 500
DebugLog:foo.length: 500

After index=500 program crash. It's mean that index increase but foo.length decrase, and they meet in the middle.

Edit: Maybe this can help:

for j = foo.fooarray.length() To 0 Step -1

TaskMaster

2009

The For loop just needs to be either an Until or To length -1.

outsider

2009

Thanks TaskMaster, but this code:

For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	foo.fooarray.remove(f:foo,f.index)
Next

and this:

For j = 0 To foo.fooarray.length()-1
	f:foo = foo(foo.fooarray.getbyindex(j))
	foo.fooarray.remove(f:foo,f.index)
Next

crash that same, exacly after this moment:

DebugLog:index: 500
DebugLog:foo.length: 500

Is it work for you this Nate the Great's example?

Sorry for my english.

TaskMaster

2009

I don't think you can loop like that. I think the .length in the For loop is only going to get evaluated once. So it will always try to go to the arrays original length, even though the length is decreasing because you are removing items.

I don't see why you would do that anyway, since you should just be able to clear it.

outsider

2009

You have a right TaskMaster, but this example:

SuperStrict

Print "Creating foo's"

Local i:Int = MilliSecs()
Local j:Int
Local k:Int
For j = 0 To 10000
	foo.Create(j)
Next

Print MilliSecs()-i

Local f:foo
Local ff:foo
Local blah:Int

Print "Looping through all foo's"

i = MilliSecs()


For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	For k = 0 To foo.fooarray.length()
		ff:foo = foo(foo.fooarray.getbyindex(k))
		ff.blah = f.blah	'do somethin...
	Next
Next

Print MilliSecs()-i
Print "Removing foo's"
i = MilliSecs()

For j = 0 To foo.fooarray.length()
	f:foo = foo(foo.fooarray.getbyindex(j))
	foo.fooarray.remove(f:foo,f.index)
Next

Print MilliSecs()-i


Type foo
	Global fooarray:Array = Array.Create(1000)
	
	Field blah:Int
	Field index:Int
	
	Function Create:foo(blah:Int)
		Local f:foo = New foo
		f.blah = blah
		f.index = fooarray.add(f:foo)
		Return f:foo
	End Function
End Type


Type Array		'array to act like tlist except a million times faster
	Field a:Object[10]	'starts off with 100 objects...
	Field last:Int
		
	Function Create:Array(Length:Int)
		Local a:array = New array
		a.a = a.a[..length]
		Return a:array
	End Function
	
	Method length:Int()
		Return (last-1)
	End Method
	
	Method add:Int(obj:Object)
		a[last] = obj
		If a.length < last+2 Then
			a = a[..(a.length+1000)]
		EndIf
		last :+ 1
		Return (last-1)
	End Method
	
	Method Getbyindex:Object(in:Int)
		Return a[in]
	End Method
	
	Method remove(obj:Object,index:Int = -1)
		If index > -1 Then
			a[index] = a[last]
			a[last] = Null
			last :- 1
		Else
			For Local i:Int = 0 Until last
				If obj = a[i] Then
					last :- 1
					a[i] = a[last]
					a[last] = Null
				EndIf
			Next
		EndIf
	End Method
End Type

doesn't work on my machine. Error "Unhandled Exception: Attempt to acces field or method of Null object" is in line

foo.fooarray.remove(f:foo,f.index)

I don't know why this doesn't work :/. I have XP sp2, BM1.36.

Nate the Great

2010

hmm sorry about the problems guys... ill look into it... if its not working, could be a real problem.. and you should get different results on different chip sets, some are more optimized for the way arrays work, some more so for tlists

Nate the Great

2010

all fixed!

you must note that you have to loop through them backwards to delete them correctly... but deleting one by one you can go in any order...

there is also a special way you must delete them... and the "special" way keeps the array nice and clean and keeps it goin fast

Pineapple

2010

I see you're putting an impressive amount of effort toward optimization here ;)

Nate the Great

2010

its all needed though for what im planning :)

Code Archives Forum