Wydajność: rekurencja vs. iteracja w JavaScript

24

Niedawno przeczytałem kilka artykułów (np. Http://dailyjs.com/2012/09/14/functional-programming/ ) na temat funkcjonalnych aspektów Javascript i relacji między Scheme i Javascript (na ten drugi miał wpływ pierwszy, na który jest językiem funkcjonalnym, podczas gdy aspekty OO są dziedziczone z Self, który jest językiem opartym na prototypowaniu).

Moje pytanie jest jednak bardziej szczegółowe: zastanawiałem się, czy istnieją wskaźniki dotyczące wydajności rekurencji w porównaniu z iteracją w JavaScript.

Wiem, że w niektórych językach (gdzie z założenia iteracja działa lepiej) różnica jest minimalna, ponieważ interpreter / kompilator konwertuje rekurencję na iterację, jednak sądzę, że prawdopodobnie nie jest tak w przypadku Javascript, ponieważ jest on przynajmniej częściowo funkcjonalny język.

javascript functional-programming recursion mastazi
źródło
3
Wykonaj własny test i dowiedz się od razu na jsperf.com
TehShrike,
z nagrodą i jedną odpowiedzią wspominającą TCO. Wygląda na to, że ES6 określa TCO, ale jak dotąd nikt go nie wdraża, jeśli uważamy, że kangax.github.io/compat-table/es6 Czy czegoś brakuje?
Matthias Kauer,

Odpowiedzi:

28

JavaScript nie wykonuje optymalizacji rekurencji ogona , więc jeśli twoja rekurencja jest zbyt głęboka, możesz dostać przepełnienie stosu wywołań. Iteracja nie ma takich problemów. Jeśli uważasz, że masz zamiar za dużo powtórzyć i naprawdę potrzebujesz rekurencji (na przykład, aby wypełnić zalewanie), zamień rekursję na własny stos.

Wydajność rekurencji jest prawdopodobnie gorsza niż wydajność iteracji, ponieważ wywołania funkcji i powroty wymagają zachowania i przywrócenia stanu, podczas gdy iteracja po prostu przeskakuje do innego punktu funkcji.

Triang3l
źródło
Zastanawiam się ... Widziałem trochę kodu, w którym tworzona jest pusta tablica, a miejsce funkcji rekurencyjnej jest przypisywane do pozycji w tablicy, a następnie zwracana jest wartość przechowywana w tablicy. Czy to rozumiesz przez „zastąpienie rekursji własnym stosem”? Np .: var stack = []; var factorial = function(n) { if(n === 0) { return 1 } else { stack[n-1] = n * factorial(n - 1); return stack[n-1]; } }
mastazi
@mastazi: Nie, to spowoduje, że stos będzie bezużyteczny wraz z wewnętrznym. Miałem na myśli coś takiego jak wypełnianie kolejki z Wikipedii .
Triang3l,
Warto zauważyć, że język nie wykonuje TCO, ale implementacja może. Sposób, w jaki ludzie optymalizują JS, oznacza, że ​​być może TCO może pojawić się w kilku implementacjach
Daniel Gratzer
1
@mastazi Zamień elsew tej funkcji na else if (stack[n-1]) { return stack[n-1]; } elsei masz notatkę . Ktokolwiek napisał ten kod czynnikowy miał niepełną implementację (i prawdopodobnie powinien był użyć stack[n]wszędzie zamiast stack[n-1]).
Izkata
Dziękuję @Izkata, często robię tego rodzaju optymalizację, ale do dziś nie znałem jej nazwy. Powinienem był studiować CS zamiast IT ;-)
mastazi
20

Aktualizacja : od ES2015 JavaScript ma całkowity koszt posiadania , więc część poniższego argumentu już nie ma znaczenia.

Mimo że JavaScript nie ma optymalizacji wywołania ogona, rekursja jest często najlepszym sposobem. I szczerze, z wyjątkiem przypadków skrajnych, nie dostaniesz przepełnienia stosu wywołań.

Należy pamiętać o wydajności, ale także o przedwczesnej optymalizacji. Jeśli uważasz, że rekurencja jest bardziej elegancka niż iteracja, wybierz ją. Jeśli okaże się, że to twoje wąskie gardło (które może nigdy nie być), możesz zastąpić je brzydką iteracją. Ale w większości przypadków wąskim gardłem są manipulacje DOM lub bardziej ogólnie We / Wy, a nie sam kod.

Rekurencja jest zawsze bardziej elegancka 1 .

1 : Osobista opinia.

Florian Margaine
źródło
3
Zgadzam się, że rekurencja jest bardziej elegancka, a elegancja jest ważna, ponieważ zarówno czytelność, jak i łatwość konserwacji (jest to subiektywne, ale moim zdaniem rekurencja jest bardzo łatwa do odczytania, a zatem możliwa do utrzymania). Czasami jednak wydajność ma znaczenie; czy możesz poprzeć twierdzenie, że rekurencja jest najlepszą drogą, nawet jeśli chodzi o wydajność?
mastazi
3
@mastazi, jak powiedziałem w mojej odpowiedzi, wątpię, czy rekurencja będzie twoim wąskim gardłem. W większości przypadków jest to manipulacja DOM lub bardziej ogólnie I / O. I nie zapominaj, że przedwczesna optymalizacja jest źródłem wszelkiego zła;)
Florian Margaine,
+1 za manipulację DOM, która przez większość czasu stanowi wąskie gardło! Pamiętam bardzo interesujący wywiad z Yehuda Katz (Ember.js) na ten temat.
mastazi
1
@mike Definicja „przedwczesna” to „dojrzała lub dojrzała przed właściwym czasem”. Jeśli wiesz, że rekurencyjne robienie czegoś spowoduje przepełnienie stosu, nie jest to przedwczesne. Jeśli jednak zakładasz kaprys (bez żadnych faktycznych danych), jest to przedwczesne.
Zirak,
2
Z Javascriptem nie wiesz, ile stosów będzie miał program. Możesz mieć mały stos w IE6 lub duży stos w FireFox. Algorytmy rekurencyjne rzadko mają stałą głębokość, chyba że wykonujesz pętlę rekurencyjną w stylu Scheme. Po prostu nie wydaje się, aby rekurencja oparta na pętli nie pozwalała uniknąć przedwczesnych optymalizacji.
mike30
7

Byłem bardzo ciekawy tej wydajności w javascript, więc przeprowadziłem kilka eksperymentów (aczkolwiek na starszej wersji węzła). Napisałem kalkulator czynnikowy rekurencyjnie w stosunku do iteracji i uruchomiłem go kilka razy lokalnie. Wynik wydawał się dość mocno wypaczony w kierunku rekurencji z podatkiem (oczekiwany).

Kod: https://github.com/j03m/trickyQuestions/blob/master/factorial.js

Result:
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:557
Time:126
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:519
Time:120
j03m-MacBook-Air:trickyQuestions j03m$ node factorial.js 
Time:541
Time:123
j03m-MacBook-Air:trickyQuestions j03m$ node --version
v0.8.22
Dr.HappyPants
źródło
Możesz spróbować z tym "use strict";i sprawdzić, czy to robi różnicę. (Wyprodukuje jumps zamiast standardowej sekwencji wywołań)
Burdock,
1
W najnowszej wersji węzła (6.9.1) uzyskałem bardzo podobne wyniki. Jest trochę podatku od rekurencji, ale uważam to za przypadek krawędziowy - różnica 400 ms dla 1 000 000 pętli wynosi 0,0025 ms na pętlę. Jeśli wykonujesz 1 000 000 pętli, warto o tym pamiętać.
Kelz
6

Zgodnie z prośbą OP włożę się (bez robienia z siebie głupca, mam nadzieję: P)

Myślę, że wszyscy się zgodziliśmy, że rekurencja jest po prostu bardziej eleganckim sposobem kodowania. Jeśli zostanie to zrobione dobrze, może sprawić, że kod będzie łatwiejszy w utrzymaniu, co jest równie ważne (jeśli nie więcej) IMHO, że goli 0,0001 ms.

Jeśli chodzi o argument, że JS nie wykonuje optymalizacji wywołania ogona: nie jest to już do końca prawdą, użycie trybu ścisłego ECMA5 umożliwia TCO. To było coś, z czego nie byłem zbyt zadowolony, ale przynajmniej teraz wiem, dlaczego arguments.calleerzuca błędy w trybie ścisłym. Wiem, że powyższy link prowadzi do raportu o błędzie, ale błąd jest ustawiony na WONTFIX. Ponadto nadchodzi standardowy TCO: ECMA6 (grudzień 2013 r.).

Instynktownie i trzymając się funkcjonalnej natury JS, powiedziałbym, że rekurencja jest bardziej wydajnym stylem kodowania 99,99% czasu. Jednak Florian Margaine ma rację, gdy mówi, że wąskie gardło można znaleźć gdzie indziej. Jeśli manipulujesz DOM, prawdopodobnie najlepiej skupiasz się na pisaniu kodu tak, aby był możliwie jak najłatwiejszy w utrzymaniu. DOM API jest tym, czym jest: wolno.

Myślę, że prawie niemożliwe jest udzielenie ostatecznej odpowiedzi na pytanie, która opcja jest szybsza. Ostatnio wiele jsprefów, które widziałem, pokazuje, że silnik Chrome V8 jest absurdalnie szybki w niektórych zadaniach, które działają 4x wolniej na SpiderMonkey w FF i odwrotnie. Nowoczesne silniki JS mają różne sztuczki, aby zoptymalizować kod. Nie jestem ekspertem, ale wydaje mi się, że na przykład V8 jest wysoce zoptymalizowany do zamykania (i rekurencji), podczas gdy silnik JScript MS nie. SpiderMonkey często działa lepiej, gdy DOM jest zaangażowany ...

W skrócie: Powiedziałbym, która technika będzie bardziej wydajna, jak zwykle w JS, prawie niemożliwe do przewidzenia.

Elias Van Ootegem
źródło
3

Bez trybu ścisłego wydajność iteracji jest zwykle nieco szybsza niż rekurencja ( oprócz zwiększania wydajności JIT ). Optymalizacja rekurencji ogona zasadniczo eliminuje zauważalną różnicę, ponieważ zmienia całą sekwencję wywołań w skok.

Przykład: Jsperf

Sugerowałbym martwienie się o przejrzystość i prostotę kodu, jeśli chodzi o wybór między rekurencją a iteracją.

Łopian
źródło