07 Jul 2012
Code now available at https://github.com/rmaclean/ArrayFighter. If you wish to suggest a flaw or make a suggestion to improve it please create a pull request OR give me a detailed comment explaining what is needed, why it will help/hinder etc... ideally with links.

The myths I want to tackle are:

  • Arrays are not collections
  • Arrays are faster than collections

These are two statements I have heard recently and I initially felt are wrong, so to check I myself I decided to research this myth. I am assuming when people say collections they mean classes in System.Collections or System.Collections.Generics.

Arrays are not collections

In computer science, an array type is a data type that is meant to describe a collection of elements

Source: http://en.wikipedia.org/wiki/Array_data_type

So we have established that they are collections but how to they compare to say .NET collection classes like List<T>, ArrayList & LinkedList<T>?

List<T>

Official Documentation: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

What it implements

The first aspect is what interfaces are implemented in each, and you can see below both implement the same interfaces that deal with collections and lists. Note that since List<T> is generic we have both generic & non-generic interfaces.

Where is the data?

Where does List>T? store data? In an internal field: _items which is just an array of T.

So List<T> is just an array? Yup! So how does it handle inserting new items? It increases the array size when needed by creating a new array and copying the pointers to the items into it.

Complexity of the operations

  • Add: O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
  • Insert: O(n) – where n is count
  • Remove: O(n) – where n is count

ArrayList

Official Documentation: http://msdn.microsoft.com/en-us/library/system.collections.arraylist.aspx

Let me warn you about ArrayList, if you are using .NET 2.0 or higher and you are using this class, I have the full right to smack you across the face with a glove. There is NO REASON TO USE THIS ANYMORE! Use List<T> instead, it is faster & safer.

What it implements

The first aspect is what interfaces are implemented in each, and you can see below both implement the same interfaces that deal with collections and lists.

  • Array implement: ICloneable, IList, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable
  • ArrayList implement: IList, ICollection, IEnumerable, ICloneable

Where is the data?

Where does ArrayList store data? In an internal field: _items which is just an object[].

So ArrayList is just an array? Yup! So how does it handle inserting new items? It increases the array size when needed by creating a new array and copying the pointers to the items into it.

Complexity of the operations

  • Add: O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.
  • Insert: O(n) – where n is count
  • Remove: O(n) – where n is count

Did you copy and paste List<T> for ArrayList?

Yip – because they are virtually the same, in fact the only core difference is that the internal storage is object[] versus T[]. That has side effects, like the Add methods taking in T versus object but that is it!

LinkedList<T>

Official Documentation: http://msdn.microsoft.com/en-us/library/he2s3bh7.aspx

So now we are onto something really different. An Array (and as we have seen ArrayList & List<T>) assign a continuous block of memory (number of items * item size) and then put the items in there are the correct offset.

This has the benefit for reading, for example if I need item 6, all I do is work out 6 * item size + start of array in memory and boom I am at the item. However, the problem is when I run out of space – List<T> & ArrayList solve this by making new bigger arrays! The cost of this is very high indeed (two arrays, having to copy all the items from one array to another, cleanup of the first array).

LinkedList is different, it knows about the first item in the collection, and that item has a property to the next item in the collection and so on. This means that I can add infinitely and never have issues as all I do is get the last item, and set it’s property to point to the my new item. Inserts are also way faster compared to arrays – rather than having to move all items down (as Arrays must) we just need to adjust the properties of the item before & the item I am inserting. So it is awesome? Nope – Reading is way slower.

If I need to get to item 6? I need to go to item 1, then item 2 and so on – moving along the entire way. It is slow, VERY much so. However moving backwards may be faster! This is because the node has not only a property that shows the next item but also a property that shows the previous item. So if I need to move one back it is very quick and easy, compare to arrays where I need to go back to the start and apply some math. Performance of moving backwards will really depend on how many steps backwards & the size, so in some cases array may still be faster.

What it implements

The first aspect is what interfaces are implemented in each, and you can see below both implement the same interfaces that deal with collections but not lists. So it is a collection, in the .NET sense, but not a list. It also contains the generic and non-generic versions.

  • Array implement: ICloneable, IList, ICollection, IEnumerable, IStructuralComparable, IStructuralEquatable
  • LinkedList<T> implement: ICollection<T>, IEnumerable<T>, ICollection, IEnumerable, ISerializable, IDeserializationCallback

Where is the data?

LinkedList<T> stores the first item in the list in a field called head which is of type LinkedListNode<T> which points to the first node in the collection. That is it, thee rest of the items in the collection are just linked to the head.

Complexity of the operations

Myth Outcome?

BUSTED! Arrays are collections, in both CS & .NET definitions.

Arrays are faster than collections

imageSo let’s see if they are with some micro-benchmarks & the code, if you want to dispute, is below.

I ran 6 tests on Array, ArrayList, List<T>, LinkedList<T> & Dictionary<T,K>

The tests were:

  • If we know we have 1000 items ahead of time – optimise and insert 1000 ints.
  • Insert 1000 ints, but do not preallocate any space more than 4.
  • Read every item in an collection of 100 and validate it.
  • Get the 100th item and validate it.
  • Get the 100th item, and then the 99th item and validate it.
  • Get an item based on a key
  • Insert an item at position 0.

Results

9 July 2012: As I added a new test I re-tested everything (so numbers & chart has been updated) – however the winner did not change on the tests.

Inserting into a known size?

Winner: Array

No surprise here.

LinkedList disqualified because you can’t preallocate.

Disqualified

  • Dictionary: Needs a key – we only have values in this test.

Inserting into an unknown size?

Winner: List<T>.

Interesting is that I would’ve assumed LinkedList to be faster & ArrayList to be closer to List<T>.

In hindsight it makes sense that LinkedList is slower – it needs to find the last item first as we we are adding at the end.

Disqualified

  • Array: Disqualified since it can’t magically expand like the others.
  • Dictionary: Needs a key – we only have values in this test.

Read every item?

Winner: Array

Disqualified

  • Dictionary: Needs a key – we only have values in this test.

Get Item 100?

Winner: ArrayList.

Interesting here since I would’ve guessed Array but these are all so close it likely is just background noise interfering.

Disqualified

  • Dictionary: Needs a key – we only have values in this test.

Get Item 100 & 99

Winner: Array

This test was designed for LinkedList, so very surprised it didn’t win but these are all so close it likely is just background noise interfering

No surprise – it is perfect for this situation.

Disqualified

  • Dictionary: Needs a key – we only have values in this test.

Find with a key

Winner: Dictionary.

No surprise – it is perfect for this situation.

Insert At Zero

Winner: LinkedList<T>.

No surprise – it is perfect for this situation.

Disqualified

  • Array: No way to insert at zero.
  • Dictionary: Needs a key – we only have values in this test.

Raw Numbers

Test Array ArrayList List<T> LinkedList<T> Dictionary<T,K>
Known Size Insert Speed 0,0067952 0,0251845 0,0125625    
Unknown Size Insert Speed   0,0322676 0,0178365 0,0324339  
Read Every Item Forward 0,0081916 0,0135402 0,0124702 0,03132  
Get Item 100 0,0023351 0,0021007 0,0021014 0,0033034  
Get Item 100 Then Get Item99 0,0020214 0,0021889 0,002163 0,0032026  
Find Item With Key 0,0059856 0,0042258 0,0063673 0,0067397 0,0026851
Insert At Zero   0,0047753 0,0034568 0,0024224  

Myth Outcome?

BUSTED! Arrays are fast, taking half the awards for speed, but they are not universally the fastest (depends on situation) and also the other options are so close that performance is likely not the issue when considering which structure to choose.

Comments

rein's picture

I'm not sure if you did this but try to always insert into position 0 with LinkedList. The insertions might be a bit faster since you no longer need to scan to the end of the linked list to insert an item.

Also, it's not technically correct that the items are copied into the new array when the size changes. Only the references to the objects (pointers for us old C vets) are copied so there's not that much memory that needs to be moved.

Robert MacLean's picture

Didn't try it but I agree an insert at almost any position in a linked list show out perform a array. Updated the text about it being the pointers not the objects. Thanks :)
Anonymous Coward's picture

This article isn’t sitting well with me.

Big O notation really says nothing about how an algorithm preforms. It is asymptotic notation, so it says everything about how an algorithm _scales_. n= 1000 is really far too small to be a valid test. 1000000 or even 10000000 may be more appropriate.

For example (and I stand corrected here) but in .NET 4.0 List is initialised with a capacity of 0. After the first item is inserted it is increased to 4. After that each time the capacity is reached it is doubled. So for n=1000 you are only resizing 10 times, remembering each resize becomes increasingly more expensive. In addition List.Add() is only O(n) if the size == capacity, otherwise it's O(1).

The “find item with key benchmark” is useless. Firstly you are always searching for 17 (”R”) on an input that is always sequential. This is essentially a mini version of the “Read every item” benchmark where the first 17 elements of each collection are iterated then returned. Worse the use of Linq .Single() doesn’t seem to have any optimisations. According to .NET Reflector Single() in 4.0 iterates the IEnumerable and executes the Func on each element until one passes. From what I’m seeing Single() doesn’t optimise to break out the iteration after the first element is found, so you are always iterating the entire collection.

Find item is really code for “search”. Dictionary is a hash table that doesn’t allow duplicate keys (read collisions) so it will search O(1). (http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx). So you were correct, for the wrong reasons. What you were performing on the other data structures is a linear search which is O(n). With n = 26 big O doesn’t come into play (n small). Hence the tight grouping you were seeing in your results.

I see your results were obtained in 4.5. Some of the framework details I mention may have changed but the core concepts wouldn’t. I could be waaay of the mark here, but this benchmark doesn’t seem sound to me.

Robert MacLean's picture

"Big O notation really says nothing about how an algorithm preforms." - Agreed, it is in the post to give more background and info, not to imply performance. "The “find item with key benchmark” is useless" - Thanks for pointing out the issues with it. I have adjusted the code to fix those (we have a random ordering of the data & we using first rather than single), and you know Dictionary still is the fastest. If you have other suggestions to how to improve it, let me know :)
Michael Paterson's picture

Really great post. FYI a bunch of the links for "What it implements" -> List (such as IReadOnlyList) are pointing to 127.0.0.1.

Robert MacLean's picture

Thanks :) I know they are - if you have Reflector from RedGate then clicking those will launch reflector and take you to the items themselves. I am in two minds if I should leave them or not.
Sander's picture

Re-run your tests with 100* bigger collections - i.e. 100k instead of 1000 - and see if the results are different. And then try 1m. To get actual results, you'll need meaningful times - i.e. 10..15s, not 0.0001. Never trust a benchmark that has results that are less than 3s.

Don't get 100th item, but .Count - 1. Dump LINQ completely - it will add roughly 5% overhead. Declare your IBattle implementing classes as sealed and use [MethodImpl(MethodImplOptions.NoInlining)].

I am predicting that results will look different.

Robert MacLean's picture

Thanks for the suggestions. I did try them out (haven't tried the million yet though) and my answers are below. Based on the fact no changes to winners, I am leaving the blog post as is. Code is on GitHub now too, so you are welcome to review it and I would welcome any suggestions or indications where I may have gotten it wrong.

Please also remember the goal of this post - show if array is *ALWAYS* faster, not to micro-optimize everything. So my view on this is really to see who wins, not how fast it could be made. Put another way, if all tests are unoptimised versus all test optimised that may be interesting but it is not the point - as long as the playing field is fair I am happy with it.

Answering your points specifically:

  1. Bigger collections. Impact = none. I say none, sure there was minor adjustments but winners were no affected.
  2. Meaningful times. The times displayed are averages for a single iteration.
  3. Don't get 100th item. Impact = none.
  4. Don't use LINQ. Really?! *sigh* The point is to prove Array performance (or lack of), so removed LINQ from array to give it a supposed boost. Impact = none.
  5. Sealed classes. Impact = none. You should read Do sealed classes really offer performance Benefits?
  6. Method Implementation attribute. Impact = none.
Robert MacLean's picture

All the way to a million now, and no changes to the winners.

You can see the results at: https://github.com/rmaclean/ArrayFighter/wiki/Results.-From-rmaclean%2C-...

Dirkie's picture

Very cool article. I saw another article on For vs Foreach performance a while ago, which is also quite interesting. http://abi.exdream.com/post/2009/04/22/For-vs-Foreach-Performance.aspx

Add new comment