Dziwna wydajność JavaScript

Question

Kiedy wdrażałem ChaCha20 w JavaScript, natknąłem się na dziwne zachowanie.

Moja pierwsza wersja została budować tak (nazwijmy go „Encapsulated Version”):

function quarterRound(x, a, b, c, d) { 
    x[a] += x[b]; x[d] = ((x[d]^x[a]) << 16) | ((x[d]^x[a]) >>> 16); 
    x[c] += x[d]; x[b] = ((x[b]^x[c]) << 12) | ((x[b]^x[c]) >>> 20); 
    x[a] += x[b]; x[d] = ((x[d]^x[a]) << 8) | ((x[d]^x[a]) >>> 24); 
    x[c] += x[d]; x[b] = ((x[b]^x[c]) << 7) | ((x[b]^x[c]) >>> 25); 
} 

function getBlock(buffer) { 
    var x = new Uint32Array(16); 

    for (var i = 16; i--;) x[i] = input[i]; 
    for (var i = 20; i > 0; i -= 2) { 
     quarterRound(x, 0, 4, 8,12); 
     quarterRound(x, 1, 5, 9,13); 
     quarterRound(x, 2, 6,10,14); 
     quarterRound(x, 3, 7,11,15); 
     quarterRound(x, 0, 5,10,15); 
     quarterRound(x, 1, 6,11,12); 
     quarterRound(x, 2, 7, 8,13); 
     quarterRound(x, 3, 4, 9,14); 
    } 
    for (i = 16; i--;) x[i] += input[i]; 
    for (i = 16; i--;) U32TO8_LE(buffer, 4 * i, x[i]); 
    input[12]++; 
    return buffer; 
} 

celu zmniejszenia niepotrzebnych wywołań funkcji (z parametrem napowietrznych itp) usunąłem quarterRound -function i umieścić jego zawartość inline (jest to poprawne, ja zweryfikowane go przed niektórymi wektorów testowych):

function getBlock(buffer) { 
    var x = new Uint32Array(16); 

    for (var i = 16; i--;) x[i] = input[i]; 
    for (var i = 20; i > 0; i -= 2) { 
     x[ 0] += x[ 4]; x[12] = ((x[12]^x[ 0]) << 16) | ((x[12]^x[ 0]) >>> 16); 
     x[ 8] += x[12]; x[ 4] = ((x[ 4]^x[ 8]) << 12) | ((x[ 4]^x[ 8]) >>> 20); 
     x[ 0] += x[ 4]; x[12] = ((x[12]^x[ 0]) << 8) | ((x[12]^x[ 0]) >>> 24); 
     x[ 8] += x[12]; x[ 4] = ((x[ 4]^x[ 8]) << 7) | ((x[ 4]^x[ 8]) >>> 25); 
     x[ 1] += x[ 5]; x[13] = ((x[13]^x[ 1]) << 16) | ((x[13]^x[ 1]) >>> 16); 
     x[ 9] += x[13]; x[ 5] = ((x[ 5]^x[ 9]) << 12) | ((x[ 5]^x[ 9]) >>> 20); 
     x[ 1] += x[ 5]; x[13] = ((x[13]^x[ 1]) << 8) | ((x[13]^x[ 1]) >>> 24); 
     x[ 9] += x[13]; x[ 5] = ((x[ 5]^x[ 9]) << 7) | ((x[ 5]^x[ 9]) >>> 25); 
     x[ 2] += x[ 6]; x[14] = ((x[14]^x[ 2]) << 16) | ((x[14]^x[ 2]) >>> 16); 
     x[10] += x[14]; x[ 6] = ((x[ 6]^x[10]) << 12) | ((x[ 6]^x[10]) >>> 20); 
     x[ 2] += x[ 6]; x[14] = ((x[14]^x[ 2]) << 8) | ((x[14]^x[ 2]) >>> 24); 
     x[10] += x[14]; x[ 6] = ((x[ 6]^x[10]) << 7) | ((x[ 6]^x[10]) >>> 25); 
     x[ 3] += x[ 7]; x[15] = ((x[15]^x[ 3]) << 16) | ((x[15]^x[ 3]) >>> 16); 
     x[11] += x[15]; x[ 7] = ((x[ 7]^x[11]) << 12) | ((x[ 7]^x[11]) >>> 20); 
     x[ 3] += x[ 7]; x[15] = ((x[15]^x[ 3]) << 8) | ((x[15]^x[ 3]) >>> 24); 
     x[11] += x[15]; x[ 7] = ((x[ 7]^x[11]) << 7) | ((x[ 7]^x[11]) >>> 25); 
     x[ 0] += x[ 5]; x[15] = ((x[15]^x[ 0]) << 16) | ((x[15]^x[ 0]) >>> 16); 
     x[10] += x[15]; x[ 5] = ((x[ 5]^x[10]) << 12) | ((x[ 5]^x[10]) >>> 20); 
     x[ 0] += x[ 5]; x[15] = ((x[15]^x[ 0]) << 8) | ((x[15]^x[ 0]) >>> 24); 
     x[10] += x[15]; x[ 5] = ((x[ 5]^x[10]) << 7) | ((x[ 5]^x[10]) >>> 25); 
     x[ 1] += x[ 6]; x[12] = ((x[12]^x[ 1]) << 16) | ((x[12]^x[ 1]) >>> 16); 
     x[11] += x[12]; x[ 6] = ((x[ 6]^x[11]) << 12) | ((x[ 6]^x[11]) >>> 20); 
     x[ 1] += x[ 6]; x[12] = ((x[12]^x[ 1]) << 8) | ((x[12]^x[ 1]) >>> 24); 
     x[11] += x[12]; x[ 6] = ((x[ 6]^x[11]) << 7) | ((x[ 6]^x[11]) >>> 25); 
     x[ 2] += x[ 7]; x[13] = ((x[13]^x[ 2]) << 16) | ((x[13]^x[ 2]) >>> 16); 
     x[ 8] += x[13]; x[ 7] = ((x[ 7]^x[ 8]) << 12) | ((x[ 7]^x[ 8]) >>> 20); 
     x[ 2] += x[ 7]; x[13] = ((x[13]^x[ 2]) << 8) | ((x[13]^x[ 2]) >>> 24); 
     x[ 8] += x[13]; x[ 7] = ((x[ 7]^x[ 8]) << 7) | ((x[ 7]^x[ 8]) >>> 25); 
     x[ 3] += x[ 4]; x[14] = ((x[14]^x[ 3]) << 16) | ((x[14]^x[ 3]) >>> 16); 
     x[ 9] += x[14]; x[ 4] = ((x[ 4]^x[ 9]) << 12) | ((x[ 4]^x[ 9]) >>> 20); 
     x[ 3] += x[ 4]; x[14] = ((x[14]^x[ 3]) << 8) | ((x[14]^x[ 3]) >>> 24); 
     x[ 9] += x[14]; x[ 4] = ((x[ 4]^x[ 9]) << 7) | ((x[ 4]^x[ 9]) >>> 25); 
    } 
    for (i = 16; i--;) x[i] += input[i]; 
    for (i = 16; i--;) U32TO8_LE(buffer, 4 * i, x[i]); 
    input[12]++; 
    return buffer; 
} 

Ale wynik występ był nie całkiem zgodnie z oczekiwaniami:

vs.

Chociaż różnica wydajności w Firefoksie i Safari jest neglectible lub nie ważna jest wydajność cięcia pod Chrome jest ogromny ... Jakieś pomysły dlaczego tak się dzieje?

PS: Jeśli obrazy są małe, otworzyć je w nowej karcie :)

PP.S .: Oto linki:

Inlined

Encapsulated

Answer 1

regresji dzieje się, ponieważ trafiłeś błąd w jednym z przebiegów w aktualnym kompilatorze optymalizacji V8 Crankshaft.

Jeśli spojrzysz na to, co robi wał korbowy w powolnym "liniowym" przypadku, zauważysz, że funkcja getBlock nieustannie dezoptymalizuje.

Aby zobaczyć, że można po prostu przekazać flagę --trace-deopt do V8 i odczytać dane wyjściowe zrzucane na konsolę lub użyć narzędzia o nazwie IRHydra.

Zebrałem wyjście V8 dla obu włączonych i uninlined przypadkach można zbadać w IRHydra:

• inlined sprawy: http://mrale.ph/irhydra/2/#gist:1fefdc70567a924d4cf2
• zamknięty case: http://mrale.ph/irhydra/2/#gist:be3de64f860c78ca640b

Oto co pokazuje na "Inline":

Każdy wpis na liście funkcji jest pojedynczą próbą optymalizacji. Kolor czerwony oznacza, że ​​zoptymalizowana funkcja została później zdereoptymowana, ponieważ zostały naruszone niektóre założenia dokonane przez kompilator optymalizujący.

Oznacza to, że getBlock jest stale optymalizowany i zdefragmentowany.Nie ma nic takiego w „kapsułkach” sprawy:

Tutaj getBlock jest zoptymalizowany raz i nigdy deoptimizes.

Jeśli spojrzymy wewnątrz getBlock widzimy, że jest to obciążenie tablica z Uint32Array że deoptimizes ponieważ skutkiem tego obciążenia jest wartością, która nie pasuje do int32 wartości.

Przyczyny tego deopt są trochę skomplikowane. Jedynym typem liczby JavaScript jest liczba zmiennoprzecinkowa podwójnej precyzji. Wykonanie z nim wszystkich obliczeń byłoby nieco nieefektywne, więc optymalizacja JIT zwykle stara się utrzymywać liczby całkowite reprezentowane jako rzeczywiste liczby całkowite w zoptymalizowanym kodzie.

Najszersza reprezentacja liczby całkowitej wału korbowego to int32, a połowa wartości uint32 nie może być reprezentowana w tej wartości. Aby częściowo ograniczyć to ograniczenie, wał korbowy wykonuje test optymalizacji o nazwie analiza uint32. Ta przepustka próbuje ustalić, czy można bezpiecznie reprezentować wartość uint32 jako wartość int32 - co można uzyskać, analizując, w jaki sposób jest używana ta wartość: niektóre operacje, na przykład: bitowe, nie troszcz się o "znak", ale tylko o pojedyncze bity, inne operacje (na przykład deoptimizacja lub konwersja z liczby całkowitej na podwójną) mogą być nauczone, aby obsłużyć int32-to-jest-faktycznie-uint32 w specjalny sposób. Jeśli analiza się powiedzie - wszystkie zastosowania wartości uint32 są bezpieczne - wtedy ta operacja jest oznaczona w specjalny sposób, w przeciwnym razie (niektóre zastosowania zostaną uznane za niebezpieczne) operacja nie zostanie oznaczona i zostanie zdefragmentowana, jeśli wygeneruje wartość uint32, która nie pasuje w zakresie int32 (cokolwiek powyżej 0x7fffffff).

W tym przypadku analizy nie było oznakowanie x[i] jako bezpieczny uint32 pracy - tak było deoptimizing gdy wynik x[i] był poza int32 zakresie. Przyczyną niezałatwienia oznaczenia x[i] jako bezpiecznego było to, że jedno z jego zastosowań, sztuczna instrukcja utworzona przez inliner podczas wstawiania U32TO8_LE, została uznana za niebezpieczną. Oto patch for V8 że rozwiązuje problem zawiera także małą ilustrację problemu:

var u32 = new Uint32Array(1); 
u32[0] = 0xFFFFFFFF; // this uint32 value doesn't fit in int32 

function tr(x) { 
    return x|0; 
    //  ^^^ - this use is uint32-safe 
} 
function ld() { 
    return tr(u32[0]); 
    // ^^^^^^^ uint32 op, will deopt if uses are not safe 
    //  | 
    //  \--- tr is inlined into ld and an hidden artificial 
    //   HArgumentObject instruction was generated that 
    //   captured values of all parameters at entry (x) 
    //   This instruction was considered uint32-unsafe 
    //   by oversight. 
} 

while (...) ld(); 

Nie były trafienia ten błąd w „kapsułkach” wersji, ponieważ własny Inliner wał korbowy został uruchomiony z budżetu, zanim osiągnął U32TO8_LE połączenia teren. Jak widać w IRHydra tylko trzy pierwsze rozmowy do quarterRound są inlined:

Można obejść ten problem poprzez zmianę U32TO8_LE(buffer, 4 * i, x[i]) do U32TO8_LE(buffer, 4 * i, x[i]|0) co sprawia, że ​​tylko zastosowanie x[i] wartości UInt32 bezpieczny i nie zmienia wynik.