Strana performance JavaScript

Question

Quando stavo implementando ChaCha20 in JavaScript, mi sono imbattuto in qualche strano comportamento.

La mia prima versione è stato costruito in questo modo (chiamiamolo "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; 
} 

Per ridurre le chiamate di funzione inutili (con il parametro spese generali, ecc) ho rimosso il quarterRound -funzione e mettere il suo contenuto in linea (è corretto, ho verificato che nei confronti di alcuni vettori di test):

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; 
} 

Ma il risultato prestazioni non era del tutto come previsto:

vs.

Mentre la differenza di prestazioni in Firefox e Safari è neglectible o meno importante il taglio prestazioni in Chrome è ENORME ... Tutte le idee perché questo accade?

PS: Se le immagini sono di piccole dimensioni, aprirli in una nuova scheda :)

PP.S .: Ecco i link:

Inlined

Encapsulated

Answer 1

Regressione succede perché si colpisce un bug in uno dei passaggi nel motore di ottimizzazione attuale del motore V8.

Se si guarda cosa fa l'albero motore al caso "in linea" lento, si noterà che la funzione getBlock è costantemente deoptimizzata.

Per vedere che è possibile passare semplicemente il flag --trace-deopt a V8 e leggere l'output che invia alla console o utilizzare uno strumento chiamato IRHydra.

ho raccolto uscita V8 per entrambi i casi inline e uninlined, è possibile esplorare in IRHydra:

• caso inline: http://mrale.ph/irhydra/2/#gist:1fefdc70567a924d4cf2
• caso incapsulato: http://mrale.ph/irhydra/2/#gist:be3de64f860c78ca640b

ecco quello che si vede per caso "in linea":

Ogni voce nell'elenco delle funzioni è un singolo tentativo di ottimizzazione. Il colore rosso significa che la funzione ottimizzata è stata successivamente deottimizzata perché è stata violata qualche ipotesi fatta da un compilatore ottimizzatore.

Ciò significa che getBlock è costantemente ottimizzato e deottimizzato.Non c'è nulla di simile nel caso "incapsulato":

Qui getBlock è ottimizzato una volta e mai deoptimizes.

Se guardiamo dentro getBlock vedremo che è carico di matrice da Uint32Array che deoptimizes perché conseguenza di questo carico è un valore che non rientra in int32 valore.

Le ragioni di questo deopt sono un po 'contorto. L'unico tipo di numero di JavaScript è un numero in virgola mobile a precisione doppia. Effettuare tutti i calcoli con esso sarebbe alquanto inefficiente, quindi l'ottimizzazione delle JIT di solito cerca di mantenere le vlaue integer rappresentate come interi effettivi all'interno del codice ottimizzato.

La rappresentazione intera più ampia dell'albero motore è int32 e la metà dei valori di uint32 non è rappresentabile in essa. Per mitigare parzialmente questa limitazione, Crankshaft esegue un passaggio di ottimizzazione chiamato analisi uint32. Questo passaggio cerca di capire se è sicuro rappresentare il valore uint32 come valore int32, che viene eseguito osservando come viene utilizzato questo valore uint32: alcune operazioni, ad es. quelli bit a bit, non si preoccupano del "segno" ma solo dei singoli bit, altre operazioni (ad esempio deoptimizzazione o conversione da intero a doppio) possono essere insegnate a gestire int32-that-is-actually-uint32 in un modo speciale. Se l'analisi ha esito positivo - tutti gli usi di un valore uint32 sono sicuri - quindi questa operazione è contrassegnata in un modo speciale, altrimenti (alcuni usi sono ritenuti non sicuri) l'operazione non è contrassegnata e verrà annullata se produce un valore uint32 non adatto nell'intervallo int32 (qualsiasi valore superiore a 0x7fffffff).

In questo caso l'analisi non era marcando x[i] come uint32 funzionamento sicuro - quindi era deoptimizing quando risultato x[i] era fuori int32 gamma. Il motivo per cui non si contrassegnava x[i] come sicuro era perché uno dei suoi usi, un'istruzione artificiale creata da inliner quando era in linea U32TO8_LE, era considerata non sicura. Ecco un patch for V8 che risolve il problema contiene anche una piccola illustrazione del problema:

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(); 

Non eri colpire questo bug nella versione "incapsulato" in quanto proprio inliner di albero motore era a corto di budget prima che raggiungesse U32TO8_LE chiamata luogo. Come si può vedere nella IRHydra solo i primi tre chiamate a quarterRound sono inline:

È possibile risolvere questo bug modificando U32TO8_LE(buffer, 4 * i, x[i]) a U32TO8_LE(buffer, 4 * i, x[i]|0) che rende il solo uso di x[i] valore uint32-safe e non cambia il risultato.