How/When to abandon the use of Arrays in c#.net?

Question

I've always been told that adding an element to an array happens like this:

An empty copy of the array+1element is created and then the data from the original array is copied into it then the new data for the new element is then loaded

If this is true, then using an array within a scenario that requires a lot of element activity is contra-indicated due to memory and cup utilization, correct?

If that is the case, shouldn't you try to avoid using an array as much as possible when you will be adding a lot of elements? Should you use iStringMap instead? If so, what happens if you need more than 2 dimensions AND need to add a lot of element additions do you just take the performance hit or is there something else that should be used?

---

PS:If your answering the question, consider moding the question up to give your answers more of a chance of being seen by the public.

Answer 1

When the array is resized, a new array must be allocated, and the contents copied. If you are only modifying the contents of the array, it is just a memory assignment.

So, you should not use arrays when you don't know the size of the array, or the size is likely to change. However, if you have a fixed length array, they are an easy way of retrieving elements by index.

Answer 2

Look at the generic List<T> as a replacement for arrays. They support most of the same things arrays do, including allocating an initial storage size if you want.

Answer 3

The best thing you can do is allocate as much memory as you need upfront if possible. This will prevent .Net from having to make additional calls to get memory on the heap. Failing that then it makes sense to allocate in chunks of 5 or whatever number makes sense for your application.

This is a rule you can apply to anything really.

Answer 4

A standard array should be defined with a length, which reserves all of the memory that it needs in a contiguous block. Adding an item to the array would put it inside of the block of already reserved memory.

Answer 5

In general, I prefer to avoid array usage. Just use List<T>. It uses a dynamically-sized array internally, and is fast enough for most usage. If you're using multi-dimentional arrays, use List<List<List<T>>> if you have to. It's not that much worse in terms of memory, and is much simpler to add items to.

If you're in the 0.1% of usage that requires extreme speed, make sure it's your list accesses that are really the problem before you try to optimize it.

Answer 6

ArrayList and List grow the array by more than one when needed (I think it's by doubling the size, but I haven't checked the source). They are generally the best choice when you are building a dynamically sized array.

When your benchmarks indicate that array resize is seriously slowing down your application (remember - premature optimization is the root of all evil), you can evaluate writing a custom array class with tweaked resizing behavior.

Answer 7

Arrays are great for few writes and many reads, particularly those of an iterative nature - for anything else, use one of the many other data structures.

Answer 8

If you're going to be adding/removing elements a lot, just use a List. If it's multidimensional, you can always use a List<List<int>> or something.

On the other hand, lists are less efficient than arrays if what you're mostly doing is traversing the list, because arrays are all in one place in your CPU cache, where objects in a list are scattered all over the place.

If you want to use an array for efficient reading but you're going to be "adding" elements frequently, you have two main options:

1) Generate it as a List (or List of Lists) and then use ToArray() to turn it into an efficient array structure.

2) Allocate the array to be larger than you need, then put the objects into the pre-allocated cells. If you end up needing even more elements than you pre-allocated, you can just reallocate the array when it fills, doubling the size each time. This gives O(log n) resizing performance instead of O(n) like it would be with a reallocate-once-per-add array. Note that this is pretty much how StringBuilder works, giving you a faster way to continually append to a string.

Answer 9

You are correct an array is great for look ups. However modifications to the size of the array are costly.

You should use a container that supports incremental size adjustments in the scenario where you're modifying the size of the array. You could use an ArrayList which allows you to set the initial size, and you could continually check the size versus the capacity and then increment the capacity by a large chunk to limit the number of resizes.

Or you could just use a linked list. Then however look ups are slow...

Answer 10

This really depends on what you mean by "add."

If you mean:

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

Then, no, this does not create a new array, and is in-fact the fastest way to alter any kind of IList in .NET.

If, however, you're using something like ArrayList, List, Collection, etc. then calling the "Add" method may create a new array -- but they are smart about it, they don't just resize by 1 element, they grow geometrically, so if you're adding lots of values only every once in a while will it have to allocate a new array. Even then, you can use the "Capacity" property to force it to grow before hand, if you know how many elements you're adding (list.Capacity += numberOfAddedElements)

Answer 11

This forum post might or might not be of some use to you regarding efficiency of various array types: C# arrays - multidimensional vs lexicographic

Answer 12

If I think I'm going to be adding items to the collection a lot over its lifetime, than I'll use a List. If I know for sure what the size of the collection will be when its declared, then I'll use an array.

Another time I generally use an array over a List is when I need to return a collection as a property of an object - I don't want callers adding items that collection via List's Add methods, but instead want them to add items to the collection via my object's interface. In that case, I'll take the internal List and call ToArray and return an array.

Answer 13

Generally, if you must have the BEST indexed lookup performance it's best to build a List first and then turn it into a array thus paying a small penalty at first but avoiding any later. If the issue is that you will be continually adding new data and removing old data then you may want to use a ArrayList or List for convenience but keep in mind that they are just special case Arrays. When they "grow" they allocate a completely new array and copy everything into it which is extremely slow.

ArrayList is just an Array which grows when needed. Add is amortized O(1), just be careful to make sure the resize won't happen at a bad time. Insert is O(n) all items to the right must be moved over. Remove is O(n) all items to the right must be moved over.

Also important to keep in mind that List is not a linked list. It's just a typed ArrayList. The List documentation does note that it performs better in most cases but does not say why.

The best thing to do is to pick a data structure which is appropriate to your problem. This depends one a LOT of things and so you may want to browse the System.Collections.Generic Namespace.

In this particular case I would say that if you can come up with a good key value Dictionary would be your best bet. It has insert and remove that approaches O(1). However, even with a Dictionary you have to be careful not to let it resize it's internal array (an O(n) operation). It's best to give them a lot of room by specifying a larger-then-you-expect-to-use initial capacity in the constructor.

-Rick

Answer 14

If you are going to be doing a lot of adding, and you will not be doing random access (such as myArray[i]). You could consider using a linked list (LinkedList<T>), because it will never have to "grow" like the List<T> implementation. Keep in mind, though, that you can only really access items in a LinkedList<T> implementation using the IEnumerable<T> interface.