Collection Speed Test (JS Array vs .Net Array vs ArrayList)

I've seen a lot of talk on the forum about the differences in performance between types of collections, but I've never really seen any actual performance specs. I ran a few tests to get a sense of this and (despite the anxiety it seems to cause in some) I thought I'd share.

Early Efforts:
I initially posted test results that had logical errors (patched by Tseng). Also NPSF3000 suggested use of System.Diagnostics.Stopwatch to avoid overhead. Thanks to these guys, the test was rewritten to its current form.

Methodology:
I tested differences between 4 collection types:
1.] "JavaScript" Unity Arrays
2.] .Net "Built-In" Arrays
3.] .Net ArrayLists
4.] .Net Generic Lists

Each of these were run through 3 tests comparing the time it takes to:
1.] READ stored values
2.] ADD values into a sized collection
3.] RESIZE the array and add a value per iteration.

I did this by setting up a predertermined number of itterations to cycle through and used System.Diagnostics.Stopwatch to count the elapse milliseconds it took to complete.

READ:
I prebuilt the collection to store 10 Million incrementing integers. I start the test and iterate through the array reading the current array value and passing it into a variable. After the iteration is complete, I stop the watch and record the time.

ADD:
I prebuilt the collection to store 10 Million values, each = 0. I start the test and iterate through the collection adding i to the current position in the array. After iteration is complete, I stop the watch and record the time.

RESIZE:
This test increases the array size each loop and passes in an incriminating integer that is equal to the increment count. The "JavaScript" Unity Arrays and the .Net ArrayLists / Generic Lists have methods for automatically Pushing / Adding the new number. The "Built-In" .Net Array would need to be manually resized. I did this by using Array.Resize(i+1) each loop.


EDITOR Results:
I ran the test 3 times for each category and averaged the results in the chart below:



Written in UnityScript, running in the Editor on Unity 3.5.0f5 on a computer with Intel Corei7 970 (GulfTown) @ 3.2Ghz

For reading through a collection, the .Net Array is the clear winner, Generic List is about half that speed, with the "JavaScript" Array clocking in around 1/5th the speed of the .Net Array.

For adding valuse to pre-sized collections, the .Net Array won by huge margins. Generic List were about 1/3rd that speed, with the "JavaScript" Array and .Net Array List performing less than 5% the speed of the .Net Array.

Resizing is a different story. The .Net Array resize was less than 1% the speed of the other collections. Generic List handled the resize test with speeds on par with its "ADD" test results (see comments for explanantion), out performing both the ArrayList and "JavaScript" Array by 6x to 9x respectivly.


BUILD Results:
I ran the same test on a stripped down build (Windows 64-bit). Relative speed differences amonst clollection types were simular, the the overall speeds without the Editor overhead was in the range of 50% - 150% faster , except for the .Net Array RESIZE, which was actually slower (?).



Thoughts:
I'd be curious to see if the speed results changed if another data type (besides int) was used inside the Arrays, if the code was written in C#, or if other work was performed on the arrays. There are other collection types that I didn't explore that could be tested the same way. Also, if anyone reading would like to improve or advance the code or methodology used here, I'd be curious to see the results.

My Test Code: http://pastebin.com/kGYpvE1S

 

It would be interesting to see how generics compare, i.e. System.List<int>. It ought to be around the same performance as a plain array for general access, but more like the performance of ArrayList for resizing. The main reason for that is that these collections over-allocate, so although you're increasing them one item at a time, the backing allocation is increasing in larger steps, fewer times.

 

You left out List, which is what you'd use if you want to resize arrays (which, like other dynamic arrays, gets resizing speed by not really resizing the array most of the time, but that's beside the point, although it might be worth mentioning that for built-in arrays, Resize and CopyTo are essentially doing the exact same thing). There's no real reason to use Array, or ArrayList either; a List of Object would do the same thing if you need an array that contains multiple types.

List is a fair bit slower than built-in arrays for general access, depending on what you're doing exactly and what type you use.

--Eric

 

I haven't really used Lists before, but I was VERY surprised how fast they re-sized.



It iterated through on par with the ArrayList, but was ~2.5x faster at resizing that ArrayList.

updated test script: http://pastebin.com/0r9izwjJ

 

Not surprising actually. As Eric said - its not really resizing most of the time. The array that backs List is resized in "chunks" so my guess would be that you hit a fair number of iterations where resize didn't do anything because the backing array was already big enough.

 

I just watched this happen with a list by looking at capacity and was very confused until reading these posts.

 

First off, your test is completely useless. In your itterate methods you don't test how fast read access to the array is, you test how fast their "length/count" calls are.

Code (csharp):

1.  
2. //Iterate Tests
3.  
4. function IterateJSArrayTESTER (){
5.     var timeCounter : float = 0.0;
6.     var StartTime = Time.realtimeSinceStartup;
7.     var itterationCount : int = 0;
8.     test_JSArray = new Array(1000);
9.     for(i=0; i<1000; i++){test_JSArray.Push(i);}
10.  
11.     while(timeCounter < testDuration){
12.         for(i=0; i<test_JSArray.length; i++){
13.             var thisNum : int = i;
14.         }
15.         itterationCount++;
16.         timeCounter = (Time.realtimeSinceStartup - StartTime);
17.     }
18.     test_JSArray = new Array();
19.     var formattedItCount : String = itterationCount.ToString().Format("{0:###,###,###,###0}",itterationCount);
20.     TestResult+= "ITERATE TEST: JavaScript Array - In "+testDuration+" secs Iterated through 1000 loops x Count :  "+formattedItCount+"\n";
21. }

As you see, the only thing you access from the array is "test_JSArray.length". and inside the "for" block you only assign the "i" (the itterator value, not the content of the array!!!!!) to a variable.

In the for you must do something like

Code (csharp):

1.  
2.         for(i=0; i<test_JSArray.length; i++){
3.             var thisNum : int = test_JSArray[i];
4.         }
5.  

Second error is, your JS itterator does this:

Code (csharp):

1.  
2.     test_JSArray = new Array(1000);   // initialize array of 1000
3.     for(i=0; i<1000; i++){test_JSArray.Push(i);} /// add 1000 another one. Push increases the array size => adds the element at the end of the array. What you want is test_JSArray[i] = i;
4.  

In fact you end up with an array of the 2000, not 1000. That's the reasons why your JS array is half as slow as, because it has to itterate double as twice

And no offense, but you should seriously improve your coding style somewhat and your testing logic too

 

I should probably mention that my test for List resize was actually done for 2.5 seconds and the the results doubled to match the other 5 second tests. When I tried to execute the List for 5 seconds, I would get an OutOfMemoryException.

Apparently storing 70 million ints in a List is too much to ask

 

After fixing your mess, I get for itterate

JS Array: 95,219
ArrayList: 192,501
List: 305,369
built-in C#: 887,283

However, this is still flawed, if you do that stuff in your code. Your for loop is horribly broken, wrong and not optimized. You shall never ever use myArray.count, myArray.length or myArray.length inside a for or while statement.

The only reason would be, if you think the array may change it's size while looping and usually as a programmer you would avoid such situations or solve them with some other way. For this tests, it's unnecessary, because it will tamper the endresult, because different array, have a different access time to their .length, Count or .Length variables/properties (with properties generally being slower, because of an additional function call required for the getter method)

So the final test methods must look something like

Code (csharp):

1.  
2.  
3. //Iterate Tests
4.  
5. function IterateJSArrayTESTER (){
6.     var timeCounter : float = 0.0;
7.     var StartTime = Time.realtimeSinceStartup;
8.     var itterationCount : int = 0;
9.     test_JSArray = new Array(1000);
10.     for(i=0; i<1000; i++){test_JSArray[i] = i;}
11.  
12.     var count :int = test_JSArray.length;
13.     while(timeCounter < testDuration){
14.         for(i=0; i<count; i++){
15.             var thisNum : int = test_JSArray[i];
16.         }
17.         itterationCount++;
18.         timeCounter = (Time.realtimeSinceStartup - StartTime);
19.     }
20.     test_JSArray = new Array();
21.     var formattedItCount : String = itterationCount.ToString().Format("{0:###,###,###,###0}",itterationCount);
22.     TestResult+= "ITERATE TEST: JavaScript Array - In "+testDuration+" secs Iterated through 1000 loops x Count :  "+formattedItCount+"\n";
23. }
24.  

for JS. As you can see the length gets cached in a variable, so it won't influence the tests below:

Code (csharp):

1.  
2. var count :int = test_JSArray.length;
3.  

and the final results with the optimized for loops are:

JS Array: 165,352
ArrayList: 248,565
List: 479,981
built-in C#: 1,008,748


As you see, it's a huge difference, if you use .length inside the loop or cache its value before. If you use it inside the loop, it will have to call the getter method every in every loop. Function calls are generally slow

edit:
Posted the quickly fixed stuff at http://pastebin.com/QSFdTvtc

Also your test scenario was quite... well strange. Usually people test stuff by looping x times through a certain array, reading it's values or updating/removing entries and measure the time and not in the way you did

 

That's consistent with my experience with collection types. I was going to look at the original code, since the data posted was somewhat different from what I would expect.

--Eric

 

Tseng, thanks for taking the time to look through it, those were pretty big catches. I've retested with he updated code and posted the results to my original entry.

If my method seems wonky, it's probably because I'm a 3D artist teaching myself to write code. This is a learning experience for me so I appreciate the insight.

 

+1 while I enjoy the novel approach - this method adds in some overhead that's not normally found in these micro-benchmarks.

System.Diagnostics.Stopwatch is your friend.

 

As people pointed out the way you did this is completely broken and your results can't be trusted even the slightest, so a fair warning to anyone reading this: This test is essentially useless, and you should ignore the results.

There is little reason to even do any testing, the speed is already known in the two cases that matter: Native array and List<T>. The array will be marginally faster for every operation. List<T> looses out on some speed due to the method calls you need to do to add, remove, etc. but you gain the added benefit of not having to manage the size of it yourself.

ArrayList and the JS Array are essentially useless and should be avoided. They are also slower then List<T> and native araays.

 

fholm, I think it's pretty obvious that I'm attempting to crowd-source ways to do an appropriate speed test and if you have something to offer to the conversation, I'd be glad to hear it, but I reject the notion that the speed of these different collections is unquantifiable under controlled conditions and should not be attempted, or that subjective characterization from someone like you is superior to actual numbers.

If I get some more time, I'll try running tests using System.Diagnostics.Stopwatch as NPSF3000 suggested. But to make things perfectly clear, I'd rather learn than to be right and I understand there are better ways to conduct the test, but even if mine is flawed, its the best this forum currently has to offer.

 

I think you miss-understood me, the reason I'm saying the tests are essential useless are because the performance is already a well known and well established fact. It's sort of like a 3 year old conducting a test of the color in the pens he got for his birthday when they are labeled with the color on the outside.

Let me break it down for you:

1) The System.Array or native array, written as T[] where T is any type you wish will always be fastest.
2) Next is the System.Collections.Generic.List<T> which uses an array as it's underlying storage, and since it adds more "features" on top of the basic array (such as dynamic expansion or shrinking) it will obviously be slower (but not by that much) in every case.
3) Third is the System.Collections.ArrayList, which works in the same way as the List<T> but uses boxing conversions for all values (as it's not generic). It will be significantly slower then List<T> and T[] for value types and somewhat slower for reference types. And this is just inherent in it's definition, it's literally impossible for it to be faster then List<T> and T[].
4) Last is the "JS Array" that ships with Unitys which is also built in the internal pieces of .NET, and will _also_ just by that definition be slower then any of them.

To put it in a sentance: If you need absolute performance use the native array, T[]. If you need a little bit of utility and don't want to have to deal with re-sizing the array yourself use a List<T>. Ignore all others.

 

I don't disbelieve you, it's just that the natural curiosity in me would like to define "slower", "faster", "slightly slower", "almost as fast".

It is interesting to note that your characterization of these collections is completely consistent with my "useless" test results.

 

fholm, your analogy is spot on, but do you actually have kids? Any time my children want to investigate something which I already know and tell them is a fact, I applaud them for wanting to do it. Things are much easier to understand and absorb when you've experimented with them yourself. I don't understand why you guys are being so rude about this.

In my opinion, while the benchmarking may be a bit crude, it is a helpful hands-on demonstration of some performance differences you should expect if you used these collections - in this way - in your own code.

It's fair enough to constructively point out mistakes in the code, or ways to reduce the instrumentation cost, but dismissing the whole thing as pointless is just wrong.

 

No they don't, you show the resize for T[] as being slower then for List<T> when it's not. You just did the benchmark wrong.

 

The test has been updated to use System.Diagnostics.Stopwatch, and a 3rd test added to test speeds of adding values to pre-sized collections. Results updated in the original post.

I'd be curious to get feedback on the testing method in it's current form.

 

Getting better [though I haven't scrutinized your code].

I'm not sure about the array re-sizing test though. Sure it's super slow - but that's because you've picked the worst possible use case for it. Anybody who re-sizes an array like that deserves to be shot. As such, I'm not sure of the relevance of it.

 

The resize test is still wrong, the array should win every test if they are performed properly.