Czy System.Linq.Enumerable.Reverse kopiuje wszystkie elementy wewnętrznie do tablicy?

Question

Kilka lat wstecz, somebody complained about the implementation of Linq.Reverse() and Microsoft promised to fix that. Było to w 2008 roku, więc pytanie brzmi, czy Framework 4 ma zoptymalizowaną implementację Linq.Reverse(), która nie zmaterializowuje kolekcji (to jest kopiuje wszystkie elementy do wewnętrznej tablicy), gdy pozwala na to typ kolekcji (na przykład IList<T>)?

Answer 1

Oczywiście nie można zoptymalizować wszystkich przypadków. Jeśli jakiś obiekt implementuje tylko IEnumerable<T>, a nie IList<T>, musisz go powtórzyć do końca, aby znaleźć ostatni element. Optymalizacja dotyczy tylko typów implementujących IList<T> (takich jak T[] lub List<T>).

Teraz, jest jest rzeczywiście zoptymalizowany w .Net 4.5 DP?Załóżmy odpalić Reflektor ILSpy:

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

Dobra, jak robi ReverseIterator<TSource>() wygląd?

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; 
} 

Co oznacza, że ​​blok iterator jest stworzenie Buffer<T> zbierania i iteracji wstecznej poprzez to. Już prawie jesteśmy, co to jest 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 
} 

Co tu mamy? Kopiujemy zawartość do tablicy. W każdym przypadku. Jedyną optymalizacją jest to, że jeśli znamy Count (tzn. Kolekcja implementuje ICollection<T>), nie musimy ponownie przydzielać tablicy.

Optymalizacja pod kątem IList<T> to , a nie w .Net 4.5 DP. W każdym przypadku tworzy kopię całej kolekcji.

Jeśli miałbym zgadywać, dlaczego nie jest zoptymalizowany, po przeczytaniu Jon Skeet's article on this issue, myślę, że to dlatego, że ta optymalizacja jest obserwowalna. Jeśli zmutujesz kolekcję podczas iteracji, zobaczysz zmienione dane z optymalizacją, ale stare dane bez tego. A optymalizacje, które faktycznie zmieniają zachowanie czegoś w subtelny sposób, są złe, ze względu na kompatybilność wsteczną.

Answer 2

EDIT: Tak, wydaje się, że ta zmiana została dokonana

Raport błędów jesteś połączony do znaków bug ustalone, ale chciałem się upewnić dla siebie. Więc napisałem ten mały program:

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); 
    } 
} 

Chodzi o to, że program przydziela 400 MB miejsca na bigList, następnie czeka, aby użytkownik mógł nacisnąć klawisz, a następnie wywołuje Enumerable.Reverse(bigList) poprzez składnia metodę rozszerzenia.

Testowałem ten program z kompilacją debugowania na maszynie z systemem Windows 7 x64. Moje użycie pamięci przed uruchomieniem programu wynosi dokładnie 2,00 GB, zgodnie z Menedżerem zadań. Następnie, zanim uderzę w klawisz, zużycie pamięci osiąga 2,63 GB. Po naciśnięciu klawisza zużycie pamięci krótko skacze do 2,75 GB. Co ważne, nie zwiększa się o 400 MB lub więcej, co miałoby miejsce, gdyby kopie wykonał Enumerable.Reverse().

ORIGINAL POST

To niemożliwe prawidłowe Enumerable.Reverse() realizacja nie skopiować do tablicy lub innej struktury danych w niektórych sytuacjach.

Skarga, którą podajesz, dotyczy wyłącznie oferty IList<T>. W ogólnym przypadku twierdzę jednak, że należy skopiować elementy do wewnętrznego bufora.

Rozważmy następującą metodę

private int x = 0; 

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

Teraz powiedzmy, że Enumerable.Reverse() nie kopiować wejście IEnumerable<T> do bufora w tym przypadku. Następnie pętla

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

byłoby iteracji przez całą drogę bloku iteratora dostać pierwszą n, przez całą drogę pierwszych 999 elementów, aby uzyskać drugą n, i tak dalej. Ale nie miałoby to takiego samego wpływu na x jako kolejną iterację, ponieważ będziemy mutować x za każdym razem, gdy powtarzaliśmy iterację przez całą wartość zwracaną przez Foo(). Aby zapobiec temu rozłączeniu między iteracją w przód i w tył, należy wykonać kopię wejścia .