- Home /
Is List as fast to access as a standard array?
Hi.
Are generic lists (or ArrayLists for that matter) as fast to access as standard arrays (i.e T[])? If I understand correctly they both hold an internal array for storing the data, so they should be about the same speed.
Answer by Statement · Dec 16, 2010 at 10:24 PM
Are generic lists as fast to access as standard arrays?
No.
T[] is quite faster than List< T > in terms of raw read/write speed.
I devised a series of tests to simply update a list of integers and an array of integers. Both collections held 10 million items. I tested both Visual Studio 2008 Console Application, both Debug and Release and finally I also tested Unity Editor and Unity Standalone - windows. The tests were run 10 times in succession to rule out noise, and I could see the numbers were roughly the same so I could easily pick any of the results and still happy there wasn't any major differences.
This is a simple test that only modifies each item with a simple addition.
These two blocks of code were exercised on the collections:
// size = 10000000
// For list for (int i = 0; i < size; i++) { list[i] = list[i] + 1; }
// For array for (int i = 0; i < size; i++) { array[i] = array[i] + 1; }
Results
In VS Console App Debug:
(Higher numbers are worse)
- Tests.ListTest - 173,0099 ms
- Tests.ArrayTest - 133,0076 ms
- Tests.ListTest took 130,08 % of Tests.ArrayTest
In VS Console App Release:
- Tests.ListTest - 108,0062 ms
- Tests.ArrayTest - 15,0008 ms
- Tests.ListTest took 720,00 % of Tests.ArrayTest
In Unity Editor:
- Tests.ListTest - 174.0099 ms
- Tests.ArrayTest - 36.002 ms
- Tests.ListTest took 483.33 % of Tests.ArrayTest
In Unity Standalone Windows (Not debug build):
- Tests.ListTest - 172.0099 ms
- Tests.ArrayTest - 35.0021 ms
- Tests.ListTest took 491.43 % of Tests.ArrayTest
Another test (mini stress test)
I made another test with the 10 million integers. This time I changed the loops to perform some extra calculation to simulate doing something meningful.
// For array, and there is a similar one for list aswell.
// Bogus calculation to put some more stress on CPU.
for (int i = 0; i < size; i++)
{
int temp = array[i];
temp = Mathf.Abs(temp * 15);
temp = temp / 3;
temp = Mathf.Clamp(temp, 0, 10);
array[i] = temp;
}
Results (Unity Editor only):
- Tests.ListTest - 288.0164 ms
- Tests.ArrayTest - 165.0094 ms
- Tests.ListTest took 174.55 % of Tests.ArrayTest
With this new code in place, calculation is about 75% slower using using list than array (note that 100% slower is simply a doubling of execution time, so it isn't even doubly slow). 174.55% is much better than 483.33%! As you see, loops doing anything more demanding shrinks the gap for the access times.
Third test, with Vector3 and Quaternion operations!
Results (Unity Editor only):
- Tests.ListTest - 6483.3708 ms
- Tests.ArrayTest - 6325.3617 ms
- Tests.ListTest took 102.50 % of Tests.ArrayTest
Finally we arrive to a point where the underlaying structure doesn't matter as much any more. As usual, 10 million items were used with identical operations performed on the list and the array. This time however, it was loaded not with int, but with Vector3. And I devised a bogus function to put some stress to simulate some useful calculation:
// Make some calcs on the vector! for (int i = 0; i < size; i++) { Vector3 temp = array[i]; temp = Stress.Vector(temp); array[i] = temp; }
// I got sick of writing copies so I refactored to a method instead. // This is called both from the array and the list. public static class Stress { public static Vector3 Vector(Vector3 temp) { var direction = temp.normalized; var offset = temp + direction * 40; var rotation = Quaternion.FromToRotation(offset.normalized, direction.normalized); temp = rotation.eulerAngles; return temp; } }
So, we're down to a mere 2.5% difference in calculation speed. That is, with 10 million vertices, List< T > is 2.5% slower than T[]. This only proves to point that while the raw access to list and array differ somewhat, their actual access times are so small they become negligible when faced with some calculation in the loop. But yeah, in raw access speed - arrays are faster. Would it help you in practice? Not sure, you'd have to profile your own program to see if it helps. It really depends on what you're doing with your code.
Please note that while accessing is faster on the array, it has a drawback in that it can't easily resize. Also note that when there is more calculation going on in the loop, the difference between list and array performance shrink considerably. If you want I can devise another test where I put some more stress on the calculations for each item in the loop. I have a feeling we'll see near similar performance then.
It's worth noting that difference is probably slightly more than the numbers show because both tests have the overhead of processing the loop and the addition. Also that for a million iterations the worst case for List was 174 ms, that means it's less than 0.000174ms for one read and one write.
Putting that in perspective there is 33.3ms per frame in a game running at 30FPS. That is enough time to do almost 200,000 list reads and writes. There is obviously other processing that has to happen, but unless you're accessing the data thousands of times per frame it's probably not a bottleneck.
Correct Petroz, and I am devising another test with collections of Vector3 to see if the difference won't shrink even further to the point having to bother with arrays are neglible.
The difference does depend on what you're using in the arrays...for example, a List of GameObjects vs a GameObject[] array had hardly any speed difference last time I tested that. Something basic like int or float is another matter of course.
BerggreenD$$anonymous$$, it is a more complex issue than that. You need to take into consideration the scope of the collection. Are other objects using it? Can you make constraints on them to live with the fact they can't add/remove items? These are design issues. The array surely has its place, I'm not saying it's utterly evil. I'm just saying I wouldn't throw out my nice List for an array unless I know I have a performance problem and I know I won't be needing dynamic size and I tried other algorithms first.
Answer by Mike 3 · Dec 16, 2010 at 08:20 PM
Generic lists should be roughly the same speed, ArrayList may be a little slower because you have to cast data coming out of it
I guess it depends on the context. I wouldn't say $$anonymous$$ike is wrong. In a normal case scenario, collection access times become near negligible and may cause them to generally have the same computational speed. He's right with the ArrayList, since you have to box/unbox the data. For value types this adds extra overhead.
This was the correct answer - the answer that received 5 votes I$$anonymous$$HO received them incorrectly. But interestingly, to their credit the author of that post admitted that in practical situation the difference between List and Array is negligible even if the analysis had been correct as operations in the loop bring the difference down to nothing and are far more important than the loop/iteration itself.
To my amazement I just ran the following two sets of code and both on my machine ran under Unity in exactly the same time to the millisecond. I'd be interested for others to try it yourself and report your results :) What does everyone think this means for performance and use of Generics vs Arrays?
/Arrays Version - 40 milliseconds ***/
DateTime dt1 = DateTime.Now;
int[] myArray = new int[100000]; for (int i = 0; i != 100000; i++) myArray[i] = i;
int j;
for (int i = 0; i != 100000; i++) j = myArray[i];
DateTime dt2 = DateTime.Now;
//break here time creation, writes and reads is dt2 - dt1 j = 1;
/ Lists Version 1 - 40 milliseconds */
DateTime dt1 = DateTime.Now;
List myList = new List();
for (int i = 0; i != 100000; i++) myList.Add(i);
int j;
for (int i = 0; i != 100000; i++) j = myList[i];
DateTime dt2 = DateTime.Now;
//break here time for list creation, writes and reads is dt2 - dt1
j = 1;
/ Lists Version 2 with capacity initialisation - 40 milliseconds */
DateTime dt1 = DateTime.Now;
List myList = new List(100000);
for (int i = 0; i != 100000; i++) myList.Add(i);
int j;
for (int i = 0; i != 100000; i++) j = myList[i];
DateTime dt2 = DateTime.Now;
Answer by Eric5h5 · Dec 16, 2010 at 09:33 PM
Generic lists are slower than built-in arrays, but not by a huge amount. Built-in arrays have a fixed size so they have optimizations based on that. ArrayLists and Arrays (JS) are quite a bit slower than both because they have to deal with boxing/unboxing.
Answer by stringa · Dec 16, 2010 at 09:59 PM
This is a general datastructures question....
There is a scalability problem with lists and the number of elements goes to infinity...
O(1) vs O(n) Lookup times...
Incorrect. List isn't a linked list. It has constant lookup - O(1). Remove is O(N) because it has to look up the item.
Typo * Remove is O(N) because it has to CO$$anonymous$$PARE each item. :)