link = link.nextlink() VS eachin

BlitzMax Forums/BlitzMax Programming/link = link.nextlink() VS eachin

skn3	(Posted 2012) [#1]

Fairly recently (compared to my entire life as a blitz programmer) I started refusing to use object iterators and instead do object loops like this:

link = list.firstlink()
while link
	item = Item(link.value())
	link = link.nextlink()
wend

I just wanted to see if this is a favoured practice, or does it not matter?

Muttley

(Posted 2012) [#2]

What's your logic behind that decision?

TBH, it adds unnecessary complication and reduces flexibility in the code for absolutely no benefit whatsoever.

For example, if you were ever to decide to replace your list with an array (or a custom collection) you'd have to change every single bit of code that used the list in this way!

skn3	(Posted 2012) [#3]

Well I picked up from reading these forums that when you do an eachin it is generating the enum objects (whcih are a throw away), then there is the general processing of letting the enumerator do its work (function calls, and object conversion).

Id imagine its a small amount of overhead, but if your doing a lot of stuff it can all add up? Id like to know if this is good or wasted practice in larger scale applications? As an example I have big chunky functions that deal with data being returned from dialogues. Lots of list iterating and reusing of link objects. If this were to be done via eachin's I would essentially be throwing away the creation of enumerator objects all over the place!

At least that's the way I understand it?

Its just as flexible to do it this way as long as you don't ever decide to change the data format. Yeah in that case it would be hell to go back and change the code. I think if your designing your data structure with that in mind then its probably more sensible to think a bit harder before you design the implementation of whatever your doing.

I guess another reason the link method is good, and used to really bother me, is that if you want to iterate over a list backwards you had to do the link method anyways. I guess I prefer the neatness of only iterating through a list in one particular way...

But it sounds like I'm promoting the idea.. but Id really like to know if I'm just being paranoid about optimisation ?

Last edited 2012

Muttley

(Posted 2012) [#4]

Donald Knuth - "Premature optimization is the root of all evil."

Oddball

(Posted 2012) [#5]

Unless you are pushing the boundaries of what is possible then most of the time optimisation is a waste of valuable dev time. Make your game, then if it chugs or eats up to many resources you can optimise. Otherwise just ship the damn thing.

Zeke	(Posted 2012) [#6]

just use field _next:item

Type item
	Field _next:item
End Type

Global items:item 'items list

do not use TList if you need SPEED:

example code:

SuperStrict

Type item
	Global items:item=New item 'items list
	Global items_tlist:TList=New TList 'just to testing TList speed
	Field _next:item 'private
	'put your fields here
	Field id:Int
	
	Function get_next_id:Int()
		Global next_id:Int
		next_id:+1
		Return next_id
	End Function
	
	Function new_item:item()
		Local i:item=New item
		i.id=get_next_id()
		i._next=items._next
		items._next=i
		items_tlist.addlast(i)
		Return i
	End Function
	
	Function dump() 'dump using _next:item
		Local i:item=items._next
		Local t:Int
		While i
			Print "item id="+i.id
			i=i._next
			t=t+1
			If t=15 Then Exit
		Wend
	End Function
	
	Function calc:Int() 'speedtest
		Local t:Int=MilliSecs()
		Local i:item=items._next
		While i
			Local i2:item=items._next
			While i2
				i2.id=i2.id
				i2=i2._next
			Wend
			i=i._next
		Wend
		Return (MilliSecs()-t)
	End Function
	
	Function dump_eachin() 'dump using TList and Eachin
		Local t:Int
		For Local i:item=EachIn items_tlist
			Print "item id="+i.id
			t:+1
			If t=15 Then Exit
		Next
	End Function
	
	Function calc_eachin:Int() 'eachin speedtest
		Local t:Int=MilliSecs()
		For Local i:item=EachIn items_tlist
			For Local i2:item=EachIn items_tlist
				i2.id=i2.id
			Next
		Next
		Return (MilliSecs()-t)
	End Function
	
	Function calc_tlink:Int() 'TLink speed test
		Local t:Int=MilliSecs()
		Local i:TLink=items_tlist.firstlink()
		While i
			Local it:item=item(i.value())
			Local i2:TLink=items_tlist.firstlink()
			While i2
				Local it2:item=item(i2.value())
				it2.id=it2.id
				i2=i2.nextlink()
			Wend
			i=i.nextlink()
		Wend
		Return (MilliSecs()-t)
	End Function
End Type

For Local i:Int=0 To 10000
	item.new_item()
Next

item.dump()
Print "---"
item.dump_eachin()
Print "---"
Print "_next:item speed= "+item.calc()
Print "eachin speed= "+item.calc_eachin()
Print "TLink speed= "+item.calc_tlink()

[edit] Added Tlink speed test

Last edited 2012

skn3	(Posted 2012) [#7]

Hey Zeke, wow big difference! thanks that will be very helpful!

results:

_next:item speed= 213
eachin speed= 805
TLink speed= 550

So tlink is faster (in debug mode off) but wow massive different with just storing _next! I think i prefer the flexibility to be able to pass around my data as a list or manually iterate so i'll use tlinks for most cases but then the _next pointers for very intense operations..

cool thanks, very helpful!

Id agree most of the time... although I have always tried to adjust my coding style as I progress in order to optimise as I go. Doing something like tlink loops now 2 months in practice, is no harder/slower then using eachin. From zekes test results above I have reduced loop times by nearly a 3rd. Not a bad "free" optimisation really?

Last edited 2012

Muttley

(Posted 2012) [#8]

@Zeke: All that test proves is that you didn't choose a decent data structure for storing the objects (due to the way you're using them):

SuperStrict

Type item
	Global items:item=New item 'items list
	Global items_tlist:TList = New TList 'just to testing TList speed
	Global items_array:item[] = new item[10001]
	
	Field _next:item 'private
	'put your fields here
	Field id:Int
	
	Function get_next_id:Int()
		Global next_id:Int = -1
		next_id:+1
		Return next_id
	End Function
	
	Function new_item:item()
		Local i:item=New item
		i.id=get_next_id()
		i._next=items._next
		items._next=i
		items_tlist.addlast(i)
		items_array[i.id] = i
		Return i
	End Function
	
	Function dump() 'dump using _next:item
		Local i:item=items._next
		Local t:Int
		While i
			Print "item id="+i.id
			i=i._next
			t=t+1
			If t=15 Then Exit
		Wend
	End Function
	
	Function calc:Int() 'speedtest
		Local t:Int=MilliSecs()
		Local i:item=items._next
		While i
			Local i2:item=items._next
			While i2
				i2.id=i2.id
				i2=i2._next
			Wend
			i=i._next
		Wend
		Return (MilliSecs()-t)
	End Function
	
	Function dump_eachin() 'dump using TList and Eachin
		Local t:Int
		For Local i:item=EachIn items_tlist
			Print "item id="+i.id
			t:+1
			If t=15 Then Exit
		Next
	End Function
	
	Function calc_eachin:Int() 'eachin speedtest
		Local t:Int=MilliSecs()
		For Local i:item=EachIn items_tlist
			For Local i2:item=EachIn items_tlist
				i2.id=i2.id
			Next
		Next
		Return (MilliSecs()-t)
	End Function
	
	Function calc_array:Int() 'array speedtest
		Local t:Int = MilliSecs()
		For Local i:int = 0 to items_array.Length - 1
			For Local i2:int = 0 to items_array.Length - 1
				items_array[i2].id = items_array[i2].id
			Next
		Next
		Return (MilliSecs()-t)
	End Function
	
	Function calc_array_eachin:Int() 'array eachin speedtest
		Local t:Int = MilliSecs()
		For Local i:item = eachin items_array
			For Local i2:item = eachin items_array
				i2.id = i2.id
			Next
		Next
		Return (MilliSecs()-t)
	End Function
	
	Function calc_tlink:Int() 'TLink speed test
		Local t:Int=MilliSecs()
		Local i:TLink=items_tlist.firstlink()
		While i
			Local it:item=item(i.value())
			Local i2:TLink=items_tlist.firstlink()
			While i2
				Local it2:item=item(i2.value())
				it2.id=it2.id
				i2=i2.nextlink()
			Wend
			i=i.nextlink()
		Wend
		Return (MilliSecs()-t)
	End Function
End Type

For Local i:Int=0 To 10000
	item.new_item()
Next

item.dump()
Print "---"
item.dump_eachin()
Print "---"
Print "_next:item speed= "+item.calc()
Print "eachin speed= "+item.calc_eachin()
Print "TLink speed= "+item.calc_tlink()
Print "Array speed= " + item.calc_array()
Print "Array eachin speed= " + item.calc_array_eachin()

Results:

_next:item speed= 312
eachin speed= 1037
TLink speed= 762
Array speed= 65
Array eachin speed= 65

Last edited 2012

Last edited 2012