Co sprawia, że ta funkcja działa znacznie wolniej?

Question

Co sprawia, że ta funkcja działa znacznie wolniej?

Próbowałem zrobić eksperyment, aby sprawdzić, czy zmienne lokalne w funkcjach są przechowywane na stosie.

Więc napisałem mały test wydajności

function test(fn, times){
    var i = times;
    var t = Date.now()
    while(i--){
        fn()
    }
    return Date.now() - t;
} 
ene
function straight(){
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    a = a * 5
    b = Math.pow(b, 10)
    c = Math.pow(c, 11)
    d = Math.pow(d, 12)
    e = Math.pow(e, 25)
}
function inversed(){
    var a = 1
    var b = 2
    var c = 3
    var d = 4
    var e = 5
    e = Math.pow(e, 25)
    d = Math.pow(d, 12)
    c = Math.pow(c, 11)
    b = Math.pow(b, 10)
    a = a * 5
}

Spodziewałem się, że funkcja odwrotna będzie działać znacznie szybciej. Zamiast tego wyszedł niesamowity wynik.

Dopóki nie przetestuję jednej z funkcji, działa ona 10 razy szybciej niż po przetestowaniu drugiej.

Przykład:

> test(straight, 10000000)
30
> test(straight, 10000000)
32
> test(inversed, 10000000)
390
> test(straight, 10000000)
392
> test(inversed, 10000000)
390

To samo zachowanie podczas badania w alternatywnej kolejności.

> test(inversed, 10000000)
25
> test(straight, 10000000)
392
> test(inversed, 10000000)
394

Przetestowałem to zarówno w przeglądarce Chrome, jak i w węźle.JS i ja nie mamy pojęcia, dlaczego tak się stało. Efekt trwa do momentu odświeżenia bieżącej strony lub ponownego uruchomienia Node REPL.

Co może być źródłem tak znaczącej (~12 razy gorszej) wydajności?

PS. Ponieważ wydaje się, że działa tylko w niektórych środowiskach, napisz środowisko, którego używasz do testowania.

Moje były:

OS: Ubuntu 14.04
Node v0. 10. 37
Chrome 43.0.2357.134 (Official Build) (64-bit)

/Edit
Na Firefoksie 39 to trwa ~5500 ms dla każdego testu, niezależnie od kolejności. Wydaje się, że występuje tylko na określonych silnikach.

/Edit2
Połączenie funkcji z funkcją testową powoduje, że działa ona zawsze w tym samym czasie.
Czy jest możliwe, że istnieje optymalizacja, która wprowadza parametr funkcji, jeśli zawsze jest to ta sama funkcja?

64

javascript performance v8

Author: Krzysztof Wende, 2015-07-29

Source

3 answers

Nie rozumiesz stosu.

Podczas gdy" prawdziwy " stos rzeczywiście zawiera tylko operacje Push i Pop, tak naprawdę nie dotyczy to rodzaju stosu używanego do wykonywania. Oprócz Push i Pop, Możesz również uzyskać losowy dostęp do dowolnej zmiennej, o ile posiadasz jej adres. Oznacza to, że kolejność miejsc nie ma znaczenia, nawet jeśli kompilator nie zmieni dla Ciebie kolejności. W pseudo-assembly wydaje ci się, że

var x = 1;
var y = 2;

x = x + 1;
y = y + 1;

Tłumaczy się na coś jak

push 1 ; x
push 2 ; y

; get y and save it
pop tmp
; get x and put it in the accumulator
pop a
; add 1 to the accumulator
add a, 1
; store the accumulator back in x
push a
; restore y
push tmp
; ... and add 1 to y

Prawdę mówiąc, prawdziwy kod jest bardziej podobny do tego:

push 1 ; x
push 2 ; y

add [bp], 1
add [bp+4], 1

Gdyby stos wątków naprawdę był prawdziwym, ścisłym stosem, byłoby to niemożliwe, prawda. W takim przypadku kolejność operacji i mieszkańców byłaby ważniejsza niż teraz. Zamiast tego, zezwalając na losowy dostęp do wartości na stosie, oszczędzasz dużo pracy zarówno dla kompilatorów,jak i procesora.

Odpowiadając na twoje pytanie, podejrzewam, że żadna z funkcji nie działa. Jesteś tylko modyfikowanie lokalnych funkcji, a twoje funkcje nic nie zwracają - jest całkowicie legalne, aby kompilator całkowicie porzucił ciała funkcji, a być może nawet wywołania funkcji. Jeśli rzeczywiście tak jest, niezależnie od różnicy wydajności, którą obserwujesz, prawdopodobnie jest to tylko artefakt pomiarowy lub coś związanego z nieodłącznymi kosztami wywołania funkcji / iteracji.

17

Author: Luaan,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-07-29 11:28:12

Połączenie funkcji z funkcją testową powoduje, że działa ona zawsze w tym samym czasie.
Czy jest możliwe, że istnieje optymalizacja, która wprowadza parametr funkcji, jeśli zawsze jest to ta sama funkcja?

Tak, to wydaje się być dokładnie to, co obserwujesz. Jak już wspomniał @Luaan, kompilator prawdopodobnie i tak upuszcza ciała Twoich funkcji straight i inverse, ponieważ nie mają one żadnych skutków ubocznych, a jedynie manipulują niektórymi lokalnymi funkcjami zmienne.

Kiedy wywołujesz test(…, 100000) po raz pierwszy, kompilator optymalizujący uświadamia sobie po kilku iteracjach, że wywołanie fn() jest zawsze takie samo i robi to w linii, unikając kosztownego wywołania funkcji. Wszystko, co teraz robi, to 10 milionów razy zmniejszając zmienną i testując ją przeciwko 0.

Ale kiedy dzwonisz {[6] } z innym fn, to musi się od optymalizacji. Może później zrobić kilka innych optymalizacji ponownie, ale teraz wiedząc, że są dwie różne funkcje, które można nazwać, nie mogą być już wbudowane.

Ponieważ jedyną rzeczą, którą tak naprawdę mierzysz, jest wywołanie funkcji, co prowadzi do poważnych różnic w wynikach.

Eksperyment sprawdzający, czy zmienne lokalne w funkcjach są przechowywane na stosie

Jeśli chodzi o twoje pytanie, nie, pojedyncze zmienne nie są przechowywane na stosie (maszyna stosu ), ale w rejestrach (maszyna rejestru). To nie ma znaczenia w w jakiej kolejności są deklarowane lub używane w twojej funkcji.

[[9]}jednak są one przechowywane na stos, w ramach tzw. "ramek stosowych". Będziesz mieć jedną ramkę na wywołanie funkcji, przechowującą zmienne kontekstu jej wykonania. W Twoim przypadku stos może wyglądać tak:

[straight: a, b, c, d, e]
[test: fn, times, i, t]
…

3

Author: Bergi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-07-29 13:03:18

score 100 · Accepted Answer

Po wywołaniu test z dwoma różnymi funkcjami fn() callsite wewnątrz niego staje się megamorficzny i V8 nie jest w stanie na nim wejść.

Wywołania funkcji (w przeciwieństwie do wywołań metod o.m(...)) W V8 są połączone z jednym elementem inline cache zamiast prawdziwego polimorficznego inline cache.

Ponieważ V8 nie jest w stanie wbudować się w fn() callsite, nie jest w stanie zastosować różnych optymalizacji do Twojego kodu. Jeśli spojrzysz na swój kod w IRHydra (wgrałem artefakty kompilacji do gist dla Twojej wygody) zauważysz, że pierwsza zoptymalizowana wersja test (kiedy była wyspecjalizowana dla fn = straight) ma całkowicie pustą pętlę główną.

V8 właśnie wstawił straighti usunął cały kod, który chciałeś porównać z optymalizacją eliminacji martwego kodu. Na starszej wersji V8 zamiast DCE V8 po prostu wyciągnie kod z pętli przez LICM - ponieważ kod jest całkowicie pętli niezmienny.

Gdy straight nie jest inlined V8 nie może zastosować tych optymalizacji-stąd różnica wydajności. Nowsza wersja V8 nadal będzie stosować DCE do straight i inversed same zamieniając je w puste funkcje

Więc różnica w wydajności nie jest aż tak duża(około 2-3x). Starsze V8 nie było wystarczająco agresywne z DCE - i to przejawiałoby się większą różnicą między inlined i nie-inlined przypadkach, ponieważ szczytowe osiągi inlined przypadek był wyłącznie wynikiem agresywnego loop-invariant code motion (LICM).

To pokazuje, dlaczego benchmarki nigdy nie powinny być pisane w ten sposób - ponieważ ich wyniki nie są użyteczne, ponieważ w końcu mierzysz pustą pętlę.

Jeśli interesuje Cię polimorfizm i jego implikacje w V8 sprawdź mój post "o co chodzi z monomorfizmem" (sekcja "nie wszystkie bufory są takie same" mówi o buforach związanych z wywołaniami funkcji). Polecam również lekturę poprzez jeden z moich rozmów na temat zagrożeń mikrobenchmarkingu, np. najnowszy "Benchmarking JS" rozmowa z GOTO Chicago 2015 ( wideo ) - może pomóc uniknąć typowych pułapek.