¿System.Linq.Enumerable.Reverse copia todos los elementos internamente en una matriz?

Question

Hace unos años, somebody complained about the implementation of Linq.Reverse() and Microsoft promised to fix that. Esto fue en 2008, por lo que la pregunta es, ¿el Framework 4 tiene una implementación optimizada de Linq.Reverse() que no materializa la colección (es decir, copia todos los elementos en una matriz interna) cuando el tipo de colección lo permite (por ejemplo, IList<T>)?

Answer 1

Obviamente no es posible optimizar todos los casos. Si algún objeto implementa solo IEnumerable<T> y no IList<T>, debe iterarlo hasta el final para encontrar el último elemento. Por lo tanto, la optimización sería solo para los tipos que implementan IList<T> (como T[] o List<T>).

Ahora, es realmente optimizado en .Net 4.5 DP?Vamos a iniciar Reflector ILSpy:

public static IEnumerable<TSource> Reverse<TSource>(
    this IEnumerable<TSource> source) 
{ 
    if (source == null) 
    { 
     throw Error.ArgumentNull("source"); 
    } 
    return ReverseIterator<TSource>(source); 
} 

bien, ¿cómo ReverseIterator<TSource>() mirada?

private static IEnumerable<TSource> ReverseIterator<TSource>(
    IEnumerable<TSource> source) 
{ 
    Buffer<TSource> buffer = new Buffer<TSource>(source); 
    for (int i = buffer.count - 1; i >= 0; i--) 
    { 
     yield return buffer.items[i]; 
    } 
    yield break; 
} 

Lo que hace que el bloque de iterador es crear un Buffer<T> para la recogida y recorrer hacia atrás a través de eso. Ya casi llegamos, ¿qué es Buffer<T>?

[StructLayout(LayoutKind.Sequential)] 
internal struct Buffer<TElement> 
{ 
    internal TElement[] items; 
    internal int count; 
    internal Buffer(IEnumerable<TElement> source) 
    { 
     TElement[] array = null; 
     int length = 0; 
     ICollection<TElement> is2 = source as ICollection<TElement>; 
     if (is2 != null) 
     { 
      length = is2.Count; 
      if (length > 0) 
      { 
       array = new TElement[length]; 
       is2.CopyTo(array, 0); 
      } 
     } 
     else 
     { 
      foreach (TElement local in source) 
      { 
       if (array == null) 
       { 
        array = new TElement[4]; 
       } 
       else if (array.Length == length) 
       { 
        TElement[] destinationArray = new TElement[length * 2]; 
        Array.Copy(array, 0, destinationArray, 0, length); 
        array = destinationArray; 
       } 
       array[length] = local; 
       length++; 
      } 
     } 
     this.items = array; 
     this.count = length; 
    } 

    // one more member omitted 
} 

¿Qué tenemos aquí? Copiamos el contenido a una matriz. En cada caso. La única optimización es que si conocemos Count (es decir, la colección implementa ICollection<T>), no es necesario reasignar la matriz.

Por lo tanto, la optimización para IList<T> es no en .NET 4.5 DP. Crea una copia de la colección completa en todos los casos.

Si tuviera que adivinar por qué no está optimizado, después de leer Jon Skeet's article on this issue, creo que es porque esa optimización es observable. Si muta la colección durante la iteración, verá los datos modificados con la optimización, pero los datos antiguos sin ella. Y las optimizaciones que realmente cambian el comportamiento de algo de manera sutil son algo malo, debido a la compatibilidad con versiones anteriores.

Answer 2

EDITAR: Sí, parece que este cambio se ha realizado

El informe de error se ha vinculado a las marcas como el insecto fijo, pero quería asegurarse por mí mismo. Por lo tanto, escribí este pequeño programa:

static void Main(string[] args) 
{ 
    List<int> bigList = Enumerable.Range(0, 100000000).ToList(); 

    Console.WriteLine("List allocated"); 
    Console.ReadKey(); 

    foreach (int n in bigList.Reverse<int>()) 
    { 
     // This will never be true, but the loop ensures that we enumerate 
     // through the return value of Reverse() 
     if (n > 100000000) 
      Console.WriteLine("{0}", n); 
    } 
} 

La idea es que el programa asigna 400 MB de espacio en bigList, espera a que el usuario presione una tecla, luego llama a través de la sintaxis Enumerable.Reverse(bigList) método de extensión.

Probé este programa con una compilación de depuración en una máquina con Windows 7 x64. Mi uso de memoria antes de iniciar el programa es exactamente 2,00 GB, de acuerdo con el Administrador de tareas. Luego, antes de presionar una tecla, el uso de la memoria llega a 2,63 GB. Después de presionar la tecla, el uso de la memoria aumenta brevemente a 2,75 GB. Es importante destacar que, sin embargo, no aumenta en 400 MB o más, que sería el caso si Enumerable.Reverse() estaban haciendo una copia.

Post original

Es imposible para una correcta aplicación Enumerable.Reverse() no copiar a una matriz u otra estructura de datos en algunas situaciones.

La queja que usted vincula se trata solo con IList<T>. En el caso general, sin embargo, defiendo que Enumerable.Reverse()debe copiar los elementos a un búfer interno.

Considere el siguiente método

private int x = 0; 

public IEnumerable<int> Foo() 
{ 
    for (int n = 0; n < 1000; n++) 
    { 
     yield return n; 
     x++; 
    } 
} 

Ahora vamos a decir que Enumerable.Reverse() no copió la entrada IEnumerable<T> a un búfer en este caso. A continuación, el bucle

foreach (int n in Foo().Reverse()) 
    Console.WriteLine("{0}", n); 

iteraría todo el camino a través del bloque iterador para conseguir el primer n, todo el camino a través de los primeros 999 elementos para conseguir el segundo n, y así sucesivamente. Pero esto no tendría el mismo efecto en x como iteración directa, porque estaríamos mutando x cada vez que iteramos casi todo el camino a través del valor de retorno de Foo(). Para evitar esta desconexión entre la iteración directa e inversa, el método Enumerable.Reverse()debe hacer una copia de la entrada IEnumerable<T>.