Exceptions – performance

Ileż to rozmów już prowadziłem na temat

Czy w tym miejscu powinien być rzucany wyjątek czy zwracany status?

Najlepszą na to odpowiedzią jest

To zależy 😉

Ale dzisiaj nie o tym. Kilka razy podczas takich rozmów padł argument

Wyjątki są wolne…

W tym wpisie chciałbym przeprowadzić kilka testów w celu potwierdzenia lub obalenia tej tezy.

Zbadajmy więc czy rzucanie wyjątków faktycznie spowalnia naszą aplikację. W tym celu skorzystam ze znanej już z poprzednich wpisów biblioteki BenchmarkDotNet. Porównam dwa podejścia, w pierwszym metoda będzie zwracała jakiś StatusCode, a w drugim metoda będzie rzucała wyjątkiem.

Aby testy miały podobną strukturę to po zwróceniu/przechwyceniu wyniku metody, odwołam się do obiektu oraz pobiorę jego wiadomość z pola Message. Poniżej zaimplementowane testy:

Jak widać testów jest pięć: Chciałbym zbadać następujące kwestie:

  • Czy rzucanie wyjątków faktycznie jest wolniejsze niż zwrócenie statusu
  • Jaki jest narzut czasowy na tworzenie obiektu typu Exception
  • Czy blok try…catch ma jakikolwiek wpływ na szybkość wykonania metody

Jeszcze dla dopełnienia, implementacja metod z obiektu Helper:

Chciałem aby obiekt statusu miał podobną strukturę do obiektu Exception i aby były wykorzystane tego samego typu konstruktory.

No to wyniki!!!

Faktycznie, wyniki mówią same za siebie. Potwierdzają tezę, wyjątki są znacznie wolniejsze niż zwykłe zwrócenie statusu. Różnica faktycznie jest kolosalna, ponad 2700 razy na jednostkowym wywołaniu. Ale należy zwrócić uwagę na jednostki. Nanosekundy. Po szybkim przeliczeniu wyjdzie, że  rzucenie wyjątku trwa dużo, dużo mniej niż 1 milisekunda. Biorąc pod uwagę specyfikę w której używa się wyjątków (przeważnie w „górnych” partiach wykonywanego kodu) mogę z całą pewnością stwierdzić, że to podejście nie ma najmniejszego znaczenia jeżeli chodzi o wydajność aplikacji.

Możemy jeszcze porównać podejście z tworzeniem obietów StatusCode oraz Exception. Tworzenie wyjątku poprzez new faktycznie trwa dłużej. Jest to spowodowane dodatkową inicjalizacją pól wewnątrz klasy.

Poniżej wkleiłem częściowa implementację klasy Exception:

Jeżeli chodzi o samą konstrukcję try…catch. Widać tu niewielki narzut na wydajność. Wynika on najprawdopodobniej z implementacji tego mechanizmu. Chciałem wrzucić kod maszynowy generowany z bloku  try…catch oraz bez niego, ale nie do końca go jeszcze rozumiem ;D

Podsumowanie

Czy to wszystko oznacza, że rzucanie wyjątków może być używane zawsze i wszędzie ? Nie wydaje mi się.

Wpis ten pokazuje jedynie, że obsługa wyjątków trwa, ale trwa na tyle krótko, że na pewno nie jest to miejsce gdzie bym zaczął optymalizację swojego kodu.

Poniżej jeszcze dopełnienie tego co napisałem powyżej:

Reference Equality – co i jak

Tym wpisem chciałbym rozpocząć serię o trzewiach c# i ILAssembly. Ostatnimi czasy chyba dwa razy słyszałem pytanie, czym się różni operator == od metody Equals. Czy zawsze porównują referencję, czy to jest to samo? W tym wpisie chciałbym pokazać metody porównywania typów referencyjnych, dostępnych w c#. Również spojrzeć troszkę niżej i zobaczyć jak takie metody są zaimplementowane i jaki kod IL generują.

 

Więc na jakie sposoby możemy porównać dwa obiekty. Poniżej przedstawiłem wszystkie znane mi metody:

Jako że klasa Foo nie dostarcza nam, żadnej implementacji operatora == oraz metody Equals, wywoływane są bazowe z obiektu bazowego typu Object.

Operator ==

 

Operator == zawsze będzie porównywać referencję przekazanych obiektów. Na dowód tego, poniżej zamieściłem kod z IlSpy jaki został wygenerowany właśnie dla tego operatora.

Najważniejszym elementem powyższego kodu jest instrukcja ceq. Jak z dokumentacji wynika, ceq porównuje dwie wartości ze stosu, jeżeli są te same zwraca 1, w przeciwnym wypadku zwraca 0. W naszym przypadku wartościami są referencję do instancji klas Foo i dla nich następuje porównanie.

Metoda Equals

Jeżeli metoda Equals nie jest przeciążona, wywoływana jest metoda bazowa z klasy Object, metoda zwróci true w momencie gdy referencje obiektów będą te same. Zobaczmy jak ona jest zaimplementowana:

No jak widać nie za wiele widać. Atrybut MethodImplOptions.InternalCall  informuje nas, że implementacja metody jest w samym CLR. Jeszcze się nie doszukałem tego w kodzie cpp. Jak ktoś znajdzie dajcie znać.

Jeszcze kod w IL:

A więc potwierdzenie, wywołana metoda wirtualna Equals.

W tym linku znajdziemy potwierdzenie tego co napisałem, plus parę wskazówek kiedy i co najlepiej stosować.

Metoda Object.ReferenceEquals

Metoda statyczna klasy Object. Porównuje zawsze referencje. Na dowód tego kodzik źródłowy:

Wywołanie operatora ==. Jako że jest to metoda statyczna więc nie ma możliwości nadpisania jej w żaden sposób. Wywołując tą metodę mamy pewność, że zawsze wykonamy porównanie referencji.

Metoda Object.Equals

W pierwszej kolejności porównywana jest referencja. Następnie sprawdzane jest czy obiekty nie są null. Na końcu wywoływane jest Equals na pierwszej instancji.

Na podstawie powyższych przykładów można wyciągnąć jeden bardzo istotny wniosek.

Dla typów referencyjnych, jeżeli nie dostarczymy jawnych implementacji operatora == lub metody Equals, powyższe wywołania zawsze porównują referencję obiektów.

Dla potwierdzenia powyższego zaimplementujmy np. Equals:

I jeszcze porównanie za pomocą statycznej metody Equals:

Wynikiem tego porównania będzie oczywiście True. Jako, że operator == zwrócił False, oraz żadne z obiektów nie jest null, wykonana została metoda Equals. Jest ona przeciążona w klasie Bar, więc ta implementacja została wywołana.

Podsumowanie

W powyższym wpisie opisałem różne metody porównywania obiektów referencyjnych. Chciałbym nadmienić, że rozpatrywałem wyłącznie nasze implementacje. I zasada którą przytoczyłem dotyczy wyłącznie obiektów nie implementujących operatorów i metod. Należy o tym pamiętać. Zwrócić należny uwagę na np.  klasę string która posiada takie implementacje i niekoniecznie musi się zachowywać w dokładnie taki sam sposób. Omówienie klasy string zachowam sobie na inny wpis.

git log – optymalizacja

Iteruj po liście commitów, dla każdego commita na liście wyszukaj jego rodziców z tej samej listy. Połącz każdego rodzica z obecnym commitem obiektem Link.

Tak brzmi zadanie które musiałem zaimplementować w celu uzyskania pięknych kolorowych linii pomiędzy commitami na grafie.

Proste? Jasne. Szybkie 3 linijki w LINQ i mam! Mój projekt testowy ładuje się 3 ms! Genialnie!

A może podepnę jakieś firmowe repozytorium i zobaczę jaka będzie wydajność dla struktury o większej ilości commitów? Może zamiast 13 commitów, uruchomię to na 2200 commitach? Sure… czekamy…. czekamy. Umarło.

W dzisiejszym wpisie chciałbym przedstawić kilka podejść do implementacji tego zadania. Od najgorszego, po takie w którym rezultaty są zadowalające. Zastrzegam że nie musi być to koniecznie najlepsza implementacja. Po prostu lepszej mi się nie udało zrobić. Jeżeli widzisz jakieś potencjalne miejsca optymalizacji, pisz w komentarzu!

Zadanie zrealizowałem w pięciu różnych konfiguracjach:

  1. Kolekcja typu List, metoda wyszukująca LINQ
  2. Kolekcja typu Array, metoda wyszukująca LINQ
  3. Kolekcja typu Array, metoda wyszukująca Array.Find
  4. Kolekcja typu Array, klasyczne wyszukiwanie poprzez pętle for
  5. Kolekcja typu Dictionary, wyszukiwanie po kluczu słownika

Poniżej jeszcze sam obiekt Commit

Wynika z tego, że zawsze wyszukujemy po kluczu typu string.

Jeszcze w gwoli wstępu. Do pomiaru wydajności z każdych z metod użyłem frameworka benchmarkDotNet, naprawdę polecam. Dodatkowo posiłkowałem się kodem źródłowym c# dostępnym tu.

Podejście pierwsze

Pierwsze podejście najbardziej klasyczne, czyli lista i Linq. Zaletą Linq jest to, że jest wygodne, łatwo dostępne, ładnie wygląda. Wadą, są jego pierwsze dwie zalety. Dlaczego? Czasami wydaje mi się, że zbyt łatwa dostępność tego narzędzia sprawia, że ludzie przestają myśleć o implikacjach jego użycia. Nie zastanawiają się co siedzi pod spodem, dla jakich operacji, zadań jest ono dobre, a dla jakich nie.

Jaki problem może wynikać z tego kawałka kodu.

Rozszerzenie Where oraz metoda Contains. Obie te metody posiadają złożoność O(n), a co to oznacza? Przeszukiwanie liniowe, szukamy elementu, który spełnia nasze kryteria i zwracamy wynik. W przypadku Contains, wynik jest zwracany natychmiastowo po spełnieniu wymagań. W przypadku Where, iterowane są wszystkie elementy i zwrócona kolekcja poprawnych elementów. Można to podejrzeć w kodzie źródłowym c#:

Contains:

Contains to rozszerzenie metody IndexOf – który iteruje po każdym elemencie listy i porównuje go poprzez operator ==. Przypomnę, że operator ten w domyślnej implementacji zachowuje się tak samo jak Equals.

Where to tak naprawdę Extension na IEnumerable, które implementuje List. Poniżej kod źródłowy:

Tak jak w przypadku Contains,iterator przechodzi po każdym elemencie kolekcji sprawdzając predicate czyli warunek przekazany w wyrażeniu lambda. W tym przypadku jest to wynik metody Contains.

Drugie podejście

Jak widać różnicą jest jedynie przekazany typ. Tym razem użyta została tablica commtów. Jako, że tablice typów dziedziczą po typie Array, który jest z kolei klasą abstrakcyjną implementującą IEnumerable, mamy dostęp do Linq. Implementacja Where wygląda następująco:

Wywoływana jest dokładnie ta sama metoda Where rozszerzająca typ IEnumerable. Istotna w tym przypadku jest ta linijka:

A więc sprawdzenie czy typem na którym operujemy jest tablica. Jeżeli tak zwracamy WhereArrayIterator.

Tak jak mogło by się spodziewać w tym przypadku została wykorzystała „natywna” operacja dostępu do elementu poprzez index. I jest to jedyna różnica w implementacji metody MoveNext.

Trzecie podejście

Klasyczne podejście przy operacjach na tablicach. Tak nas uczyli na studiach. Brak Linq i innych „magii”. Nic szczególnego się tu nie dzieje więc przejdę dalej.

Czwarte podejście

Tutaj wykorzystałem dedykowaną metodę z obiektu Array. Można by pomyśleć, że to dobry pomysł. Zobaczmy co siedzi w środku:

Cóż my tu mamy. Na pierwszy rzut oka widać, że wykorzystanie tej metody nie jest najlepszym pomysłem. Zachowuje się jak powyższe przykłady, dodatkowo tymczasowa lista jest ponownie konwertowana na tablicę za pomocą ToArray. Można się spodziewać wyższego zużycia pamięci przy tym podejściu.

Piąte podejście

W ostatnim podejściu zastosowałem Dictionary. Jako, że w zadaniu głównie chodzi o wyszukiwanie commitów po kluczu, można się spodziewać, że ten typ będzie idealny do tego zadania. Jeżeli chodzi o wydajność wyszukiwania. MSDN informuje, że złożoność przy wyszukiwaniu po kluczu zbliżona jest do O(1). Zobaczmy jak to jest zaimplementowane:

Widać wyraźnie dlaczego operacja pobrania wartości na podstawie klucza nie jest ani O(1) ani O(n). Dzięki zastosowaniu hasha naszego klucza, ilość iteracji na kolekcji jest maksymalnie ograniczona.

Wydajność

Tak jak już wcześniej wspomniałem, testy przeprowadziłem za pomocą frameworka benchmarkDotNet. Przeprowadziłem trzy testy na różnej wielkości repozytoriach.

Benchmark – 13 commitów
Benchmark – 514 commitów
Benchmark – 2144 commitów

Chyba nikogo nie zaskoczyły powyższe wyniki. Najwydajniejszym podejściem w tym zadaniu jest zastosowanie Dictionary. Szybki dostęp do zasobu dzięki zastosowaniu hash powoduje, że różnica z podejściami opartymi na liniowym przeszukiwaniu jest kolosalna.

Z pozoru „najbrzydsze”, klasyczne podejście z użyciem pętli for również wychodzi o niebo lepiej niż pozostałe metody. W tym przypadku wyszukiwanie również jest liniowe. Wydaje mi się że na wydajność w tym przypadku ma wpływ przede wszystkim prostota rozwiązania, szybki dostęp do zasobu poprzez Index tablicy i niski współczynnik alokacji pamięci.

No właśnie, a co z pamięcią. Tak jak wspomniałem w punkcie przedstawiającym podejście z Array.FindAll, zużycie pamięci w tym przypadku jest największe. Tak jak w przypadku wydajności, ilość za alokowanej w przypadku Dictionary oraz „klasycznego” podejścia jest najniższa.

Uwaga na koniec – zaalokowana pamięć nie jest tylko wynikiem wyszukiwania i iteracji po kolekcjach. Każde podejście wywoływało metodę CreateLinks która dodawała do listy nowe linki. Metoda była wywoływana tyle samo razy. Więc ilość pamięci za alokowanej w tym przypadku nie jest miarodajną wartością. Należało by w tym przypadku wyskalować te wartości do najwyższej.

Method Alocated Scaled %
Run_LinqApproach 0,08 100
Run_DictionaryApproach 0,03 37,5
Run_ArrayApproach_WithLinq 0,07 87,5
Run_ArrayApproach_WithForLoopSearching 0,03 37,5
Run_ArrayApproach_WithArrayFindAllMethod 0,09 112,5

Przygotowanie danych

Podczas recenzji tego wpisu zwrócono mi uwagę, zadano pytanie. A co z przygotowaniem danych? Przecież takie Dictionary należy wcześniej przygotować. Na szczęście pomiar zajął mi kilka chwil. Poniżej wyniki:

Czas konwersji listy 2144 commitów na odpowiedni typ

Te kolekcje są na tyle małe, że czasy konwersji na odpowiedni typ jest znikomy. Zsumowanie obydwu wartości i tak nie zmienia wyników na tyle aby rozważać jeszcze ten aspekt.

Podsumowanie

Wiele się nauczyłem przy tym prostym zadaniu. Wydaje mi się, że problem jaki dzisiaj poruszyłem jest dość często spotykanym problemem w naszej pracy. Jak dobrać strukturę danych i algorytm aby zadanie było wydajne? Ważne jest aby sprawdzać zaimplementowane rzeczy na większej ilości danych. Żeby nie trzeba było mówić „u mnie działa”. Działa bo lista zawiera 20 elementów albo ilość produktów w DB to 4.

Przede wszystkim musimy też wiedzieć jak coś jest zbudowane. To, że Linq jest łatwo dostępne i łatwe w u życiu nie oznacza, że jest to remedium na wszystkie nasze problemy. Zanim użyjesz, zastanów się, czy przypadkiem nie będzie lepszego rozwiązania. Tak jak w tym przypadku, znalazłem ich 5, a wydaje mi się, że jest ich jeszcze wiele, wiele więcej.

Od momentu gdy .NET wszedł do świata open source, poznawanie wewnętrznej implementacji stało się dużo łatwiejsze. Nie trzeba już nic dekompilować aby poznać szczegóły, wystarczy wejść na https://referencesource.microsoft.com.