Performance Comparison: IList<T> Between Arrays and List<T> - Jonathan Pryor's web log

« The Return of Patriarchy | Main | Happy 1st Birthday, Sarah! »

Performance Comparison: IList<T> Between Arrays and List<T>

Rico Mariani recently asked a performance question: given the following code, which is faster, Sum(array), which converts a ushort[] to an IList<T>, or Sum(list), which uses the implicit conversion between List<T> and IList<T>.

using System;
using System.Collections.Generic;

class Test {
  static int Sum (IList<ushort> indeces)
  {
    int result = 0;
    for (int i = 0; i < indeces.Count; ++i)
      result += indeces [i];
    return result;
  }

  const int Size = 500000;

  public static void Main ()
  {
    ushort[] array= new ushort [Size];
    DateTime start = DateTime.UtcNow;
    Sum (array);
    DateTime end = DateTime.UtcNow;
    Console.WriteLine ("    ushort[]: {0}", end-start);

    List<ushort> list = new List<ushort> (Size);
    for (int i = 0; i < Size; ++i) list.Add (0);
    start = DateTime.UtcNow;
    Sum (list);
    end = DateTime.UtcNow;
    Console.WriteLine ("List<ushort>: {0}", end-start);
  }
}

Note that the question isn't about comparing the performance for constructing a ushort[] vs. a List<T>, but rather the use of an IList<ushort> backed by a ushort[] vs a List<ushort>.

The answer for Mono is that, oddly enough, List<ushort> is faster than ushort[]:

    ushort[]: 00:00:00.0690370
List<ushort>: 00:00:00.0368170

The question is, why?

The answer is, "magic." System.Array is a class with magical properties that can't be duplicated by custom classes. For example, all arrays, such as ushort[], inherit from System.Array, but only have an explicitly implemented IList indexer. What looks like an indexer usage results in completely different IL code; the compiler is involved, and must generate different code for an array access.

For example, an array access generates the IL code:

// int i = array [0];
ldarg.0    // load array
ldc.i4.0   // load index 0
ldelem.i4  // load element array [0]
stloc.0    // store into i

While an IList indexer access generates this IL code:

// object i = list [0];
ldarg.0    // load list
ldc.i4.0   // load index 0
callvirt instance object class [mscorlib]System.Collections.IList::get_Item(int32)
           // call IList.this [int]
stloc.0    // store into i

This difference in IL allows the JIT to optimize array access, since different IL is being generated only for arrays.

In .NET 2.0, System.Array got more magic: all array types implicitly implement IList<T> for the underlying array type, which is why the code above works (ushort[] implicitly implements IList<ushort>). However, this is provided by the runtime and is "magical," in that System.Reflection won't see that System.Array implements any generics interfaces. Magic.

On Mono, this is implemented via an indirection: arrays may derive from System.Array.InternalArray<T> instead of System.Array. InternalArray<T> implements IList<T>, permitting the implicit conversion from ushort[] to IList<ushort>.

However, this indirection has a performance impact: System.Array.InternalArray<T>.get_Item invokes System.Array.InternalArray<T>.GetGenericValueImpl, which is an internal call. This is the source of the overhead, as can be seen with mono --profile=default:stat program.exe:

prof counts: total/unmanaged: 172/97
     27 15.79 % mono
     12  7.02 % mono(mono_metadata_decode_row
     11  6.43 % Enumerator:MoveNext ()
     10  5.85 % Test:Sum (System.Collections.Generic.IList`1)
     10  5.85 % (wrapper managed-to-native) InternalArray`1:GetGenericValueImpl (int,uint16&)
     10  5.85 % InternalEnumerator:MoveNext ()

To conclude, List<ushort> is faster than ushort[], when accessed via an IList<ushort> reference, because the ushort[] can't be accessed as a normal array, procluding the usual runtime optimizations:

IList<T>.get_Current → List<T>.get_Current → direct T[] access, optimized by the runtime as a normal array access; vs.
IList<T>.get_Current → Array.InternalArray<T>.get_Current → Array.InternalArray<T>.GetGenericValueImpl (internal call).

It should be also noted that because of this "magic," all arrays under .NET 2.0 have more overhead than the same arrays under .NET 1.1, because of the need to support the "magic" generics interfaces. This could be optimized to save memory, such that if you never access the array via a generic interface no memory is used, but Mono has not performed such an optimization yet.

Update: After discussing this on #mono, Paolo Molaro implemented an optimization which makes the array usage much faster. Now it's only slightly slower than IList<T>:

    ushort[]: 00:00:00.0133390
List<ushort>: 00:00:00.0132830

Update 2: Rico Mariani has posted his .NET performance analysis. The key take home point? "Arrays are magic."

Posted on 10 Mar 2006 | Path: /development/mono/ | Permalink