NewsForumsCodeLogsGallerySpecsSearch

The TList vs Slicin' Arrays

BlitzMax Forums/BlitzMax Programming/The TList vs Slicin' Arrays

Leiden(Posted 2006) [#1]
Did a few little tests to find out which is faster, here are my results:

Creating a new TList: 0ms
Creating a new Array: 0ms
Fill the TList with 100,000 Objects: 14ms
Fill the Array with 100,000 Objects: 40393ms
Read the values back from the TList: 3ms
Read the values back from the Array: 0ms

Most of you probably already know this, but it seems creating/filling TLists are faster than arrays, but reading values back from Arrays are way faster. Excellent!

' TList vs Array

Global HelloDump:Int

Type Test
	Field Hello:Int = 100
End Type

Global m = MilliSecs()

Global Array:Test[]
Global List:TList = New TList

Global T:Test = New Test

Print MilliSecs() - m

For i = 0 To 100000
	List.AddLast(T)
Next

Global z = (MilliSecs() - m)
Print z

For h = 0 To 100000
	Array = Array[..Len(Array)+1]
	Array[h] = T
Next

Global q = (MilliSecs() - z - m)
Print q

For a:Test = EachIn List
	HelloDump = a.Hello
Next

Global r = (MilliSecs() - z - m - q)
Print r

For y = 0 To 10000
	HelloDump = Array[y].Hello
Next

Global b = (MilliSecs() - z - m - q - r)
Print b


Run it!


Will(Posted 2006) [#2]
I got:

0
30
23890
9
0

That was in debug mode. Leaving debug mode gave a significant boost to filling the TList, and a significant boost to reading back from it:

0
10
24080
2
0


xlsior(Posted 2006) [#3]
Hm... My results appear significantly worse than the ones posted above. AMD Athlon 2800+, 1 GB.

In release mode:

0
22
141968
9
0


H&K(Posted 2006) [#4]
For h = 0 To 100000
	Array = Array[..Len(Array)+1]
	Array[h] = T
Next

Is not how you would normaly fill an array. Valid results, but you would never do this

In a Tlist you would add the elements one at a time. But in an array you just simply would never ever do that. You would create the array in one go.


Grey Alien(Posted 2006) [#5]
yeah or increase in chunk sizes of say 1000.


FlameDuck(Posted 2006) [#6]
You would create the array in one go.
Except the point was to show which was fastest - slicing arrays or insreting into a list. Since the first is in linear time complexity, and the second is in constant time complexity the results aren't really surprising.

yeah or increase in chunk sizes of say 1000.
Or more useful, by twice the amount you already have.


H&K(Posted 2006) [#7]
Except the point was to show which was fastest -slicing arrays or insreting into a list

No thats what they do show, what the intention was, was to show how fast it was to Fill the TList and
Fill the Array.
Just because they have acidently shown something else doesn't mean they are right. I have already said the results are valid, just not for what it was stated as proving


Oddball(Posted 2006) [#8]
The answer is not to use array slices for creating arrays item by item. Here's an alternative to the above test with very different results.


My results:
0
19
32
9
0


Leiden(Posted 2006) [#9]
With the above I got:

0
13
19
3
1

But I changed the 'For y = 0 To 10000' to 'For y = 0 To 100000'. Results are much much faster, So you basically use a list to store the objects then dumped the list to an array. Why didnt I think of that?


FlameDuck(Posted 2006) [#10]
the intention was, was to show how fast it was to Fill the TList and Fill the Array.
You forgot to add 'in an instance where you do not know up-front how many entries you need'.


Grey Alien(Posted 2006) [#11]
So you basically use a list to store the objects then dumped the list to an array. Why didnt I think of that?
Yeah sounds good.


Dreamora(Posted 2006) [#12]
FD: Even then there wouldn't be a reason to slice 1 by 1 ... still doubling size (as you suggested above) and "cut off" at the end of the filling operation ...


tonyg(Posted 2006) [#13]
Something like this...
If h >= Len(array) Array = Array[..Len(Array)+500]



Dreamora(Posted 2006) [#14]
for example, or just

If h >= Len(array) Array = Array[..array.length * 2]


H&K(Posted 2006) [#15]
@Fd
You forgot to add 'in an instance where you do not know up-front how many entries you need'.

Fill the TList with 100,000 Objects: 14ms
Fill the Array with 100,000 Objects

It was mentioned that you knew how many.

Look flame Im not saying you are wrong, Im just saying that what Laiden was claiming as testing wasnt.


Leiden(Posted 2006) [#16]
What are you talking about? The 100,000 was just a number out of the blue to represent the average amount of faces in a scene, The idea behind the test was too see if adding additional values to each of the candidates was faster/slower. How about I tested it with just one loop, now thats really goin' to give me more realistic results isnt it?

Yesh you remind me of Draconus.


H&K(Posted 2006) [#17]
What I was talking about, (which was really quite obvious if you read all the thread) was the differecne between what you said you were doing, and what you actualy did.

Each would have been valid. What you said you were doing was , filling an array with 1000000 objects. Were as what you did was Slice 1000000 new objects into an array.

As Ive said several times, your results were valid for Sliccing 1000000 new objects into an array, but are not valid for what you said they were, that is Filling an array with 1000000 new elements

And yes it is padantic, but in this case the use of the two terms were important.

PS. I also was impressed with the idea of making the Tlist and then transfering it to an array


Takuan(Posted 2006) [#18]
shame..makes your face red:D

That post has been edited by me.


Leiden(Posted 2006) [#19]
Each would have been valid. What you said you were doing was , filling an array with 1000000 objects. Were as what you did was Slice 1000000 new objects into an array.


Well it depends on how literally you took what I said. Also it wasnt 1,000,000 objects, get your facts straight.