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.
ConcurrentModificationExceptionktóra jest zwykle spowodowana przez ten sam wątek mutujący kolekcję w tym samym wątku, w cieleforeachpętli nad tą samą kolekcją.