Dlaczego <= wolniej niż <używanie tego fragmentu kodu w wersji 8?

Czytam slajdy Breaking the Javascript Speed ​​Limit with V8 i jest przykład podobny do kodu poniżej. Nie wiem, dlaczego <=jest wolniejszy niż <w tym przypadku, czy ktoś może to wyjaśnić? Wszelkie uwagi są mile widziane.

Powolny:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

(Wskazówka: liczby pierwsze to tablica długości liczba_pierwsza)

Szybciej:

this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i < this.prime_count; ++i) {
        if (candidate % this.primes[i] == 0) return true;
    }
    return false;
} 

[Więcej informacji] poprawa szybkości jest znacząca, w moim teście w środowisku lokalnym wyniki są następujące:

V8 version 7.3.0 (candidate) 

Powolny:

 time d8 prime.js
 287107
 12.71 user 
 0.05 system 
 0:12.84 elapsed 

Szybciej:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed

Pracuję nad V8 w Google i chciałem zapewnić dodatkowe informacje na temat istniejących odpowiedzi i komentarzy.

Dla porównania, oto przykład pełnego kodu ze slajdów :

var iterations = 25000;

function Primes() {
  this.prime_count = 0;
  this.primes = new Array(iterations);
  this.getPrimeCount = function() { return this.prime_count; }
  this.getPrime = function(i) { return this.primes[i]; }
  this.addPrime = function(i) {
    this.primes[this.prime_count++] = i;
  }
  this.isPrimeDivisible = function(candidate) {
    for (var i = 1; i <= this.prime_count; ++i) {
      if ((candidate % this.primes[i]) == 0) return true;
    }
    return false;
  }
};

function main() {
  var p = new Primes();
  var c = 1;
  while (p.getPrimeCount() < iterations) {
    if (!p.isPrimeDivisible(c)) {
      p.addPrime(c);
    }
    c++;
  }
  console.log(p.getPrime(p.getPrimeCount() - 1));
}

main();

Przede wszystkim różnica w wydajności nie ma bezpośredniego związku z operatorami <i <=. Więc proszę, nie przeskakuj przez obręcze tylko po to, aby uniknąć <=w kodzie, ponieważ przeczytałeś na Stack Overflow, że jest wolny - tak nie jest!

Po drugie, ludzie zauważyli, że tablica jest „dziurawa”. Nie było to jasne z fragmentu kodu w poście OP, ale jest to jasne, gdy spojrzysz na kod, który się inicjalizuje this.primes:

this.primes = new Array(iterations);

Prowadzi to do tablicy z ciągu HOLEYelementów rodzaj w V8, nawet jeśli tablica kończy się całkowicie wypełniona / zapakowane / przyległe. Ogólnie rzecz biorąc, operacje na tablicach dziurawych są wolniejsze niż operacje na tablicach upakowanych, ale w tym przypadku różnica jest znikoma: wynosi 1 dodatkową kontrolę Smi ( mała liczba całkowita ) (w celu ochrony przed dziurami) za każdym razem, gdy trafimy this.primes[i]w pętlę wewnątrz isPrimeDivisible. Nie ma sprawy!

TL; DR Istnienie macierzy nie HOLEYjest tutaj problemem.

Inni wskazywali, że kod odczytuje poza zakresem. Generalnie zaleca się unikanie czytania poza długością tablic iw tym przypadku rzeczywiście pozwoliłoby to uniknąć ogromnego spadku wydajności. Ale dlaczego? Wersja 8 może obsłużyć niektóre z tych scenariuszy poza zakresem przy niewielkim wpływie na wydajność. Co zatem jest takiego specjalnego w tym konkretnym przypadku?

Odczyt poza zakresem powoduje, this.primes[i]że znajdujesz się undefinedw tej linii:

if ((candidate % this.primes[i]) == 0) return true;

I to prowadzi nas do prawdziwego problemu : %operator jest teraz używany z operandami niecałkowitymi!

• integer % someOtherIntegermożna obliczyć bardzo wydajnie; Silniki JavaScript mogą w tym przypadku generować wysoce zoptymalizowany kod maszynowy.

• integer % undefinedz drugiej strony jest o wiele mniej wydajne Float64Mod, ponieważ undefinedjest reprezentowane jako podwójne.

Fragment kodu można rzeczywiście ulepszyć, zmieniając na <=w <tym wierszu:

for (var i = 1; i <= this.prime_count; ++i) {

... nie dlatego, że <=jest jakimś lepszym operatorem niż <, ale tylko dlatego, że pozwala to uniknąć odczytywania poza zakresem w tym konkretnym przypadku.

Inne odpowiedzi i komentarze wspominają, że różnica między dwiema pętlami polega na tym, że pierwsza wykonuje o jedną iterację więcej niż druga. To prawda, ale w tablicy, która rozrasta się do 25 000 elementów, jedna iteracja mniej więcej spowodowałaby niewielką różnicę. Przypuszczam, że jeśli przyjmiemy, że średnia długość rośnie 12 500, wówczas różnica, której możemy się spodziewać, powinna wynosić około 1/12 500, czyli tylko 0,008%.

Różnica w wydajności jest tutaj znacznie większa, niż można by to wytłumaczyć jedną dodatkową iteracją, a problem został wyjaśniony pod koniec prezentacji.

this.primes jest ciągłą tablicą (każdy element ma wartość), a wszystkie elementy są liczbami.

Silnik JavaScript może zoptymalizować taką tablicę, aby była prostą tablicą rzeczywistych liczb, zamiast tablicy obiektów, które tak się składa, że ​​zawierają liczby, ale mogą zawierać inne wartości lub nie zawierać żadnej wartości. Pierwszy format jest znacznie szybszy w dostępie: zajmuje mniej kodu, a tablica jest znacznie mniejsza, więc będzie lepiej pasować do pamięci podręcznej. Ale są pewne warunki, które mogą uniemożliwić użycie tego zoptymalizowanego formatu.

Jednym z warunków byłby brak niektórych elementów tablicy. Na przykład:

let array = [];
a[0] = 10;
a[2] = 20;

Jaka jest teraz wartość a[1]? Nie ma wartości . (Nie jest nawet poprawne stwierdzenie, że ma wartość undefined- element tablicy zawierający undefinedwartość różni się od elementu tablicy, którego całkowicie brakuje).

Nie ma sposobu, aby przedstawić to za pomocą samych liczb, więc silnik JavaScript jest zmuszony do używania mniej zoptymalizowanego formatu. Gdyby a[1]zawierała wartość liczbową, podobnie jak pozostałe dwa elementy, tablica mogłaby zostać zoptymalizowana do postaci tablicy tylko liczb.

Innym powodem, dla którego tablica ma zostać wymuszona w niezoptymalizowanym formacie, może być próba uzyskania dostępu do elementu poza granicami tablicy, jak omówiono w prezentacji.

Pierwsza pętla z <=próbami odczytania elementu znajdującego się poza końcem tablicy. Algorytm nadal działa poprawnie, ponieważ w ostatniej dodatkowej iteracji:

• this.primes[i]zwraca się, undefinedponieważ iznajduje się poza końcem tablicy.
• candidate % undefined(dla dowolnej wartości candidate) przyjmuje wartość NaN.
• NaN == 0ocenia do false.
• Dlatego return truenie jest wykonywany.

Więc to tak, jakby dodatkowa iteracja nigdy się nie wydarzyła - nie ma wpływu na resztę logiki. Kod daje ten sam wynik, co bez dodatkowej iteracji.

Ale żeby się tam dostać, próbował odczytać nieistniejący element poza końcem tablicy. To zmusza tablicę do wycofania się z optymalizacji - a przynajmniej tak było w czasie tej rozmowy.

Druga pętla <odczytuje tylko elementy, które istnieją w tablicy, więc umożliwia zoptymalizowanie tablicy i kodu.

Problem jest opisany na stronach 90-91 wykładu, z powiązaną dyskusją na stronach przed i po nim.

Zdarzyło mi się uczestniczyć w tej prezentacji Google I / O i później rozmawiałem z mówcą (jednym z autorów V8). W swoim własnym kodzie używałem techniki, która polegała na czytaniu poza końcem tablicy jako błędnej (z perspektywy czasu) próbie optymalizacji jednej konkretnej sytuacji. Potwierdził, że jeśli spróbujesz odczytać nawet poza końcem tablicy, uniemożliwi to użycie prostego zoptymalizowanego formatu.

Jeśli to, co powiedział autor V8, nadal jest prawdą, odczytanie poza koniec tablicy uniemożliwiłoby jej optymalizację i musiałoby wrócić do wolniejszego formatu.

Możliwe, że w międzyczasie V8 został ulepszony, aby efektywnie obsłużyć ten przypadek, lub że inne silniki JavaScript obsługują to inaczej. Nie wiem, czy tak czy inaczej, ale o tej deoptimizacji mówiła prezentacja.

TL; DR Wolniejsza pętla wynika z dostępu do tablicy `` poza granicami '', co zmusza silnik do ponownej kompilacji funkcji z mniejszą lub nawet żadną optymalizacją LUB nie kompiluje funkcji z żadną z tych optymalizacji na początku ( jeśli (JIT-) Compiler wykrył / podejrzewał ten stan przed pierwszą wersją kompilacji), przeczytaj poniżej dlaczego;

Przykład 1:
a Dense Array(ciągły (oznacza brak przerw między indeksami) ORAZ w rzeczywistości element w każdym indeksie) z 5 elementów przy użyciu indeksowania w oparciu o 0 (zawsze w ES262).

var arr_five_char=['a', 'b', 'c', 'd', 'e']; // arr_five_char.length === 5
//  indexes are:    0 ,  1 ,  2 ,  3 ,  4    // there is NO index number 5

Dlatego tak naprawdę nie mówimy o różnicy w wydajności między <vs <=(lub „jedną dodatkową iteracją”), ale mówimy:
„dlaczego poprawny fragment (b) działa szybciej niż błędny fragment (a)”?

Odpowiedź jest podwójna (chociaż z perspektywy implementującego język ES262 obie są formami optymalizacji):

1. Reprezentacja danych: jak reprezentować / przechowywać tablicę wewnętrznie w pamięci (obiekt, hashmap, `` rzeczywista '' tablica numeryczna itp.)
2. Funkcjonalny kod maszynowy: jak skompilować kod, który uzyskuje dostęp / obsługuje (odczytuje / modyfikuje) te „tablice”

Punkt 1 jest wystarczająco (i poprawnie IMHO) wyjaśniony przyjętą odpowiedzią , ale w pozycji 2: kompilacja zajmuje tylko 2 słowa („kod”) .

Dokładniej: JIT-Compilation i co ważniejsze JIT- RE -Compilation!

Specyfikacja języka to po prostu opis zestawu algorytmów („czynności, jakie należy wykonać, aby osiągnąć określony wynik końcowy”). Co, jak się okazuje, jest bardzo pięknym sposobem opisania języka. I pozostawia rzeczywistą metodę, której silnik używa do osiągnięcia określonych wyników, otwartą dla wdrażających, dając szerokie możliwości wymyślenia bardziej wydajnych sposobów uzyskania zdefiniowanych wyników. Silnik zgodny ze specyfikacją powinien dawać wyniki zgodne ze specyfikacją dla dowolnego zdefiniowanego wejścia.

Teraz, gdy kod / biblioteki / użycie javascript rośnie i zapamiętuje, ile zasobów (czasu / pamięci / itp.) Wykorzystuje `` prawdziwy '' kompilator, jasne jest, że nie możemy zmusić użytkowników odwiedzających stronę internetową do czekania tak długo (i wymagają ich mieć tyle dostępnych zasobów).

Wyobraź sobie następującą prostą funkcję:

function sum(arr){
  var r=0, i=0;
  for(;i<arr.length;) r+=arr[i++];
  return r;
}

Całkowicie jasne, prawda? Nie wymaga ŻADNEGO dodatkowego wyjaśnienia, prawda? Typ zwrotny to Number, prawda?
Cóż ... nie, nie i nie ... To zależy od tego, jaki argument przekażesz do nazwanego parametru funkcji arr...

sum('abcde');   // String('0abcde')
sum([1,2,3]);   // Number(6)
sum([1,,3]);    // Number(NaN)
sum(['1',,3]);  // String('01undefined3')
sum([1,,'3']);  // String('NaN3')
sum([1,2,{valueOf:function(){return this.val}, val:6}]);  // Number(9)
var val=5; sum([1,2,{valueOf:function(){return val}}]);   // Number(8)

Widzisz problem? W takim razie zastanów się, że to tylko ledwie skrobanie ogromnych możliwych permutacji ... Nie wiemy nawet, jakiego rodzaju TYPE funkcja RETURN jest dopiero, gdy skończymy ...

Teraz wyobraź sobie ten sam kod funkcji, który jest faktycznie używany na różnych typach lub nawet odmianach danych wejściowych, zarówno całkowicie dosłownie (w kodzie źródłowym) opisanym, jak i dynamicznie generowanych w programie „tablicach”.

Tak więc, jeśli miałbyś skompilować funkcję sumTYLKO RAZ, to jedyny sposób, który zawsze zwraca wynik zdefiniowany przez specyfikację dla dowolnego i wszystkich typów danych wejściowych, to oczywiście tylko przez wykonanie WSZYSTKICH określonych przez specyfikację głównych kroków I podrzędnych może zagwarantować wyniki zgodne ze specyfikacją (jak nienazwana przeglądarka w wersji starszej niż Y2K). Brak optymalizacji (ponieważ nie ma założeń) i martwy, wolno interpretowany język skryptowy.

Kompilacja JIT (JIT jak w Just In Time) jest obecnie popularnym rozwiązaniem.

Tak więc zaczynasz kompilować funkcję, korzystając z założeń dotyczących tego, co robi, zwraca i akceptuje.
wymyślasz testy tak proste, jak to tylko możliwe, aby wykryć, czy funkcja może zacząć zwracać wyniki niezgodne ze specyfikacją (np. ponieważ otrzymuje nieoczekiwane dane wejściowe). Następnie odrzuć poprzednio skompilowany wynik i ponownie skompiluj do czegoś bardziej złożonego, zdecyduj, co zrobić z wynikiem częściowym, który już masz (czy można zaufać, czy ponownie obliczyć, aby mieć pewność), przywiąż funkcję z powrotem do programu i Spróbuj ponownie. Ostatecznie powrót do krokowej interpretacji skryptu, jak w specyfikacji.

Wszystko to wymaga czasu!

Wszystkie przeglądarki działają na swoich silnikach, dla każdej podwersji zobaczysz poprawę i regres. Łańcuchy były w pewnym momencie w historii naprawdę niezmiennymi łańcuchami (stąd array.join był szybszy niż konkatenacja ciągów), teraz używamy lin (lub podobnych), które rozwiązują problem. Oba zwracają wyniki zgodne ze specyfikacją i to się liczy!

Krótko mówiąc: tylko dlatego, że semantyka języka javascript często nam pomagała (jak w przypadku tego cichego błędu w przykładzie OP), nie oznacza, że ​​„głupie” błędy zwiększają nasze szanse na wyplucie przez kompilator szybkiego kodu maszynowego. Zakłada się, że napisaliśmy `` zwykle '' poprawne instrukcje: aktualna mantra, którą my `` użytkownicy '' (języka programowania) musimy mieć: pomóc kompilatorowi, opisać, czego chcemy, faworyzować popularne idiomy (weź wskazówki z asm.js dla podstawowego zrozumienia jakie przeglądarki mogą próbować optymalizować i dlaczego).

Z tego powodu mówienie o osiągach jest zarówno ważne, ALE TAKŻE pole minowe (iz powodu tego pola minowego naprawdę chcę zakończyć wskazaniem (i zacytowaniem) jakiegoś istotnego materiału:

Dostęp do nieistniejących właściwości obiektu i elementów tablicy spoza granic zwraca undefinedwartość zamiast zgłaszania wyjątku. Te dynamiczne funkcje sprawiają, że programowanie w JavaScript jest wygodne, ale utrudniają też kompilację JavaScript w wydajny kod maszynowy.

...

Ważną przesłanką skutecznej optymalizacji JIT jest to, że programiści używają dynamicznych funkcji JavaScript w sposób systematyczny. Na przykład kompilatory JIT wykorzystują fakt, że właściwości obiektu są często dodawane do obiektu danego typu w określonej kolejności lub że dostęp do tablicy poza granicami występuje rzadko. Kompilatory JIT wykorzystują te założenia dotyczące regularności do generowania wydajnego kodu maszynowego w czasie wykonywania. Jeśli blok kodu spełnia założenia, silnik JavaScript wykonuje wydajny, wygenerowany kod maszynowy. W przeciwnym razie silnik musi wrócić do wolniejszego kodu lub zinterpretować program.

Źródło:
„JITProf: Pinpointing JIT-unfriendly JavaScript Code”
publikacja Berkeley, 2014, autorstwa Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (również nie lubi dostępu do tablicy poza granicami):

Kompilacja z wyprzedzeniem

Ponieważ asm.js jest ścisłym podzbiorem języka JavaScript, ta specyfikacja definiuje tylko logikę walidacji - semantyka wykonywania jest po prostu semantyka JavaScript. Jednak zweryfikowany plik asm.js jest podatny na kompilację z wyprzedzeniem (AOT). Co więcej, kod generowany przez kompilator AOT może być dość wydajny, oferując:

• reprezentacje liczb całkowitych i liczb zmiennoprzecinkowych bez ramki;
• brak kontroli typu w czasie wykonywania;
• brak zbierania śmieci; i
• wydajne ładowanie sterty i składowanie (ze strategiami wdrażania różniącymi się w zależności od platformy).

Kod, który nie przejdzie walidacji, musi wrócić do wykonania tradycyjnymi metodami, np. Interpretacją i / lub kompilacją just-in-time (JIT).

http://asmjs.org/spec/latest/

i wreszcie https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
gdzie jest mała podsekcja na temat wewnętrznych ulepszeń wydajności silnika podczas usuwania ograniczeń- check (po prostu podnosząc granicę - check poza pętlą miał już poprawę o 40%).

EDYCJA:
zauważ, że wiele źródeł mówi o różnych poziomach rekompilacji JIT, aż do interpretacji.

Teoretyczny przykład oparty na powyższych informacjach, dotyczący fragmentu PO:

• Wywołanie isPrimeDivisible
• Skompiluj isPrimeDivisible przy użyciu ogólnych założeń (np. Brak dostępu poza granicami)
• Wykonać pracę
• BAM, nagle tablica uzyskuje dostęp poza granicami (na samym końcu).
• Bzdura, mówi silnik, skompilujmy ponownie, że jest PrimeDivisible przy użyciu innych (mniej) założeń, a ten przykładowy silnik nie próbuje dowiedzieć się, czy może ponownie wykorzystać bieżący wynik częściowy, więc
• Przelicz ponownie całą pracę używając wolniejszej funkcji (miejmy nadzieję, że się zakończy, w przeciwnym razie powtórz i tym razem po prostu zinterpretuj kod).
• Wynik zwrotu

Stąd czas był następujący:
pierwsze uruchomienie (zakończone niepowodzeniem) + wykonywanie całej pracy od nowa przy użyciu wolniejszego kodu maszynowego dla każdej iteracji + rekompilacja itp. Wyraźnie trwa> 2 razy dłużej w tym teoretycznym przykładzie !

EDYCJA 2: (zrzeczenie się: przypuszczenie oparte na faktach poniżej)
Im więcej o tym myślę, tym bardziej myślę, że ta odpowiedź może faktycznie wyjaśniać bardziej dominujący powód tej `` kary '' za błędny fragment a (lub premię za wydajność za fragment b , w zależności od tego, jak o tym myślisz), właśnie dlaczego uważam, że to (fragment a) błąd programistyczny:

Dość kuszące jest założenie, że this.primesjest to „gęsta tablica” czysto numeryczna, która też była

• Zakodowane w dosłowny kodu źródłowego (znany excelent kandydatem do stania się „prawdziwe” array jak wszystko jest już znany kompilator przed kompilacją) LUB
• najprawdopodobniej wygenerowane przy użyciu funkcji numerycznej wypełniającej pre-size ( new Array(/*size value*/)) w rosnącej kolejności sekwencyjnej (kolejny znany od dawna kandydat na tablicę „prawdziwą”).

Wiemy również, że primesdługość tablicy jest buforowana jako prime_count! (wskazując na zamiar i stały rozmiar).

Wiemy również, że większość silników początkowo przekazuje tablice jako kopiowanie przy modyfikacji (w razie potrzeby), co znacznie przyspiesza ich obsługę (jeśli ich nie zmienisz).

Dlatego rozsądnie jest założyć, że Array primesnajprawdopodobniej jest już wewnętrznie zoptymalizowaną tablicą, która nie zmienia się po utworzeniu (łatwe do rozpoznania dla kompilatora, jeśli nie ma kodu modyfikującego tablicę po utworzeniu) i dlatego już jest (jeśli ma zastosowanie do silnik) przechowywany w zoptymalizowany sposób, prawie tak, jakby był plikiem Typed Array.

Jak próbowałem wyjaśnić w moim sumprzykładzie funkcji, argument (y), które są przekazywane, mają duży wpływ na to, co faktycznie musi się wydarzyć i jako takie, jak ten konkretny kod jest kompilowany do kodu maszynowego. Przekazanie Stringdo sumfunkcji nie powinno zmieniać ciągu znaków, ale zmieniać sposób kompilacji funkcji w JIT! Przekazanie tablicy do sumpowinno skompilować inną (być może nawet dodatkową dla tego typu lub „kształt”, jak to nazywają, przekazanego obiektu) wersję kodu maszynowego.

Ponieważ wydaje się nieco bonkus, aby przekonwertować tablicę typu primesArray podobną do Typed_Array w locie na coś_else, podczas gdy kompilator wie, że ta funkcja nawet jej nie zmodyfikuje!

Przy tych założeniach pozostawia 2 opcje:

1. Kompiluj jako analizator liczb, zakładając, że nie ma poza zakresem, napotkaj problem z poza granicami na końcu, przekompiluj i ponów pracę (jak opisano w przykładzie teoretycznym w edycji 1 powyżej)
2. Kompilator już wykrył (lub podejrzewał?) Dostęp z góry poza granicami, a funkcja została skompilowana w JIT tak, jakby przekazany argument był rzadkim obiektem, co skutkowało wolniejszym funkcjonalnym kodem maszynowym (ponieważ miałoby więcej sprawdzeń / konwersji / wymuszeń itp.). Innymi słowy: funkcja nigdy nie kwalifikowała się do pewnych optymalizacji, została skompilowana tak, jakby otrzymywała argument „rzadka tablica” (- jak).

Teraz naprawdę zastanawiam się, który z tych 2 to jest!

Aby dodać do tego trochę naukowego charakteru, oto plik jsperf

https://jsperf.com/ints-values-in-out-of-array-bounds

Testuje przypadek kontrolny tablicy wypełnionej intami i zapętleniem wykonując arytmetykę modularną, pozostając w granicach. Posiada 5 przypadków testowych:

• 1. Wychodzenie poza granice
• 2. Tablice otworów
• 3. Arytmetyka modularna względem NaN
• 4. Całkowicie niezdefiniowane wartości
• 5. Za pomocą new Array()

Pokazuje, że pierwsze 4 przypadki są naprawdę złe dla wydajności. Pętla poza granicami jest nieco lepsza niż pozostałe 3, ale wszystkie 4 są o około 98% wolniejsze niż w najlepszym przypadku.
Obudowa new Array()jest prawie tak dobra jak tablica surowa, tylko kilka procent wolniejsza.