RemoveLink or ListRemove?

BlitzMax Forums/BlitzMax Programming/RemoveLink or ListRemove?

Regular K

(Posted 2006) [#1]

I was experimenting with lists, and I found out on my machine at least, ListRemove is about 6x faster than RemoveLink.

SuperStrict

Type TObject
	Field Link:TLink
	
	Function Create:TObject()
		Local o:TObject=New TObject
		
		o.Link=ListAddLast(List,o)
		
		Return o
	End Function
	
	Method RemoveByLink()
		RemoveLink Link
	End Method
	
	Method RemoveByList()
		ListRemove List,Self
	End Method
End Type

Global List:TList=CreateList()

Global maxobjects:Int=163840

PopulateList()

RemoveAllByLink()

PopulateList()

RemoveAllByList()

Function PopulateList()
	Local start:Int,time:Int,i:Int

	start=MilliSecs()
	For i=0 To maxobjects
		TObject.Create()
	Next
	time=MilliSecs()-start
	Print "Add To List Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

Function RemoveAllByLink()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	For o=EachIn List
		o.RemoveByLink()
	Next
	time=MilliSecs()-start
	Print "Remove By Link Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

Function RemoveAllByList()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	For o=EachIn List
		o.RemoveByList()
	Next
	time=MilliSecs()-start
	Print "Remove By List Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

But I've heard to always use RemoveLink, even the documents suggests that ("RemoveLink is more efficient than ListRemove.")

I'm I missing something or is ListRemove truely faster than RemoveLink?

It doesn't really make a big difference unless if your handling tens of thousands of objects.

dmaz	(Posted 2006) [#2]

that's basically impossible here, so lets look at the test itself

At first I got this in a release build
Remove By Link Time: 363 ms
Remove By List Time: 60 ms

Then, I had swapped when the 2 functions get called in the code and got
Remove By List Time: 297 ms
Remove By Link Time: 50 ms

The timing looks like it’s being affected by the memory the allocation….

So, this is not a good test. doesn’t matter RemoveLink can’t be slower than ListRemove because ListRemove uses RemoveLink after it potentially runs through the whole list checking each element until it finds what it’s looking for. Another problem with this test, you’re not randomizing the removals. You are always only removing the first link in the list which is always going to be the fastest implementation of ListRemove. (that should almost be as fast as RemoveLink).

so the point about using RemoveLink... or as I prefer, thelink.Remove, is you don't scan the list. Think about that. say you have a sprite list with 100 sprites and you do an eachin removing the sprite that are off screen. when you call ListRemove it actually loops through the list unitl it 'happens' to find the matching link. so you would do that for each sprite you going to remove! on the hand, with link remove you are not looping though the list at all.

dmaz	(Posted 2006) [#3]

after I notice some other weird timings I tested it a little more. I pulled the printing out of the functions and placed them at the end of the program and I put the Garbage Collector in manual mode... still no randomizing...

run 1
list: 25
list: 25
link: 23
list: 28
link: 24

run2 change order
list: 25
link: 24
list: 31
link: 23
list: 26

with the GC in manual it seemed to take a long time for the program to clean up at the end...?

dmaz	(Posted 2006) [#4]

ok, I couldn't end without showing how slow ListRemove can actually be... I took your program, added a int that was a mod 256 of the object position. so in the code below "num" will be 0-256 for the first 256 items and then 0-256 for the next and so on.

now, in the remove function I only remove the item if it equals 1. I would expect the ListRemove to REALLY slow down while the removeLink should be exactly the same.

run the program and after a long long time I got this
link: 20
list: 16685
link: 63
list: 38900

that's why you should remove by link when programming games.

SuperStrict

Type TObject
	Field Link:TLink
	Field num:Int = 0
	
	Function Create:TObject()
		Local o:TObject=New TObject
		
		o.Link=ListAddLast(List,o)
		
		Return o
	End Function
	
	Method RemoveByLink()
		RemoveLink Link
	End Method
	
	Method RemoveByList()
		ListRemove List,Self
	End Method
	
End Type

GCSetMode(0)

Global List:TList=CreateList()

Global maxobjects:Int=163840

PopulateList()
Local time1:Int = RemoveAllByLink()

PopulateList()
Local time2:Int = RemoveAllByList()

PopulateList()
Local time3:Int = RemoveAllByLink()

PopulateList()
Local time4:Int = RemoveAllByList()

Print "link: "+time1
Print "list: "+time2
Print "link: "+time3
Print "list: "+time4

GCCollect()

Function PopulateList()
	Local start:Int,time:Int,i:Int

	start=MilliSecs()
	For i=0 To maxobjects
		Local o:TObject = TObject.Create()
		o.num = i Mod 256
	Next
	time=MilliSecs()-start
'	Print "Add To List Time: " +time+ " ms"
'	Print "Object Count: " +CountList(List)
End Function

Function RemoveAllByLink:Int()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	For o=EachIn List
		If o.num = 1 Then o.RemoveByLink()
	Next
	time=MilliSecs()-start
	Return time
End Function

Function RemoveAllByList:Int()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	For o=EachIn List
		If o.num = 1 Then o.RemoveByList()
	Next
	time=MilliSecs()-start
	Return time
End Function

H&K	(Posted 2006) [#5]

Hi,

I Changed the start of the first post to this

Global List2:TList = CreateList()
Type TObject
	Field Link:TLink
	Field Link2:TLink
	
	Function Create:TObject()
		Local o:TObject=New TObject
		
		o.Link = ListAddLast(List , o)
		o.Link2 = ListAddLast (List, o)
		
		Return o
	End Function

Basicly by making two links I am removeing only the link, and not GC the object. (You need to run it twice, once with each of the remove methods remed)

It gives

By Link 30, By List 242

Which is what I would expect.
So if the object isnt being freed, simply the link destroyed then it works as it says on the tin.

When running yours by List gives me a value ~30, which is what I would expect, as its simply removeing the fist link in the list, by link.

By Link On yours ,(Ie with Object removal) I get 170, which leads me to believe I have garbage Collection Time

skidracer

(Posted 2006) [#6]

Your test program is using ListRemove in it's optimal form - removing the first element in the list.

It will be siginificantly slower if you were to test by removing the last element, the following also shows up how slow List.Count() is:

SuperStrict

Type TObject
	Field Link:TLink
	
	Function Create:TObject()
		Local o:TObject=New TObject
		
		o.Link=ListAddLast(List,o)
		
		Return o
	End Function
	
	Method RemoveByLink()
		RemoveLink Link
	End Method
	
	Method RemoveByList()
		ListRemove List,Self
	End Method
End Type

Global List:TList=CreateList()

Global maxobjects:Int=16384'0

PopulateList()

RemoveAllByLink()

PopulateList()

RemoveAllByList()

Function PopulateList()
	Local start:Int,time:Int,i:Int

	start=MilliSecs()
	For i=0 To maxobjects
		TObject.Create()
	Next
	time=MilliSecs()-start
	Print "Add To List Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

Function RemoveAllByLink()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	While List.Count()
		o=TObject(List.Last())
		o.RemoveByLink()
	Wend
	time=MilliSecs()-start
	Print "Remove By Link Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

Function RemoveAllByList()
	Local start:Int,time:Int,i:Int,o:TObject

	start=MilliSecs()
	While List.Count()
		o=TObject(List.Last())
		o.RemoveByList()
	Wend
	time=MilliSecs()-start
	Print "Remove By List Time: " +time+ " ms"
	Print "Object Count: " +CountList(List)
End Function

Regular K

(Posted 2006) [#7]

Ah, I guess I wasn't looking at how the code was really running. According to dmazs results, RemoveLink is really more effective.

Well, let this be an example for new BlitzMax users who are interested in using lists :)

MGE	(Posted 2007) [#8]

This thread was very informative, thank you!

Grey Alien

(Posted 2007) [#9]

Also when running any tests it's best to run the app, let it stablise for a few seconds THEN run the test. Especially with graphics apps as you may get system-based delays introduced in the first few seconds.