Important tip

BlitzMax Forums/BlitzMax Programming/Important tip

JoshK

(Posted 2006) [#1]

I just implemented a portal system into my engine and came across an important design aspect that affects any complex BlitzMax program that uses lists.

I was wondering why my portal routine took 0 msecs in a small scene, and 30-60 msecs in a large scene with the same number of portals. I finally isolated the problem in a part of the code that freed a temporary object that had been created. The slowdown was caused entirely by the tlist.remove() command!

The tlist in question had about 600 items in the larger map. I guessed that the routine probably sorts through the list from start to finish, so I changed the code to add objects to the front of the tList, using tlist.addfirst() instead of tlist.addlast(). My portal routine sped up from 30-60 msecs to 0-1.

I think a good general rule when adding objects to a tlist is to use the tlist.addfirst() method. Your static objects will gradually sort themselves towards the back, while your dynamic objects that get created and freed a lot will always be quickly accessible to a tlist.remove() call.

N	(Posted 2006) [#2]

Or you could just store the link like so:

Strict

Type Foo
    Field link:TLink
End Type

Const Count = 1000000
Local arr:Foo[COUNT]
Local listRemove:TList = New TList
Local linkRemove:TList = New TList

Local f:Foo
For Local i:Int = 0 To COUNT-1
    arr[i] = New Foo
    listRemove.AddLast( arr[i] )
    arr[i].link = linkRemove.AddLast( arr[i] )
Next

Delay 100

Local t:Int = Millisecs( )
For Local i:Int = 0 To COUNT-1
    listRemove.Remove( arr[i] )
Next
t = Millisecs( ) - t
Print t

Delay 100

t = Millisecs( )
For Local i:Int = 0 To COUNT-1
    arr[i].link.Remove( )
Next
t = Millisecs( ) - t
Print t

Input

TList.Remove searches through a list for the object you pass to it, which can take a large amount of time depending on the amount of links in the list.

By storing the link and using TLink.Remove, you never have to use TList.Remove, which means that there is no time spent searching for the link in the list that references the object in question.

FlameDuck

(Posted 2006) [#3]

Also if you find yourself using TList.Sort() a lot on large data sets, it is actually faster to convert to an Array, sort that (because arrays are sorted using QuickSort, rather than BubbleSort) and then move it back into a list.

Robert Cummings

(Posted 2006) [#4]

Interesting - thanks for the tips.

Robert

(Posted 2006) [#5]

The slowdown was caused entirely by the tlist.remove() command!

If you need fast deletion then a linked list data structure is not really appropriate.

The TMap type is probably better suited to your needs.

ozak	(Posted 2006) [#6]

No vector lists? (Array with resize on boundary overflow)

Shambler

(Posted 2006) [#7]

An interesting and useful tip, thanks.

Dreamora

(Posted 2006) [#8]

For fast insert and remove I would really suggest creating a AVL tree structure or something similar. (for 3D perhaps even quad tree to have sorting in 2D)
Its significantly faster on all operations that need to be done.

Grey Alien

(Posted 2006) [#9]

I read the docs when I bought BlitzMax and they said this "You can also remove objects with the ListRemove command. However this is not as efficient as using RemoveLink because the list must first be searched for the object to be removed." So luckily I know about this tip thanks, but it's a good one.

Flameduck's convert to array to sort tip is neat as well.

Tibit

(Posted 2006) [#10]

Yes, Tlist Remove is slow, and it could be dangerous if it is used a lot during small periods of time on large lists. Using links seems like a very good solution. Using addfirst instead of addlast is also a great tip.

Here is a Test which includes TMap to (copy from Noel's), can you verify if this is correct? TMap seems to have the same speed as List with TLink. However the time to add an object to a TMap is imense!

And why use bubblesort when quicksort is so much faster? I did a quick test on this too and quicksort is very much faster, I do not understand why TLists are not converted to arrays and sorted and then back as standard, because it seems to be a hugh speed gain in doing so.

add 10000 objects to three lists
Adding..
TList time: 8
TLink + TList time: 9
TMap time: 12251

Lists filled with 10000 objects each, removing..

Removed all from normal TList, time taken: 6
Removed using TLink in a TList, time taken: 4
Removed all object in TMap, time taken: 3

' Reminder for using TMap
' Insert( Key:Object, O:Object ) - Instead of AddLast/AddFirst
' ValueForKey( Key ) ' Get Specific Object
' Remove( Key )


'TLIST with TLink
'__________________________________

SuperStrict 

Type TestObj
    Field link:TLink
End Type

Const COUNT:Int = 10000
Local TestListA:TList = New TList
Local TestListB:TList = New TList
Local TestListC:TMap  = New TMap

Local T:TestObj
Local Time:Int = MilliSecs( )

Print "Step I is to add "+COUNT+" objects to three lists"
Print "Adding.."

' Add to a TList
For Local i:Int = 1 To COUNT
    Local T:TestObj = New TestObj
    TestListA.AddLast( T )'List A
Next
Print "TList time: "+(MilliSecs( ) - Time)

' Add to a TList and saving the TLink
Time:Int = MilliSecs( )
For Local i:Int = 1 To COUNT
    Local T:TestObj = New TestObj
    TestListB.AddLast( T )'List B /w Links
	T.Link = TestListB.LastLink()'Save Link
Next
Print "TLink + TList time: "+(MilliSecs( ) - Time)

' Add to a TMap
Time:Int = MilliSecs( )
For Local i:Int = 1 To COUNT
    Local T:TestObj = New TestObj
	'TMap
	TestListC.Insert( T, T ) 'Use object as Key 
Next
Print  "TMap time: "+(MilliSecs( ) - Time)
Print 
Print "Lists filled with "+COUNT+" objects each, removing.."
Print 
Delay 100 '__________________________________

' Test Normal Remove List A
Time:Int = MilliSecs( )
For T = EachIn TestListA
    TestListA.Remove( T )
Next

Print "Removed all from normal TList, time taken: "+(MilliSecs( ) - Time)

Delay 100 '__________________________________

' Test Quick Link Remove List B
Time = MilliSecs( )
For T = EachIn TestListB
	T.Link.Remove()
Next

Print "Removed using TLink in a TList, time taken: "+(MilliSecs( ) - Time)

Delay 100 '__________________________________
' Test TMap Remove from List C
Time = MilliSecs( )
For T = EachIn TestListC
	TestListC.Remove( T )
Next

Print "Removed all object in TMap, time taken: "+(MilliSecs( ) - Time)

Dreamora

(Posted 2006) [#11]

I fear your way of doing it totally destroys TMAP
TMAP is not a balanced bin tree so your adding will create a linear list in the end ... (its totally degenerated)
It would need an AVL underlaying to become performant if "sorted data" are put into it.

Tibit

(Posted 2006) [#12]

You mean using objects as keys? but how else can I retreive a specific object without naming them all? If every bullets must have a name then it gets complicated.

Dreamora

(Posted 2006) [#13]

No what I mean is: Don't create them in a row and enter them like that. In a real environment you would use strings or something as key and they wont be ascending ordered so it won't degenerate that bad.

Oddball

(Posted 2006) [#14]

Cheers people. This is all useful info. Keep it coming.