Czy niezmienność jest bardzo opłacalna, gdy nie ma współbieżności?

Wydaje się, że bezpieczeństwo wątków jest zawsze / często wymieniane jako główna zaleta korzystania z niezmiennych typów, a zwłaszcza kolekcji.

Mam sytuację, w której chciałbym się upewnić, że metoda nie zmodyfikuje słownika ciągów (które są niezmienne w języku C #). Chciałbym ograniczyć rzeczy tak bardzo, jak to możliwe.

Nie jestem jednak pewien, czy warto dodać zależność do nowego pakietu (Microsoft Immutable Collections). Wydajność też nie jest dużym problemem.

Wydaje mi się, że moje pytanie brzmi, czy zdecydowanie zaleca się niezmienne kolekcje, gdy nie ma twardych wymagań wydajnościowych i nie ma problemów z bezpieczeństwem wątków? Rozważ, że semantyka wartości (jak w moim przykładzie) może, ale nie musi być również wymogiem.

Niezmienność upraszcza ilość informacji potrzebnych do mentalnego śledzenia podczas późniejszego czytania kodu . W przypadku zmiennych zmiennych, a zwłaszcza zmiennych członków klasy, bardzo trudno jest ustalić, w jakim stanie będą w określonej linii, o której czytasz, bez uruchamiania kodu za pomocą debugera. Niezmienne dane są łatwe do uzasadnienia - zawsze będą takie same. Jeśli chcesz to zmienić, musisz wprowadzić nową wartość.

Wolałbym domyślnie uczynić rzeczy niezmiennymi domyślnie , a następnie zmienić je na zmienne tam, gdzie udowodniono, że muszą być, niezależnie od tego, czy oznacza to, że potrzebujesz wydajności, czy algorytm, który masz, nie ma sensu dla niezmienności.

Twój kod powinien wyrażać twoją intencję. Jeśli nie chcesz, aby obiekt był modyfikowany po utworzeniu, uniemożliwić modyfikację.

Niezmienność ma kilka zalet:

• Intencja oryginalnego autora jest wyrażona lepiej.

  Skąd możesz wiedzieć, że w poniższym kodzie modyfikacja nazwy spowodowałaby, że aplikacja wygeneruje wyjątek gdzieś później?

  public class Product
  {
      public string Name { get; set; }
  
      ...
  }
  

• Łatwiej jest upewnić się, że obiekt nie pojawi się w nieprawidłowym stanie.

  Musisz to kontrolować w konstruktorze i tylko tam. Z drugiej strony, jeśli masz kilka ustawień i metod modyfikujących obiekt, takie kontrole mogą stać się szczególnie trudne, szczególnie gdy, na przykład, dwa pola powinny się zmieniać jednocześnie, aby obiekt był ważny.

  Na przykład obiekt jest poprawny, jeśli adres nie jest null lub współrzędne GPS nie null, ale jest nieważny, jeśli podano zarówno adres, jak i współrzędne GPS. Czy możesz sobie wyobrazić, do diabła, by to sprawdzić, jeśli zarówno adres, jak i współrzędne GPS mają ustawiacz lub oba są zmienne?

• Konkurencja.

Nawiasem mówiąc, w twoim przypadku nie potrzebujesz żadnych pakietów stron trzecich. .NET Framework już zawiera ReadOnlyDictionary<TKey, TValue>klasę.

Istnieje wiele jednowątkowych powodów, dla których warto zastosować niezmienność. Na przykład

Obiekt A zawiera obiekt B.

Kod zewnętrzny wysyła zapytanie do obiektu B i zwraca go.

Teraz masz trzy możliwe sytuacje:

1. B jest niezmienny, nie ma problemu.
2. B jest zmienny, wykonujesz kopię obronną i oddajesz ją. Uderzenie wydajności, ale bez ryzyka.
3. B jest zmienny, zwracasz go.

W trzecim przypadku kod użytkownika może nie zdawać sobie sprawy z tego, co zrobiłeś, i może wprowadzać zmiany w obiekcie, zmieniając w ten sposób wewnętrzne dane obiektu, nie mając kontroli ani widoczności tego zdarzenia.

Niezmienność może również znacznie uprościć implementację śmieciarek. Z wiki GHC :

[...] Niezmienność danych zmusza nas do wygenerowania wielu danych tymczasowych, ale pomaga też szybko zbierać te śmieci. Sztuka polega na tym, że niezmienne dane NIGDY nie wskazują na młodsze wartości. Rzeczywiście, młodsze wartości nie istnieją jeszcze w momencie tworzenia starej wartości, więc nie można jej wskazać od zera. A ponieważ wartości nigdy nie są modyfikowane, nie można na nie wskazać później. Jest to kluczowa właściwość niezmiennych danych.

To znacznie upraszcza zbieranie śmieci (GC). W dowolnym momencie możemy skanować ostatnio utworzone wartości i uwolnić te, na które nie wskazuje się z tego samego zestawu (oczywiście prawdziwe stosy hierarchii wartości rzeczywistych znajdują się na stosie). [...] Ma więc działanie sprzeczne z intuicją: większy procent twoich wartości to śmieci - im szybciej to działa. [...]

Rozwijając to, co KChaloux podsumował bardzo dobrze ...

Najlepiej, jeśli masz dwa typy pól, a zatem dwa typy kodu, które je wykorzystują. Oba pola są niezmienne, a kod nie musi uwzględniać zmienności; lub pola są zmienne i musimy napisać kod, który albo wykonuje migawkę ( int x = p.x), albo z wdziękiem obsługuje takie zmiany.

Z mojego doświadczenia wynika, że większość kodów mieści się pomiędzy nimi, będąc kodem optymistycznym : swobodnie odwołuje się do zmiennych danych, zakładając, że pierwsze wywołanie do p.xbędzie miało taki sam wynik jak drugie wywołanie. I przez większość czasu jest to prawda, z wyjątkiem sytuacji, gdy okazuje się, że już nie jest. Ups

Tak więc, naprawdę, odwróć to pytanie: jakie są moje powody, dla których można to zmienić ?

• Ograniczenie przydziału pamięci / zwolnienia?
• Zmienny z natury? (np. licznik)
• Zapisuje modyfikatory, szum poziomy? (const / final)
• Czy kod jest krótszy / łatwiejszy? (domyślna inicjacja, możliwe zastąpienie po)

Czy piszesz kod obronny? Niezmienność zaoszczędzi ci kopiowania. Czy piszesz optymistyczny kod? Niezmienność oszczędza ci szaleństwa tego dziwnego, niemożliwego robaka.

Kolejną zaletą niezmienności jest to, że jest to pierwszy krok w zaokrąglaniu tych niezmiennych obiektów do puli. Następnie możesz nimi zarządzać, aby nie tworzyć wielu obiektów, które koncepcyjnie i semantycznie reprezentują to samo. Dobrym przykładem może być napis Java.

Jest to dobrze znane zjawisko w językoznawstwie polegające na tym, że kilka słów pojawia się często, a także w innym kontekście. Zamiast tworzyć wiele Stringobiektów, możesz użyć jednego niezmiennego. Ale musisz utrzymać menedżera puli, aby zajął się tymi niezmiennymi obiektami.

Pozwoli ci to zaoszczędzić dużo pamięci. Jest to również ciekawy artykuł do przeczytania: http://en.wikipedia.org/wiki/Zipf%27s_law

W Javie, C # i innych podobnych językach pola typu klasy mogą być używane albo do identyfikacji obiektów, albo do enkapsulacji wartości lub stanu w tych obiektach, ale języki nie rozróżniają takich zastosowań. Załóżmy, że obiekt klasy Georgema pole typu char[] chars;. To pole może zawierać sekwencję znaków w:

1. Tablica, która nigdy nie będzie modyfikowana ani narażona na żaden kod, który mógłby ją zmodyfikować, ale do której mogą istnieć odwołania zewnętrzne.

2. Tablica, do której nie istnieją żadne odniesienia zewnętrzne, ale którą George może dowolnie modyfikować.

3. Tablica należąca do George'a, ale do której mogą istnieć widoki zewnętrzne, które mogłyby reprezentować obecny stan George'a.

Dodatkowo zmienna może zamiast enkapsulować sekwencję znaków, enkapsulować podgląd na żywo do sekwencji znaków należących do jakiegoś innego obiektu

Jeśli charsobecnie enkapsuluje sekwencję znaków [wiatr], a George chce charsenkapsulować sekwencję znaków [różdżka], George może zrobić wiele rzeczy:

A. Skonstruuj nową tablicę zawierającą znaki [różdżkę] i zmień ją, charsaby zidentyfikować tę tablicę zamiast starej.

B. Zidentyfikuj istniejącą tablicę znaków, która zawsze będzie zawierać znaki [różdżka] i zmień ją, charsaby zidentyfikować tę tablicę zamiast starej.

C. Zmień drugi znak tablicy identyfikowanej przez charsna a.

W przypadku 1, (A) i (B) są bezpiecznymi sposobami na osiągnięcie pożądanego rezultatu. W przypadku, gdy (2), (A) i (C) są bezpieczne, ale (B) nie byłoby [nie spowodowałoby to bezpośrednich problemów, ale skoro George założyłby, że ma własność tablicy, to założyłby, że może zmienić tablicę do woli]. W przypadku (3) wybory (A) i (B) złamałyby wszelkie widoki zewnętrzne, a zatem tylko wybór (C) jest poprawny. Zatem wiedza o tym, jak zmodyfikować sekwencję znaków enkapsulowaną przez pole, wymaga wiedzy, jaki to typ pola semantycznego.

Jeśli zamiast używać pola typu char[], które zawiera potencjalnie zmienną sekwencję znaków, kod użył typu String, który zawiera niezmienną sekwencję znaków, wszystkie powyższe problemy znikają. Wszystkie pola typu Stringzawierają sekwencję znaków przy użyciu obiektu współdzielonego, który nigdy się nie zmieni. W związku z tym, jeśli pole typuStringenkapsuluje „wiatr”, jedynym sposobem, aby enkapsulować „różdżkę” jest zidentyfikowanie innego obiektu - takiego, który trzyma „różdżkę”. W przypadkach, w których kod zawiera jedyne odniesienie do obiektu, mutowanie obiektu może być bardziej wydajne niż tworzenie nowego, ale za każdym razem, gdy klasa jest modyfikowalna, konieczne jest rozróżnienie różnych sposobów, w jakie może hermetyzować wartość. Osobiście uważam, że do tego celu należało użyć Apps Hungarian (rozważałbym cztery zastosowania char[]semantycznie odrębnych typów, nawet jeśli system typów uważa je za identyczne - dokładnie taka sytuacja, w której Apps Hungarian błyszczy), ale ponieważ nie był najłatwiejszym sposobem uniknięcia takich dwuznaczności jest zaprojektowanie niezmiennych typów, które ujmują wartości tylko w jeden sposób.

Jest tu kilka dobrych przykładów, ale chciałem wskoczyć w te osobiste, w których niezmienność pomogła tonie. W moim przypadku zacząłem projektować niezmienną współbieżną strukturę danych, głównie z nadzieją, że będę w stanie pewnie uruchomić kod równolegle z nakładającymi się odczytami i zapisami i nie martwić się warunkami wyścigu. Była rozmowa, którą John Carmack zainspirował mnie do zrobienia tego, gdy mówił o takim pomyśle. Jest to dość podstawowa struktura i dość trywialna w implementacji:

Oczywiście z kilkoma dodatkowymi dzwonkami i gwizdkami, jak na przykład możliwość ciągłego usuwania elementów i pozostawiania dających się odzyskać dziur, a bloki zostają wyrejestrowane, jeśli staną się puste i potencjalnie uwolnione dla danej niezmiennej instancji. Ale w zasadzie, aby zmodyfikować strukturę, modyfikujesz „przejściową” wersję i atomowo zatwierdzasz wprowadzone w niej zmiany, aby uzyskać nową niezmienną kopię, która nie dotyka starej, a nowa wersja tworzy tylko nowe kopie bloków, które muszą być wyjątkowe, a płytkie kopiowanie i odliczanie innych.

Jednak nie znalazłem tegoprzydatne do celów wielowątkowości. W końcu nadal istnieje problem koncepcyjny, w którym powiedzmy, system fizyki stosuje fizykę jednocześnie, gdy gracz próbuje przenosić elementy w świecie. Z którą niezmienną kopią przetworzonych danych korzystasz, tą, którą przekształcił gracz lub tą, którą przekształcił system fizyki? Tak naprawdę nie znalazłem dobrego i prostego rozwiązania tego podstawowego problemu pojęciowego, oprócz modyfikowalnych struktur danych, które blokują się w bardziej inteligentny sposób i zniechęcają do nakładających się odczytów i zapisów w tych samych sekcjach bufora, aby uniknąć blokowania wątków. To jest coś, co John Carmack prawdopodobnie wymyślił, jak rozwiązać w swoich grach; przynajmniej mówi o tym, jakby prawie widział rozwiązanie bez otwierania samochodu robaków. W tym zakresie nie dotarłem tak daleko jak on. Wszystko, co widzę, to niekończące się pytania projektowe, gdybym próbował po prostu zrównoważyć wszystko wokół niezmiennych. Żałuję, że nie mogłem spędzić dnia na analizowaniu jego mózgu, ponieważ większość moich wysiłków rozpoczęła się od pomysłów, które on wyrzucił.

Niemniej jednak odkryłem ogromną wartość tej niezmiennej struktury danych w innych obszarach. Używam go nawet teraz do przechowywania obrazów, które są naprawdę dziwne i sprawiają, że dostęp losowy wymaga dodatkowych instrukcji (przesunięcie w prawo i nieco andwraz z warstwą pośredniej wskazówki), ale omówię poniższe korzyści.

Cofnij system

Jednym z najbardziej bezpośrednich miejsc, w których skorzystałem z tego, był system cofania. Kod systemu cofania był kiedyś jedną z najbardziej podatnych na błędy rzeczy w moim obszarze (branża efektów wizualnych), i to nie tylko w produktach, nad którymi pracowałem, ale w produktach konkurencyjnych (ich systemy cofania również były wadliwe), ponieważ było tak wiele różnych rodzaje danych, które należy martwić o prawidłowe cofanie i ponawianie (system właściwości, zmiany danych siatki, zmiany modułu cieniującego, które nie były oparte na właściwościach, takie jak zamiana jednego z drugim, zmiany hierarchii scen, takie jak zmiana elementu nadrzędnego dziecka, zmiany obrazu / tekstury, itp. itd.).

Wymagana ilość kodu cofania była więc ogromna, często rywalizując z ilością kodu implementującego system, dla którego system cofania musiał rejestrować zmiany stanu. Opierając się na tej strukturze danych, udało mi się sprowadzić system cofania tylko do tego:

on user operation:
    copy entire application state to undo entry
    perform operation

on undo/redo:
    swap application state with undo entry

Zwykle powyższy kod byłby niezwykle nieefektywny, gdy dane sceny obejmują gigabajty, aby skopiować go w całości. Ale ta struktura danych tylko płytko kopiuje rzeczy, które nie zostały zmienione, i faktycznie sprawiła, że ​​wystarczająco tanio przechowuje niezmienną kopię całego stanu aplikacji. Teraz mogę zaimplementować systemy cofania tak łatwo, jak powyższy kod i skupić się na użyciu tej niezmiennej struktury danych, aby kopiowanie niezmienionych części stanu aplikacji było tańsze, tańsze i tańsze. Odkąd zacząłem używać tej struktury danych, wszystkie moje osobiste projekty mają cofnięte systemy tylko przy użyciu tego prostego wzorca.

Teraz jest tu jeszcze trochę kosztów ogólnych. Ostatnim razem, gdy mierzyłem, było to około 10 kilobajtów, aby po prostu płytko skopiować cały stan aplikacji bez dokonywania żadnych zmian (jest to niezależne od złożoności sceny, ponieważ scena jest ułożona w hierarchię, więc jeśli nic nie zmienia się poniżej katalogu głównego, tylko katalog główny jest płytko kopiowane bez konieczności schodzenia w dół do dzieci). Jest to dalekie od 0 bajtów, co byłoby potrzebne w przypadku systemu cofania przechowującego tylko delty. Ale przy 10 kilobajtach narzutu cofania na operację to wciąż tylko megabajt na 100 operacji użytkownika. Co więcej, w razie potrzeby nadal mogę potencjalnie zmiażdżyć tę sytuację w przyszłości.

Wyjątek - bezpieczeństwo

Wyjątkowe bezpieczeństwo przy złożonej aplikacji nie jest banalną sprawą. Jeśli jednak stan aplikacji jest niezmienny i używasz tylko obiektów przejściowych do próby dokonania transakcji zmiany atomowej, to jest to z natury bezpieczne dla wyjątków, ponieważ jeśli jakakolwiek część kodu zostanie wyrzucona, stan przejściowy jest odrzucany przed przekazaniem nowej niezmiennej kopii . To trywializuje jedną z najtrudniejszych rzeczy, które zawsze znajdowałem w złożonej bazie kodu C ++.

Zbyt wiele osób często korzysta tylko z zasobów zgodnych z RAII w C ++ i uważa, że ​​to wystarczy, aby być bezpiecznym dla wyjątków. Często tak nie jest, ponieważ funkcja może generalnie powodować działania niepożądane w stanach wykraczających poza te lokalne. W takich przypadkach zazwyczaj musisz zacząć zajmować się osłonami zakresu i wyrafinowaną logiką cofania. Ta struktura danych sprawiła, że ​​tak często nie muszę się tym przejmować, ponieważ funkcje nie powodują efektów ubocznych. Zwracają przekształcone niezmienne kopie stanu aplikacji zamiast przekształcać stan aplikacji.

Edycja nieniszcząca

Nieniszcząca edycja polega zasadniczo na nakładaniu warstw / układaniu w stosy / łączeniu operacji bez dotykania danych pierwotnego użytkownika (tylko dane wejściowe i wyjściowe bez dotykania danych wejściowych). Zazwyczaj jest to trywialne za pomocą prostej aplikacji graficznej, takiej jak Photoshop, i może nie korzystać z takiej struktury danych, ponieważ wiele operacji może chcieć przekształcić każdy piksel całego obrazu.

Jednak na przykład przy nieniszczącej edycji siatki wiele operacji często chce przekształcić tylko część siatki. Jedna operacja może po prostu chcieć przenieść tutaj niektóre wierzchołki. Inny może po prostu podzielić tam kilka wielokątów. Niezmienna struktura danych pomaga tonowi uniknąć potrzeby tworzenia całej kopii całej siatki tylko po to, aby zwrócić nową wersję siatki ze zmienioną niewielką jej częścią.

Minimalizowanie efektów ubocznych

Dzięki tym strukturom ułatwia także pisanie funkcji, które minimalizują skutki uboczne bez ponoszenia za to ogromnej straty wydajności. Odkryłem, że piszę coraz więcej funkcji, które zwracają obecnie całe niezmienne struktury danych według wartości bez wywoływania skutków ubocznych, nawet jeśli wydaje się to trochę marnotrawstwem.

Na przykład, pokusa, aby przekształcić kilka pozycji, może polegać na zaakceptowaniu macierzy i listy obiektów i przekształceniu ich w sposób zmienny. Obecnie zwracam właśnie nową listę obiektów.

Kiedy masz więcej takich funkcji w swoim systemie, które nie powodują żadnych skutków ubocznych, zdecydowanie łatwiej jest wnioskować o jego poprawności, a także przetestować jej poprawność.

Korzyści z tanich kopii

W każdym razie są to obszary, w których najbardziej wykorzystałem niezmienne struktury danych (lub trwałe struktury danych). Na początku też byłem trochę nadgorliwy i stworzyłem niezmienne drzewo i niezmienną listę powiązań i niezmienną tabelę skrótów, ale z czasem rzadko znajdowałem dla nich takie zastosowanie. Największe wykorzystanie tego masywnego niezmiennego podobnego do tablicy pojemnika znalazłem głównie na powyższym schemacie.

Wciąż mam dużo kodu do pracy ze zmiennymi (uważam, że jest to praktyczną koniecznością przynajmniej dla kodu niskiego poziomu), ale głównym stanem aplikacji jest niezmienna hierarchia, przechodząca od niezmiennej sceny do niezmiennych składników w niej zawartych. Niektóre tańsze komponenty są nadal kopiowane w całości, ale najdroższe, takie jak siatki i obrazy, wykorzystują niezmienną strukturę, aby umożliwić te częściowe tanie kopie tylko części, które musiały zostać przekształcone.

Jest już wiele dobrych odpowiedzi. To tylko dodatkowe informacje nieco specyficzne dla .NET. Przeglądałem stare posty na blogu .NET i znalazłem niezłe podsumowanie korzyści z punktu widzenia programistów Microsoft Immutable Collections:

1. Semantyka migawki, umożliwiająca udostępnianie kolekcji w taki sposób, że odbiorca może liczyć na to, że nigdy się nie zmieni.

2. Domniemane bezpieczeństwo wątków w aplikacjach wielowątkowych (nie wymaga żadnych blokad, aby uzyskać dostęp do kolekcji).

3. Za każdym razem, gdy masz członka klasy, który akceptuje lub zwraca typ kolekcji i chcesz zawrzeć w umowie semantykę tylko do odczytu.

4. Przyjazne programowanie funkcjonalne.

5. Zezwalaj na modyfikację kolekcji podczas wyliczania, jednocześnie upewniając się, że oryginalna kolekcja się nie zmienia.

6. Implementują te same interfejsy IReadOnly *, z którymi Twój kod już się zajmuje, więc migracja jest łatwa.

Jeśli ktoś przekaże Ci ReadOnlyCollection, IReadOnlyList lub IEnumerable, jedyną gwarancją jest to, że nie możesz zmienić danych - nie ma gwarancji, że osoba, która przekazała Ci kolekcję, nie zmieni tego. Często jednak potrzebujesz pewności, że to się nie zmieni. Te typy nie oferują zdarzeń powiadamiających Cię o zmianie ich zawartości, a jeśli się zmieniają, czy mogą one wystąpić w innym wątku, być może podczas wyliczania jego zawartości? Takie zachowanie prowadziłoby do uszkodzenia danych i / lub przypadkowych wyjątków w Twojej aplikacji.