Chciałbym rozpocząć nowy cykl na blogu, tym razem o PLINQ.  Dzisiaj zaczniemy od podstaw czyli czym jest LINQ oraz kiedy z niego korzystać.

PLINQ to skrót od Parallel Linq czyli są to zapytania wykonywane równolegle. W dzisiejszym świecie, programiści starają się zrównoleglić co tylko jest możliwe. Samodzielne pisanie LINQ w sposób równoległy jest dość niewygodne i dlatego Microsoft wprowadził PLINQ. Należy oczywiście zawsze pamiętać, że próba zrównoleglenia operacji, które muszą po prostu zostać wykonane sekwencyjnie, zwykłe pogarsza wydajność.

Z tego wynika fakt, że możemy zrównoleglić wyłącznie zadania, które da się od siebie oddzielić i można je wykonywać niezależnie od siebie – tzn. zadanie A nie potrzebuje danych z zadania B. Taka sytuacja jest komfortowa i wtedy najwięcej zyskujemy z PLINQ. W przypadku gdy zadanie B musi czekać na wynik z A, należy unikać PLINQ i tą cześć wykonać w sposób całkowicie sekwencyjny. Kluczem do prawidłowej implementacji PLINQ jest zatem podział (partition) zapytania na części. PLINQ wewnętrznie dokonuje analizy zapytania i na podstawie tego, dokonuje wyboru najbardziej optymalnej strategii. Nie chcę omawiać szczegółowo wszystkich metod podziału ponieważ jest to implementacja wewnętrzna i może ona się z czasem zmienić. Myślę jednak, że warto chociaż ogólnikowo przedstawić jak to może wyglądać. Załóżmy, że mamy następujące zapytanie:

 (from employee in employees where CalculateBonus(employee) > 10 select employee.Salary).Sum();

Powyższe zapytanie jest dobre do zrównoleglenia jeśli np. klauzula CalculateBonus lub employee.Salary pochłaniają dużo czasu. W końcu PLINQ mógłby np. cześć pracowników przetwarzać na rdzeniu A a cześć na rdzeniu B a potem tylko na końcu złączyć rezultaty aby policzyć Sum. W jaki sposób  PLINQ rozdziela zadania? Zależy to od typu kolekcji. Wewnętrzna implementacja korzysta np. z Range Partitioning dla tablic oraz list. Jeśli do danego źródła danych można dostać się za pomocą indeksów (T[]), wtedy Range Partitioning rozdziela równomiernie pomiędzy różne wątki np. elementy od 0 do 5 są przetwarzane przez ThreadA, od 6 do 10 przez Thread B itp. Taki komfort niestety można mieć dla kolekcji z góry określonych czyli takich, które mają właściwość Length oraz można do nich dostać się przez indeks.

Jeśli długość nie jest znana wtedy należy skorzystać z bardziej wyrafinowanego algorytmu np. Chunk Partitioning. Najpierw przydzielana jest stała liczba elementów do każdego wątku. Po pierwszej iteracji, jeśli nie wszystkie elementy zostały przetworzone, liczba jest podwajana. Szczegóły wewnętrzne zmieniają się, więc nie wiadomo dokładnie czy ThreadA będzie miał najpierw jeden elementy a potem 2,4,8,16 czy skok jest np. poczwórny. Jedynie co trzeba wiedzieć to fakt, że dla IEnumerable nie można w łatwy sposób dokonać podziału zadań i trzeba wykonywać to heurystycznie.

Z tego co mi wiadomo, PLINQ implementuje jeszcze dwie strategie: Striped Partitioning  oraz Hash Partitioning. Pierwsza z nich jest wykorzystywana dla SkipWhile oraz TakeWhile, druga z kolei dla GroupBy

PLINQ jest dość sprytny i jeśli uzna, że dane zapytanie nie powinno zostać wykonane w sposób równoległy to zostanie one przetworzone w klasyczny sposób. Można oczywiście takie zachowanie zmienić (tzn. zmusić .NET do wykonywania zawsze zapytania równolegle), ale zwykle jest to pożądana decyzja. Najważniejsza będzie dla nas klasa ParallelEnumerable, która dostarcza implementacje oraz rozszerzenia metod dla PLINQ.

W celu wykonania jakiegoś zapytania równolegle, zawsze należy wywołać funkcję AsParallel. Domyślnie wszystkie zapytania to czysty LINQ. Na przykład rozważmy poniższy kod:

var source = Enumerable.Range(1, 10000);
var evenNums = from num in source
               where Compute(num) > 0
               select num;

Wersja PLINQ będzie wyglądała następująco:

var source = Enumerable.Range(1, 10000);
var evenNums = from num in source.AsParallel()
               where Compute(num) > 0
               select num;

Domyślnie PLINQ wykonuje zapytania na wszystkich dostępnych CPU\Cores. Czyli jeśli mamy dwa rdzenie, tylko dwa wątki będą tworzone. Można takie zachowanie przeładować:

 (from employee in employees.AsParallel().WithDegreeOfParallelism(4) where CalculateBonus(employee) > 10 select employee.Salary).Sum();

Funkcja WithDegreeOfParallelism określa ile wątków maksymalnie może zostać stworzonych.

Jak wspomniałem, bardzo ważne jest rozpoznanie sytuacji w których PLINQ jest dobrym rozwiązaniem.

Jeśli mamy jakaś funkcję, której wykonanie zajmuje dużo czasu to jest to pierwszy sygnał do zrównoleglenia czegoś. W pierwszym zapytaniu (na początku wpisu) była użyta funkcja CalculateBonus. Jeśli jest ona czasochłonna to naturalne jest, ze dobrze byłoby ją wykonywać na więcej niż jednym rdzeniu. Załóżmy, że mamy 4 pracowników i wykonanie CalculateBonus zajmuje 1 sekundę. Wtedy poniższe zapytanie zajmie >4s:

 (from employee in employees where CalculateBonus(employee) > 10 select employee.Salary).Sum();

Wersja PLINQ na procesorze z 4 rdzeniami zajmie trochę więcej niż jedna sekunda:

 (from employee in employees.AsParallel() where CalculateBonus(employee) > 10 select employee.Salary).Sum();

W przypadku jednak, gdy zapytanie jest proste wtedy nie warto korzystać z PLINQ. Zmodyfikujmy trochę powyższy przykład:

 (from employee in employees where employee.Bonus > 10 select employee.Salary).Sum();

Jeśli właściwości Bonus, Salary nie są zbyt czasochłonne a zwracają jedynie czystą wartość, wtedy nie uzyskamy już takich dobrych rezultatów. Oczywiście dla tablic (gdzie rozmiar jest z góry znany) prawdopodobnie można zaobserwować małą optymalizację ale nie jest to przypadek wpisujący się w dobre zastosowanie PLINQ.

Następna kwestia to liczba dostępnych rdzeni. Dzisiaj na szczęście chyba wszystkie komputery mają już po kilka rdzeni. Jeśli jednak, zdarzyłoby się, że przyjdzie nam uruchamiać nasz kod na komputerach wyłącznie z jednym procesorem\rdzeniem wtedy PLINQ to po prostu zmarnowanie czasu.

Najlepsze rezultaty osiąga się, gdy kolejność elementów nie ma znaczenia. Oczywiście różne elementy są przetwarzane na różnych rdzeniach zatem kolejność domyślnie może zostać niezachowana. Istnieje funkcja AsOrdered (o niej w przyszłych wpisach) ale powoduje to utratę wydajności, podobnie jak OrderBy. Podobnie, użycie zwykłego foreach również powoduje zakłócenie wielowątkowości ponieważ co prawda zapytanie samo w sobie, zostanie wykonane równolegle, ale już foreach będzie musiał czekać na całość kolekcji.