Seltsame JavaScript-Leistung

Question

Als ich ChaCha20 in JavaScript implementierte, stolperte ich über seltsames Verhalten.

Meine erste Version wie dieses bauen wurde (nennen wir es „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; 
} 

unnötige Funktionsaufrufe zu reduzieren (mit dem Parameter Overhead etc.) Ich entfernte die quarterRound -function und legte seinen Inhalt Inline (es ist richtig, ich es gegen einige Testvektoren überprüft):

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

Aber die Leistung Ergebnis war nicht ganz wie erwartet:

gegen

Während der Performance-Unterschied unter Firefox und Safari ist vernachlässigbar oder nicht wichtig, die Leistung Schnitt unter Chrome ist riesig ... Irgendwelche Ideen, warum dies geschieht?

PS: Wenn die Bilder zu klein sind, öffnen Sie sie in einem neuen Tab :)

PP.S .: Hier sind die Links:

Inlined

Encapsulated

Answer 1

Regression passiert, weil Sie einen Fehler in einem der Durchgänge in V8's aktuellen optimierenden Compiler Crankshaft getroffen haben.

Wenn Sie sich ansehen, was die Kurbelwelle mit dem langsamen "Inline" -Fall macht, werden Sie bemerken, dass die getBlock-Funktion ständig die Optimierung durchführt.

Um zu sehen, dass Sie entweder einfach --trace-deopt Flag an V8 übergeben und lesen Sie die Ausgabe, die es auf die Konsole ablädt oder verwenden Sie ein Tool mit der Bezeichnung IRHydra.

sammelte ich V8 Ausgang für beide inlined und uninlined Fällen können Sie in IRHydra erkunden:

• inlined Fall: http://mrale.ph/irhydra/2/#gist:1fefdc70567a924d4cf2
• verkapselt Fall: http://mrale.ph/irhydra/2/#gist:be3de64f860c78ca640b

Hier ist, was es zeigt für "inlined" Gehäuse:

Jeder Eintrag in der Funktionsliste ist ein einzelner Optimierungsversuch. Rote Farbe bedeutet, dass die optimierte Funktion später nicht optimiert wurde, da einige Annahmen, die von einem optimierenden Compiler gemacht wurden, verletzt wurden.

Das bedeutet getBlock wird ständig optimiert und deoptimiert.Es gibt nichts Vergleichbares in der „gekapselten“ Fall:

Hier getBlock einmal optimiert und nie deoptimizes.

Wenn wir innerhalb getBlock schauen wir werden sehen, dass es Array Last von Uint32Array ist die deoptimizes weil aufgrund dieser Belastung ein Wert ist, der nicht in int32 Wert passt.

Die Gründe für diese deopt sind ein bisschen gewunden. Der einzige Zahlentyp von JavaScript ist eine Fließkommazahl mit doppelter Genauigkeit. Alle Berechnungen damit durchzuführen wäre etwas ineffizient, so dass Optimierungs-JITs normalerweise versuchen, ganzzahlige Werte als tatsächliche Ganzzahlen innerhalb des optimierten Codes darzustellen.

Die breiteste ganzzahlige Darstellung der Kurbelwelle ist int32 und die Hälfte der uint32 Werte sind nicht darstellbar. Um diese Einschränkung teilweise zu mindern, führt die Kurbelwelle einen Optimierungsdurchlauf mit der Bezeichnung uint32 Analyse durch. Dieser Durchlauf versucht herauszufinden, ob es sicher ist, einen Wert von uint32 als einen int32 Wert darzustellen - was durch Betrachten durchgeführt wird, wie dieser uint32 Wert verwendet wird: einige Operationen, z. bitweise, interessieren sich nicht für das "Zeichen", sondern nur für einzelne Bits, andere Operationen (z. B. Deoptimisierung oder Umwandlung von Ganzzahl zu Doppel) können gelehrt werden, um int32-das-ist-eigentlich-uint32 in einer speziellen Weise zu behandeln. Wenn die Analyse erfolgreich ist - alle Verwendungen eines uint32 Wertes sind sicher - dann wird dieser Vorgang auf eine spezielle Weise markiert, andernfalls (einige Verwendungen sind unsicher) ist der Vorgang nicht markiert und wird deaktiviert, wenn uint32 Wert erzeugt wird, der nicht passt in int32 Bereich (alles über 0x7fffffff).

In diesem Fall Analyse wurde Markierung nicht x[i] als sicherer uint32 Betrieb - so war es deoptimizing als Ergebnis von x[i] außerhalb int32 Bereichs lag. Der Grund dafür, x[i] nicht als sicher zu markieren, war, dass einer seiner Verwendungen, ein künstlicher Befehl, der von Inliner beim Inlining U32TO8_LE erstellt wurde, als unsicher angesehen wurde. Hier ist ein patch for V8, der das Problem behebt es auch eine kleine Darstellung der Frage enthält:

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

Sie haben nicht diesen Fehler in „verkapselt“ -Version schlagen, weil Kurbelwelle eigenen Inliner aus Budget ausgeführt wurde, bevor es U32TO8_LE Anruf erreicht Seite? ˅. Wie Sie sehen können in IRHydra nur die ersten drei Anrufe quarterRound sind inlined: diesen Fehler

Sie durch Ändern U32TO8_LE(buffer, 4 * i, x[i]) zu U32TO8_LE(buffer, 4 * i, x[i]|0) umgehen kann, die die einzige Verwendung von x[i] Wert uint32 sicher und ändert sich nicht, macht die Ergebnis.