**Głupi programiści, prawo Moore'a, prędkość światła, 1024 rdzenie i t... (@Sh1eldeR)

Głupi programiści, prawo Moore'a, prędkość światła, 1024 rdzenie i to cholerne #programowanie funkcyjne
(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.

@Sh1eldeR: problem polega na tym, że programowanie funkcyjne jest cholernie niewygodne. Nie bez powodu jest obecnie dość niszowe, choć może się to - do pewnego stopnia - zmienić.

Z początku programowanie wielowątkowe wydaje się bardzo trudne, ale w praktyce przy odrobinie wprawy nie jest aż tak skomplikowane. Istnieją też debuggery które pozwalają sprawdzić *wszystkie* możliwości przeplotu, czy są zachowane dane z wpisanych niezmienników i czy nie ma zakleszczenia procesów, bądź ich zagłodzenia. Istnieją też systemy teoretyczne które pomagają w synchronizacji wątków - chociażby sieci petriego.

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ę

s.....s

konto usunięte 11.10.2015, 16:14:28

@Sh1eldeR: na razie to idzie raczej w kierunku dorzucania elementów funkcyjnych do innych języków. I to jest rozsądny kompromis, używasz tego co pasuje.

zajety_login

11.10.2015, 16:14:53

@lukasz1985m: Czepianie się słów (swoją drogą powszechnie przyjętych i dobrze rozumianych) nie zmienia faktu, że Twoje porównanie sugeruje, że nie do końca rozumiesz jaki jest związek między paradygmatem funkcyjnym, a innymi paradygmatami.

l.....m

konto usunięte 11.10.2015, 16:16:12

Komentarz usunięty przez autora

konto usunięte 11.10.2015, 16:16:54

11.10.2015, 16:18:32

@lukasz1985m: Słowa "ortogonalne"?

konto usunięte 11.10.2015, 16:20:54

11.10.2015, 16:26:36

@lukasz1985m: To już Twój problem że znasz tylko jedno znaczenie pojęcia "ortogonalny". Żeby nie zaśmiecać tej dyskusji kompletnymi pierdołami, w moim wcześniejszym zdaniu zamień sobie "paradygmat funkcyjny jest ortogonalny względem paradygmatu obiektowego" na "paradygmat funkcyjny jest całkowicie niezależny od paradygmatu obiektowego". Będzie łatwiej.