Pętle w JavaScript oraz ich performance

7m
nowy

Intro

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

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.
const suite = new Benchmark.Suite; suite.add('RegExp#test', () => { /o/.test('Hello World!'); }) .add('String#indexOf', () => { 'Hello World!'.indexOf('o') > -1; }) .add('String#match', () => { !!'Hello World!'.match(/o/); }) .on('cycle', (event) => { console.log(String(event.target)); }) .on('complete', () => { console.log('Fastest is ' + this.filter('fastest').map('name')); }) .run({ 'async': true });
Code sandbox
do zabawy oraz
repozytorium
z gotowym kodem.
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?
utworzono 1 miesiąc temu
zaktualizowano 1 miesiąc temu