Kilka tygodni temu, w jednym z wpisów, porównałem wydajność List z LinkedList. Przykład udowodnił, że dodawanie nowych elementów w LinkedList potrafi być nawet wolniejsze niż w przypadku List. Bardzo często, programiści myślą, że to LinkedList jest lepszy do dodawania nowych elementów, ponieważ łatwiej doczepić nowy wskaźnik niż alokować ponownie pamięć (też tak kiedyś uważałem). W przypadku List jest to jednak nie do końca prawda, ponieważ List<T> alokuje pamięć z góry (zawsze więcej niż aktualnie jest potrzebne), co powoduje, że dodanie nowego elementu ma złożoność również O(1). W przypadku List nie musimy również tworzyć wrappera w formie LinkedListNode, co ma znaczenie dla value type.
Dzisiaj jednak kolejny przykład, pokazujący przewagę List. Zacznijmy po prostu od kodu:
private static void Main(string[] args) { var data = Enumerable.Range(0, 10000000).ToArray(); const int tests = 10; TestLinkedList(tests,data); TestList(tests, data); } private static void TestLinkedList(int tests, int[] data) { var linkedList = new LinkedList<int>(data); for (int i = 0; i < tests; i++) { Stopwatch stopwatch = Stopwatch.StartNew(); LinkedListNode<int> node = linkedList.First; int sum = 0; while (node != null) { sum += node.Value; node = node.Next; } Console.WriteLine("LinkedList: {0}", stopwatch.ElapsedMilliseconds); } } private static void TestList(int tests, int[] data) { var list = data.ToList(); for (int i = 0; i < tests; i++) { Stopwatch stopwatch = Stopwatch.StartNew(); int sum = 0; for (int j = 0; j < list.Count; j++) { sum += list[j]; } Console.WriteLine("List: {0}", stopwatch.ElapsedMilliseconds); } }
Wynik:
Różnica w trybie Release jest dość znacząca. Jak można to wytłumaczyć? W końcu mierzymy tutaj tylko przeglądanie elementów a nie alokowanie pamięci. W obydwu przykładach przechodzimy wyłącznie jeden raz, nie alokując zbędnych zmiennych lokalnych. Ponadto, LinkedListNode jest typem referencyjnym więc nie musimy kopiować całej zawartości w każdej iteracji.
Na blogu już wspomniałem, że dzisiaj wyzwaniem dla programistów i producentów CPU to nie ich szybkość, ale pamięć. Pamięć stanowi element w architekturze komputerów, który może spowolnić działanie algorytmów. Budowanie szybszych CPU, nie ma aż tak dużego sensu, jeśli i tak będą musiały one czekać na dane. Co z tego, że operacja może być wykonana w kilka cykli, jeśli dostarczenie danych zajmuje kilkadziesiąt cykli.
Procesory mają wielowarstwową pamięć podręczną. Dostęp do L1 jest najszybszy i z tego względu najbardziej korzystny dla nas. Ponadto, czytając jakaś zmienną, pobieramy tak naprawdę np. 64B, a nie wyłącznie pojedynczą zmienną – pisałem o tym w przypadku false sharing.
Jeśli zależy nam na wysokiej wydajności, szczególnie w środowisku wielowątkowym, powinniśmy wziąć pod uwagę jak dane są rozmieszczone w pamięci. Ma to ogromne znaczenie na wspomniany false sharing, jak i po prostu na szybkość dostępu do danych.
Wracając do przykładu… Pojedynczy element listy, to Int32 czyli 32 bity (4 bajty). Jeśli cache line wynosi 64 bajty to w jednym odczycie możemy pobrać aż 16 elementów tablicy. Kolejne iteracje zatem będą korzystać wyłącznie z L1 co jest ogromną optymalizacją (ale może spowodować również false sharing – zawsze pamiętajmy o tym).
A co w przypadku LinekdList? Musimy najpierw zobaczyć, co zawiera LinkedListNode:
public sealed class LinkedListNode<T> { /// <summary> /// Initializes a new instance of the <see cref="T:System.Collections.Generic.LinkedListNode`1"/> class, containing the specified value. /// </summary> /// <param name="value">The value to contain in the <see cref="T:System.Collections.Generic.LinkedListNode`1"/>.</param> [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] public LinkedListNode(T value); /// <summary> /// Gets the <see cref="T:System.Collections.Generic.LinkedList`1"/> that the <see cref="T:System.Collections.Generic.LinkedListNode`1"/> belongs to. /// </summary> /// /// <returns> /// A reference to the <see cref="T:System.Collections.Generic.LinkedList`1"/> that the <see cref="T:System.Collections.Generic.LinkedListNode`1"/> belongs to, or null if the <see cref="T:System.Collections.Generic.LinkedListNode`1"/> is not linked. /// </returns> public LinkedList<T> List { [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] get; } /// <summary> /// Gets the next node in the <see cref="T:System.Collections.Generic.LinkedList`1"/>. /// </summary> /// /// <returns> /// A reference to the next node in the <see cref="T:System.Collections.Generic.LinkedList`1"/>, or null if the current node is the last element (<see cref="P:System.Collections.Generic.LinkedList`1.Last"/>) of the <see cref="T:System.Collections.Generic.LinkedList`1"/>. /// </returns> public LinkedListNode<T> Next { get; } /// <summary> /// Gets the previous node in the <see cref="T:System.Collections.Generic.LinkedList`1"/>. /// </summary> /// /// <returns> /// A reference to the previous node in the <see cref="T:System.Collections.Generic.LinkedList`1"/>, or null if the current node is the first element (<see cref="P:System.Collections.Generic.LinkedList`1.First"/>) of the <see cref="T:System.Collections.Generic.LinkedList`1"/>. /// </returns> public LinkedListNode<T> Previous { get; } /// <summary> /// Gets the value contained in the node. /// </summary> /// /// <returns> /// The value contained in the node. /// </returns> public T Value { [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] get; [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")] set; } }
Widać wyraźnie, że oprócz wartości (Value), mamy wskaźnik na następny i poprzedni element oraz całą listę. Z tego względu, w pojedynczym cache-line, można załadować dużo mniej elementów, niż to ma miejsce w przypadku tablicy\listy.
Problemy z rozmieszczeniem elementów w pamięci są dość częste zatem należy zdawać sobie sprawę, jak to działa w przypadku poszczególnych struktur danych.
Tablicami wielowymiarowy zajmowałem już się tutaj. Dla przypomnienia:
for (int row = 0; row < N; row++) { for (int column = 0; column < N; column++) { array[row, column] = GetRandomValue(); } } for (int column = 0; column < N; column++) { for (int row = 0; row < N; row++) { array[row, column] = GetRandomValue(); } }
Jeśli nie jest jasne dlaczego jedna z powyższych pętli jest dużo wolniejsza, zachęcam do przeczytania ponownie wspomnianego wpisu.