Pętle w JavaScript oraz ich performance

Widziałem kiedyś , 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 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 , 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ę . 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ę , więc teraz musimy ją uruchomić 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 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 . Całkowity czas trwania tych obliczeń wyniósł 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 . Jest to celowe. Tutaj mały spoiler - ta implementacja będzie miała najgorszy wynik. Na tyle zły, że przepełni 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 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 ma przewagę nad , bo kod "pod spodem" jest do tego zoptymalizowany.

Jednak nie można powiedzieć, że pętla 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 jest najszybsza dla zbioru z jakiegoś przedziału, a nie że jest "najszybsza".

Jeszcze jedna sprawa. Dlaczego w takim razie metody wbudowane w prototyp są wolniejsze, jeżeli i tak używaja pętli 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 oraz wykonują dodatkowe sprawadzenia przy każdej iteracji, więc to złożyło się na ich gorszy wynik w porównaniu do czy . Jako dowód podaje link do .

Dziękuje dla 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 (taka przypadłość u frątasi). Wrzuciłem wcześniejsze przykłady i wyszedł mi dokładnie taki sam werdykt. Pętla 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 , 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 });

do zabawy oraz 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 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?