Czy programowanie funkcjonalne jest szybsze w wielowątkowości, ponieważ piszę rzeczy inaczej lub ponieważ rzeczy są kompilowane inaczej?

63

Nurkuję w świecie programowania funkcjonalnego i czytam wszędzie, że języki funkcjonalne są lepsze dla programów wielowątkowych / wielordzeniowych. Rozumiem, w jaki sposób języki funkcjonalne robią wiele rzeczy inaczej, na przykład rekurencję , liczby losowe itp., Ale nie wydaje mi się, aby dowiedzieć się, czy wielowątkowość jest szybsza w języku funkcjonalnym, ponieważ jest inaczej skompilowana lub dlatego, że piszę inaczej.

Na przykład napisałem program w Javie, który implementuje pewien protokół. W tym protokole obie strony wysyłają i odbierają sobie tysiące wiadomości, szyfrują je i ponownie wysyłają (i odbierają). Zgodnie z oczekiwaniami wielowątkowość jest kluczowa, gdy masz do czynienia w skali tysięcy. W tym programie nie występuje blokowanie .

Jeśli napiszę ten sam program w Scali (który używa JVM), czy ta implementacja będzie szybsza? Jeśli tak, dlaczego? Czy to z powodu stylu pisania? Jeśli dzieje się tak ze względu na styl pisania, ponieważ teraz Java zawiera wyrażenia lambda, czy nie mógłbym osiągnąć takich samych wyników przy użyciu Java z lambda? A może jest to szybsze, ponieważ Scala będzie kompilować wszystko inaczej?

Awentyn
źródło
64
Programowanie funkcjonalne Afaik nie przyspiesza wielowątkowości. To sprawia, że ​​wielowątkowość jest łatwiejsza do wdrożenia i bezpieczniejsza, ponieważ istnieją pewne funkcje programowania funkcjonalnego, takie jak niezmienność i funkcje niepowodujące skutków ubocznych, które pomagają w tym względzie.
Pieter B
7
Zauważ, że 1) lepiej nie jest tak naprawdę zdefiniowane 2) z pewnością nie jest zdefiniowane jako po prostu „szybsze”. Język X, który wymaga miliarda razy większego rozmiaru kodu dla wzrostu wydajności o 0,1% względem Y, nie jest lepszy niż Y dla jakiejkolwiek rozsądnej definicji lepszego.
Bakuriu
2
Czy chciałeś zapytać o „programowanie funkcjonalne” lub „programy napisane w stylu funkcjonalnym”? Często szybsze programowanie nie daje szybszego programu.
Ben Voigt
1
Nie zapominaj, że zawsze jest GC, który musi działać w tle i nadążać za Twoimi żądaniami alokacji ... i nie jestem pewien, że jest wielowątkowy ...
Mehrdad
4
Najprostsza odpowiedź brzmi: programowanie funkcjonalne pozwala na pisanie programów, które uwzględniałyby mniej problemów z wyścigami, jednak nie oznacza to, że programy o stylu imperatywnym będą wolniejsze.
Dawid Pura

Odpowiedzi:

97

Powodem, dla którego ludzie mówią, że języki funkcjonalne są lepsze do przetwarzania równoległego, jest fakt, że zwykle unikają one stanu zmiennego. Zmienny stan jest „źródłem wszelkiego zła” w kontekście przetwarzania równoległego; sprawiają, że bardzo łatwo jest biegać w warunkach wyścigowych, gdy są one dzielone między równoległymi procesami. Rozwiązanie warunków wyścigu obejmuje następnie mechanizmy blokowania i synchronizowania, jak wspomniano, które powodują obciążenie w czasie wykonywania, ponieważ procesy czekają, aż nawzajem skorzystają z udostępnionego zasobu, i większa złożoność projektu, ponieważ wszystkie te koncepcje są zwykle głęboko zagnieżdżone w takich aplikacjach.

Gdy unikasz stanu zmiennego, wraz z nim znika potrzeba synchronizacji i mechanizmów blokowania. Ponieważ języki funkcjonalne zwykle unikają stanu zmiennego, są one naturalnie bardziej wydajne i wydajne dla przetwarzania równoległego - nie będziesz mieć narzutu zasobów współdzielonych i nie będziesz mieć dodatkowej złożoności projektowej, która zwykle następuje.

Jest to jednak przypadkowe. Jeśli Twoje rozwiązanie w Javie pozwala również na unikalny stan (szczególnie współdzielony między wątkami), konwersja do funkcjonalnego języka, takiego jak Scala lub Clojure, nie przyniosłaby żadnych korzyści pod względem równoczesnej wydajności, ponieważ oryginalne rozwiązanie jest już wolne od kosztów ogólnych spowodowanych przez mechanizmy blokujące i synchronizujące.

TL; DR: Jeśli rozwiązanie w Scali jest bardziej wydajne w przetwarzaniu równoległym niż jedno w Javie, nie dzieje się tak ze względu na sposób kompilacji lub uruchamiania kodu przez JVM, ale z tego powodu, że rozwiązanie Java dzieli stan zmiennych między wątkami, powodując warunki wyścigu lub dodając koszty synchronizacji, aby ich uniknąć.

MichelHenrich
źródło
2
Jeśli tylko jeden wątek modyfikuje kawałek danych; nie jest wymagana specjalna opieka. Tylko wtedy, gdy wiele wątków może modyfikować te same dane, potrzebujesz szczególnej opieki (synchronizacja, pamięć transakcyjna, blokowanie itp.). Przykładem tego jest stos wątku, który jest stale mutowany przez kod funkcjonalny, ale nie modyfikowany przez wiele wątków.
Brendan
31
Mając jeden wątek mutując dane, podczas gdy inne go czytają, wystarczy zacząć „zachować szczególną ostrożność”.
Peter Green
10
@Brendan: Nie, jeśli jeden wątek modyfikuje dane, podczas gdy inne wątki odczytują te same dane, oznacza to, że masz wyścig. Należy zachować szczególną ostrożność, nawet jeśli modyfikuje się tylko jeden wątek.
Cornstalks
3
Stan zmienny jest „źródłem wszelkiego zła” w kontekście równoległego przetwarzania => jeśli jeszcze nie spojrzałeś na Rdza, radzę, abyś zerknął na to. Udaje mu się bardzo skutecznie zezwalać na zmienność, uświadamiając sobie, że prawdziwy problem można modyfikować w połączeniu z aliasingiem: jeśli masz tylko aliasing lub tylko zmienność, nie ma problemu.
Matthieu M.
2
@MatthieuM. Racja, dzięki! Zredagowałem, aby wyrazić rzeczy jaśniej w mojej odpowiedzi. Zmienny stan jest „korzeniem wszelkiego zła” tylko wtedy, gdy jest dzielony między równoległymi procesami - coś, czego Rust unika dzięki mechanizmom kontroli własności.
MichelHenrich
8

W pewnym sensie oba. Jest szybszy, ponieważ łatwiej jest napisać kod w sposób łatwiejszy do szybszej kompilacji. Niekoniecznie uzyskasz różnicę prędkości, zmieniając języki, ale jeśli zacząłeś od języka funkcjonalnego, prawdopodobnie mógłbyś wykonać wielowątkowość przy znacznie mniejszym wysiłku programisty . W ten sam sposób programiście dużo łatwiej popełnia błędy w wątkach, które będą kosztować szybkość w języku imperatywnym, i znacznie trudniej je zauważyć.

Powodem jest to, że programiści zazwyczaj starają się umieścić cały bezblokowany, wątkowy kod w jak najmniejszym pudełku, i jak najszybciej uciec z niego, z powrotem do swojego wygodnego, synchronicznego, synchronicznego świata. Większość błędów, które kosztują Twoją prędkość, popełnianych jest na interfejsie granicznym. W funkcjonalnym języku programowania nie musisz się tak bardzo martwić popełnieniem błędów na tej granicy. Większość kodu telefonicznego znajduje się również „w pudełku”.

Karl Bielefeldt
źródło
7

Programowanie funkcjonalne z reguły nie powoduje szybszych programów. Pozwala to na łatwiejsze programowanie równoległe i współbieżne. Są do tego dwa główne klucze:

  1. Unikanie stanu zmiennego ma tendencję do zmniejszania liczby rzeczy, które mogą się nie udać w programie, a tym bardziej w programie współbieżnym.
  2. Unikanie operacji podstawowych synchronizacji z pamięcią współużytkowaną i blokadą na korzyść koncepcji wyższego poziomu zwykle upraszcza synchronizację między wątkami kodu.

Doskonałym przykładem punktu 2 jest to, że w Haskell mamy wyraźne rozróżnienie między równoległością deterministyczną a niedeterministyczną współbieżnością . Nie ma lepszego wytłumaczenia niż cytowanie doskonałej książki Simona Marlowa „ Programowanie równoległe i współbieżne” w Haskell (cytaty pochodzą z rozdziału 1 ):

Program równoległy to taki, który wykorzystuje wiele sprzętu obliczeniowego (np. Kilka rdzeni procesora) do szybszego wykonywania obliczeń. Celem jest wcześniejsze uzyskanie odpowiedzi poprzez przekazanie różnych części obliczeń do różnych procesorów wykonujących się w tym samym czasie.

Natomiast współbieżność jest techniką konstruowania programu, w której istnieje wiele wątków kontroli. Koncepcyjnie wątki kontroli wykonują się „w tym samym czasie”; to znaczy, użytkownik widzi, że ich efekty są przeplatane. To, czy faktycznie wykonują się w tym samym czasie, czy nie, jest szczegółem implementacji; współbieżny program może być wykonywany na jednym procesorze poprzez przeplatanie lub na wielu procesorach fizycznych.

Oprócz tego Marlow wspomina także o wymiarze determinizmu :

Powiązane jest rozróżnienie między deterministycznymi i niedeterministycznymi modelami programowania. Deterministyczny model programowania to taki, w którym każdy program może dawać tylko jeden wynik, podczas gdy niedeterministyczny model programowania dopuszcza programy, które mogą mieć różne wyniki, w zależności od niektórych aspektów wykonania. Współbieżne modele programowania są z konieczności niedeterministyczne, ponieważ muszą wchodzić w interakcje z agentami zewnętrznymi, które powodują zdarzenia w nieprzewidzianych momentach. Niedeterminizm ma jednak pewne istotne wady: Programy stają się znacznie trudniejsze do przetestowania i uzasadnienia.

W przypadku programowania równoległego chcielibyśmy stosować deterministyczne modele programowania, jeśli to w ogóle możliwe. Ponieważ celem jest po prostu szybsze uzyskanie odpowiedzi, wolelibyśmy, aby nasz program nie był trudniejszy do debugowania w tym procesie. Deterministyczne programowanie równoległe jest najlepsze z obu światów: testowanie, debugowanie i wnioskowanie można wykonywać na programie sekwencyjnym, ale program działa szybciej z dodaniem większej liczby procesorów.

W Haskell funkcje równoległości i współbieżności zostały zaprojektowane wokół tych koncepcji. W szczególności, jakie inne języki grupują razem jako jeden zestaw funkcji, Haskell dzieli się na dwa:

  • Deterministyczne cechy i biblioteki dla równoległości .
  • Niedeterministyczne cechy i biblioteki współbieżności .

Jeśli próbujesz tylko przyspieszyć czyste, deterministyczne obliczenia, posiadanie deterministycznego paralelizmu często znacznie ułatwia. Często po prostu robisz coś takiego:

  1. Napisz funkcję, która tworzy listę odpowiedzi, z których każda jest kosztowna do obliczenia, ale nie bardzo od siebie zależy. To jest Haskell, więc listy są leniwe - wartości ich elementów nie są obliczane, dopóki konsument ich nie zażąda.
  2. Użyj biblioteki Strategie, aby równolegle korzystać z elementów list wyników funkcji na wielu rdzeniach.

Zrobiłem to w jednym z moich programów zabawkowych kilka tygodni temu . Równoważenie programu było trywialne - kluczową rzeczą, którą musiałem zrobić, było dodanie kodu, który mówi „oblicz równolegle elementy tej listy” (linia 90), i uzyskałem prawie liniową poprawę przepustowości w niektóre z moich droższych przypadków testowych.

Czy mój program jest szybszy niż gdybym korzystał z konwencjonalnych narzędzi do wielowątkowości opartych na blokadach? Bardzo w to wątpię. W moim przypadku fajną rzeczą było uzyskanie tak wielkiego huku z tak małej złotówki - mój kod jest prawdopodobnie bardzo nieoptymalny, ale ponieważ jest tak łatwy do zrównoleglenia, uzyskałem duże przyspieszenie przy znacznie mniejszym wysiłku niż odpowiednie profilowanie i optymalizacja, i bez ryzyka warunków wyścigu. I to, jak twierdzę, jest to główny sposób, w jaki programowanie funkcjonalne pozwala pisać „szybsze” programy.

sacundim
źródło
2

W Haskell modyfikacja jest dosłownie niemożliwa bez uzyskania specjalnych modyfikowalnych zmiennych poprzez bibliotekę modyfikacji. Zamiast tego funkcje tworzą potrzebne zmienne w tym samym czasie, co ich wartości (które są obliczane leniwie), a śmieci są gromadzone, gdy nie są już potrzebne.

Nawet gdy potrzebujesz zmiennych do modyfikacji, zwykle możesz to zrobić, używając zapasowo i wraz ze zmiennymi niemodyfikowalnymi. (Kolejną fajną rzeczą w haskell jest STM, który zastępuje zamki operacjami atomowymi, ale nie jestem pewien, czy dotyczy to programowania funkcjonalnego, czy nie.) Zwykle tylko jedna część programu musi być połączona równolegle, aby poprawić rzeczy pod względem wydajności.

To sprawia, że ​​równoległość w Haskell jest bardzo łatwa, a w rzeczywistości trwają starania, aby była ona automatyczna. W przypadku prostego kodu równoległość i logikę można nawet rozdzielić.

Ponadto ze względu na fakt, że kolejność oceny nie ma znaczenia w Haskell, kompilator po prostu tworzy kolejki rzeczy, które wymagają oceny, i wysyła je do dowolnych dostępnych rdzeni, dzięki czemu można utworzyć grupę „wątków”, które nie mają znaczenia faktycznie stają się wątkami, dopóki nie są konieczne. Kolejność oceny bez znaczenia jest charakterystyczna dla czystości, która zwykle wymaga programowania funkcjonalnego.

Dalsza lektura
Równoległość w Haskell (HaskellWiki)
Programowanie współbieżne i wielordzeniowe w „Real-World Haskell”
Programowanie równoległe i współbieżne w Haskell przez Simon Marlow

PyRulez
źródło
7
grep java this_post. grep scala this_posti grep jvm this_postnie zwracają żadnych wyników :)
Andres F.,
4
Pytanie jest niejasne. W tytule i akapicie pierwszym pyta ogólnie o programowanie funkcjonalne , w akapicie drugim i trzecim pyta w szczególności o Javę i Scalę . Jest to niefortunne, zwłaszcza, że jednym z podstawowych atutów Scala jest właśnie fakt, że to nie (tylko) język funkcjonalny. Martin Odersky nazywa to „postfunkcjonalnym”, inni nazywają to „obiektowo-funkcjonalnym”. Istnieją dwie różne definicje terminu „programowanie funkcjonalne”. Jednym z nich jest „programowanie przy użyciu procedur najwyższej klasy” (oryginalna definicja stosowana w LISP), drugim jest…
Jörg W Mittag
2
„programowanie z względnie przejrzystymi, czystymi funkcjami wolnymi od skutków ubocznych i niezmiennymi trwałymi danymi” (znacznie surowsza, a także nowsza interpretacja). Ta odpowiedź dotyczy drugiej interpretacji, co ma sens, ponieważ a) pierwsza interpretacja jest całkowicie niezwiązana z paralelizmem i współbieżnością, b) pierwsza interpretacja stała się w zasadzie bez znaczenia, ponieważ z wyjątkiem C prawie każdego języka w nawet umiarkowanie szerokim zastosowaniu dziś ma pierwszorzędne procedury (w tym Java), c) OP pyta o różnicę między Javą a Scalą, ale nie ma…
Jörg W Mittag
2
pomiędzy tymi dwoma w odniesieniu do definicji nr 1, tylko definicja nr 2.
Jörg W Mittag
Ocena nie jest do końca prawdziwa, ponieważ jest tu napisana; Domyślnie środowisko wykonawcze w ogóle nie korzysta z wielowątkowości, a IIRC nawet jeśli włączysz wielowątkowość, nadal musisz powiedzieć środowisku wykonawczemu, jakie rzeczy powinien oceniać równolegle.
Cubic