Hi guys,
I've read somewhere on this forum that an array ( i.e. Label[] ) is much faster than a List<>. I'm having small lag problem on my development so I'm trying to find where is the problem. One thing I know is that I'm using List<> instead of arrays.
So made this simple test to see if there is really a difference on the timing. To my surprise, the List<> is quicker than the array. I'm not sure if my test is wrong.
I would like to know your opinion.

Thanks,

You should be using a profiler. Guessing at the problem, especially at such a micro level like whether or not List<T> is faster than T[], is going to cause you to spin your tires on something that might not even be an issue.

Using my own performance test framework I get these results :

2.000.000 elements of type int

26860 ticks array with foreach 
26776 ticks array with for
139474 ticks list with foreach
53511 ticks list with for

on a Core 2 Duo T7250 2 Ghz.

Not that any of these will actually make a difference unless you have this high number of iterations. (do test not in the visual studio interface because when the apps are runned from there lots of optimizations are not performed, and anyway use a Stopwatch to keep track of the times)

There is a great set of articles on all types of data structures here http://creators.xna.com/en-US/article/datastructures

feal87:

Using my own performance test framework I get these results :

2.000.000 elements of type int

26860 ticks array with foreach 
26776 ticks array with for
139474 ticks list with foreach
53511 ticks list with for

on a Core 2 Duo T7250 2 Ghz.

Not that any of these will actually make a difference unless you have this high number of iterations. (do test not in the visual studio interface because when the apps are runned from there lots of optimizations are not performed, and anyway use a Stopwatch to keep track of the times)

What test are you running? Simply giving numbers is useless unless you show the code and explain what those numbers mean. Are you just iterating the list? Adding? Removing? Sorting? I'm all for benchmarking (I do it myself frequently and almost made one for this thread), but you need to present the code you ran otherwise the numbers don't mean much.

Nick,

Thank you for your valuable response.

About your points:

Nick Gravelyn:

feal87:

Using my own performance test framework I get these results :

2.000.000 elements of type int

26860 ticks array with foreach 
26776 ticks array with for
139474 ticks list with foreach
53511 ticks list with for

on a Core 2 Duo T7250 2 Ghz.

Not that any of these will actually make a difference unless you have this high number of iterations. (do test not in the visual studio interface because when the apps are runned from there lots of optimizations are not performed, and anyway use a Stopwatch to keep track of the times)

What test are you running? Simply giving numbers is useless unless you show the code and explain what those numbers mean. Are you just iterating the list? Adding? Removing? Sorting? I'm all for benchmarking (I do it myself frequently and almost made one for this thread), but you need to present the code you ran otherwise the numbers don't mean much.

Just iterating and adding the values (randomly generated in the initialization phase) into an integer. Here it is the content of the foreach for array. It is pretty much the same in the other case. I use a framework created by me that can can use multiple testing classes with multiple code to test and benchmark the speed of the execution.

Anyway it is pretty much obvious this result cause iterating with the foreach in the list cause an enumerator to be generated and used creating a big useless overhead. (arrays will be always faster)


Array is just a "Int32[] Array;" with 2.000.000 as length filled with random values.

jmartingarcia:

1) I thought the List<> it was that, really a list and not something encapsulating an array. Because in that case, deleting the first member of the list will be the same than deleting any other member, just the pointer of the previous member will point to the next member on the list. (Linked list. I know there another class called like that but a list is a list)

A list is not the same as a linked list. List<T> in .NET is basically like std::vector from C++: a basic wrapping over an array. The behavior you described is a trait of linked list, which is implemented in .NET as LinkedList<T>.

feal87:

Anyway it is pretty much obvious this result cause iterating with the foreach in the list cause an enumerator to be generated and used creating a big useless overhead. (arrays will be always faster)

That's not necessarily true. I'm also not entirely sure how you got faster times using a for loop instead of a foreach when all of my tests have show the latter to be faster. Then again, I was using a List<Vector3> so perhaps (and I don't know for sure) the size of T might be affecting performance somehow.

Either way, while a raw array might be more performant in simple iterating, there's a lot of functionality in List<T> that an array doesn't have that you'd have to implement yourself such as sorting, dynamic resizing, etc. And considering the perf differences are, in my experiences, neglible in either direction, I recommend people use whatever is easiest for them. If someone is using List<T>, they should just stick with it.

Based on this and the documentation pointed by Dean, seems that using a List<> or Array won't make a big impact in my case.

I run the profiler and for my surprise where the application is wasting a lot of time is calling Convert.ToInt32(float64) ... all my objects are in world coordinates and this world coordinates can have decimals, that's why I;m using floats. When I'm going to draw them I need to do the conversion for each sprite. 

Is there any cheaper way to do that ?

Are you using floats or doubles? "float64" sounds like a double since I believe a float is 32 bits. If you're using doubles and don't need that amount of accuracy, try switching to floats which will not only cut your memory footprint in half for each one, but should make the conversion a little faster.

Is that the top of your time eaters or is there something else higher? What percent of the execution time is that getting?

Interested from your results I've tried with the Vector4 class from SlimDX and some other kind of tests to be sure of my findings.
These are the codes used. The first is the common foreach over array, then there is an unoptimized for over array, then there is an optimized for over array and then all the lists one.

TestCodes.Add(new Action(delegate

{

float lol = 0;

foreach (var itm in Array)

{

lol += itm.X;

lol += itm.Y;

lol += itm.Z;

lol += itm.W;

}

lol -= 1;

}));

TestCodes.Add(new Action(delegate

{

float lol = 0;

for (int i = 0; i < 2000000; i++)

{

lol += Array[i].X;

lol += Array[i].Y;

lol += Array[i].Z;

lol += Array[i].W;

}

lol -= 1;

}));

TestCodes.Add(new Action(delegate

{

float lol = 0;

for (int i = 0; i < 2000000; i++)

{

Vector4 val = Array[i];

lol += val.X;

lol += val.Y;

lol += val.Z;

lol += val.W;

}

lol -= 1;

}));

TestCodes.Add(new Action(delegate

{

float lol = 0;

foreach (var itm in Lista)

{

lol += itm.X;

lol += itm.Y;

lol += itm.Z;

lol += itm.W;

}

lol -= 1;

}));

TestCodes.Add(new Action(delegate

{

float lol = 0;

for (int i = 0; i < 2000000; i++)

{

lol += Lista[i].X;

lol += Lista[i].Y;

lol += Lista[i].Z;

lol += Lista[i].W;

}

lol -= 1;

}));

TestCodes.Add(new Action(delegate

{

float lol = 0;

for (int i = 0; i < 2000000; i++)

{

Vector4 Elem = Lista[i];

lol += Elem.X;

lol += Elem.Y;

lol += Elem.Z;

lol += Elem.W;

}

lol -= 1;

}));

31304 ticks foreach | array 
118180 ticks for | array unoptimized
32206 ticks for | array optimized
250323 ticks foreach | list
219090 ticks for | list unoptimized
66991 ticks for | list optimized

Over 2.000.000 array/list members. This confirms that over iteration and reading data, using an array data structure is preferable.
My opinion of the first post remains, if you need a collection that change frequently use the list and stick with it, if you need a collection to be only read and changed rarely arrays are better.

P.S. Please note that each result is executed 500 times in a series and the better result is picked to be sure that the result is not influenced by caches, optimization and such calamities.

What numbers do you get if you write out milliseconds (with decimals) instead of ticks? Ticks vary from machine to machine and in general it's just hard to conceptualize what the difference between 32,206 ticks and 66,991 ticks is. Is that .01ms? .1ms? 1ms? 10ms?

However it's worth noting that your foreach loop was (albeit almost as minimally as possible) faster than the for loop on your array. Interesting that it's not such with the list, but it does show that using foreach over the array did gain a little bit of time and, in my opinion, made the code much more readable.

Nick Gravelyn:

What numbers do you get if you write out milliseconds (with decimals) instead of ticks? Ticks vary from machine to machine and in general it's just hard to conceptualize what the difference between 32,206 ticks and 66,991 ticks is. Is that .01ms? .1ms? 1ms? 10ms?

However it's worth noting that your foreach loop was (albeit almost as minimally as possible) faster than the for loop on your array. Interesting that it's not such with the list, but it does show that using foreach over the array did gain a little bit of time and, in my opinion, made the code much more readable.

Yes, the foreach on the arrays is almost the same speed as it does not use enumerators. (that little difference may be noise actually) And i agree with you that is quite better in readability.
Enumerators are the reason of the terrible slowdown in the foreach for the list and the reason they are discouraged IMHO to be used in tight loops.

The list used with for in array fashion it is quite performant and should be used in every situation where the list is the best idea as collection type. (when basically there are lots of changes into the collection)

I'll do the calculation in milliseconds right away...

3,167861 ms foreach array
9,075665 ms for array unoptimized
2,935359 ms for array optimized 
20,38946 ms foreach list
17,04064 ms for list unoptimized
6,171315 ms for list optimized

As i said they are very little differences between them, only the foreach list is the very slow one compared to the rest (9 times slower than the for over array optimized).

P.S. the ms results are calculated this way. Can you confirm it is correct?

Why not just use sw.Elapsed.TotalMilliseconds? There's already a property that gives you the time in milliseconds with a decimal. :)

Nick Gravelyn:

Why not just use sw.Elapsed.TotalMilliseconds? There's already a property that gives you the time in milliseconds with a decimal. :)

http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch.elapsedmilliseconds.aspx

well, because its a long without decimals.
The results are anyway the same but without decimals.

feal87:

Nick Gravelyn:

Why not just use sw.Elapsed.TotalMilliseconds? There's already a property that gives you the time in milliseconds with a decimal. :)

http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch.elapsedmilliseconds.aspx

well, because its a long without decimals.
The results are anyway the same but without decimals.

That property you linked is not what I said. Look at it again: sw.Elapsed.TotalMillseconds. You get the Elapsed property from Stopwatch (which returns a TimeSpan) and then use the TotalMilliseconds property of that TimeSpan to get the total milliseconds with decimal place. :)

Ah lol, anyway tried and same results.

Benjamin Nitschke has written an article on this :

http://benjaminnitschke.com/2009/04/22/ForVsForeachPerformance.aspx

As you can see, a foreach + array seems to be the more efficient way to make an iteration (even if you convert a list to an array)

In most cases the readability hence smaller bug potential of foreach is preferable to the small performance difference, unless of course you must have the index, in which case the for statement is appropriate.

But the garbage problem with lists that are constantly cleared and refilled every frame is said to be a problem on the 360 and in those cases it might be worth looking at using a fixed size array.

I don't know why the NProf does not want to work anymore. It runs the application but then after some seconds the application disappears and the profiler never stops.

Well, anyway, the profiler said my application was taking about 20% of the time on the collision detection. The childs of the collision detection where basically the calculation of the rectangle coordinates and the creation of the rectangle. Ignoring the creation of the rectangle, the more consuming task was the Convert.ToInt32(float64), now I'm using float in my application but is float64 because I convert to In32 the Rounded number of my float, so the rectangle creation is like this:

        new Rectangle(Convert.ToInt32(Math.Round( X )), ...)

Now I'm thinking, I'm creating a rectangle for each sprite on the screen to check collision detection each Frame (update call) ... maybe I should create a rectangle once and then modify its properties on each frame.

The float64 (double) is coming from the Math.Round(..) call.

Just do this.

new Rectangle((int)X, ...)

or if that code is a real performance problem

instantiate the Rectangle outside the loop

Rectangle rect = new Rectangle();

then inside the loops do this

rect.X = (int)X;
rect.Y = (int)Y;
etc

so you are reusing the same object rather than instantiating a new one every time.

1.- Yes, you are right, I should create the rectangle outside the loop.

2.- That won't really work I think. You see, if the X position is the pixel 1.90 then should be the pixel 2 and not the pixel 1 on the screen.
     When I convert from world units to pixels I will get fractional pixels that I need to convert to the best matching pixel position.

jmartingarcia:

2.- That won't really work I think. You see, if the X position is the pixel 1.90 then should be the pixel 2 and not the pixel 1 on the screen.
     When I convert from world units to pixels I will get fractional pixels that I need to convert to the best matching pixel position.

There's actually a little trick you can do with this. Basically add .5 to the number and cast to integer. Then if the number was .5 or more towards the next number, it will round correctly. So make a custom round method:


Then give it a try with some numbers:


You'll see that it now rounds to the proper number without using the Math.Round method.