More faster?

BlitzMax Forums/BlitzMax Programming/More faster?

orgos(Posted 2010) [#1]
Hi folks.

I have a question for the blitzmax professionals.

I want to get an element from a list, I have two ways

1- create a TMap and insert objects with respective name as param
2- have a tlist containing object with id field

What is more faster get the object from tmap or making an eachin cicle with tlist and compare the string param passed with the id field of the object?


Who was John Galt?(Posted 2010) [#2]
TMap


ziggy(Posted 2010) [#3]
If you need indexed acces and insertion of data, TMaps are your best option. If you fill in everything once, and then you just need indexed acces, then Arrays are your best option, but if you need realtime insertion and there's no need for indexed access, then TList are your best option:

I think this will clarify a bit the existing options:
 -------------------------------------------------------------
| Method  |   Insertion  |  Indexed Access | Iteration EachIn |
|=============================================================|
| Arrays  |   very slow  |    Instant      |     Instant      |
|-------------------------------------------------------------|
| TLists  |    Instant   |   very slow     |       Fast       |
|-------------------------------------------------------------|
| TMaps   |     Fast     |      Fast       |    a bit slow    |
 -------------------------------------------------------------

Usually, the diferences are visible when using big amounts of data.


hub(Posted 2010) [#4]
Is there some tutorials about tmap ?


orgos(Posted 2010) [#5]
Thanks for the full explanation ziggy.


Jesse(Posted 2010) [#6]
@ziggy
What makes you so sure that Tmap is that much faster than Tlist. From test I have done I can say that they are just as fast or that Tmap is even slower. They use the same priciple for search. Besides if you use a link for direct access then Tlist is really fast "almost" as fast as arrays. adding objects to Tmap will be slower than adding objects To Tlist specially for large quantities of items. The problem with Tmaps is that it don't allow for duplicate keys so it will compare the key at hand for the keys stored and then either replace or insert it while Tlist will just insert it unless you want it on a certain position of course but then again if you are using links to do that then Tlist will still be faster. removing items should be the same speed sense in both cases it needs to search through the list and compare before removing but with direct link access Tlist will still be faster.
When you get a chance compare both modules source code and you will see what I am talking about.


GW(Posted 2010) [#7]
"eachin" on a tlist is far from instant.


ziggy(Posted 2010) [#8]
@Jesse:
They use the same priciple for search

No, they don't. TMaps uses a sort of key/value pair search algorithm, *similar* to what you may find on a Hash table algorithm. There's nothing near similar to this on the TList implementation. TList can only be searched sequentially. Obviously, once you have performed a search and already have a TLink, this helps avoiding the need to search again something, but this does not mean that searching is faster.
When you get a chance compare both modules source code and you will see what I am talking about.
I've already done it, and wrote some alternatives to both of them. Even have done a key/value pair collection, wich is something missing in BlitzMax (but very similar to TMaps).
"eachin" on a tlist is far from instant.
It's comparable to what you get on an array, as it is not using indexing, but the _pred and _succ pointers, so it is very near to the speed you get with arrays, in this respect. Obviously not as fast as arrays, maybe not instant, but it's usually fafst enough.


smilertoo(Posted 2010) [#9]
How does the array compare if you predefine the size then just insert data into it?


Jesse(Posted 2010) [#10]
you are going to tell me that using this:
	Method ValueForKey:Object( key:Object )
		Local node:TNode=_FindNode( key )
		If node<>nil Return node._value
	End Method

and this:
	Method _FindNode:TNode( key:Object )
		Local node:TNode=_root
		While node<>nil
			Local cmp=key.Compare( node._key )
			If cmp>0
				node=node._right
			Else If cmp<0
				node=node._left
			Else
				Return node
			EndIf
		Wend
		Return node
	End Method

is just as fast as using Tlist with Tlink. I doubt it very much.

@GW
do you know exactly what does eachin does? I do.

@smilertoo
there is nothing faster, none that i know anyway.


ziggy(Posted 2010) [#11]
It's very diferent Jesse. Here you have a demonstration:
SuperStrict

'Create data in a string array:
Const DataVolume:Int = 1000000
Local MyArray:String[] = New String[DataVolume]
Local List:TList = New TList
Local Map:Tmap = New Tmap

'------------------------------------------------------
Print "Creating the array..."
For Local i:Int = 0 Until DataVolume
	MyArray[i] = Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) ;
Next

'Create a TList with the contents of the string array:

'------------------------------------------------------
Print "Filling the List..."
For Local i:Int = 0 Until DataVolume
	List.AddLast(MyArray[i])
Next

'------------------------------------------------------
Print "Filling the TMap. .."
For Local i:Int = 0 Until DataVolume
	Map.Insert(MyArray[i], MyArray[i])
Next

'------------------------------------------------------
Print "Now searching 1000 items on the Tlist"
Local M:Int = MilliSecs()
For Local i:Int = 1 To 1000
	Local Result:String = List.FindLink(MyArray[Rand(0, DataVolume - 1)]).Value().ToString()
Next
Print "Searching the TList took: " + (MilliSecs() - M)

'------------------------------------------------------
Print "Now searching 1000 items on the Map"
M:Int = MilliSecs()
For Local i:Int = 1 To 1000
	Local Result:String = Map.ValueForKey(MyArray[Rand(0, DataVolume - 1)]).ToString()
Next
Print "Searching the Map took: " + (MilliSecs() - M)

'------------------------------------------------------
Print "Performing Eachin on the Array"
M:Int = MilliSecs()
For Local i:Int = 0 To 10
	For Local S:String = EachIn MyArray
		Local Result:String = S
	Next
Next
Print "Eachin in the array took " + (MilliSecs() - M)

'------------------------------------------------------
Print "Performing Eachin on the TList"
M:Int = MilliSecs()
For Local i:Int = 0 To 10
	For Local S:String = EachIn List
		Local Result:String = S
	Next
Next
Print "Eachin in the List took " + (MilliSecs() - M)

'------------------------------------------------------
Print "Performing Eachin on the Map"
M:Int = MilliSecs()
For Local i:Int = 0 To 10
	For Local S:String = EachIn Map
		Local Result:String = S
	Next
Next
Print "Eachin in the Map took " + (MilliSecs() - M)


That's the output generated on my machine Debug OFF:
Creating the array...
Filling the List...
Filling the TMap. ..
Now searching 1000 items on the Tlist
Searching the TList took: 16310
Now searching 1000 items on the Map
Searching the Map took: 3
Performing Eachin on the Array
Eachin in the array took 12
Performing Eachin on the TList
Eachin in the List took 634
Performing Eachin on the Map
Eachin in the Map took 1795

I supose you agree than 16,3 seconds is a lot more than 3 millisecs...
is just as fast as using Tlist with Tlink. I doubt it very much.

No, TLink is the fastest way, but you need to search for the Tlink instance first, or iterate until you find it. Tlink lets you avoid the search sometimes but it does not make the search faster. That's my point.


Jesse(Posted 2010) [#12]
there is really no comparison ziggy.
tlist with tlink will automatically remove items from the list with out a search.
SuperStrict

'Create data in a string array:
Const DataVolume:Int = 1000000
Type myTpe
	Field str:String
	Field link:TLink
End Type
Local MyArray:myTpe[] = New mytpe[DataVolume]

Print "Creating the array..."
For Local i:Int = 0 Until DataVolume
	myArray[i] = New myTpe
	MyArray[i].str = Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + ..
	Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164)) + Chr(Rand(32, 164))
Next

'Create a TList with the contents of the string array:

Print "Filling the List..."
Local List:TList = New TList
For Local i:Int = 0 Until DataVolume
	myArray[i].link = List.AddLast(MyArray[i])
Next

Print mytpe(myArray[3].link.value()).str 'this prints the string
myarray[3].link.remove() 'this remove the item from the list instantly with out a search.

you can also add them just as fast. can Tmaps do that? don't think so.
nlink:tlink = list.insertAfterLink(myArray[3],myArray[4].link)

and access them just as fast
print mytpe(nlink.value()).str



dynaman(Posted 2010) [#13]
Jesse - if the user is looking for a specific item in the list, which is faster finding that item? The tlist will have to iterate through the entire list sequentially while the tmap will do a boolean search. Your example above does not work - you accessed the item since your code knew ahead of time exactly what element was needed.


Jesse(Posted 2010) [#14]
lets say your game has a for loop that iterates through all of the badies to collide with a bullet:
for alien:Talien = eachin list
   if collision(alien,bullet)
      alien.link.remove() 'this is way faster than listRemove(list,alien)
      EXIT
   endif
next


in order for you to know which object needs to be romoved you must have the object at hand so if you are removing objects this would be the best solution.
when you add the object to the list you insert the link to the object then and there and there is no searching.
what do you think Tmap will do?
If anyone can prove me wrong, you will be my idol!


dynaman(Posted 2010) [#15]
Orgos was asking about removing a specific item from the list, in which case using a tmap is faster since it can use a boolean search to find the item.

If needing to iterate through in order to see if a bullet collided with ANY of the items is a different problem for which the tlist may indeed be faster (for that purpose I would use the tlist as well).


Jesse(Posted 2010) [#16]
all of the objects in the list have to go in at a certain point why not take care of it as such. there is really no reason to search the list. can you think of one example?
every game I have ever done, I have never had a reason to search the list for objects.
[edit]
note that Orgos wrote:

2- have a tlist containing object with id field


why use an id to search when you can use a link:Tlink and have direct access?


Jesse(Posted 2010) [#17]
@ziggi
here is a better example of your code:
SuperStrict
Global DataVolume:Int = 1000000
Global list:TList = New TList
Global map:Tmap = New Tmap
Global array:Talien[DataVolume]

Type Talien
	Field x:Int
	Field y:Int
	Field link:TLink
End Type

Print "Filling the Array"
Local M:Long = MilliSecs()
For Local i:Int =0 Until DataVolume
	array[i] = New Talien
	array[i].x = i+i
	array[i].y = i*2
Next
Print "it took "+(MilliSecs()-m)+" to fill it"
Print
Print"--------------------------------------"
Print "Filling the TList"
M = MilliSecs()
For Local i:Int = 0 Until DataVolume
	array[i].link = list.addlast(array[i])
Next
Print "it took "+(MilliSecs()-M)+" to fill it"
Print
Print "------------------------------------"
Print "Filling the TMap. .."
M = MilliSecs()
For Local i:Int = 0 Until DataVolume
	Map.Insert(Array[i], Array[i])
Next
Print "it took "+(MilliSecs()-m)+" to fill it"
Print
Print "--------------------------------------"
Print "Now searching 1000000 items on the Tlist"
M = MilliSecs()
For Local i:Int = 1 To DataVolume
	Local alien:Talien = Talien(array[Rand(0, DataVolume - 1)].link.value()) 'no need to search
Next
Print "Searching the TList took: " + (MilliSecs() - M)
Print
Print "-------------------------------------"
Print "Now searching 1000000 items on the Map"
M = MilliSecs()
For Local i:Int = 1 To DataVolume
	Local Result:Talien = Talien(Map.ValueForKey(Array[Rand(0, DataVolume - 1)]))
Next
Print "Searching the Map took: " + (MilliSecs() - M)
Print
Print "------------------------------------"
Print "Performing Eachin on the Array"
M = MilliSecs()
For Local i:Int = 0 To 1000
	For Local S:Talien = EachIn Array
		Local alien:Talien = S
	Next
Next
Print "Eachin in the array took " + (MilliSecs() - M)
Print 
Print "-------------------------------------"
Print "Performing Eachin on the TList"
M = MilliSecs()
For Local i:Int = 0 To 1000
	For Local S:Talien = EachIn List
		Local Result:Talien = S
	Next
Next
Print "Eachin in the List took " + (MilliSecs() - M)
Print
Print "--------------------------------------"
Print "Performing Eachin on the Map"
M = MilliSecs()
For Local i:Int = 0 To 1000
	For Local S:Talien = EachIn Map
		Local Result:Talien = S
	Next
Next
Print "Eachin in the Map took " + (MilliSecs() - M)

see if you still think Tmap is better.


plash(Posted 2010) [#18]
here is a better example of your code
That's not even close to the same. You're dealing with indexes here, which are obviously going to be faster with an array. Also, you're not actually searching the list, you're grabbing aliens from an array using an index.

Maps really useful only where items are identified and retrieved by some other object or string. In your example a Map would be really unnecessary.


Jesse(Posted 2010) [#19]
exactly. the whole argument was about Tlist, or tmap as related to orgos post. I guarantee you that his code would be faster with Tlist using Tlink than using Tmap.
and no, I am not grabbing aliens from the list I am accessing the link value inside the list


ziggy(Posted 2010) [#20]
@Jesse: This is a very good example that shows how to avoid a search on a list, but I was comparing search operations, so if you take out one of the searches, there's no comparison. Also, storing a Tlink into a field of a class that is already in the list is a way to add cyclic references, wich helps do things faster, but can be dangerous. I see what you're talkign about, I agree that using the tlink object usually avoids search operations on tlists, and this makes things a lot faster, nobody is telling this is not true, you're right at this respect but when you compare real search operations, TMaps are several orders of magnitude faster than a linked list. It's up to the coder to decide wich is best at every given situation.
see if you still think Tmap is better.
I don't think it's better, I think it is more appropiate if you have to do search operations using given keys, and if you need a key/value pair like collection.
Thanks for your example, anyway ilustrates the usage of Tlinks in a way I hope will help other BlitzMax coders (as long as you avoid the cyclic reference in a real scenario).


plash(Posted 2010) [#21]
the whole argument was about Tlist, or tmap as related to orgos post.
No it was not. ziggy was responding to your post that stated TLists search in the same way that TMaps do (in fact, TLists don't search at all, they don't serve that purpose).


Jesse(Posted 2010) [#22]
yes it's really don't see any cyclic reference as there is no back and for linking. just one way reference. when the variable that access the type and removes it from the list and the local variable goes out of scope the object will be collected by the garbage collector. the problem would be if you put it in two list at the same time. but that would be a problem with any code.
I have been programming for ages like that and never ran in to that problem before.

@Plash
there is just no winning you wrong or wright. ;)
well you keep on using Tmap and I'll keep on using Tlist and well both be happy.


Czar Flavius(Posted 2010) [#23]
in order for you to know which object needs to be romoved you must have the object at hand so if you are removing objects this would be the best solution.
when you add the object to the list you insert the link to the object then and there and there is no searching.
what do you think Tmap will do?
If anyone can prove me wrong, you will be my idol!


I am making a network strategy game, where orders for units needs to be sent across the network using streams. So each controllable object needs some kind of id which I have stored in a map. If you send a movement order to unit 57, then this id needs to be sent over the stream and then unit 57 found on the other computer. As you cannot transfer TLinks over a network, I use TMaps for this purpose!

I could also use large arrays whose size is carefully managed yada yada but game commands occur infrequently (compared to updating the game every frame) so TMap is good enough for me.

I await my shrine!


Jesse(Posted 2010) [#24]
I think that is debatable. or at least I need to research that before I can make your "shrine".;)


ziggy(Posted 2010) [#25]
Cyclick reference: The TLink object has a Value field than points to a class instance with a field called Link that is the link itself:
Cycle: Object (link field) --> Tlink (value field) --> Object


Jesse(Posted 2010) [#26]
when you use link.remove() the method takes care of references. as I said, I never had problems with it. I have it working on this game:
http://www.filefront.com/15098021/millenia.zip/
and is really fast but that is not the only thing is making it really fast. I have other optimizations at play.
as an alternative to doing in it in c which will be faster, challenging myself to make a shmup has really made me look for better ways to do stuff. I have been trying to make bullet hell type which would really make me look for ways to optimize my code even further.

[edit]
you know, just to agree with you ziggy and let you know that you are correct, this should work perfect:
link.remove()
link = null

always have them together.


orgos(Posted 2010) [#27]
Hi, thanks for all comments.

This is the real problem.

I'm working on a game framework and I have a object called xScene, this object act like a parent entity, he must have a list of child objects, so when the draw method of xScene is called it must call all the draw method of hes child's, so i need to make eachin operation to draw all child objects.

Based on all the comments I guess that Tmap is more faster for it?

There is another way to make it more efficiently?

Note: The xScene behavior affect the behavior of hes child.


Jesse(Posted 2010) [#28]
?!


GW(Posted 2010) [#29]
If you care about speed at all, use arrays. Otherwise maps and lists are a little easier.


Czar Flavius(Posted 2010) [#30]
If you need to draw every child object at once, then a TList would be faster.

As for the TLink cyclic issue, is it a problem or not??? As I use this method in my game.


Jesse(Posted 2010) [#31]
it is! just make sure you null the link after using link.remove(). I did have the link = null in my game. I just forgot all about it(I don't know how). I finally remembered that from a previous post a while back. went back and looked at my code and there it was. it also didn't show up sense I am recycling objects.

I have a method something like this:
method delete()
.
.
.
     link.remove()
     link = null
end method



ziggy(Posted 2010) [#32]
In my honest opinion, and please don't take this wrong becouse this is absolutelly not personal, whenever a cyclic reference exists, you can be sure you have a design flaw. It can work and be functional, but I would suggest to look for safer alternatives (just my opinion). The benefits of using a managed language is that you don't have to free things and you easilly avoid memory leaks. But a design with cross-referencing breaks this principle and adds no benefits.

That said, Orgos, if the number of childs is fixed, that is, if you don't add or remove childs to the parent entity, an Array is the faster option. If the number of childs is not fixed and childs are dynamically added and removed from the parent entity, then a TList is your best option.


Jesse(Posted 2010) [#33]
I dont have a reason to get offended. I might agree with you mostly but the fact is that even though blitzMax is good at what it does it's far from perfect. In my opinion it's missing a lot of functionality and if the options are there to do something more efficiently by circumventing some rules I will do it. After all, in this case, he lives the option of grabbing the link while adding the object to a list. what do you do with it?
it's there, use it. thats my opinion.


Czar Flavius(Posted 2010) [#34]
Why does it cause cyclic reference? Because the TLink refers back to the object? When you call the remove method it seems to nullify the value of the link, which would break the cycle.

Local list:TList = New TList

Type t
	Field me:TLink
	Method test()
		Print "hi"
	End Method
End Type

Local a:t = New t
a.me = list.addlast(a)

t(a.me.value()).test() 'prints hi
a.me.remove()
t(a.me.value()).test() 'null object error



ziggy(Posted 2010) [#35]
Yes, the cycle is fixed when the remove method is called. That does not mean that the cycle does not exists, just that there's a way to fix it (and if you forget to use it... Leak!) That why I said it was dangerous, as it can be a source of problems, it's a bit like it's unmanaged, but each to their own!


Czar Flavius(Posted 2010) [#36]
One more thing don't use Delete as a method name as it is reserved.


Arowx(Posted 2010) [#37]
Something else that may be worth considering, is the size overhead of the datastores.

For example I recently used a TList to store historic data and lots of it, now the problem here is every list element is stored as a link, taking up more memory.

In addition clearing a very long list (100k items) is very slow.

I ended up using an array, almost no overhead, fast as long as you don't have to re-dimension and quick to delete!

So if you are just storing log data and lots of it that you clear regularly you are probably better off using a simple array!

TIP, if your going to reuse it don't keep deleting and creating new data objects just zero them and reuse, it's faster still!


Czar Flavius(Posted 2010) [#38]
How does the array compare if you predefine the size then just insert data into it?
Fast for everything.