Wiele programistów c# zapomina, że struktury również istnieją w .NET. Mam wrażenie, że jest to konstrukcja bardziej popularna w CPP niż w C#.

W praktyce jednak, wybranie struktur zamiast klas, może mieć kolosalne znaczenie jeśli chodzi o wydajność i płynność aplikacji. Nie jednokrotnie porównywałem te dwa typy obiektów na blogu więc podstaw nie będę omawiał tutaj. Przyjmuje, że każdy wie, że struktury znajdują się na stosie a obiekty klas na stercie.

W poście chciałbym skupić się na następującym scenariuszu. Mamy obiekt reprezentujący punkt za pomocą dwóch współrzędnych (X,Y). Jaka jest w praktyce różnica pomiędzy następującymi konstrukcjami?

struct Point
{
    public int X{get;private set;}
    public int Y{get;private set;}
}
class Point
{
    public int X{get;private set;}
    public int Y{get;private set;}
}

Point[] dataSource = new Point[10000000]

Zastanówmy się, co się dzieje gdy mamy kilka milionów punktów w pamięci w sytuacji gdy każdy z nich zdefiniowany jest przez strukturę oraz klasę.

W przypadku, gdy musimy stworzyć kilka milinów instancji, zużycie pamięci ma znaczenie. Struktura jest prosta i zajmie 8 bajtów (każdy int ma 4). Oczywiście zależy to od przyjętego layoutu, ponieważ integer i byte nie będą zajmować 5 bajtów a prawdopodobnie 8, gdyż jest to jest optymalne z punktu widzenia CPU i dostępu do takiej pamięci.

Każda klasa posiada jednak wiele dodatkowych pól. Przede wszystkim ma wskaźnik na tabelę zawierającą wskaźniki do metod. Programiści z CPP znają ją, ponieważ jest to jedyny sposób na wywołanie wirtualnych metod. Załóżmy, że mamy następujący kod:

BaseClass data = new ConcreteImplementationA();
data.Insert();

Ponadto, przyjmujemy, że Insert jest wirtualną metodą i może zostać przeładowana w różnych implementacjach. Skąd wiadomo, jaką implementację wywołać? Gdyby była to niewirtualna metoda, wtedy kompilator sprawdziłby, że zmienna data jest typu BaseClass i należy wywołać Insert znajdujący się w BaseClass. Metoda jest wirtualna więc w tym przypadku chcemy wywołać ConcreteImplementationA::Insert(). Pewnym trickiem, mogłaby być dynamiczna analiza kodu czyli sprawdzenie czym tak naprawdę jest data. W powyższym scenariuszu sprawdziłoby się to ale w praktyce możemy mieć przecież ServiceLocator albo wstrzyknięcie implementacji za pomocą konstruktora. Sprawa może być naprawdę skomplikowana, zależna od wielu warunków. W rzeczywistości problem jest rozwiązany właśnie przez tabelę wskaźników do metod. Gdy chcemy wywołać metodę, przeszukujemy taką tabelę  i za pomocą niej uzyskujemy wskaźnik do konkretnej implementacji. Tworząc ConcreteImplemantionA(), tabela zostanie stworzona z prawidłowymi wskaźnikami. Oczywiście wywołanie takiej metody jest bardziej czasochłonne ponieważ najpierw należy znaleźć odpowiedni wpis w tabeli co w przypadku gdy mamy wiele metod jest jakimś obciążeniem.

Warto zauważyć, że wspomniana tabela nie jest dokładnie tym samym czym jest w CPP. Przede wszystkim posiada ona metody do wszystkich metod, a nie tylko tych wirtualnych. Kolejną różnicą są wpisy dla interfejsów, które w CPP nie istnieją.W rzeczywistości jest tam o wiele więcej informacji przydatnych przy reflection.

W nagłówku klasy znajduje się również pole na tzw. Sync Block. Służy one do synchronizacji w środowisku wielowątkowym. Gdy chcemy skorzystać z lock, musimy przekazać jakiś obiekt, który będzie służył za identyfikator sekcji krytycznej – tylko jeden obiekt może do takowej wejść. Zakładając blokadę na obiekcie A, ustawiany w nim jest SyncBlock, który stanowi wskaźnik na specjalny obiekt w tablicy SyncBlocks. Każdy SyncBlock nie jest tworzony od nowa. W momencie, gdy zakładamy blokadę, wskaźnik jest po prostu ustawiany na odpowiedni SyncBlock. Dzięki temu jest to bardzo wydajne ponieważ nie ma niepotrzebnej alokacji obiektu – mamy do dyspozycji pulę SyncBlock. Gdy zabraknie odpowiedniej ilości SyncBlock, wtedy dopiero zostaną one utworzone. Każdy SyncBlock zawiera informacje o blokadzie takie jak wątek, który aktualnie wykonuje sekcję krytyczną, liczbę wątków oczekujących oraz recursion count czyli liczbę wykorzystywaną gdy ten sam wątek ponownie chce wejść do takiej samej sekcji krytycznej.

Wniosek jest taki, że alokacja klas jest dużo bardziej czasochłonna. Należy stworzyć dodatkowe obiekty oraz końcowy rozmiar obiektu jest dużo większy. Dla jednej instancji nie ma to większego znaczenia, ale jak mamy do czynienia z kilku-milionową tablicą wtedy jest już sytuacja warta przemyślenia.

Kolejny problem to zwolnienie pamięci. W przypadku struktury, w momencie gdy np. metoda kończy wywołanie to wszystkie obiekty zostaną automatycznie zwolnione (wyzerowane) wraz z całym stosem. Zwolnienie pamięci na stercie jest z kolei koszmarnie wolnym i czasochłonnym procesem. Należy przede wszystkim przeszukać graf obiektów, składający się z kilku milionów obiektów co już jest skomplikowanym procesem. A co jeśli, któryś z obiektów zostanie wypromowany do kolejnych generacji? Sprawa się jeszcze bardziej skomplikuje i spowolni działanie aplikacji. Pamiętajmy (pomijając specjalne tryby), że GC musi zatrzymać wszystkie wątki jeśli chce dokonać kolekcji co wiąże się z zatrzymaniem aplikacji.

Biorąc pod uwagę powyższe rozważania, używajmy zawsze struktur gdy tworzymy wiele małych obiektów (wyłącznie kilka pól). Gdy dany obiekt zajmuje kilka bajtów, wtedy klasa jest po prostu zbyt ciężkim obiektem i dodaje niepotrzebne pola.

Struktury danych w niektórych scenariuszach są dużo szybsze niż klasy.  W następnym wpisie pokażę dokładnie kiedy należy ich używać i dlaczego. W dzisiejszym poście natomiast chciałbym pokazać bardzo często popełniany błąd:

internal struct Point
{
    public int X;
    public int Y;
}

Mamy tutaj prostą strukturę. Oczywiście pierwszy problem jaki rzuca się w oczy to nie spełnienie wymogu immutable object. Kiedyś o tym pisałem, że jeśli dane w strukturach można zmieniać to spowoduje to wiele problemów. Ale dzisiaj nie o tym. Taka struktura danych spowoduje problem wydajnościowy jeśli chcemy np. przeszukiwać kolekcję danych:

if(list.Contains(new Point{X=5,Y=0}))
{
}

Dlaczego taka prosta linia kodu jest zła?

Największym zagrożeniem przy pracy ze strukturami jest boxing. Wywołanie Contains spowoduje przynajmniej dwukrotne wykonanie boxingu. Po pierwsze standardowo metoda Equals jako parametr przyjmuje object a nie oczywiście Point. Z tego względu mamy już na wstępnie boxing.  Equal jest metodą wirtualną, czyli aby ją wywołać należy uzyskać dostęp do specjalnej tablicy zawierającej wskaźniki do metod (pointers table). Struktury nie mają takiej tablicy więc należy znów skonwertować taki typ value do referencyjnego. Musimy powyższe czynności wywołać dla każdego elementu znajdującego się w tablicy, którą przeszukujemy.

Napiszmy prosty test, pokazujący ile czasu zajmie wyszukiwanie powyższej struktury w tablicy:

var list=new List<Point>();
const int elementsCount = 10000000;

for (int i = 0; i < elementsCount; i++)
{
 Point p = new Point {X = i, Y = elementsCount - i};
 list.Add(p);
}

const int testsCount = 10;

for (int i = 0; i < testsCount; i++)
{
 GC.Collect();
 GC.WaitForPendingFinalizers();

 var stopwatch = Stopwatch.StartNew();
 list.Contains(new Point{X=5,Y=0});

 GC.Collect();
 GC.WaitForPendingFinalizers();

 Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

Otrzymany wynik to 500. Kolejnym krokiem jest optymalizacja poprzez stworzenie metod, które nie będą potrzebowały boxingu:

internal struct Point:IEquatable<Point>
{
   public int X, Y;

   public bool Equals(Point other)
   {
       return X == other.X && Y == other.Y;
   }
}

Stworzenie jednej prostej metody (implementacja IEquatable) likwiduje wszelkie problemy. Mamy dokładnie dopasowany parametr wejściowy oraz nie musimy wywoływać bazowej implementacji Equal (znajdującej się w ValueType), co wymagało dostępu do tabeli wskaźników.

Po optymalizacji wykonanie tego samego przeszukania zajmuje tylko <70. Różnica jest więc kolosalna i należy o tym pamiętać. Struktury używamy w sytuacjach gdzie tworzymy setki lub miliony małych obiektów – wtedy wyszukiwanie jest realnym problemem a nie mikro-optymalizacją.

Zapytania LINQ bardzo skracają kod i zamiast wielu pętli czy warunków, możemy wszystko ładnie przedstawić za pomocą jednego zapytania. Niestety, dosyć często można zaobserwować następujący kod (sztuczny przykład):

class Person
{
   public int Age { get; set; }
   public string FirstName { get; set; }
   public IEnumerable<Person> Friends { get; set; } 
}


 dataSource.Where(p => p.FirstName == firstName).Where(p => p.Friends.Any(f => f.FirstName == friendName)).GroupBy(p => p.Age).Where(g => g.ToArray().Length > 0).OrderBy(f => f.Key).ThenBy(g => g.Count());
 

Proszę nie zwracać uwagi na optymalizacje czy logikę. Przykład stworzyłem tylko po to, aby pokazać jak bardzo można zaciemnić kod, tworząc zbyt długie zapytania. LINQ zwiększa czytelność kodu jeśli nie jest zbyt długi. Idealnie, LINQ powinien wyglądać jak zwykłe zdanie po angielsku, które nie wymaga żadnego komentarza.

Refaktoryzacja jest bardzo łatwa. Wystarczy rozdzielić powyższe zapytanie na podzapytania w formie zwykłych lub rozszerzających metod. Jeśli podobne podzapytania będą występować w różnych miejscach w kodzie, to wtedy lepiej skorzystać z metod rozszerzających:

static class PersonExtensions
{
public static IOrderedEnumerable<IGrouping<int, Person>> GroupAndSortByAge(this IEnumerable<Person> persons)
{
  return persons.GroupBy(p => p.Age).Where(g => g.ToArray().Length > 0).OrderBy(f => f.Key).ThenBy(g => g.Count());
}
public static IEnumerable<Person> HasFriend(this IEnumerable<Person> persons,string friendName)
{
  return persons.Where(p => p.Friends.Any(f => f.FirstName == friendName));
}
}

Teraz zapytanie będzie wyglądać następująco:

dataSource.Where(p => p.FirstName == firstName).HasFriend(friendName).GroupAndSortByAge();

Następnie można pokusić się o dalsze rozdzielanie podzapytań na coraz to mniejsze zapytania.

Inną kwestią jest stworzenie specjalnej metody, która zwraca zapytanie a nie za każdym razem kopiowanie całego query. Można to zrobić za pomocą wzorca gateway, repository czy znów metody rozszerzającej.

Powyższe rozwiązanie nie zadziała jeśli korzystamy z Entity Framework albo z LINQ to SQL. W takich technologiach, zapytanie musi być skonwertowane np. do T-SQL. Wyrażenia lambda to po prostu skompilowany kod c# i ciężko z tego byłoby wydobyć SQL. Z tego względu, musimy skorzystać z Expression Tree, o którym można poczytać sobie np. tutaj. W skrócie, expression dostarczają informacji o danym wyrażeniu. Za pomocą ich łatwo można zobaczyć, jakie wyrażenia zawiera kod (warunki, pętle itp.). Na końcu można skompilować to do standardowej metody lub skonwertować  wyrażenie do innego języka, np. SQL. Wyrażenia zatem zawierają opis logiki, a nie informacje w jaki sposób ją przetworzyć. Za pomocą obiektów możemy przeanalizować całą logikę metody, bez potrzeby parsowania tekstu.

Entity Framework zatem nie potrafi operować na czystych lambda ale możemy zwrócić po prostu Expression tzn.:

class Program
{
   private static void Main(string[] args)
   {
       var dataContext=new CustomDataContext();

       var lambdaQuery = dataContext.Persons.Where(SimpleLambda("test"));
       var expressionQuery = dataContext.Persons.Where(SimpleExpression("test"));
   }

   private static Func<Person,bool> SimpleLambda(string firstName)
   {
       return person => person.FirstName == firstName;
   }
   private static Expression<Func<Person, bool>> SimpleExpression(string firstName)
   {
       return person => person.FirstName == firstName;
   }
}

Pierwsze wyrażenie lambda nie zadziała, ponieważ nie da się wygenerować SQL na podstawie czystej metody C# (lambda to nic innego jak delegate). Drugie zwraca Expression – wyrażenie opisujące logikę jaką należy wykonać. Metody Where tak naprawdę zwracają kolejno IEnumerable oraz IQueryable, ale o tym pisałem już kiedyś tutaj.

Poza tym, Expression można dynamicznie tworzyć. Na przykład można dodać warunek na etapie działania aplikacji a nie kompilacji. Expression należy traktować jako kolekcje warunków, pętli i innych elementów programistycznych.

List jest bardzo popularną kolekcją danych, niestety często źle używaną. Kiedyś pisałem, że jeśli ma się jakiekolwiek informację o rozmiarze kolekcji, warto w konstruktorze przekazać początkowy rozmiar.

Temat jednak będzie dotyczył porównania List<T> z LinkedList<T>.

Jeśli ktoś samemu kiedyś pisał dynamiczną tablicę danych, to wie, że realokacja pamięci jest bardzo kosztowna. W przypadku np. listy jednokierunkowej, dodawanie nowego elementu to nic innego jak doczepienie kolejnego węzła.

List<T> ma tą zaletę, że można uzyskać dostęp przez indeks – identycznie jak w przypadku  tablic. LinkedList ma oczywiście funkcję ElementAt ale kosztuje to O(n), a nie O(1). W praktyce jednak, bardzo często nie trzeba używać dostępu przez indeks…

Czytając powyższe rozważania można dojść do wniosku, że zwykle lepiej używać LinkedList niż List. Niestety wiele programistów wpada tą w pułapkę, ponieważ złożoność pesymistyczna jest wyższa dla List<T> niż LinkedList<T>, jeśli chodzi o dodawanie nowego elementu. W praktyce jest jednak dokładnie odwrotnie:

var list = new List<int>();
var linkedList = new LinkedList<int>();
const int n = 10000000;

var stopwatch = Stopwatch.StartNew();
for(int i=0;i<n;i++)
list.Add(i);

Console.WriteLine(stopwatch.ElapsedMilliseconds);

stopwatch=Stopwatch.StartNew();
for (int i = 0; i < n; i++)
linkedList.AddLast(i);

Console.WriteLine(stopwatch.ElapsedMilliseconds);

Wynik dla List<T> to 67 a dla LinkedList<T> 1754.

Dlaczego LinkedList jest tak wolny? List<T> to dynamiczna kolekcja danych i nie realokuje pamięci za każdym razem, gdy wywołujemy Add. W momencie gdy brakuje pamięci w buforze, alokowana jest dodatkowa pamięć – za każdym razem tworząc większą rezerwę. Skutkuje to, że tylko w kilku wywołaniach Add, należy przealokować pamięć. LinkedList z kolei, za każdym razem musi stworzyć LinkedNode, który opakowuje wartość (dodaje wskaźniki Next, Previous itp.).

Nie znaczy to, że LinkedList jest zawsze wolniejszy. Wszystko zależy jak dodajemy elementy. LinkedList jest skuteczny jak chcemy dodać wartość konkretnie pomiędzy dwa inne elementy. Wtedy za pomocą wskaźników Previous, Next jest to dość łatwe – nie trzeba nic przesuwać.

Mam nadzieje, że pokazałem jak łatwo popełnić błąd w optymalizacji, jeśli nie ma się dobrego zestawu testów, potwierdzających przypuszczenia.