The speed of TLists compared to Arrays?

For an implentation I had in mind I need VERY many lists. I was thinking about using normal TLists, but I'm unsure how slow they are compared to arrays or perhaps banks. It still needs to be dynamic so the arrays would need to change size from time to time.

How big is the difference? Will it ever be noticable? Can I go with Lists without any worries? Is there anything else (limitation perhaps?) I should think about before deciding?

Arrays are faster. you should create a sample app to do a comparison. maybe do a hybrid with Lists of arrays

Yet, does it matter?

Don't really know how to actually do a fair test.. Last time I made a benchmark it wasn't really a good measure of the speed at all.

I think I'll try with TLists and it shoudn't be to hard to convert to arrays if ever needed. What about banks?

Might be missing something but you were both involved with this...
LL vs Array
Maybe use Lists while you're adding/removing and convert to array when you won't need to resize?

http://www.blitzbasic.com/Community/posts.php?topic=51138

Try this :)

The Tlist are very very slow ..

If the arrays need the size to be changed, then you will most likely suffer some pretty big speed penalties. Adding a link to a list is far faster, and if you code correctly then you'll have no problems with the lists.

[quote]

Might be missing something but you were both involved with this...

[/quote)

hmm. I was involved in that thread. Wish I could remember :)

Tonyg, well true. But in this case I need to use EXTREMLY many lists. ( I don't want to give anything away yet ). I'm just hoping that the project woun't end in a "Don't use *this*, it slows your game down!".

Filax, well from Mark's comment the speed of Arrays and TLists should be close. And I do need to add/remove stuff so TLists might actually be faster..

I mean the ~4000 lists will probably never have more than 1000 objects each in them, which I hope will be np. Still I'm afraid it won't work when it comes to these amounts.

I'll start a new thread - Hashtables..

The choice of datastructure typically depends on your data *AND* your access patterns.

There are a lot of things to consider
- each node of a list is an object, it needs some overhead (memory management) and at least 2 members for a double linked list. So each node is at least 8+2*4 bytes = 16 bytes - if you really have 4000*1000 objects so about 64mb - thats quite a lot (it's all overhead, not a single byte used for your own needs)
- an array only needs one block and 4 byte per object reference
- sequential access is not that different in terms of speed but if your lists change often you'll find your nodes quite distributed in memory so lots of iterations will end quite slower than using an array because of cash misses.
- random access on arrays is o(1) and on lists o(n) so using lists with up to 1000 elements may really slow down you quite a lot (if you have to do random access)

So in general - you just have to give us more information about your data/access patterns for a good recommendation.

16 bytes for each object in a list, that's much more overhead that I expected!

And 4000 lists with 1000 objects is clearly an overstatement from my side. The more I think about it the more I'm thinking that the amount will never be larger than~100. I mean how often do you see 1000 missiles on screen at one time? Anyhow it could perhaps happen in a worst case scenario. And, as you said, that's "just" the overhead!

This is hard to say as it depends.. Perhaps I could say that I would like to check for a specific type in a type's object_list. The only thing I need is a YES if it exsists or a NO if it don't. The problem is that this need to happen almost everytime I call a method. So the time will increase drastic with every new object added to this object_list. Also the adding of objects to this list will mostly happen before the main-loop, so arrays might be a real time saver. What about Hashtables?

I first discovered lists using Blitz 3D. They were cool and I really liked working with them. Now that I've moved over to Max I'm back to using arrays exclusively. It just seems simpler and cleaner to me to be working with array indexes.

It's also making networking and save load a little simpler. When objects are linked together I keep track of their array index rather the object directly. (a pointer to the object).

I could make the array an object - Like in the example below. Jay, do note that everytime (see code below) that I remove something from the array I need to move all the slots below. The same if I add anyting NOT to the last of the array. Still this seems to give a smaller overhead, I can't see why I never would benefit of using TLists? Unless they are faster? To add a insert command, next and previous to this arrayList is almost trival..

'Strict

Type LArray
	
	Field ID
	Field Array:Object[]

	Method AddLast( Obj:Object )
		IncreaseSize()
		Array[ Array.length-1 ] = Obj'Add Last
	EndMethod

	Method AddFirst( Obj:Object )
		IncreaseSize()
		'Move all slots
		For i = (Array.length-1) Until 0 Step -1
			Array[i] = Array[i-1]
		Next  	
		Array[ 0 ] = Obj'Add First
	EndMethod

	Method IncreaseSize()
		Array = Array[..Array.length + 1]	
	EndMethod

	Method DecreaseSize()'Removes Last Index of the Array
		Array = Array[..Array.Length - 1]	
	EndMethod

	Method Find( Obj:Object )
		Local n
		For Local O:Object = EachIn Array
			If O = Obj Return n' The index
			n:+1
		Next	
		Return -1'Not found
	EndMethod

	Method Remove( Obj:Object )
		Local n = Find( Obj )
		If n < 0 Then Return False
		For i = n Until Array.length -1
			Array[i] = Array[i+1]			
		Next  
		DecreaseSize()
		Return True
	EndMethod
	
	Method Debug()
		Local n = 0
		For Local S$ = EachIn Array
			DebugLog "Array[ "+n+" ] = "+S
			n:+1
		Next 
	EndMethod
	
End Type

Global Array:LArray = New LArray
Array.AddLast ( "Car"   )
Array.AddFirst( "Ship"  )
Array.AddFirst( "Train" )
Array.AddLast ( "Bike"  )
Array.AddLast ( "UFO"   )
Print "-------------------"
Array.Debug
Array.Remove( "UFO"   )
Array.Remove( "Train" )
Array.Remove( "Bike"  )
Print "-------------------"
Array.Debug
Print "-------------------"
If Array.Find( "Car"   ) 	Then Print "Found Car!"
If Array.Find( "Train" ) 	Then Print "Found Train!"
If Array.Find( "Ship"  ) 	Then Print "Found Ship!"

The tricky part is when you have a bunch of objects referencing other objects in an array by their index. You need update each reference when you compress the array. I haven't found a nice way to do this.

I think I'd like experiment with leaving NULL spots in the array and filling them in as new entries are added. This way objects never move around in the array and references never need to be added.

hmm.. this sounds kind of messy by I guess this is how your ram works so it cant be all that bad. Can it? :)

Hmmm, the extra overhead is that you have to iterate through the array every time you add an object looking for empty slots. (and the extra memory for having and array with lots of holes in it)

I would say making your own linked list system with pre-allocated memory would be fastest.