Wykorzystuje trwałe struktury danych w językach niefunkcjonalnych

Języki, które są czysto funkcjonalne lub prawie wyłącznie funkcjonalne, korzystają z trwałych struktur danych, ponieważ są niezmienne i dobrze pasują do bezpaństwowego stylu programowania funkcjonalnego.

Ale od czasu do czasu widzimy biblioteki trwałych struktur danych dla języków (opartych na stanie, OOP), takich jak Java. Często słyszanym twierdzeniem na rzecz trwałych struktur danych jest to, że ponieważ są niezmienne, są bezpieczne dla wątków .

Jednak powodem, dla którego trwałe struktury danych są bezpieczne dla wątków, jest to, że jeśli jeden wątek „doda” element do trwałej kolekcji, operacja zwraca nową kolekcję, tak jak oryginał, ale z dodanym elementem. Inne wątki zobacz zatem oryginalną kolekcję. Te dwie kolekcje mają oczywiście wiele wewnętrznych stanów - dlatego te trwałe struktury są wydajne.

Ale ponieważ różne wątki zobaczyć różne stany danych, wydaje się, że trwała struktura danych są nie same w sobie wystarczające, aby obsłużyć scenariusze gdzie jeden wątek sprawia, że zmiana, która jest widoczna dla innych wątków. W tym celu wydaje się, że musimy użyć urządzeń takich jak atomy, referencje, pamięć transakcyjna oprogramowania, a nawet klasyczne blokady i mechanizmy synchronizacji.

Dlaczego zatem niezmienność PDS jest reklamowana jako coś korzystnego dla „bezpieczeństwa wątków”? Czy istnieją prawdziwe przykłady, w których PDS pomagają w synchronizacji lub rozwiązywaniu problemów z współbieżnością? Czy też PDS to po prostu sposób na zapewnienie bezstanowego interfejsu do obiektu, który wspiera funkcjonalny styl programowania?

Trwałe / niezmienne struktury danych same nie rozwiązują problemów współbieżności, ale znacznie ułatwiają ich rozwiązywanie.

Rozważ wątek T1, który przekazuje zestaw S do innego wątku T2. Jeśli S jest zmienny, T1 ma problem: traci kontrolę nad tym, co dzieje się z S. Wątek T2 może go modyfikować, więc T1 nie może w ogóle polegać na treści S. I odwrotnie - T2 nie może mieć pewności, że T1 nie modyfikuje S, gdy T2 na nim działa.

Jednym z rozwiązań jest dodanie pewnego rodzaju umowy do komunikacji T1 i T2, aby tylko jeden z wątków mógł modyfikować S. Jest to podatne na błędy i obciąża zarówno projekt, jak i implementację.

Innym rozwiązaniem jest klonowanie struktury danych przez T1 lub T2 (lub oba, jeśli nie są skoordynowane). Jeśli jednak S nie jest trwałe, jest to kosztowna operacja O (n) .

Jeśli masz trwałą strukturę danych, jesteś wolny od tego obciążenia. Możesz przekazać strukturę do innego wątku i nie musisz się przejmować, co ona z tym zrobi. Oba wątki mają dostęp do oryginalnej wersji i mogą wykonywać na niej dowolne operacje - nie ma to wpływu na to, co widzi drugi wątek.

Zobacz także: trwała vs niezmienna struktura danych .

Dlaczego zatem niezmienność PDS jest reklamowana jako coś korzystnego dla „bezpieczeństwa wątków”? Czy istnieją prawdziwe przykłady, w których PDS pomagają w synchronizacji lub rozwiązywaniu problemów z współbieżnością?

Główną zaletą PDS w tym przypadku jest to, że możesz modyfikować część danych bez uczynienia wszystkiego unikalnym (bez głębokiego kopiowania wszystkiego, że tak powiem). Ma to wiele potencjalnych korzyści poza tym, że umożliwia pisanie tanich funkcji wolnych od skutków ubocznych: tworzenie kopii i wklejonych danych, trywialne systemy cofania, trywialne funkcje odtwarzania w grach, trywialna nieniszcząca edycja, trywialne bezpieczeństwo wyjątków itp. Itp.

Można sobie wyobrazić strukturę danych, która byłaby trwała, ale zmienna. Na przykład, możesz wziąć połączoną listę reprezentowaną przez wskaźnik do pierwszego węzła i operację poprzedzającą, która zwróci nową listę, składającą się z nowego węzła głównego i poprzedniej listy. Ponieważ nadal masz odniesienie do poprzedniej głowy, możesz uzyskać dostęp do tej listy i modyfikować ją, która tymczasem została również osadzona na nowej liście. Chociaż jest to możliwe, taki paradygmat nie zapewnia korzyści z trwałych i niezmiennych struktur danych, np. Z pewnością nie jest domyślnie bezpieczny dla wątków. Może jednak mieć zastosowanie, o ile deweloper wie, co robią, np. W zakresie wydajności przestrzeni. Pamiętaj też, że chociaż struktura może być zmienna na poziomie językowym, ponieważ nic nie stoi na przeszkodzie, aby kod ją zmodyfikował,

Tak długa historia, bez niezmienności (narzuconej przez język lub konwencję), trwałość struktur danych traci niektóre ze swoich korzyści (bezpieczeństwo wątków), ale nie inne (wydajność przestrzeni dla niektórych scenariuszy).

Jeśli chodzi o przykłady z języków niefunkcjonalnych, Java String.substring()używa czegoś, co nazwałbym trwałą strukturą danych. Ciąg jest reprezentowany przez tablicę znaków oraz przesunięcia początkowe i końcowe zakresu faktycznie używanej tablicy. Po utworzeniu podłańcucha nowy obiekt ponownie wykorzystuje tę samą tablicę znaków, tylko ze zmodyfikowanymi przesunięciami początkowymi i końcowymi. Ponieważ Stringjest niezmienny, jest (w odniesieniu do substring()operacji, a nie innych) niezmienną trwałą strukturą danych.

Niezmienność struktur danych jest częścią istotną dla bezpieczeństwa wątków. Ich trwałość (ponowne wykorzystanie istniejących fragmentów podczas tworzenia nowej struktury) ma znaczenie dla wydajności podczas pracy z takimi kolekcjami. Ponieważ są one niezmienne, operacja taka jak dodanie elementu nie modyfikuje istniejącej struktury, ale zwraca nową, z dołączonym dodatkowym elementem. Gdyby za każdym razem kopiowano całą strukturę, zaczynając od pustej kolekcji i dodając 1000 elementów jeden po drugim, aby skończyć z kolekcją 1000 elementów, tworzyłby tymczasowe obiekty z 0 + 1 + 2 + ... + 999 = Łącznie 500 000 elementów, co byłoby ogromną stratą. W przypadku trwałych struktur danych można tego uniknąć, ponieważ kolekcja 1-elementowa jest ponownie wykorzystywana w 2-elementowym, który jest ponownie używany w 3-elementowym i tak dalej,

Przyznaję, że jestem stronniczy jako osoba stosująca takie pojęcia w C ++ ze względu na język i jego naturę, a także moją domenę, a nawet sposób, w jaki używamy języka. Ale biorąc pod uwagę te rzeczy, uważam, że niezmienne projekty są najmniej interesującym aspektem, jeśli chodzi o czerpanie większości korzyści związanych z programowaniem funkcjonalnym, takich jak bezpieczeństwo wątków, łatwość wnioskowania o systemie, znajdowanie większego ponownego wykorzystania funkcji (i znalezienie, że możemy łączyć je w dowolnej kolejności bez niemiłych niespodzianek) itp.

Weźmy ten uproszczony przykład C ++ (co prawda nie został zoptymalizowany pod kątem prostoty, aby uniknąć zawstydzenia się przed ekspertami w dziedzinie przetwarzania obrazu):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Podczas gdy implementacja tej funkcji mutuje lokalny (i tymczasowy) stan w postaci dwóch przeciwnych zmiennych i tymczasowego lokalnego obrazu na wyjście, nie ma zewnętrznych skutków ubocznych. Wprowadza obraz i wyprowadza nowy. Możemy wielowątkowość do treści naszych serc. Łatwo jest uzasadnić, łatwo dokładnie przetestować. Jest wyjątkowo bezpieczny, ponieważ jeśli coś zostanie rzucone, nowy obraz zostanie automatycznie odrzucony i nie musimy się martwić o wycofanie zewnętrznych efektów ubocznych (że tak powiem, nie modyfikuje się zewnętrznych obrazów poza zakresem funkcji).

Widzę niewiele do zyskania, a potencjalnie do stracenia, przez uczynienie Imageniezmiennego w powyższym kontekście, w C ++, z wyjątkiem potencjalnie utrudnienia implementacji powyższej funkcji i być może nieco mniej wydajnego.

Czystość

Tak więc czyste funkcje (wolne od zewnętrznych efektów ubocznych) są dla mnie bardzo interesujące i podkreślam znaczenie częstego faworyzowania ich dla członków zespołu, nawet w C ++. Ale niezmienne projekty, stosowane w zasadzie nieobecny kontekst i niuans, nie są dla mnie tak interesujące, ponieważ biorąc pod uwagę nadrzędny charakter języka, często przydatne i praktyczne jest możliwość skutecznego mutowania niektórych lokalnych obiektów tymczasowych w trakcie procesu (oba dla programistów i sprzętu) implementujących czystą funkcję.

Tanie kopiowanie skomplikowanych struktur

Drugą najbardziej użyteczną właściwością, którą znalazłem, jest możliwość taniego kopiowania naprawdę dużych struktur danych, gdy koszt takiego działania, który często musiałby być poniesiony w celu oczyszczenia funkcji ze względu na ich ścisły charakter wejścia / wyjścia, byłby nieistotny. To nie byłyby małe struktury, które mogłyby zmieścić się na stosie. Byłyby to duże, mocne konstrukcje, jak całość Scenedo gry wideo.

W takim przypadku narzut kopiowania może uniemożliwić efektywną równoległość, ponieważ może być trudno zrównoleglić fizykę i efektywnie renderować bez wzajemnego blokowania i wąskiego gardła, jeśli fizyka mutuje scenę, którą renderer próbuje jednocześnie narysować, jednocześnie mając głęboką fizykę kopiowanie całej sceny gry tylko w celu wyświetlenia jednej klatki z zastosowaną fizyką może być równie nieskuteczne. Jeśli jednak system fizyki był „czysty” w tym sensie, że po prostu wprowadził scenę i wyprowadził nowy z zastosowaną fizyką, a taka czystość nie kosztowała astronomicznego kopiowania w górze, mogłaby bezpiecznie działać równolegle z renderer bez jednego oczekiwania na drugim.

Zatem możliwość taniego kopiowania naprawdę dużych danych stanu aplikacji i generowania nowych, zmodyfikowanych wersji przy minimalnym koszcie przetwarzania i wykorzystania pamięci może naprawdę otworzyć nowe drzwi dla czystości i skutecznego równoległości, i tam znajdę wiele lekcji do nauczenia się od sposobu implementacji trwałych struktur danych. Ale wszystko, co stworzymy przy użyciu takich lekcji, nie musi być w pełni trwałe ani oferować niezmiennych interfejsów (może na przykład używać kopiowania przy zapisie lub „konstruktora / przejściowego”), aby osiągnąć tę zdolność do bycia tanią kopiowanie i modyfikowanie tylko części kopii bez podwojenia użycia pamięci i dostępu do pamięci w naszym dążeniu do równoległości i czystości w naszych funkcjach / systemach / potoku.

Niezmienność

Wreszcie istnieje niezmienność, którą uważam za najmniej interesującą z tych trzech, ale może ona wymusić żelazną pięścią, gdy niektóre projekty obiektów nie mają być używane jako lokalne tymczasowe funkcje czyste, a zamiast tego w szerszym kontekście, cenne rodzaj „obiektowej czystości”, ponieważ we wszystkich metodach nie powodują już zewnętrznych skutków ubocznych (nie mutują już zmiennych składowych poza bezpośrednim lokalnym zakresem metody).

I chociaż uważam, że jest to najmniej interesujące z tych trzech języków, takich jak C ++, z pewnością może uprościć testowanie, bezpieczeństwo wątków i rozumowanie nietrywialnych obiektów. Praca z gwarancją, że obiektowi nie można przypisać żadnej unikalnej kombinacji stanów poza jego konstruktorem, może być odciążeniem, i że możemy go swobodnie przekazywać, nawet przez odniesienie / wskaźnik bez oparcia się na stałości i read- tylko iteratory i uchwyty i tym podobne, jednocześnie gwarantując (cóż, przynajmniej tyle, ile możemy w danym języku), że jego oryginalna zawartość nie zostanie zmutowana.

Ale uważam tę najmniej interesującą właściwość, ponieważ większość obiektów, które widzę, są tak samo korzystne, jak tymczasowe, w postaci zmiennej, do implementacji czystej funkcji (lub nawet szerszej koncepcji, takiej jak „czysty system”, który może być przedmiotem lub serią funkcjonuje z ostatecznym efektem po prostu wprowadzania czegoś i przekazywania czegoś nowego bez dotykania czegokolwiek innego, i myślę, że niezmienność zabrana do kończyn w bardzo imperatywnym języku jest raczej nieproduktywnym celem. Stosowałbym go oszczędnie w częściach bazy kodu, w których to naprawdę najbardziej pomaga.

Wreszcie:

[...] wydaje się, że trwałe struktury danych same w sobie nie wystarczają do obsługi scenariuszy, w których jeden wątek wprowadza zmianę widoczną dla innych wątków. W tym celu wydaje się, że musimy użyć urządzeń takich jak atomy, referencje, pamięć transakcyjna oprogramowania, a nawet klasyczne blokady i mechanizmy synchronizacji.

Oczywiście, jeśli twój projekt wymaga modyfikacji (w sensie projektowania użytkownika), aby były widoczne dla wielu wątków jednocześnie, gdy one występują, wracamy do synchronizacji lub przynajmniej tablicy kreślarskiej, aby wypracować kilka wyrafinowanych sposobów radzenia sobie z tym ( Widziałem kilka bardzo skomplikowanych przykładów używanych przez ekspertów zajmujących się tego rodzaju problemami w programowaniu funkcjonalnym).

Ale znalazłem, że gdy już otrzymujesz tego rodzaju kopiowanie i możliwość wypisania częściowo zmodyfikowanych wersji potężnych struktur taniego, tak jak w przypadku trwałych struktur danych jako przykładu, często otwiera to wiele drzwi i możliwości, które możesz nie zastanawiałem się wcześniej nad równoległym kodowaniem, które może działać całkowicie niezależnie od siebie w ścisłym równoległym potoku. Nawet jeśli niektóre części algorytmu muszą mieć charakter szeregowy, możesz odroczyć przetwarzanie do pojedynczego wątku, ale odkryjesz, że oparcie się na tych koncepcjach otworzyło drzwi do łatwego i bez obaw równoległego 90% ciężkiej pracy, np.