What is more efficient: List<T>.Add() or System.Array.Resize()?

Question

I'm trying to determine when it's more efficient to List<T>.Add() versus using the Array.Resize() method.

The documentation for Array.Resize says it makes a copy of the entire array, and places it into a new object. The old object would have to be discarded. Where does this old object reside? On the stack or the heap?

I don't know how List.Add() works.

Does anyone know how the List.Add method compares to the static Array.Resize method?

I'm interested in memory usage (and cleanup), and what is better for 300 value types, versus 20,000 value types.

For what it's worth, I'm planning on running this code on one of the embedded flavors of .NET. Potentially the .NET Gadgeteer

Misusage

There aren't any boxing issues. Do not re-invent the wheel. List<T> exists for a reason; use it! – Tamratamsky

I had a feeling List<T> was the answer for anything above 500 objects, but am curious after reading this (search for 500) msdn.microsoft.com/en-us/library/6sh2ey19.aspx – Misusage

Are there boxing issues with System.Array? – Misusage

No, there aren't. Boxing is only an issue with non-generic collections. – Tamratamsky

That line (about 500) is talking about the size of the generic bytecode. Don't worry about it. Performance (boxing / copying) is more important than memory usage (at least at this scale) – Tamratamsky

You are probably worrying about stuff that you don't need to worry about. Unless you have a problem use List<T> if you have a fairly good idea how many items your list will usually hold you can use the capacity parameter. If you have performance problems - you can probably make better fixes than this in your code. – Playoff

@Misusage Arrays are "reference types" -- it doesn't matter what type the cell is. They have an underlying backing that is only exposed through the access operators. The conception that "value types" live on the stack is largely wrong, applies only in certain cases (e.g. local specific-typed variables and/or method arguments), and is an implementation feature/detail. – Parenteau

Answer 1

You should use a List<T>.

Using Array.Resize will force you to expand the array separately each time you add an item, making your code much slower. (since arrays cannot have spare capacity)

A List<T> is backed by an array, but holds spare capacity to put items into.
All it needs to do to add an item is to set an element in the array and increase its internal size counter.
When the array gets full, the list will double its capacity, allowing future items to be added effortlessly again.

Tamratamsky

I'm curious about what is best for 300 objects since MSDN says List<T> pays for itself at about 500 objects – Misusage

Going further, I will be creating many many arrays of 300 objects, and so understanding this optimization may be beneficial, and not just academic. – Misusage

That's in comparison to ArrayList, which should be avoided at all costs (since it's non-generic and requires casts and boxing). Also, the 500 items don't need to be in one list. If you have two lists, it'll still pay off. – Tamratamsky

If you know exactly how many items you'll need, you can set the List's Capacity in the constructor. This way, you won't need any resizes. Its performance will then be completely equivalent to an array. – Tamratamsky

When the list<T> increases in capacity, does it do a copy of existing data, or does it create some kind of psuedo linked list? Perhaps similar to an Unrolled Linked List : #4718811 – Misusage

It copies the array; the old copy is collected by the GC. – Tamratamsky

@Tamratamsky looking at this benchmark that a for over an array is 5 times more efficient than a foreach on a List<T>. Can you please recommend the best of both worlds. ie Using List<T>.Add() and then iterating over the internal array to get that efficiency gain? – Carlitacarlo

@JeremyThompson: Try for over List<T>. Or call ToArray(). – Tamratamsky

Answer 2

The .NET Micro Framework does not support generics, so I will be using an array, copying and destroying it as needed.

I might compare that perfmance to the unrolled linked list mentioned in the powertools library here: Any implementation of an Unrolled Linked List in C#?

Misusage

Answer 3

The .NET Micro Framework does not (yet) support generics. You're limited with regard to dynamic collections.

One thing to consider when picking your approach is that managed code on the microcontroller is very, very slow. Many operations in the managed .NET Micro Framework objects are actually just calling into native code to do the work. This is much faster.

For instance, compare copying an array element by element in a for loop versus calling Array.Copy() which essentially does the same thing but in native code.

Where possible, use these native extensions to get better performance. Also consider taking a look at the MicroLinq project on CodePlex. There is a sub project devoted just to enhanced collections on NETMF (also available as a NuGet package). The code is freely available and openly licensed for any purpose. (Full disclosure: I'm the dev of that project.)

If you can get away with allocating a large array and keeping track of the max position at which real data has been saved, this would be the fastest but requires more work / thought put into the design and takes away time from building the cool stuff.

Kentonkentucky

Answer 4

List will only be faster if you resize the array frequently, for example every time you add an item. However if you resize it every few frames, List and built-in arrays should be equivalent, perhaps arrays still faster.

Roentgen

Answer 5

I've seen List implementation after decompilation and found that it uses Array.Resize() for internal array. But it manages elements counter and uses array's length as capacity and resizes the array with some extra space when you call Add(). So, I guess you can develop more optimal allocation strategy than List for your case. But you will have to manage elements counter manually. Also you'll get rid of indexers overhead when accessing array elements, because indexers inside List are just methods that request internal array elements. I think it is worth to replace List by array with manual resize if it is bottleneck only.

Albite