Aktywne Wpisy
Francesco123 +1026
#!$%@? czasem juz #!$%@? jak stary boomer ale jak widze młode laski kolo 20 lat i ich beznadziejny styl ubierania to ja jebix xD dobrze ze jak ja bylem mlodym napalonym #!$%@? co myslal tylko o ruchaniu w czasie dojrzewania i byl rok kolo 2012 to byla moda na obcisłe rurki i laski w galerii mialy takie opiete na dupskach te spodnie co ledwo wkladaly. Teraz nastoletnie oskariusze moga sobie spojrzec na
dobry_chlopak +180
(Nie wiem czy jest tu duże zapotrzebowanie na takie dłuższe, mniej typowe wpisy -- sprawdźmy!)
Co nas ratowało, gdy w ciągu dziesiątek lat pisaliśmy coraz bardziej skomplikowane programy, coraz bardziej na odpieprz, coraz mniej przejmując się wydajnością?
Kolesie projektujący hardware. Prawo Moore'a. Liczba tranzystorów na małym czipie rosła wykładniczo, a wraz z nią częstotliwość pracy procesora. Nie musieliśmy robić nic, by ten sam program chodził ze 2x szybciej na sprzęcie o rok-dwa lata nowszym, bo nowy procek w każdej sekundzie wykonywał 2x więcej instrukcji.
Ale kolesie od hardware'u już nie mogą już nas ratować. Są limity częstotliwości. Prędkość światła. Szerokość ścieżek przewodzących. Już teraz mają ile -- kilka atomów? Kilkadziesiąt?
Zegary procesorów praktycznie stanęły w miejscu, ale za to przybywa nam rdzeni. Dzisiaj w maszynach developerskich 4 to normalka, a da się kupić i 8.
Jak dziwnie by to nie brzmiało, wygląda na to, że w przyszłości zaliczymy nie tylko 16 rdzeni, ale i 512, i 1024 i więcej. Dziesiątki tysięcy rdzeni! Podobne rzeczy dzieją się już teraz na rynku kart graficznych.
100 rdzeni. 999 nieużywanych
Czy zwykły kod może zyskać na szybkości gdy odpalimy go na 1000 rdzeniach? Np. taka pętla for:
for (i = 0; i < MILION; i++) {
zrobcos(i);
}
Skoro mamy odpalić zrobcos() milion razy, każdy rdzeń mógłby -- równolegle -- zrobić to po 1000x. I mielibyśmy praktycznie tysiąckrotne przyspieszenie.
Ale skąd mamy wiedzieć, czy wolno nam wywoływać równolegle zrobcos()? A może funkcja ta modyfikuje jakiś stan globalny? Może kolejne jej wywołanie bazuje na poprzednim? Mogłaby przecież dodawać otrzymany parametr do jakiejś listy. Zrównoleglenie wywołań oznaczyłoby praktycznie przypadkową kolejność wykonywania funkcji, a więc zaburzyłoby zawartość listy.
Są też niezliczone inne sposoby, w które nawet ledwie dwa wątki, wywołujące równolegle zrobcos(), psułyby sobie nawzajem sytuację.
W ogólności więc, taka pętla musi się wykonywać szeregowo. Na jednym rdzeniu. Pozostałe 999 może sobie spać.
Aby to naprawić, obecnie stosujemy zwykle jedną technikę.
Ręcznie synchronizowany kod współbieżny
Mówimy maszynie, że ten fragment wydaje nam się bezpieczny i że można go zrównoleglić. Ale na ilu wątkach? Już przy dwóch mogą wystąpić zakleszczenia. Jeden wątek może nadpisać drugiemu współdzielone dane. W kolejności, której nie przewidzieliśmy. W dowolnej instrukcji. W dowolnej kombinacji.
Ręczne żonglowanie trzema czy czterema wątkami jest jeszcze bardziej karkołomne.
Stosujemy więc synchronizację, semafory i inne narzędzia.
Niestety, współbieżne wykonanie jest chaotyczne. Nigdy nie wiadomo, co się dokładnie kiedy wykona i w jakiej kolejności. Trudno więc tu wykryć błąd. Możemy w 100% pokryć test automatycznymi testami. Możemy go wykonać na 10 różnych maszynach po 100x. Bezbłędnie.
W gotowym produkcie, w tysiąc pierwszym odpaleniu, nasz kod się wyłoży. A my nie będziemy w stanie tego odtworzyć.
Dlatego programowanie współbieżne jest tak szalenie trudne. Gdy ktoś nam mówi, że wcale nie -- najprawdopodobniej znaczy to, że sam nawet nie zdaje sobie sprawy z jego trudności.
Takie problemy mamy już przy 2 czy 4 wątkach. A przy 1024? Przy 64k?
Niby jak mamy wykorzystać dziesiątki tysięcy rdzeni, które kolesie od hardware'u dadzą nam za 20 lat, skoro nie ogarniamy zaledwie kilku?
Okazuje się, że jest sposób programowania, które jest z definicji bezpieczne dla wielu wątków. Więcej: dla dowolnej ilości wątków.
Programowanie funkcyjne
Tak, używa się w nim funkcji. Można tworzyć funkcje anonimowe, dostawać funkcje jako argumenty i zwracać funkcje z innych funkcji.
Ale dla współbieżności, kluczowa jest w zasadzie tylko jedna dyscyplina.
Musimy pozbyć się... operatora przypisania.
Tak. Operatora przypisania. Nie można używać "=". No OK, można sobie go użyć by nadać zmiennej wartość początkową, ale potem tej wartości nie można już zmieniać. Więc w sumie mamy nie tyle zmienne, co stałe. Nie można też używać rzeczy takich jak i++, bo to tak naprawdę tyle co i=i+1, a więc znowu operator przypisania.
Miejsca w pamięci mogą zostać zainicjalizowane wartościami, ale te wartości muszą tam potem zostać. Nie mogą się zmienić.
Co nam to da?
To, że nawet jeśli nasz kod będzie wykonywał się na milionie wątków, żaden nie nadpisze danych drugiego. Bo w ogóle żaden nic nie będzie "nadpisywał".
Czy da się tak w ogóle pisać? Dane to dane, ale jak np. pisać głupie pętle bez zmiennych sterujących?
Okazuje się, że się da. I ludzie piszą tak w językach funkcyjnych, takich jak Clojure, OCaml czy Erlang.
Pętle? Kolekcje, które możemy modyfikować?
Tutaj nie używa się pętli. Używa się rekurencji.
Myślisz, że to powolne? Że wywali stos? Nie. Te języki mają optymalizację rekurencji ogonowej. Jeśli napisze się rekurencję poprawnie, interpreter będzie wykonywał nasz kod "w miejscu", bez spamowania niepotrzebnymi ramkami stosu wywołań. Szybkie i bezpieczne.
A co z listami, tablicami, mapami? Często przecież piszemy kod, który dodaje coś do listy.
Tu, w językach czysto funkcyjnych, listy są stałe. O tak: masz funkcje, które wstawiają coś np. na początek listy. Ale to nie tak, że one modyfikują jakąś listę. One zwracają nową listę, z dodatkowym elementem z przodu.
Myślisz, że to powolne i strasznie pamięciożerne? Nie. Te języki optymalizują listy. Kojarzysz listy wiązane, gdzie jeden element ma referencję do następnego? Wyobraź sobie taką listę:
C->B->A
Wyobraź sobie, że dodajesz kolejny element na jej początek:
D->C->B->A
Widzisz jakąś prawidłowość? Tak: stara lista zawiera się w nowej. Nowa lista to po prostu referencja do elementu D, którego referencja następnego elementu wskazuje na element C, a więc na de facto poprzednią listę. Nic nie jest kopiowane. Nic się nie marnuje.
W językach funkcyjnych, funkcje nie mają efektów ubocznych. Załóżmy, że masz funkcję zrobcos(i). Oraz że gdy przekażesz jej parametr 42, to ona zwróci ciąg "foobar". Co zwróci, gdy wywołasz ją drugi raz z takim samym parametrem? Zwróci tę samą wartość: "foobar". To gwarantowane. I po raz trzeci. I po raz tysięczny. I za żadnym razem funkcja nie zrobi niczego innego poza zwróceniem ciągu znaków. Niczego nigdzie indziej nie popsuje.
Nie ma ukrytego stanu. Nie ma efektów ubocznych. Teoretycznie -- a stopniowo coraz praktyczniej -- daje to potężne możliwości.
Nie dzieje się nic ciekawego i mamy akurat 500 wolnych rdzeni?
No to wykorzystajmy je, by odpalić funkcję zrobcos() dla wartości od MILION do DWA_MILIJONY. I żeby zapamiętać wyniki. Na przyszłość. Gdy ktoś o nie poprosi -- już je będziemy mieli.
Ktoś nas poprosił o silnię z 5, a mamy jeszcze 5 wolnych rdzeni? Policzmy silnię do 10, na wszelki wypadek, i zapamiętajmy wyniki na potrzebę przyszłych wywołań.
Wracając do początku...
Co z tą pętlą po milionie elementów listy? Implementujemy ją trochę inaczej. Odpalamy funkcję MAP, której przekazujemy listę miliona liczb ([0..MILION)) i funkcję F, która jest fragmentem kodu, który chcemy wywołać dla każdego elementu listy. Wygląda to jakoś tak:
MAP(F, RANGE(0, 1000000))
Choć w językach funkcyjnych obowiązuje często składnia z LISP-a, w której nie trzeba stawiać przecinków pomiędzy argumentami, a nawiasy otwierające stawia się w złym miejscu (przed nazwą funkcji, a nie po niej):
(MAP F (RANGE 0 1000000))
Funkcja F zostanie wywołana dokładnie raz dla każdego elementu, i dostanie ten element -- tj. liczbę -- za argument. Ponieważ F nie może mieć efektów ubocznych, jedynym sposobem, żebyśmy coś tu w ogóle zrobili, jest zwrócenie wartości przez funkcję F. Funkcja MAP zwróci nową listę o milionie elementów, z czego i-ty element będzie zawierał wartość funkcji F(i).
Co nam to daje? Skoro F nie ma efektów ubocznych, nie trzeba jej nawet wykonywać w dobrej kolejności. Nie ma "dobrej kolejności". F(1) zwróci jakąś wartość X, a F(123) zwróci Y niezależnie od tego, w jakiej kolejności zostaną wykonane.
Środowisko wykonawcze może więc ją odpalać równolegle na 1000 rdzeniach. Czyli dla 1000 elementów naraz. A jak nam dołożą drugi tysiąc rdzeni, to dla 2000.
Programista już się o to nie musi martwić.
Musiał się tylko martwić o to, jak u licha napisać kod bez instrukcji przypisania.
Parę osób pytało mnie tu o kwestie poruszone w tym poście, ale zapamiętałem tylko tego, co zrobił to ostatnio. @ufik78 -- wołam.
Czekam na więcej!
niby jakie problemy? jeżeli jakiś pomysł zadziała w języku funkcyjnym,
całość tego wpisu sprowadza się do napisania kodu funkcji, która może zostać uruchomiona współbieżnie, dzięki temu, że nie zmienia żadnego stanu globalnego. czy nie prościej byłoby napisać tą samą funkcje w jakimś "normalnym" języku, a potem wywołać ją w parallel loop? po co się męczyć z tym programowaniem funkcyjnym? czy chodzi może o to, że w językach funkcyjnych trudniej jest coś #!$%@?ć?
Poza tym nie trzeba korzystać z ręcznej synchronizacji - są frameworki/biblioteki/rozszerzenia do języków które umożliwiają dość wygodne i bezpieczne pisanie skalowalnych programów.
@ly000: są problemy które wygodniej jest przedstawić funkcyjnie - z mojego doświadczenia programiści z matematycznym wykształceniem (nie wiem jak dobrze przetłumaczyć "background") częściej preferują podejście funkcyjne.
@ly000:
Nie, to w praktyce nieprawda, że "wszyscy wiedzą" jak pisać kod współbieżny. Możliwe, że niby wiedzą, ale... nie potrafią. Porada: "uważaj na stan globalny!" w praktyce nie wystarczy, gdy niemal każdy kod może modyfikować stan globalny.
Parallel for czy map w językach z normalną wielowątkowością (jak Java) nie wystarczą. Nawet jeśli wykonywany współbieżnie fragment kodu to ledwie parę linijek, te linijki zwykle polegają na wykonywaniu metod innych obiektów.
Komentarz usunięty przez autora
Przewidywanie przyszłości to wróżenie z fusów. Podałem tutaj jedną z możliwych ścieżek, wg mnie relatywnie prawdopodobną. Ale historia uczy, że zwykle wszelkie przewidywania są błędne.
Co do "trudności" i "nieintuicyjności" programowania funkcyjnego, to ciężko powiedzieć. Na jakiej podstawie to oceniasz? Czego uczyłeś się od początku? Nie przypadkiem programowania strukturalnego czy proceduralnego? Niemal wszyscy się tego uczą i wszyscy tego uczą. Dużo mniej osób uczy się (i naucza) FP.
Jak więc
Komentarz usunięty przez autora