Should updating an element in List<T> by index be quicker than using ArrayList index?

Question

I am running through some tests about using ArrayLists and List.

Speed is very important in my app.

I have tested creating 10000 records in each, finding an item by index and then updating that object for example:

List[i] = newX;

Using the arraylist seems much faster. Is that correct?

UPDATE:

Using the List[i] approach, for my List<T> approach I am using LINQ to find the index eg/

....

int index = base.FindIndex(x=>x.AlpaNumericString = "PopItem");
base[index] = UpdatedItem;

It is definately slower than

ArrayList.IndexOf("PopItem"))
base[index] = UpdatedItem;

Answer 1

ArrayList seems faster? According to the documentation ( http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx ) List should be faster when using a value type, and the same speed when using a reference type. ArrayList is slower with value types because it needs to box/unbox the values when you're accessing them.

Answer 2

I would expect them to be about the same if they are value-types. There is an extra cast/type-check for ArrayList, but nothing huge. Of course, List<T> should be preferred. If speed is the primary concern (which it almost always isn't, at least not in this way), then you might also want to profile an array (T[]) - harder (=more expensive) to add/remove, of course - but if you are just querying/assigning by index, it should be the fastest. I have had to resort to arrays for some very localised performance critical work, but 99.95% of the time this is overkill and should be avoided.

For example, for any of the 3 approaches (List<T>/ArrayList/T[]) I would expect the assignment cost to be insignificant to the cost of newing up the new instance to put into the storage.

Answer 3

A generic List (List<T>) should always be quicker than an ArrayList.

Firstly, an ArrayList is not strongly-typed and accepts types of object, so if you're storing value types in the ArrayList, they are going to be boxed and unboxed every time they are added or accessed.

A Generic List can be defined to accept only (say) int's so therefore no boxing or unboxing needs to occur when adding/accessing elements of the list.

If you're dealing with reference types, you're probably still better off with a Generic List over an ArrayList, since although there's no boxing/unboxing going on, your Generic List is type-safe, and there will be no implicit (or explicit) casts required when retrieving your strongly-typed object from the ArrayList's "collection" of object types.

There may be some edge-cases where an ArrayList is faster performing than a Generic List, however, I (personally) have not yet come across one. Even the MSDN documentation states:

Performance Considerations

In deciding whether to use the List<(Of <(T>)>) or ArrayList class, both of which have similar functionality, remember that the List<(Of <(T>)>) class performs better in most cases and is type safe. If a reference type is used for type T of the List<(Of <(T>)>) class, the behavior of the two classes is identical. However, if a value type is used for type T, you need to consider implementation and boxing issues.

If a value type is used for type T, the compiler generates an implementation of the List<(Of <(T>)>) class specifically for that value type. That means a list element of a List<(Of <(T>)>) object does not have to be boxed before the element can be used, and after about 500 list elements are created the memory saved not boxing list elements is greater than the memory used to generate the class implementation.

Make certain the value type used for type T implements the IEquatable<(Of <(T>)>) generic interface. If not, methods such as Contains must call the Object..::.Equals(Object) method, which boxes the affected list element. If the value type implements the IComparable interface and you own the source code, also implement the IComparable<(Of <(T>)>) generic interface to prevent the BinarySearch and Sort methods from boxing list elements. If you do not own the source code, pass an IComparer<(Of <(T>)>) object to the BinarySearch and Sort methods

Moreover, I particularly like the very last section of that paragraph, which states:

It is to your advantage to use the type-specific implementation of the List<(Of <(T>)>) class instead of using the ArrayList class or writing a strongly typed wrapper collection yourself. The reason is your implementation must do what the .NET Framework does for you already, and the common language runtime can share Microsoft intermediate language code and metadata, which your implementation cannot.

Touché! :)

Answer 4

Marc Gravell touched on this in his anwswer - I think it needs to be stressed.

It is usually a waste of time to prematurely optimize your code!

A better approach is to do a simple, well designed first implementation, and test it with anticipated real world data loads.

Often, you will find that it's "fast enough". (It helps to start out with a clear definition of "fast enough" - e.g. "Must be able to find a single CD in a 10,000 CD collection in 3 seconds or less")

If it's not, put a profiler on it. Almost invariably, the bottle neck will NOT be where you expect.

(I learned this the hard way when I brought a whole app to it's knees with single badly chosen string concatenation)

Answer 5

Based on your recent edit it seems as though you're not performing a 1:1 comparison here. In the List you have a class object and you're looking for the index based on a property, whereas in the ArrayList you just store the values of that property. If so, this is a severely flawed comparison.

To make it a 1:1 comparison you would add the values to the list only, not the class. Or, you would add the class items to the ArrayList. The former would allow you to use IndexOf on both collections. The latter would entail looping through your entire ArrayList and comparing each item till a match was found (and you could do the same for the List), or overriding object.Equals since ArrayList uses that for comparison.

For an interesting read, I suggest taking a look at Rico Mariani's post: Performance Quiz #7 -- Generics Improvements and Costs -- Solution. Even in that post Rico also emphasizes the need to benchmark different scenarios. No blanket statement is issued about ArrayLists, although the general consensus is to use generic lists for performance, type safety, and having a strongly typed collection.

Another related article is: Why should I use List and not ArrayList.