Przejdź do:
Punkt wyjścia
Programowanie współbieżne jest tematem bardzo rozległym i zawiera w sobie wiele elementów, o których trzeba pamiętać, aby dostosować sposób jego użycia do potrzeb danego scenariusza i by jego użycie nie przyniosło rezultatów odwrotnych do zamierzonych. Już sama historia ewolucji API .NETa (mechanizmy takie, jak instrukcja lock, semafory, interfejs IAsyncResult, zdarzenia, biblioteka TPL aż po klasę ValueTask) pokazuje, że temat ten nie jest łatwy nawet dla inżynierów Microsoftu. Świadomość niskopoziomowych mechanizmów działających pod tą technologią ułatwia prawidłowe zastosowanie tych narzędzi. W tym artykule zostanie poruszony tylko niewielki wycinek tego obszaru wiedzy.
Aby zobrazować pewne aspekty użycia programowania współbieżnego, wziąłem za przykład scenariusz, w którym chcę wyliczyć liczby pierwsze w zadanym zakresie liczb naturalnych. Aby sprawdzić, czy dana liczba jest liczbą pierwszą, posłużyłem się przykładowym kodem znalezionym na StackOverflow:
Rozpocząłem od przetwarzania sekwencyjnego, by sprawdzić, ile czasu zajmuje wyliczenie liczb pierwszych w zakresie od 1 do 100. Aby zmierzyć ten czas, wykorzystałem bibliotekę BenchmarkDotNet.
W tym celu:
- Stworzyłem program konsolowy (w moim przypadku wykorzystam .NET Core 3.0),
- Dodałem paczkę nuget BenchmarkDotNet (w moim przypadku jest to wersja 0.11.5),
- Dodałem klasę BenchmarkTest
- Do klasy BenchmarkTest dodałem wylistowaną wyżej metodę IsPrime,
- Do klasy BenchmarkTest dodałem metodę wyliczania sekwencyjnego liczb pierwszych oraz opatrzyłem tę metodę atrybutem [Benchmark] z przestrzeni nazw BenchmarkDotNet.Attributes:
Program musiał być zbudowany w trybie RELEASE, aby dać wymierne wyniki. Aby więc uniknąć usunięcia powyższej metody podczas procesu optymalizacji, powinienem był zadbać, aby jej typ zwracany nie był deklarowany jako void. Dlatego zdecydowałem, by zwracała wyliczony wynik jako listę liczb pierwszych.
- Do metody statycznej Program.Main dodałem wywołanie mechanizmu mierzenia wydajności testowanej metody:
- Zmieniłem konfigurację projektu na Release.
W dalszym kroku mogłem już uruchomić projekt, ale – uwaga! – aby zmniejszyć wpływ innych procesów na wyniki testu (np. trybu debuggowania z Visual Studio), zrobiłem to z linii poleceń.
W wyniku uruchomienia zostały wykonane wielokrotne testy, a na końcu otrzymałem tabelkę z takimi wynikami:
Pułapka naiwnej optymalizacji
Następnie chciałem zmierzyć czas potrzebny na wygenerowanie tej samej listy liczb pierwszych w sposób równoległy. W tym celu do klasy BenchmarkTest dodałem odpowiednio zmodyfikowaną metodę. Zamiast klasy Enumerable wykorzystałem ParallelEnumerable, którego metoda Range generuje równoległą sekwencję liczb (ang. parallel sequence of integral numbers):
Po uruchomieniu programu narzędzie BenchmarkDotNet zmierzyło średni czas wykonania dla każdej z obu metod.
Wyniki były następujące:
Jak widać, zrównoleglone zadanie zostało wykonane w czasie ok. 8 razy dłuższym niż zadanie wykonane sekwencyjnie. Skąd to może wynikać?
Meandry równoległości
Microsoft na stronie Understanding Speedup in PLINQ wyjaśnia, że jedną z przyczyn niepowodzenia optymalizacji przez zrównoleglenie jest zjawisko występowania pewnego narzutu czasu (ang. overhead) potrzebnego do synchronizacji zadań pomiędzy wątkami.
To zjawisko można zaobserwować, analizując zapis zdarzeń systemowych, które w systemie Windows funkcjonują pod nazwą Event Tracing for Windows. Aby zebrać i przeanalizować te zdarzenia, użyłem narzędzia Concurrency Visualizer for Visual Studio 2017, które jest dodatkiem do Visual Studio 2017 (w momencie pisania tego artykułu nie istniał dodatek dla Visual Studio 2019).
Aby ułatwić analizę zdarzeń generowanych przez Concurrency Visualizer, chwilowo zrezygnowałem z uruchamiania analizowanego kodu przez BenchmarkDotNet, a w zamian uruchomiłem tylko raz jedną z testowanych metod – najpierw wersję sekwencyjną, potem wielowątkową. W tym celu zmodyfikowałem metodę Program.Main do poniższej postaci:
Dodatkowo, aby pozwolić narzędziu na odczytanie danych diagnostycznych z uruchamianego procesu, zmodyfikowałem plik csproj projektu, dodając w nim do elementów PropertyGroup poniższy fragment XML:
Po przebudowaniu aplikacji uruchomiłem Visual Studio 2017 i z menu Analyze / Concurrency Visualizer wybrałem komendę Launch New Process. W okienku z parametrami wskazałem ścieżkę do pliku exe mojej aplikacji:
Po kliknięciu przycisku Start został uruchomiony mój program, a następnie zostały wczytane dane dotyczące zdarzeń zarejestrowanych podczas jego uruchomienia.
Przed przeprowadzeniem tego procesu istotne jest, aby zamykać wszystkie zbędne aplikacje, by ich działanie nie wpłynęło na wynik analizy. Dodatkowo warto tę analizę powtórzyć kilka razy, aby sprawdzić, czy wyniki są do siebie wystarczająco zbliżone, i w ten sposób upewnić się co do rzetelności wyników. Ja na potrzeby tego artykułu każdą analizę wykonałem po trzy razy i – porównując wyniki między sobą – uznałem tę liczbę powtórzeń za wystarczającą.
Po zakończeniu ładowania zobaczyłem taki wykres:
Przedstawia on stopień wykorzystania rdzeni logicznych przez uruchomioną aplikację (kolor zielony) w czasie (oś pozioma) analizy. Za pomocą kolorów szarych przedstawiony jest stopień wykorzystania rdzeni logicznych przez pozostałe procesy. Kolor biały przedstawia niewykorzystane zasoby procesora.
Z punktu widzenia tej analizy istotniejsze dane kryją się jednak pod elementem „Threads”. Po jego kliknięciu ukazał się taki widok:
W tym widoku u góry znajduje się pasek, który znamy już z widoku „Utilization”, a który tutaj pełni funkcję osi czasu. Za pomocą czerwonej ramki ograniczonej po bokach uchwytami (czerwonymi kwadratami) zaznaczony jest obszar, dla którego w dolnej części przedstawiono dane. Przesuwając uchwyty, można ograniczyć ten zakres do określonego odcinka czasu i tym samym zobaczyć bardziej szczegółowe dane.
Poniżej paska osi czasu znajduje się wykres obrazujący stan wątków procesu (reprezentowanych na osi pionowej) w kolejnych momentach działania procesu (oś pozioma). W dolnej części widoku znajduje się legenda przedstawiająca znaczenie użytych kolorów, np. zielonym oznaczono stan działania (executing) wątku, a czerwonym stan synchronizacji. Na legendzie widnieją też określone w procentach udziały tych stanów w zaznaczonym obrębie czasu.
W przypadku uruchomienia eksperymentalnej metody, można zauważyć, że proces działa w więcej, niż 1 wątku, oraz że 58% czasu zostało poświęcone na synchronizację wątków, czyli operację kopiowania danych z obszarów pamięci zarezerwowanych dla poszczególnych wątków. Po zakończeniu pracy poszczególnych roboczych wątków następuje zebranie wyników (ewentualne dodatkowe operacje na tych wynikach). Proces ten nazywamy synchronizacją wątków. Następuje ona po zakończeniu pracy wszystkich wątków, aby zapewnić, że operacje wykonane w jednym wątku nie wpłyną w sposób niekontrolowany na dane przydzielone do innych wątków.
Pomimo że zastosowany sposób wyliczania liczb pierwszych był sekwencyjny, proces posiadał wiele wątków. Jest to cecha każdego procesu uruchamianego w systemie Windows – po załadowaniu aplikacji (co na wykresie jest widoczne w postaci fioletowego paska w lewej części wykresu, oznaczonego w legendzie jako proces I/O) tworzonych jest kilka wątków roboczych. Więcej informacji na ten temat można znaleźć w książce „Windows Internals. Seventh Edition. Part 1” (Pavel Yosifovich et al.) oraz – odnośnie platformy .NET – w rozdziale Threads dokumentacji The Book of the Runtime.
W kolejnym kroku uruchomiłem analizę dla wersji równoległej. Zmieniłem więc odpowiednio metodę Main:
i ponownie uruchomiłem narzędzie Concurrency Visualizer. Po przełączeniu się na zakładkę Threads mój wykres wyglądał w ten sposób:
Z wykresu wynika, że w tym przypadku synchronizacja wątków zajęła 63% czasu.
Różnica pomiędzy 58% a 63% nie wydaje się być wielka, ale – jak widać po wykresie z przypadku działania sekwencyjnego – synchronizacja odbywa się nie tylko wtedy, gdy wykonywane są obliczenia wielowątkowe, ale synchronizacja jest jednym z podstawowych działań, które odbywają się w procesach. Poza tym powyższe udziały są obliczone względem czasu trwania całego procesu, który obejmuje też czas związany z ładowaniem i uruchamianiem aplikacji, zanim aplikacja rozpocznie uruchamianie kodu, który zaimplementowaliśmy (dokona obliczeń czasu liczb pierwszych). Narzędzie BenchmarkDotNet uwzględnia te czynniki podczas mierzenia wydajności.
Działanie i synchronizację wątków utworzonych przez Parallel.Range() można zaobserwować na podstawie zakresu działania oznaczonego ciemnofioletowym paskiem oznaczonym napisem „ParallelQueryBegin”. Aby zaobserwować działania przeprowadzane na poszczególnych wątkach i synchronizację pomiędzy nimi, na osi czasu (na wykresie na samej górze okna) zawęziłem zakres wyznaczony przez ten pasek do zakresu oznaczonego ciemnofioletowym paskiem. Na ekranie zobaczyłem wtedy taki widok:
Kiedy zrównoleglać obliczenia?
Kiedy w takim razie warto zrównoleglać obliczenia? We wspomnianym artykule Understanding Speedup in PLINQ Microsoft wyjaśnia, że musi być spełniony warunek: koszt operacji obliczeniowych powinien przewyższać narzut czasu związany z synchronizacją wątków związany z tymi obliczeniami.
Obliczanie liczby pierwszej, według wykorzystanego w tym przykładzie algorytmu, będzie przebiegało szybciej dla małych liczb niż dla liczb większych. Na kolejnym etapie testów wróciłem do przeprowadzania benchmarków i sprawdzania średniego czasu wykonywania obliczeń dla zakresów: od 1 do 100, od 1 do 10’000 i od 1 do 1’000’000.
BenchmarkDotNet wspomaga parametryzację przeprowadzanych testów za pomocą atrybutu ParamsAttribute z przestrzeni nazw BenchmarkDotNet.Attributes. Ustawia się go na publicznej właściwości z publicznym setterem, a opatrzonej nim właściwości używa się w testowanej metodzie:
Po uruchomieniu testów do tabeli wyników została dodana kolumna z wartością wykorzystanego parametru:
Jak widać na wynikach: im większy zakres pętli, tym bardziej korzystne okazuje się rozwiązanie wielowątkowe.
Podsumowanie: warto robić pomiary
Temat wprowadzania współbieżności do aplikacji nie jest tematem trywialnym. W zrozumieniu tematu pomaga nie tylko znajomość dokumentacji, ale też mechanizmów systemowych działających na niskim poziomie – systemu lub nawet pamięci i procesora. Dlatego, aby upewnić się, że wprowadzenie wielowątkowości do aplikacji łączy się z realną korzyścią, warto przeprowadzać testy wydajności.
Przeczytaj także: Test-Driven Development na co dzień
Wyznawca stosowania dobrych praktyk programistycznych i pisania testów automatycznych. Po godzinach triathlonista i członek wspólnoty ewangelizacyjnej.