⭐ Pętle w JavaScript oraz ich performance

Intro

Przeprowadzimy testy weryfikujące jaki wpływ na szybkość programu mogą mieć różne pętle w JavaScript.

Wstęp

Widziałem kiedyś pull requesta, w którym dwóch developerów kłóciło się o zastosowaną pętlę. Sytuacja była o tyle zabawna, że zrobiła się z tego długa konwersacja, w której każdy spamował linkami do wątków na Github i do artykułów.

To mnie zaciekawiło... Nigdy nie miałem czasu sprawdzić, która z dostępnych możliwości jest najlepsza. Artykuły poruszające ten temat były powierzchowne. Dlatego postanowiłem wyedukować się od podszewki i o tym w dzisiejszym wpisie.

Doświadczenie i wiedza działają cuda 🚀.

1. Jak mierzyć złożoność obliczeniową w JavaScript?

Nie da się stwierdzić ile dokładnie czasu zajmuje wywołanie konkretnej funkcji oraz co ciekawsze, za każdym pomiarem są to różne wartości. Na pierwszy rzut oka jest to bardzo dziwne, ale pomyśl - procesor robi o wiele więcej niż jakiś durny programik w JavaScript, a przeglądarka o wiele więcej niż uruchamianie twojego kodu.

Skoro wiemy już, że pomiar czasu jest niedokładny to wiemy też, że jakoś możemy go mierzyć. JavaScript ma wbudowane API, a nawet kilka. My skupimy się tylko na performance.now(), bo to nie zastosowane API w tym przypadku robi różnice, a sposób pomiaru i to co mierzymy.

Udowodniłem Ci, że czas się różni. Teraz musimy ustalić jak możemy stwierdzić, która pętla jest szybsza. Zastosujemy technikę, która nazywa się próbkowaniem. Zamiast wywoływać testowany kod raz i porównywać go z rezultatem innego programu uruchomimy go tysiące/miliony razy i obliczymy sumę czasów przy każdym wywołaniu.

Odpal na swoim komputerze podany kod i sprawdź jak uruchomienie programów wpływa na wynik dowolnej funkcji 💻.

2. Próbkujemy i zbieramy

Mamy funkcję measure(), więc teraz musimy ją uruchomić n razy.

3. Wyświetlanie i logowanie

Na tym etapie mamy czyste dane, ale kto by je tam chciał ręcznie przeglądać. Musimy je podliczyć i zaokrąglić do czterech miejsc po przecinku. Tylko do czterech, bo jeżeli coś trwa 0.00001532 sekundy to umówmy się - użytkownik tego raczej nie zauważy.

Co my tu mamy? Wywołaliśmy funkcję sumującą trzy razy przekazując do niej sześć liczb od 1 do 6. Całkowity czas trwania tych obliczeń wyniósł 0.0101 sekundy.

JS jest dziwny. Uruchom kod trzy razy i zobacz, że wartości są różne.

4. Pętle i rekurencje

Napiszemy kilka funkcji, które będa miały za zadanie obliczyć sumę dowolnych liczb (czyli każda zrobi to samo, ale inaczej). Później porównamy wynik z gotowym narzędziem do sprawdzania optymalizacji i wyciągniemy wnioski.

Teraz ten sam zbiór danych przekażemy do każdej z nich i wyciągniemy wnioski.

Zakładam, że rzucił Ci się w oczy brak wywołania recursiveSum. Jest to celowe. Tutaj mały spoiler - ta implementacja będzie miała najgorszy wynik. Na tyle zły, że przepełni stos wywołań i wywali nasz program 💥.

5. Sprawdźmy wyniki

W momencie gdy danych jest mało (100-1000) to nie widać większej różnicy. Wygląda nawet na to, że wyniki są losowe (trwa to tak krótko, że nie ma różnicy, której implementacji użyjemy). Wszystko zmienia się w momencie, gdy danych jest więcej. Nagle okazuje się, że pętla for pojawia się na pierwszym miejscu zawsze, a różnica pomiędzy pozostałymi jest znaczna.

Dlaczego tak się dzieje? Nowoczesne procesory są bardzo szybkie. Jeżeli nie są obciążone to nie będzie widać większej różnicy pomiędzy działaniem programu, przede wszystkim jeżeli algorytm jest ten sam. W momencie zwiększania zbioru liczb procesor zaczyna się "męczyć" (a raczej przeglądarka), więc zaczynamy widzieć różnice w pomiarach.

Dodatkowo należy pamiętać, że JavaScript jest przekształcany w zależności od implementacji silnika do języka pośredniego, a następnie do kodu maszynowego. Więc implementacja, która kryje się wewnątrz jest dla nas programistów nieznana. Może być tak, że pętla for ma przewagę nad while, bo kod "pod spodem" jest do tego zoptymalizowany.

Jednak nie można powiedzieć, że pętla for zawsze będzie najszybsza. Na pewno nie w oparciu o dane zebrane na małych zbiorach liczb. To już zależy tylko i wyłącznie od problemu. Możemy powiedzieć, że dla tego problemu pętla for jest najszybsza dla zbioru z jakiegoś przedziału, a nie że jest "najszybsza".

Jeszcze jedna sprawa. Dlaczego w takim razie metody wbudowane w prototyp Array są wolniejsze, jeżeli i tak używaja pętli for wewnątrz? Jest to spowodowane dodatkowymi operacjami, na które jako developerzy się godzimy zyskując na przejrzystości kodu a tracąc na jego szybkości (w myśl zasady coś za coś). Wykorzystane abstrakcje jak forEach oraz reduce wykonują dodatkowe sprawadzenia przy każdej iteracji, więc to złożyło się na ich gorszy wynik w porównaniu do while czy for. Jako dowód podaje link do specyfikacji.

Dziękuje dla Pawła Wolaka za pomoc w tym miejscu.

6. Jaki rezultat dało gotowe narzędzie?

W internecie jest ich naprawdę sporo, a ja postanowiłem wybrać najładniejsze, czyli perf.link (taka przypadłość u frątasi). Wrzuciłem wcześniejsze przykłady i wyszedł mi dokładnie taki sam werdykt. Pętla for przodowała przy większych zbiorach liczb, a przy mniejszych nie można było ocenić, która jest najlepsza. Sprawdziłem też funkcję rekurencyjną. Tak samo jak wcześniej od samego początku odstawała nawet na ilości 100 elementów. Tak prezentuje się wynik dla stu tysięcy numerów.

Jak widzisz rekurencja nie działa.

Do dyspozycji są jeszcze fajne biblioteki. Ja wykorzystwałem często Benchmark.js, która w mojej opini jest świetna oraz przypomina pisanie zwykłych testów jednostkowych. Tym razem będą to jednak testy szybkości działania programu a nie tego czy prawidłowo działa.

Full example

Code sandbox do zabawy oraz repozytorium z gotowym kodem.

Podsumowanie

Po tym wpisie już wiesz, że mierzenie złożoności obliczeniowej może być "tricky". Okazało się, że ciężko jest stwierdzić, która pętla jest najszybsza.

Składnia języka jest istotna, ale nie aż tak jak algorytm i umiejętności programisty, po stronie których stoi odpowiedź na pytanie - które rozwiązanie jest szybsze?

Pamiętaj, że złożoność pamięciowa jest także istotna a czasami nawet ważniejsza. Myślę, że jednak o tym innym razem.

Jeżeli Ci się podobało to pamiętaj odwiedzić nas na Linkedin gdzie regularnie wrzucamy content z programowania.

"Człowiek uczy się przez całe życie a robi to zazwyczaj odkrywając koło na nowo. Od dzieciństwa - do końca swoich dni." - cytat z książki, może wiesz jakiej?