C# List .ConvertAll Efficiency and overhead

问题:

I recently learned about List's .ConvertAll extension. I used it a couple times in code today at work to convert a large list of my objects to a list of some other object. It seems to work really well. However I'm unsure how efficient or fast this is compared to just iterating the list and converting the object. Does .ConvertAll use anything special to speed up the conversion process or is it just a short hand way of converting Lists without having to set up a loop?

回答1:

No better way to find out than to go directly to the source, literally :)

http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs#dbcc8a668882c0db

As you can see, there's no special magic going on. It just iterates over the list and creates a new item by the converter function that you specify.

To be honest, I was not aware of this method. The more idiomatic .NET way to do this kind of projection is through the use of the Select extension method on IEnumerable<T> like so: source.Select(input => new Something(input.Name)). The advantage of this is threefold:

• It's more idomatic as I said, the ConvertAll is likely a remnant of the pre-C#3.0 days. It's not a very arcane method by any means and ConvertAll is a pretty clear description, but it might still be better to stick to what other people know, which is Select.
• It's available on all IEnumerable<T>, while ConvertAll only works on instances of List<T>. It doesn't matter if it's an array, a list or a dictionary, Select works with all of them.
• Select is lazy. It doesn't do anything until you iterate over it. This means that it returns an IEnumerable<TOutput> which you can then convert to a list by calling ToList() or not if you don't actually need a list. Or if you just want to convert and retrieve the first two items out of a list of a million items, you can simply do source.Select(input => new Something(input.Name)).Take(2).

But if your question is purely about the performance of converting a whole list to another list, then ConvertAll is likely to be somewhat faster as it's less generic than a Select followed by a ToList (it knows that a list has a size and can directly access elements by index from the underlying array for instance).

回答2:

Decompiled using ILSPy:

public List<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
{
    if (converter == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
    }
    List<TOutput> list = new List<TOutput>(this._size);
    for (int i = 0; i < this._size; i++)
    {
        list._items[i] = converter(this._items[i]);
    }
    list._size = this._size;
    return list;
}

1. Create a new list.
2. Populate the new list by iterating over the current instance, executing the specified delegate.
3. Return the new list.

Does .ConvertAll use anything special to speed up the conversion process or is it just a short hand way of converting Lists without having to set up a loop?

It doesn't do anything special with regards to conversion (what "special" thing could it do?) It is directly modifying the private _items and _size members, so it might be trivially faster under some circumstances.

As usual, if the solution makes you more productive, code easier to read, etc. use it until profiling reveals a compelling performance reason to not use it.

回答3:

It's the second way you described it - basically a short-hand way without setting up a loop.

Here's the guts of ConvertAll():

List<TOutput> list = new List<TOutput>(this._size);
for (int index = 0; index < this._size; ++index)
  list._items[index] = converter(this._items[index]);
list._size = this._size;
return list;

Where TOutput is whatever type you're converting to, and converter is a delegate indicating the method that will do the conversion.

So it loops through the List you passed in, running each element through the method you specify, and then returns a new List of the specified type.

回答4:

For precise timing in your scenarios you need to measure yourself.

Do not expect any miracles - it have to be O(n) operation since each element need to be converted and added to destination list.

Consider using Enumerable.Select instead as it will do lazy evaluation that may allow avoiding second copy of large list, especially you you need to do any filtering of items along the way.