Is List<T> as fast to access as a standard array?

Questions & Answers
,
1

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.

5

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 _= list *+ 1;*_
_*}*_
_*// For array*_
_*for (int i = 0; i < size; i++)*_
_*{*_
 <em><em>array _= array *+ 1;*_</em></em>
<em><em>_*}*_</em></em>
<em><em>_*```*_</em></em>
<em><em>_*<h2>Results</h2>*_</em></em>
<em><em>_*<p><strong>In VS Console App Debug</strong>:</p>*_</em></em>
<em><em>_*<p>(Higher numbers are worse)</p>*_</em></em>
<em><em>_*<ul>*_</em></em>
<em><em>_*<li>Tests.ListTest - 173,0099 ms</li>*_</em></em>
<em><em>_*<li>Tests.ArrayTest - 133,0076 ms</li>*_</em></em>
<em><em>_*<li>Tests.ListTest took <strong>130,08 %</strong> of Tests.ArrayTest</li>*_</em></em>
<em><em>_*</ul>*_</em></em>
<em><em>_*<p><strong>In VS Console App Release</strong>:</p>*_</em></em>
<em><em>_*<ul>*_</em></em>
<em><em>_*<li>Tests.ListTest - 108,0062 ms</li>*_</em></em>
<em><em>_*<li>Tests.ArrayTest - 15,0008 ms</li>*_</em></em>
<em><em>_*<li>Tests.ListTest took <strong>720,00 %</strong> of Tests.ArrayTest</li>*_</em></em>
<em><em>_*</ul>*_</em></em>
<em><em>_*<p><strong>In Unity Editor</strong>:</p>*_</em></em>
<em><em>_*<ul>*_</em></em>
<em><em>_*<li>Tests.ListTest - 174.0099 ms</li>*_</em></em>
<em><em>_*<li>Tests.ArrayTest - 36.002 ms</li>*_</em></em>
<em><em>_*<li>Tests.ListTest took <strong>483.33 %</strong> of Tests.ArrayTest</li>*_</em></em>
<em><em>_*</ul>*_</em></em>
<em><em>_*<p><strong>In Unity Standalone Windows</strong> (Not debug build):</p>*_</em></em>
<em><em>_*<ul>*_</em></em>
<em><em>_*<li>Tests.ListTest - 172.0099 ms</li>*_</em></em>
<em><em>_*<li>Tests.ArrayTest - 35.0021 ms</li>*_</em></em>
<em><em>_*<li>Tests.ListTest took <strong>491.43 %</strong> of Tests.ArrayTest</li>*_</em></em>
<em><em>_*</ul>*_</em></em>
<em><em>_*<hr>*_</em></em>
<em><em>_*<h2>Another test (mini stress test)</h2>*_</em></em>
<em><em>_*<p>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.</p>*_</em></em>
<em><em>_*```*_</em></em>
<em><em>_*// For array, and there is a similar one for list aswell.*_</em></em>
<em><em>_*// Bogus calculation to put some more stress on CPU.*_</em></em>
<em><em>_*for (int i = 0; i < size; i++)*_</em></em>
<em><em>_*{*_</em></em>
 <em><em><em>_int temp = array*;*_</em></em></em>
 <em><em><em><em>_temp = Mathf.Abs(temp * 15);_</em></em></em></em>
 <em><em><em>_*temp = temp / 3;*_</em></em></em>
 <em><em><em>_*temp = Mathf.Clamp(temp, 0, 10);*_</em></em></em>
 <em><em><em><em>_array *= temp;*_</em></em></em></em>
<em><em><em><em>_*}*_</em></em></em></em>
<em><em><em><em>_*```*_</em></em></em></em>
<em><em><em><em>_*<p><strong>Results (Unity Editor only):</strong></p>*_</em></em></em></em>
<em><em><em><em>_*<ul>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ListTest - 288.0164 ms</li>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ArrayTest - 165.0094 ms</li>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ListTest took <strong>174.55 %</strong> of Tests.ArrayTest</li>*_</em></em></em></em>
<em><em><em><em>_*</ul>*_</em></em></em></em>
<em><em><em><em>_*<p>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.</p>*_</em></em></em></em>
<em><em><em><em>_*<hr>*_</em></em></em></em>
<em><em><em><em>_*<h2>Third test, with Vector3 and Quaternion operations!</h2>*_</em></em></em></em>
<em><em><em><em>_*<p><strong>Results (Unity Editor only):</strong></p>*_</em></em></em></em>
<em><em><em><em>_*<ul>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ListTest - 6483.3708 ms</li>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ArrayTest - 6325.3617 ms</li>*_</em></em></em></em>
<em><em><em><em>_*<li>Tests.ListTest took <strong>102.50 %</strong> of Tests.ArrayTest</li>*_</em></em></em></em>
<em><em><em><em>_*</ul>*_</em></em></em></em>
<em><em><em><em>_*<p>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:</p>*_</em></em></em></em>
<em><em><em><em>_*```*_</em></em></em></em>
<em><em><em><em>_*// Make some calcs on the vector!*_</em></em></em></em>
<em><em><em><em>_*for (int i = 0; i < size; i++)*_</em></em></em></em>
<em><em><em><em>_*{*_</em></em></em></em>
 <em><em><em><em><em>_Vector3 temp = array*;*_</em></em></em></em></em>
 <em><em><em><em><em>_*temp = Stress.Vector(temp);*_</em></em></em></em></em>
 <em><em><em><em><em><em>_array *= temp;*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*}*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*// I got sick of writing copies so I refactored to a method instead.*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*// This is called both from the array and the list.*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*public static class Stress*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*{*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*public static Vector3 Vector(Vector3 temp)*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*{*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*var direction = temp.normalized;*_</em></em></em></em></em></em>
 <em><em><em><em><em><em><em>_var offset = temp + direction * 40;_</em></em></em></em></em></em></em>
 <em><em><em><em><em><em>_*var rotation = Quaternion.FromToRotation(offset.normalized,*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*direction.normalized);*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*temp = rotation.eulerAngles;*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*return temp;*_</em></em></em></em></em></em>
 <em><em><em><em><em><em>_*}*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*}*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*```*_</em></em></em></em></em></em>
<em><em><em><em><em><em>_*<p>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.</p>*_</em></em></em></em></em></em>
2

Generic lists should be roughly the same speed, ArrayList may be a little slower because you have to cast data coming out of it

3

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.

4

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...