Czy niezmienność szkodzi wydajności w JavaScript?

Wydaje się, że w JavaScript jest ostatnio tendencja do traktowania struktur danych jako niezmiennych. Na przykład, jeśli chcesz zmienić pojedynczą właściwość obiektu, lepiej po prostu utwórz nowy obiekt za pomocą nowej właściwości i po prostu skopiuj wszystkie inne właściwości ze starego obiektu i pozwól, aby stary obiekt został wyrzucony. (I tak to rozumiem.)

Moja początkowa reakcja jest taka, że ​​brzmi to źle dla wydajności.

Ale wtedy biblioteki jak Immutable.js i Redux.js są pisane przez ludzi mądrzejszych ode mnie, i wydają się mieć silną troskę o wydajność, więc to sprawia, że zastanawiam się, czy moje rozumienie śmieci (i jego wpływ na wydajność) jest błędna.

Czy brakuje mi niezmienności dla wydajności i czy przewyższają wady tworzenia tak dużej ilości śmieci?

Na przykład, jeśli chcesz zmienić pojedynczą właściwość obiektu, lepiej po prostu utwórz nowy obiekt za pomocą nowej właściwości i po prostu skopiuj wszystkie inne właściwości ze starego obiektu i pozwól, aby stary obiekt został wyrzucony.

Bez niezmienności może być konieczne przekazanie obiektu między różnymi zakresami i nie wiadomo wcześniej, czy i kiedy obiekt zostanie zmieniony. Aby uniknąć niepożądanych efektów ubocznych, zaczynasz tworzyć pełną kopię obiektu „na wszelki wypadek” i przekazywać tę kopię, nawet jeśli okaże się, że żadna właściwość nie musi być w ogóle zmieniana. To pozostawi o wiele więcej śmieci niż w twoim przypadku.

To pokazuje - jeśli stworzysz odpowiedni hipotetyczny scenariusz, możesz udowodnić wszystko, szczególnie jeśli chodzi o wydajność. Mój przykład nie jest jednak tak hipotetyczny, jak mogłoby się wydawać. W zeszłym miesiącu pracowałem nad programem, w którym natknęliśmy się na dokładnie ten problem, ponieważ początkowo zdecydowaliśmy się nie używać niezmiennej struktury danych, i zawahałem się, aby później to zmienić, ponieważ nie wydawało się to kłopotliwe.

Więc kiedy spojrzysz na takie przypadki ze starszego posta SO , odpowiedź na twoje pytania stanie się prawdopodobnie jasna - to zależy . W niektórych przypadkach niezmienność zaszkodzi wydajności, w innych może być odwrotnie, w wielu przypadkach będzie to zależeć od tego, jak inteligentna jest twoja implementacja, aw jeszcze większej liczbie przypadków różnica będzie nieistotna.

Ostatnia uwaga: prawdziwym problemem, z którym możesz się spotkać, jest wczesne podjęcie decyzji o niezmienności niektórych podstawowych struktur danych. Następnie zbudujesz na tym wiele kodu, a kilka tygodni lub miesięcy później zobaczysz, czy decyzja była dobra, czy zła.

Moją osobistą zasadą w tej sytuacji jest:

• Jeśli projektujesz strukturę danych z tylko kilkoma atrybutami opartymi na prymitywnych lub innych niezmiennych typach, najpierw spróbuj niezmienność.
• Jeśli chcesz zaprojektować typ danych, w którym zaangażowane są tablice o dużym (lub nieokreślonym) rozmiarze, dostęp losowy i zmieniająca się zawartość, użyj zmienności.

W sytuacjach między tymi dwoma skrajnościami, użyj własnego osądu. Ale YMMV.

Po pierwsze, twoja charakterystyka niezmiennych struktur danych jest nieprecyzyjna. Zasadniczo większość struktur danych nie jest kopiowana, ale współdzielona , a kopiowane są tylko zmienione części. Nazywa się to trwałą strukturą danych . Większość implementacji jest w stanie przez większość czasu korzystać z trwałych struktur danych. Wydajność jest wystarczająco bliska zmiennym strukturom danych, które programiści funkcjonalni ogólnie uważają za nieistotny.

Po drugie, uważam, że wiele osób ma dość niedokładne wyobrażenie o typowym życiu obiektów w typowych programach imperatywnych. Być może wynika to z popularności języków zarządzanych przez pamięć. Usiądź kiedyś i naprawdę sprawdź, ile utworzysz obiektów tymczasowych i kopii obronnych w porównaniu do naprawdę długowiecznych struktur danych. Myślę, że będziesz zaskoczony tym współczynnikiem.

Miałem uwagę ludzi na zajęciach programowania funkcjonalnego, uczę o tym, ile śmieci tworzy algorytm, a następnie pokazuję typową imperatywną wersję tego samego algorytmu, który tworzy tyle samo. Z jakiegoś powodu ludzie już tego nie zauważają.

Zachęcając do udostępniania i zniechęcając do tworzenia zmiennych, dopóki nie uzyska się prawidłowej wartości do ich wprowadzenia, niezmienność zwykle zachęca do czystszych praktyk kodowania i dłuższych struktur danych. To często prowadzi do porównywalnych, jeśli nie niższych poziomów śmieci, w zależności od algorytmu.

Późno przyszedł do tego pytania i odpowiedzi z już świetnymi odpowiedziami, ale chciałem się wtrącić jako obcokrajowiec przyzwyczajony do patrzenia na rzeczy z niższego poziomu bitów i bajtów w pamięci.

Jestem bardzo podekscytowany niezmiennymi projektami, nawet pochodzącymi z perspektywy C oraz z perspektywy znalezienia nowych sposobów skutecznego programowania tego bestialskiego sprzętu, jaki mamy obecnie.

Wolniej / szybciej

Jeśli chodzi o pytanie, czy to spowalnia sytuację, odpowiedzią byłaby robot yes. Na tym bardzo technicznym poziomie koncepcyjnym niezmienność może tylko spowolnić sytuację. Sprzęt działa najlepiej, gdy nie sporadycznie przydziela pamięć i może po prostu zmodyfikować istniejącą pamięć (dlaczego mamy takie pojęcia, jak lokalizacja czasowa).

Jednak praktyczna odpowiedź brzmi maybe. Wydajność nadal jest w dużej mierze wskaźnikiem wydajności w każdej nietrywialnej bazie kodu. Zazwyczaj okropne w utrzymaniu bazy kodów potykające się o warunki wyścigowe nie są najbardziej wydajne, nawet jeśli pomijamy błędy. Wydajność jest często funkcją elegancji i prostoty. Szczyt mikrooptymalizacji może nieco konfliktować, ale zwykle są one zarezerwowane dla najmniejszych i najbardziej krytycznych sekcji kodu.

Przekształcanie niezmiennych bitów i bajtów

Z punktu widzenia niskiego poziomu, jeśli prześwietlamy koncepcje rentgenowskie takie jak objectsi stringstak dalej, w centrum tego są tylko bity i bajty w różnych formach pamięci o różnych charakterystykach prędkości / rozmiaru (szybkość i rozmiar pamięci zwykle są wzajemnie się wykluczające).

Hierarchia pamięci komputera podoba się, gdy wielokrotnie uzyskujemy dostęp do tego samego fragmentu pamięci, jak na powyższym schemacie, ponieważ utrzyma ten często używany fragment pamięci w najszybszej formie pamięci (pamięć podręczna L1, np. jest prawie tak szybki jak rejestr). Możemy wielokrotnie uzyskiwać dostęp do dokładnie tej samej pamięci (wielokrotnie ją wykorzystywać) lub wielokrotnie uzyskiwać dostęp do różnych sekcji fragmentu (np. Zapętlanie elementów w ciągłym fragmencie, który wielokrotnie uzyskuje dostęp do różnych części tego fragmentu pamięci).

W rezultacie rzucamy kluczem w tym procesie, jeśli modyfikacja tej pamięci kończy się na chęci utworzenia z boku zupełnie nowego bloku pamięci, w ten sposób:

... w tym przypadku dostęp do nowego bloku pamięci może wymagać obowiązkowych błędów strony i braków pamięci podręcznej, aby przenieść ją z powrotem do najszybszych form pamięci (aż do rejestru). To może być prawdziwy zabójca wydajności.

Istnieją jednak sposoby na złagodzenie tego, używając już zarezerwowanej puli wstępnie przydzielonej pamięci.

Duże kruszywa

Innym zagadnieniem koncepcyjnym, które wynika z nieco wyższego poziomu, jest po prostu tworzenie niepotrzebnych kopii naprawdę dużych agregatów.

Aby uniknąć zbyt skomplikowanego schematu, wyobraźmy sobie, że ten prosty blok pamięci był w jakiś sposób drogi (być może znaki UTF-32 na niewiarygodnie ograniczonym sprzęcie).

W takim przypadku, jeśli chcielibyśmy zastąpić „HELP” słowem „KILL”, a ten blok pamięci był niezmienny, musielibyśmy stworzyć cały nowy blok w całości, aby stworzyć unikalny nowy obiekt, nawet jeśli zmieniły się tylko jego części :

Rozciągając nieco naszą wyobraźnię, ten rodzaj głębokiej kopii wszystkiego innego, aby uczynić jedną małą część wyjątkową, może być dość kosztowny (w rzeczywistych przypadkach ten blok pamięci byłby o wiele, wiele większy, aby stanowić problem).

Jednak pomimo takiego kosztu, ten rodzaj konstrukcji będzie znacznie mniej podatny na błędy ludzkie. Każdy, kto pracował w funkcjonalnym języku z czystymi funkcjami, może to docenić, szczególnie w przypadku wielowątkowości, w których możemy wielowątkowość takiego kodu bez opieki na świecie. Ogólnie rzecz biorąc, programiści-ludzie mają tendencję do potykania się o zmiany stanu, szczególnie te, które powodują zewnętrzne skutki uboczne dla stanów poza zakresem bieżącej funkcji. Nawet odzyskanie po zewnętrznym błędzie (wyjątku) w takim przypadku może być niezwykle trudne ze zmiennymi zmianami stanu zewnętrznego w miksie.

Jednym ze sposobów złagodzenia tego zbędnego kopiowania jest przekształcenie tych bloków pamięci w kolekcję wskaźników (lub odniesień) do znaków, takich jak:

_{Przepraszam, nie zdawałem sobie sprawy, że nie musimy robić Lwyjątkowych rzeczy podczas tworzenia diagramu.}

_{Niebieski oznacza płytkie skopiowane dane.}

... niestety, byłoby niezwykle kosztownie zapłacić wskaźnik / koszt odniesienia za znak. Co więcej, możemy rozproszyć zawartość znaków w całej przestrzeni adresowej i ostatecznie zapłacić za nią w postaci mnóstwa błędów stron i braków w pamięci podręcznej, co z łatwością czyni to rozwiązanie jeszcze gorszym niż kopiowanie całości w całości.

Nawet jeśli staraliśmy się przydzielić te znaki w sposób ciągły, powiedzmy, że maszyna może załadować 8 znaków i 8 wskaźników do znaku w linii pamięci podręcznej. W końcu ładujemy pamięć w taki sposób, aby przejść przez nowy ciąg:

W tym przypadku wymagamy załadowania 7 różnych linii pamięci podręcznej ciągłej pamięci, aby przejść przez ten ciąg, gdy idealnie potrzebujemy tylko 3.

Chunk Up The Data

Aby złagodzić powyższy problem, możemy zastosować tę samą podstawową strategię, ale na grubszym poziomie 8 znaków, np

Wynik wymaga załadowania danych o wartości 4 linii pamięci podręcznej (1 dla 3 wskaźników i 3 dla znaków), aby przejść przez ten ciąg, który jest tylko o 1 od teoretycznego optymalnego.

Więc to wcale nie jest takie złe. Trochę marnotrawstwa pamięci, ale pamięć jest obfita, a zużywanie jej więcej nie spowalnia rzeczy, jeśli dodatkowa pamięć będzie po prostu zimnymi danymi, do których często nie ma dostępu. To tylko dla gorących, ciągłych danych, w których zmniejszone zużycie pamięci i szybkość często idą w parze, gdzie chcemy zmieścić więcej pamięci w jednej stronie lub linii pamięci podręcznej i uzyskać dostęp do wszystkich przed eksmisją. Ta reprezentacja jest dość przyjazna dla pamięci podręcznej.

Prędkość

Tak więc użycie takiej reprezentacji jak wyżej może dać całkiem przyzwoitą równowagę wydajności. Prawdopodobnie najbardziej krytyczne z punktu widzenia wydajności zastosowania niezmiennych struktur danych przyjmą ten charakter modyfikacji masywnych fragmentów danych i uczynienia ich wyjątkowymi w tym procesie, przy jednoczesnym płytkim kopiowaniu niezmodyfikowanych fragmentów. Wymaga to również narzutu operacji atomowych, aby bezpiecznie odwoływać się do płytko skopiowanych fragmentów w kontekście wielowątkowym (być może przy trwającym pewnym zliczaniu atomowym).

Jednak dopóki te masywne fragmenty danych są reprezentowane na wystarczająco grubym poziomie, duża część tego narzutu zmniejsza się, a być może nawet jest trywializowana, a jednocześnie zapewnia nam bezpieczeństwo i łatwość kodowania i wielowątkowości większej liczby funkcji w czystej postaci bez strony zewnętrznej efekty.

Przechowywanie nowych i starych danych

Moim zdaniem niezmienność jest potencjalnie najbardziej pomocna z punktu widzenia wydajności (w sensie praktycznym), kiedy możemy ulec pokusie tworzenia całych kopii dużych danych, aby uczynić je wyjątkowymi w zmiennym kontekście, w którym celem jest stworzenie czegoś nowego z coś, co już istnieje w taki sposób, że chcemy zachować zarówno nowe, jak i stare, kiedy moglibyśmy po prostu robić małe kawałki tego wyjątkowego dzięki starannemu niezmiennemu projektowi.

Przykład: Cofnij system

Przykładem tego jest system cofania. Możemy zmienić niewielką część struktury danych i chcieć zachować zarówno pierwotną formę, którą możemy cofnąć, jak i nową formę. Dzięki tego rodzaju niezmiennemu projektowi, który sprawia, że ​​małe, zmodyfikowane sekcje struktury danych są unikalne, możemy po prostu przechowywać kopię starych danych w pozycji cofania, płacąc jedynie koszt pamięci dodanych danych unikatowych części. Zapewnia to bardzo skuteczną równowagę wydajności (sprawienie, że wdrożenie systemu cofania jest dziecinnie proste) i wydajności.

Interfejsy wysokiego poziomu

Jednak w powyższej sprawie powstaje coś niezręcznego. W lokalnym kontekście funkcji zmienne dane są często najłatwiejsze i najłatwiejsze do zmodyfikowania. W końcu najłatwiejszym sposobem modyfikacji tablicy jest po prostu zapętlenie jej i zmodyfikowanie jednego elementu na raz. Możemy skończyć ze zwiększeniem narzutu intelektualnego, gdybyśmy mieli do wyboru dużą liczbę algorytmów wysokiego poziomu do transformacji tablicy i musieliśmy wybrać odpowiedni, aby upewnić się, że wszystkie te masywne płytkie kopie zostaną wykonane, a zmodyfikowane części są uczyniony wyjątkowym.

Prawdopodobnie najłatwiejszym sposobem w takich przypadkach jest użycie zmiennych buforów lokalnie w kontekście funkcji (gdzie zwykle nas nie wyzwalają), które dokonują atomowych zmian w strukturze danych, aby uzyskać nową niezmienną kopię (wierzę, że niektóre języki nazywają te „stany przejściowe”) ...

... lub możemy po prostu modelować funkcje transformacji wyższego i wyższego poziomu na danych, abyśmy mogli ukryć proces modyfikowania modyfikowalnego bufora i przypisywania go do struktury bez włączania logiki zmiennej. W każdym razie nie jest to jeszcze obszar szeroko badany, a nasza praca zostanie przerwana, jeśli przyjmiemy bardziej niezmienne projekty, aby wymyślić sensowne interfejsy do przekształcania tych struktur danych.

Struktury danych

Inną rzeczą, która się tutaj pojawia, jest to, że niezmienność stosowana w kontekście krytycznym dla wydajności prawdopodobnie spowoduje, że struktury danych rozpadną się na masywne dane, w których fragmenty nie są zbyt małe, ale też nie są zbyt duże.

Listy połączone mogą chcieć nieco zmienić, aby to dostosować i zamienić w listy rozwijane. Duże, ciągłe tablice mogą przekształcić się w tablicę wskaźników w ciągłe fragmenty z indeksowaniem modulo dla losowego dostępu.

Potencjalnie zmienia to sposób, w jaki patrzymy na struktury danych w ciekawy sposób, jednocześnie popychając funkcje modyfikujące te struktury danych, aby przypominały nieporęczną naturę, aby ukryć dodatkową złożoność w płytkim kopiowaniu niektórych bitów tutaj i czyniąc inne bity wyjątkowymi.

Występ

W każdym razie to mój mały pogląd na ten temat na niższym poziomie. Teoretycznie niezmienność może kosztować od bardzo dużych do mniejszych. Ale bardzo teoretyczne podejście nie zawsze przyspiesza działanie aplikacji. Może to uczynić je skalowalnymi, ale rzeczywista prędkość często wymaga przyjęcia bardziej praktycznego sposobu myślenia.

Z praktycznego punktu widzenia takie cechy, jak wydajność, łatwość konserwacji i bezpieczeństwo zwykle zamieniają się w jedno duże rozmycie, szczególnie w przypadku bardzo dużej bazy kodu. Podczas gdy wydajność w pewnym sensie absolutnym jest obniżana z niezmiennością, trudno jest argumentować o korzyściach, jakie ma ona w zakresie wydajności i bezpieczeństwa (w tym bezpieczeństwa wątków). Wraz z ich wzrostem często może nastąpić wzrost praktycznej wydajności, choćby dlatego, że programiści mają więcej czasu na dostrojenie i optymalizację kodu bez roju błędów.

Sądzę więc, że z tego praktycznego punktu widzenia niezmienne struktury danych mogą w rzeczywistości pomóc w wydajności w wielu przypadkach, jakkolwiek dziwnie to brzmi. Idealny świat może poszukiwać kombinacji tych dwóch: niezmiennych struktur danych i zmiennych, przy czym zmienne zwykle są bardzo bezpieczne w użyciu w bardzo lokalnym zasięgu (np. Lokalne dla funkcji), podczas gdy niezmienne mogą uniknąć strony zewnętrznej efekty wprost i zmień wszystkie zmiany w strukturę danych w operację atomową, tworząc nową wersję bez ryzyka warunków wyścigowych.

ImmutableJS jest naprawdę dość wydajny. Jeśli weźmiemy przykład:

var x = {
    Foo: 1,
    Bar: { Baz: 2 }
    Qux: { AnotherVal: 3 }
}

Jeśli powyższy obiekt stanie się niezmienny, wówczas zmodyfikujesz wartość właściwości „Baz”, a otrzymasz:

var y = x.setIn('/Bar/Baz', 3);
y !== x; // Different object instance
y.Bar !== x.Bar // As the Baz property was changed, the Bar object is a diff instance
y.Qux === y.Qux // Qux is the same object instance

Stwarza to naprawdę fajne ulepszenia wydajności dla modeli obiektów głębokich, w których wystarczy skopiować typy wartości na obiekty w ścieżce do katalogu głównego. Im większy model obiektowy i mniejsze zmiany, które wprowadzasz, tym lepsza pamięć i wydajność procesora niezmiennej struktury danych, ponieważ ostatecznie współużytkują wiele obiektów.

Jak powiedziano w innych odpowiedziach, jeśli skontrastujesz to z próbą zapewnienia takich samych gwarancji poprzez defensywne kopiowanie xprzed przekazaniem go do funkcji, która mogłaby nim manipulować, wówczas wydajność jest znacznie lepsza.

W linii prostej niezmienny kod ma narzut związany z tworzeniem obiektów, który jest wolniejszy. Istnieje jednak wiele sytuacji, w których modyfikowalnym kodem staje się bardzo trudne do efektywnego zarządzania (co skutkuje dużą ilością defensywnego kopiowania, co również jest kosztowne), a także istnieje wiele sprytnych strategii zmniejszania kosztów „kopiowania” obiektu , jak wspomnieli inni.

Jeśli masz obiekt, taki jak licznik, który jest zwiększany wiele razy na sekundę, ustawienie tego licznika na niezmiennym może nie być warte kary za wydajność. Jeśli masz obiekt, który jest odczytywany przez wiele różnych części aplikacji, a każdy z nich chce mieć swój nieco inny klon tego obiektu, znacznie łatwiej będzie ci go zorganizować w wydajny sposób, używając dobrego niezmienna implementacja obiektu.

Aby dodać do tego (już doskonale udzielonego) pytania:

Krótka odpowiedź brzmi: tak ; zaszkodzi to wydajności, ponieważ zawsze tworzysz obiekty zamiast mutować istniejące, co skutkuje większym nakładem na tworzenie obiektów.

Jednak długa odpowiedź nie jest tak naprawdę .

Z rzeczywistego punktu widzenia środowiska uruchomieniowego, w JavaScript tworzysz już całkiem sporo obiektów wykonawczych - funkcje i literały obiektowe są wszędzie w JavaScript i nikt nie zastanawia się nad ich użyciem. Twierdziłbym, że tworzenie obiektów jest w rzeczywistości dość tanie, chociaż nie mam na to żadnych cytatów, więc nie użyłbym tego jako samodzielnego argumentu.

Dla mnie największym wzrostem „wydajności” nie jest wydajność środowiska wykonawczego, ale wydajność programisty . Jedną z pierwszych rzeczy, których nauczyłem się podczas pracy z aplikacjami Real World (tm), jest to, że zmienność jest naprawdę niebezpieczna i zagmatwana. Straciłem wiele godzin ścigania wątku (nie typu współbieżności) wykonywania, próbując ustalić, co powoduje niejasny błąd, kiedy okazuje się, że jest to mutacja z drugiej strony tej cholernej aplikacji!

Używanie niezmienności znacznie ułatwia rozumowanie. Możesz natychmiast wiedzieć, że obiekt X nie zmieni się w trakcie swojego życia, a jedynym sposobem na jego zmianę jest sklonowanie go. Cenię to o wiele bardziej (szczególnie w środowiskach zespołowych) niż wszelkie mikrooptymalizacje, które może przynieść zmienność.

Istnieją wyjątki, w szczególności struktury danych, jak wspomniano powyżej. Rzadko natrafiam na scenariusz, w którym chciałem zmienić mapę po utworzeniu (chociaż wprawdzie mówię o mapach dosłownie pseudoobiektywowych, a nie mapach ES6), to samo dla tablic. W przypadku większych struktur danych zmienność może się opłacić. Pamiętaj, że każdy obiekt w JavaScript jest przekazywany jako odniesienie, a nie wartość.

To powiedziawszy, jednym punktem poruszonym powyżej była GC i jej niezdolność do wykrywania duplikacji. Jest to uzasadniona obawa, ale moim zdaniem jest to tylko problem, gdy pamięć jest problemem, i istnieją znacznie łatwiejsze sposoby zakodowania się w kącie - na przykład okrągłe odniesienia w zamknięciach.

Ostatecznie wolałbym mieć niezmienną bazę kodu z bardzo małą liczbą (jeśli w ogóle) możliwych do zmodyfikowania sekcji i być nieco mniej wydajnym niż mieć wszędzie zmienność. Zawsze możesz zoptymalizować później, jeśli niezmienność z jakiegoś powodu staje się problemem dla wydajności.