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:

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.