Warum ist <= langsamer als <bei Verwendung dieses Code-Snippets in V8?

166

Ich lese die Folien Breaking the Javascript Speed ​​Limit mit V8 , und es gibt ein Beispiel wie den folgenden Code. Ich kann nicht herausfinden, warum <=es langsamer ist als <in diesem Fall. Kann das jemand erklären? Kommentare sind willkommen.

Langsam:

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

(Hinweis: Primzahlen sind ein Array mit der Länge prime_count)

Schneller:

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

[Weitere Informationen] Die Geschwindigkeitsverbesserung ist signifikant. In meinem lokalen Umgebungstest sind die Ergebnisse wie folgt:

V8 version 7.3.0 (candidate) 

Langsam:

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

Schneller:

time d8 prime.js
287107
1.82 user 
0.01 system 
0:01.84 elapsed
Leonardo Physh
quelle
10
@DacreDenny Die Rechenschwierigkeiten von <=und <sind sowohl in der Theorie als auch in der tatsächlichen Implementierung in allen modernen Prozessoren (und Interpreten) identisch.
TypeIA
1
Ich habe das Dokument gelesen. Es gibt einen mainCode, der diese Funktion in einer Schleife aufruft, die 25000mal ausgeführt wird. Sie führen also insgesamt viel weniger Iterationen durch, um diese Änderung vorzunehmen . Wenn ein Array eine Länge von 5 hat, array[5]überschreitet der Versuch, es zu erhalten , sein Limit und gibt einen undefinedWert an, da Arrays mit der Indizierung beginnen 0.
Shidersz
1
Es wäre hilfreich, wenn diese Frage erklären würde, wie viel Geschwindigkeitsverbesserung erzielt wird (z. B. fünfmal schneller), damit die Leute nicht durch die zusätzliche Iteration abgeworfen werden. Ich habe versucht herauszufinden, wie schnell die Folien sind, aber es gab viele und ich hatte Probleme, sie zu finden, sonst würde ich sie selbst bearbeiten.
Captain Man
@CaptainMan Sie haben Recht, die genaue Geschwindigkeitsverbesserung lässt sich nur schwer aus den Folien ableiten, da sie mehrere verschiedene Probleme gleichzeitig abdecken. In meinem Gespräch mit dem Redner nach diesem Vortrag bestätigte er jedoch, dass es sich nicht nur um einen winzigen Bruchteil eines Prozent handelt, wie Sie es von der einen zusätzlichen Iteration in diesem Testfall erwarten können, sondern um einen großen Unterschied: um ein Vielfaches schneller, vielleicht um eine Bestellung von Größe oder mehr. Der Grund dafür ist, dass V8 auf das nicht optimierte Array-Format zurückgreift (oder damals zurückfiel), wenn Sie versuchen, außerhalb der Array-Grenzen zu lesen.
Michael Geary
3
Es kann nützlich sein, eine Version zu vergleichen <=, die dies <tut , sich aber ansonsten identisch mit der Version verhält i <= this.prime_count - 1. Dies löst sowohl das Problem "zusätzliche Iteration" als auch das Problem "nach dem Ende des Arrays".
TheHansinator

Antworten:

132

Ich arbeite bei Google an V8 und wollte zusätzlich zu den vorhandenen Antworten und Kommentaren zusätzliche Einblicke gewähren.

Als Referenz finden Sie hier das vollständige Codebeispiel aus den Folien :

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

In erster Linie hat der Leistungsunterschied nichts mit den Operatoren <und <=direkt zu tun . Also bitte nicht durch die Reifen springen, nur um <=in deinem Code zu vermeiden , weil du bei Stack Overflow gelesen hast, dass es langsam ist - es ist nicht!


Zweitens wiesen die Leute darauf hin, dass das Array "löchrig" ist. Dies wurde aus dem Code-Snippet in OPs Beitrag nicht deutlich, aber es ist klar, wenn Sie sich den Code ansehen, der initialisiert wird this.primes:

this.primes = new Array(iterations);

Dies führt zu einem Array mit einer HOLEYElementart in V8, selbst wenn das Array vollständig gefüllt / gepackt / zusammenhängend ist. Im Allgemeinen sind Operationen an löchrigen Arrays langsamer als Operationen an gepackten Arrays, aber in diesem Fall ist der Unterschied vernachlässigbar: Es beträgt 1 zusätzliche Smi- Prüfung ( kleine Ganzzahl ) (zum Schutz vor Löchern) jedes Mal, wenn wir this.primes[i]in der Schleife innerhalb treffen isPrimeDivisible. Keine große Sache!

TL; DR Das Array HOLEYist hier nicht das Problem.


Andere wiesen darauf hin, dass der Code außerhalb der Grenzen liest. Es wird allgemein empfohlen, das Lesen über die Länge von Arrays hinaus zu vermeiden. In diesem Fall hätte dies tatsächlich den massiven Leistungsabfall vermieden. Aber warum? V8 kann einige dieser Out-of-Bound-Szenarien mit nur geringen Auswirkungen auf die Leistung verarbeiten. Was ist dann das Besondere an diesem speziellen Fall?

Das Lesen außerhalb der Grenzen führt dazu, this.primes[i]dass Sie sich undefinedin dieser Zeile befinden:

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

Und das bringt uns zum eigentlichen Problem : Der %Operator wird jetzt mit nicht ganzzahligen Operanden verwendet!

  • integer % someOtherIntegerkann sehr effizient berechnet werden; JavaScript-Engines können für diesen Fall hochoptimierten Maschinencode erzeugen.

  • integer % undefinedAuf der anderen Seite ist dies weitaus weniger effizient Float64Mod, da undefinedes sich um ein Doppel handelt.

Das Code-Snippet kann in der Tat verbessert werden, indem das <=in <in diese Zeile geändert wird:

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

... nicht weil <=es irgendwie ein überlegener Operator ist als <, sondern nur weil dies die in diesem speziellen Fall gelesenen Out-of-Bounds vermeidet.

Mathias Bynens
quelle
1
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Samuel Liew
1
Um 100% vollständig zu sein, wird der verschlüsselte Last-IC für this.primes [i] in isPrimeDivisible in V8 unerwartet megamorph. Das scheint ein Fehler zu sein: bugs.chromium.org/p/v8/issues/detail?id=8561
Mathias Bynens
226

Andere Antworten und Kommentare erwähnen, dass der Unterschied zwischen den beiden Schleifen darin besteht, dass die erste eine Iteration mehr ausführt als die zweite. Dies ist wahr, aber in einem Array, das auf 25.000 Elemente anwächst, würde eine Iteration mehr oder weniger nur einen winzigen Unterschied bewirken. Wenn wir davon ausgehen, dass die durchschnittliche Länge während des Wachstums 12.500 beträgt, sollte der Unterschied, den wir erwarten könnten, bei 1/12500 oder nur 0,008% liegen.

Der Leistungsunterschied ist hier viel größer als dies durch diese eine zusätzliche Iteration erklärt werden würde, und das Problem wird gegen Ende der Präsentation erklärt.

this.primes ist ein zusammenhängendes Array (jedes Element enthält einen Wert) und die Elemente sind alle Zahlen.

Eine JavaScript-Engine kann ein solches Array so optimieren, dass es ein einfaches Array tatsächlicher Zahlen ist, anstatt eines Arrays von Objekten, die zufällig Zahlen enthalten, aber andere Werte oder keinen Wert enthalten können. Der Zugriff auf das erste Format ist viel schneller: Es benötigt weniger Code und das Array ist viel kleiner, sodass es besser in den Cache passt. Es gibt jedoch einige Bedingungen, die die Verwendung dieses optimierten Formats verhindern können.

Eine Bedingung wäre, wenn einige der Array-Elemente fehlen. Beispielsweise:

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

Was ist nun der Wert von a[1]? Es hat keinen Wert . (Es ist nicht einmal richtig zu sagen, dass es den Wert hat undefined- ein Array-Element, das das enthältundefined Wert enthält, unterscheidet sich von einem Array-Element, das vollständig fehlt.)

Es gibt keine Möglichkeit, dies nur mit Zahlen darzustellen, daher muss die JavaScript-Engine das weniger optimierte Format verwenden. Wenn a[1]das Array wie die beiden anderen Elemente einen numerischen Wert enthält, kann es möglicherweise nur in ein Array von Zahlen optimiert werden.

Ein weiterer Grund dafür, dass ein Array in das deoptimierte Format gezwungen wird, kann sein, dass Sie versuchen, auf ein Element außerhalb der Grenzen des Arrays zuzugreifen, wie in der Präsentation erläutert.

Die erste Schleife mit <=Versuchen, ein Element nach dem Ende des Arrays zu lesen. Der Algorithmus funktioniert immer noch korrekt, da in der letzten zusätzlichen Iteration:

  • this.primes[i]wird ausgewertet, undefinedweil idas Array-Ende überschritten ist.
  • candidate % undefined(für jeden Wert von candidate) ergibt NaN.
  • NaN == 0bewertet zu false.
  • Daher wird das return truenicht ausgeführt.

Es ist also so, als ob die zusätzliche Iteration nie stattgefunden hätte - sie hat keine Auswirkungen auf den Rest der Logik. Der Code erzeugt das gleiche Ergebnis wie ohne die zusätzliche Iteration.

Um dorthin zu gelangen, wurde versucht, ein nicht vorhandenes Element nach dem Ende des Arrays zu lesen. Dies zwingt das Array aus der Optimierung heraus - oder zumindest zum Zeitpunkt dieses Gesprächs.

Die zweite Schleife mit < schreibgeschützten Elementen, die im Array vorhanden sind, ermöglicht ein optimiertes Array und einen optimierten Code.

Das Problem wird auf den Seiten 90 bis 91 des Vortrags beschrieben, mit entsprechenden Diskussionen auf den Seiten davor und danach.

Ich habe gerade an dieser Google I / O-Präsentation teilgenommen und danach mit dem Sprecher (einem der V8-Autoren) gesprochen. Ich hatte in meinem eigenen Code eine Technik verwendet, die das Lesen über das Ende eines Arrays hinaus als fehlgeleiteten (im Nachhinein) Versuch beinhaltete, eine bestimmte Situation zu optimieren. Er bestätigte, dass wenn Sie versuchen würden, sogar über das Ende eines Arrays hinaus zu lesen , dies die Verwendung des einfachen optimierten Formats verhindern würde.

Wenn das, was der V8-Autor gesagt hat, immer noch wahr ist, würde das Lesen über das Ende des Arrays hinaus verhindern, dass es optimiert wird, und es müsste auf das langsamere Format zurückgreifen.

Jetzt ist es möglich, dass V8 in der Zwischenzeit verbessert wurde, um diesen Fall effizient zu behandeln, oder dass andere JavaScript-Engines anders damit umgehen. Ich weiß nicht so oder so, aber über diese Deoptimierung sprach die Präsentation.

Michael Geary
quelle
1
Ich bin mir ziemlich sicher, dass das Array immer noch zusammenhängend ist - es gibt keinen Grund, das Speicherlayout zu ändern. Was jedoch wichtig ist, ist, dass die Überprüfung des Indexzugriffs im Eigenschaftszugriff nicht wegoptimiert werden kann und der Code manchmal undefinedanstelle einer Zahl eingegeben wird, die zu einer anderen Berechnung führt.
Bergi
1
@Bergi Ich bin kein JS / V8-Experte, aber Objekte in GC-Sprachen verweisen fast immer auf die tatsächlichen Objekte. Diese tatsächlichen Objekte haben eine unabhängige Zuordnung, auch wenn die Referenzen zusammenhängend sind, da die Lebensdauer des GC-Objekts nicht miteinander verbunden ist. Optimierer können diese unabhängigen Zuordnungen so packen, dass sie benachbart sind, aber (a) der Speicher verwendet Skyrockets und (b) Sie haben zwei zusammenhängende Blöcke, über die iteriert wird (die Referenzen und die Daten, auf die Bezug genommen wird), anstatt eines. Ich nehme an, ein verrückter Optimierer könnte die Referenzen und die Daten, auf die verwiesen wird, verschachteln und ein Array haben, das Speicherstreifen besitzt ...
Yakk - Adam Nevraumont
1
@Bergi Das Array kann im nicht optimierten Fall noch zusammenhängend sein, aber die Array-Elemente sind nicht vom gleichen Typ wie im optimierten Fall. Die optimierte Version ist eine einfache Reihe von Zahlen ohne zusätzliche Flusen. Die nicht optimierte Version ist ein Array von Objekten (ein internes Objektformat, kein JavaScript Object), da jede Mischung von Datentypen im Array unterstützt werden muss. Wie oben erwähnt, hat der Code in der Schleife, die eingespeist undefinedwird, keinen Einfluss auf die Richtigkeit des Algorithmus - er ändert die Berechnung überhaupt nicht (es ist, als ob die zusätzliche Iteration nie stattgefunden hätte).
Michael Geary
3
@Bergi Der V8-Autor, der diesen Vortrag gehalten hat, sagte, dass der Versuch, außerhalb der Array-Grenzen zu lesen, dazu führt, dass das Array so behandelt wird, als hätte es eine Mischung von Typen: Anstelle des optimierten Nur-Zahlen-Formats wird das Array wieder auf optimiert das generische Format. Im optimierten Fall handelt es sich um ein einfaches Array von Zahlen, wie Sie es in einem C-Programm verwenden können. Im deoptimierten Fall handelt es sich um ein Array von ValueObjekten, die Verweise auf Werte eines beliebigen Typs enthalten können. (Ich habe den Namen erfunden Value, aber der Punkt ist, dass die Array-Elemente nicht nur einfache Zahlen sind, sondern Objekte, die Zahlen oder andere Typen umschließen.)
Michael Geary
3
Ich arbeite an V8. Das betreffende Array wird als markiert markiert, HOLEYweil es mit erstellt wurde new Array(n)(obwohl dieser Teil des Codes im OP nicht sichtbar war). HOLEYArrays bleiben HOLEYin V8 für immer erhalten , auch wenn sie später gefüllt werden. Das Array, das löchrig ist, ist in diesem Fall jedoch nicht der Grund für das Perf-Problem. Es bedeutet nur, dass wir bei jeder Iteration einen zusätzlichen Smi-Check durchführen müssen (um sich vor Löchern zu schützen), was keine große Sache ist.
Mathias Bynens
19

TL; DR Die langsamere Schleife ist auf den Zugriff auf das Array außerhalb der Grenzen zurückzuführen, wodurch die Engine entweder gezwungen wird, die Funktion mit weniger oder gar keinen Optimierungen neu zu kompilieren, oder die Funktion zunächst nicht mit einer dieser Optimierungen zu kompilieren ( Wenn der (JIT-) Compiler diesen Zustand vor der ersten Kompilierungsversion erkannt / vermutet hat, lesen Sie weiter unten, warum;


Jemand hat gerade hat , dies zu sagen (ganz erstaunt niemand bereits getan haben):
Früher gab es eine Zeit , in der das Snippet des OP wäre eine de-facto - Beispiel in einem Anfänger Programmierung Buch Umriss bestimmt sein / betonen , dass ‚Arrays‘ in Javascript indexierten Ausgangs sind bei 0, nicht 1, und als solches als Beispiel für einen häufigen "Anfängerfehler" verwendet werden (lieben Sie es nicht, wie ich den Ausdruck "Programmierfehler" vermieden habe ;)): Außerhalb der Grenzen Array-Zugriff .

Beispiel 1:
a Dense Array(zusammenhängend (bedeutet keine Lücken zwischen den Indizes) UND tatsächlich ein Element an jedem Index) von 5 Elementen unter Verwendung einer 0-basierten Indizierung (immer in 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



Wir sprechen also nicht wirklich über Leistungsunterschiede zwischen <vs <=(oder "eine zusätzliche Iteration"), aber wir sprechen über:
"Warum läuft das richtige Snippet (b) schneller als das fehlerhafte Snippet (a)"?

Die Antwort ist zweifach (obwohl aus Sicht eines ES262-Sprachimplementierers beide Formen der Optimierung sind):

  1. Datendarstellung: Wie wird das Array intern im Speicher dargestellt / gespeichert (Objekt, Hashmap, 'reales' numerisches Array usw.)?
  2. Funktionaler Maschinencode: Kompilieren des Codes, der auf diese 'Arrays' zugreift / sie handhabt (liest / ändert).

Punkt 1 wird durch die akzeptierte Antwort ausreichend (und meiner Meinung nach korrekt) erklärt , aber das verbraucht nur 2 Wörter ('der Code') Punkt 2: Zusammenstellung .

Genauer gesagt: JIT-Compilation und vor allem JIT- RE- Compilation!

Die Sprachspezifikation ist im Grunde nur eine Beschreibung einer Reihe von Algorithmen ("Schritte zur Erzielung eines definierten Endergebnisses"). Wie sich herausstellt, ist dies eine sehr schöne Art, eine Sprache zu beschreiben. Die eigentliche Methode, mit der eine Engine bestimmte Ergebnisse erzielt, bleibt den Implementierern offen. Dies bietet ausreichend Gelegenheit, effizientere Methoden zur Erstellung definierter Ergebnisse zu entwickeln. Ein spezifikationskonformer Motor sollte spezifikationskonforme Ergebnisse für jede definierte Eingabe liefern.

Jetzt, da Javascript-Code / Bibliotheken / Nutzung zunimmt und sich daran erinnert, wie viel Ressourcen (Zeit / Speicher / usw.) ein "echter" Compiler verbraucht, ist es klar, dass Benutzer, die eine Webseite besuchen, nicht so lange warten können (und diese benötigen) so viele Ressourcen zur Verfügung zu haben).

Stellen Sie sich die folgende einfache Funktion vor:

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

Perfekt klar, oder? Benötigt keine zusätzliche Klarstellung, oder? Der Rückgabetyp istNumber , richtig?
Nun ... nein, nein & nein ... Es hängt davon ab, welches Argument Sie an den benannten Funktionsparameter übergeben 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)

Sehen Sie das Problem? Dann denken Sie daran, dass dies kaum die massiven möglichen Permutationen abkratzt ... Wir wissen nicht einmal, welche Art von TYP die Funktion RETURN ist, bis wir fertig sind ...

Stellen Sie sich nun dieselbe Funktion vor: Code tatsächlich auf verschiedenen Typen oder auch Variationen von Eingabe verwendet werden, die beide vollständig wahrsten Sinne des Wortes (im Quellcode) beschrieben und dynamisch-Programm generiert ‚Arrays‘ ..

Also, wenn Sie Funktion kompilieren würden sum NUR EINMAL , kann der einzige Weg, der immer das spezifikationsdefinierte Ergebnis für alle Arten von Eingaben zurückgibt, natürlich nur durch Ausführen ALLER spezifikationsbedingten Haupt- UND Unterschritte spezifikationskonforme Ergebnisse garantieren (wie ein unbenannter Pre-Y2K-Browser). Es verbleiben keine Optimierungen (weil keine Annahmen) und eine absolut langsam interpretierte Skriptsprache.

JIT-Compilation (JIT wie in Just In Time) ist die derzeit beliebte Lösung.

Sie beginnen also mit dem Kompilieren der Funktion unter Verwendung von Annahmen darüber, was sie tut, zurückgibt und akzeptiert.
Sie prüfen so einfach wie möglich, ob die Funktion möglicherweise nicht spezifikationskonforme Ergebnisse zurückgibt (z. B. weil sie unerwartete Eingaben erhält). Werfen Sie dann das zuvor kompilierte Ergebnis weg und kompilieren Sie es erneut, um zu entscheiden, was mit dem bereits vorhandenen Teilergebnis geschehen soll (ist es gültig, vertrauenswürdig zu sein oder erneut zu berechnen, um sicherzugehen), binden Sie die Funktion wieder in das Programm ein und Versuch es noch einmal. Letztendlich wird auf die schrittweise Skriptinterpretation wie in der Spezifikation zurückgegriffen.

All dies braucht Zeit!

Alle Browser arbeiten an ihren Engines. Für jede Unterversion werden sich die Dinge verbessern und zurückbilden. Strings waren irgendwann in der Geschichte wirklich unveränderliche Strings (daher war array.join schneller als String-Verkettung), jetzt verwenden wir Seile (oder ähnliches), die das Problem lindern. Beide liefern spezifikationskonforme Ergebnisse und darauf kommt es an!

Lange Rede, kurzer Sinn: Nur weil die Semantik der Sprache von Javascript uns oft den Rücken gekehrt hat (wie bei diesem stillen Fehler im Beispiel des OP), bedeutet dies nicht, dass 'dumme' Fehler unsere Chancen erhöhen, dass der Compiler schnellen Maschinencode ausspuckt. Es wird davon ausgegangen, dass wir die 'normalerweise' korrekten Anweisungen geschrieben haben: Das aktuelle Mantra, das wir 'Benutzer' (der Programmiersprache) haben müssen, lautet: Helfen Sie dem Compiler, beschreiben Sie, was wir wollen, bevorzugen Sie gängige Redewendungen (nehmen Sie Hinweise von asm.js für ein grundlegendes Verständnis welche Browser versuchen können zu optimieren und warum).

Aus diesem Grund ist es wichtig, über Leistung zu sprechen, ABER AUCH ein Minenfeld (und wegen dieses Minenfeldes möchte ich wirklich damit enden, auf relevantes Material zu verweisen (und es zu zitieren):

Der Zugriff auf nicht vorhandene Objekteigenschaften und Array-Elemente außerhalb der Grenzen gibt den undefinedWert zurück, anstatt eine Ausnahme auszulösen. Diese dynamischen Funktionen machen das Programmieren in JavaScript bequem, erschweren aber auch das Kompilieren von JavaScript zu effizientem Maschinencode.

...

Eine wichtige Voraussetzung für eine effektive JIT-Optimierung ist, dass Programmierer die dynamischen Funktionen von JavaScript systematisch nutzen. Beispielsweise nutzen JIT-Compiler die Tatsache, dass Objekteigenschaften häufig zu einem Objekt eines bestimmten Typs in einer bestimmten Reihenfolge hinzugefügt werden oder dass Array-Zugriffe außerhalb der Grenzen selten auftreten. JIT-Compiler nutzen diese Regelmäßigkeitsannahmen, um zur Laufzeit effizienten Maschinencode zu generieren. Wenn ein Codeblock die Annahmen erfüllt, führt die JavaScript-Engine effizienten, generierten Maschinencode aus. Andernfalls muss die Engine auf langsameren Code oder auf die Interpretation des Programms zurückgreifen.

Quelle:
"JITProf: Auffinden von JIT-unfreundlichem JavaScript-Code"
Berkeley-Veröffentlichung, 2014, von Liang Gong, Michael Pradel, Koushik Sen.
http://software-lab.org/publications/jitprof_tr_aug3_2014.pdf

ASM.JS (mag auch keinen Off-Bound-Array-Zugriff):

Vorzeitige Zusammenstellung

Da asm.js eine strikte Teilmenge von JavaScript ist, definiert diese Spezifikation nur die Validierungslogik - die Ausführungssemantik ist einfach die von JavaScript. Validierte asm.js können jedoch vorab kompiliert werden (AOT). Darüber hinaus kann der von einem AOT-Compiler generierte Code sehr effizient sein und Folgendes umfassen:

  • Unboxed-Darstellungen von Ganzzahlen und Gleitkommazahlen;
  • Fehlen von Laufzeit-Typprüfungen;
  • Fehlen einer Müllabfuhr; und
  • Effiziente Heap-Ladevorgänge und -Speicher (wobei die Implementierungsstrategien je nach Plattform variieren).

Code, der nicht validiert werden kann, muss mit herkömmlichen Mitteln, z. B. Interpretation und / oder Just-in-Time-Kompilierung (JIT), auf die Ausführung zurückgreifen.

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

und schließlich https://blogs.windows.com/msedgedev/2015/05/07/bringing-asm-js-to-chakra-microsoft-edge/
, wo es einen kleinen Unterabschnitt über die internen Leistungsverbesserungen des Motors beim Entfernen von Grenzen gibt. check (während nur der Bounds-Check außerhalb der Schleife angehoben wurde, wurde bereits eine Verbesserung von 40% erzielt).



BEARBEITEN:
Beachten Sie, dass mehrere Quellen über verschiedene Ebenen der JIT-Neukompilierung bis hin zur Interpretation sprechen.

Theoretisches Beispiel basierend auf den obigen Informationen zum OP-Snippet:

  • Rufen Sie isPrimeDivisible auf
  • Kompilieren Sie isPrimeDivisible unter Verwendung allgemeiner Annahmen (z. B. kein Zugriff außerhalb der Grenzen).
  • Arbeite
  • BAM, plötzlich Array-Zugriffe außerhalb der Grenzen (direkt am Ende).
  • Mist, sagt Engine, lassen Sie uns dasPrimeDivisible mit anderen (weniger) Annahmen neu kompilieren, und diese Beispiel-Engine versucht nicht herauszufinden, ob sie das aktuelle Teilergebnis wiederverwenden kann
  • Berechnen Sie alle Arbeiten mit der langsameren Funktion neu (hoffentlich ist sie beendet, andernfalls wiederholen Sie sie und interpretieren Sie diesmal nur den Code).
  • Ergebnis zurückgeben

Daher war die Zeit dann:
Erster Lauf (am Ende fehlgeschlagen) + Wiederholen aller Arbeiten mit langsamerem Maschinencode für jede Iteration + Die Neukompilierung usw. dauert in diesem theoretischen Beispiel eindeutig> 2-mal länger !



EDIT 2: (Haftungsausschluss: Vermutung basierend auf den folgenden Fakten)
Je mehr ich darüber nachdenke, desto mehr denke ich, dass diese Antwort tatsächlich den dominanteren Grund für diese "Strafe" für fehlerhaftes Snippet a (oder Leistungsbonus für Snippet b) erklären könnte , je nachdem, wie Sie darüber denken), genau, warum ich es als Programmierfehler bezeichne (Snippet a):

Es ist ziemlich verlockend anzunehmen, dass this.primeses sich um ein 'dichtes Array' handelt, das entweder rein numerisch ist

  • Hartcodiertes Literal im Quellcode (bekannter hervorragender Kandidat, um ein "echtes" Array zu werden, da dem Compiler bereits vor der Kompilierungszeit alles bekannt ist ) ODER
  • höchstwahrscheinlich generiert mit einer numerischen Funktion, die ein Pre-Size ( new Array(/*size value*/)) in aufsteigender Reihenfolge füllt (ein weiterer seit langem bekannter Kandidat, um ein "reales" Array zu werden).

Wir wissen auch , dass die primesLänge des Arrays wird zwischengespeichert , wie prime_count! (zeigt die Absicht und die feste Größe an).

Wir wissen auch, dass die meisten Engines Arrays zunächst als Copy-on-Modify (bei Bedarf) übergeben, wodurch die Handhabung erheblich beschleunigt wird (wenn Sie sie nicht ändern).

Es ist daher anzunehmen, dass Array primeshöchstwahrscheinlich bereits ein intern optimiertes Array ist, das nach der Erstellung nicht geändert wird (für den Compiler einfach zu wissen, wenn kein Code vorhanden ist, der das Array nach der Erstellung ändert) und daher bereits vorhanden ist (falls zutreffend für der Motor) auf optimierte Weise gespeichert, so als wäre es ein Typed Array.

Wie ich sumanhand meines Funktionsbeispiels zu verdeutlichen versucht habe , beeinflussen die übergebenen Argumente stark, was tatsächlich passieren muss und wie dieser bestimmte Code zu Maschinencode kompiliert wird. Das Übergeben von a Stringan die sumFunktion sollte nicht die Zeichenfolge ändern, sondern die Art und Weise, wie die Funktion JIT-kompiliert ist! Wenn Sie ein Array an übergeben, sumsollte eine andere (möglicherweise sogar zusätzliche für diesen Typ oder 'Form', wie sie es nennen, von Objekt, das übergeben wurde) Version des Maschinencodes kompiliert werden.

Da es ein wenig verrückt erscheint, das Typed_Array-ähnliche primesArray im laufenden Betrieb in etwas anderes zu konvertieren , während der Compiler weiß, dass diese Funktion es nicht einmal ändern wird!

Unter diesen Annahmen bleiben 2 Optionen:

  1. Kompilieren Sie als Zahlenknacker unter der Annahme, dass keine Grenzen überschritten sind, stoßen Sie am Ende auf ein Problem außerhalb der Grenzen, kompilieren Sie die Arbeit neu und wiederholen Sie sie (wie im theoretischen Beispiel in Bearbeitung 1 oben beschrieben)
  2. Der Compiler hat bereits im Vorfeld einen gebundenen Zugriff erkannt (oder vermutet?) Und die Funktion wurde JIT-kompiliert, als ob das übergebene Argument ein spärliches Objekt wäre, was zu einem langsameren funktionalen Maschinencode führt (da es mehr Überprüfungen / Konvertierungen / Zwänge hätte etc.). Mit anderen Worten: Die Funktion war für bestimmte Optimierungen nie geeignet. Sie wurde so kompiliert, als ob sie ein '- spärliches Array' (- ähnliches) Argument erhalten hätte.

Ich frage mich jetzt wirklich, welche von diesen 2 es ist!

GitaarLAB
quelle
2
Eine gute Diskussion über einige der zugrunde liegenden Themen - allerdings erklären Sie die Antwort kaum (im allerletzten Satz). Vielleicht ganz oben ein tl; dr hinzufügen? Beispiel: "Die langsamere Schleife ist darauf zurückzuführen, dass das Bounds-Array überschritten wird, wodurch die Engine gezwungen wird, die Schleife ohne Optimierungen neu zu bewerten. Lesen Sie weiter, um zu erfahren, warum."
Brichins
@brichins: danke und danke für den Vorschlag, den ich im Lichte meiner zweiten zusätzlichen Bearbeitung ein wenig umformuliert habe, denn je mehr ich jetzt darüber nachdenke, desto mehr scheint diese Aussage oben auch richtig zu sein
GitaarLAB
6

Um etwas Wissenschaftlichkeit hinzuzufügen, hier ist ein jsperf

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

Es testet den Kontrollfall eines mit Ints und Schleifen gefüllten Arrays, wobei modulare Arithmetik ausgeführt wird, während die Grenzen eingehalten werden. Es hat 5 Testfälle:

  • 1. Außerhalb der Grenzen schleifen
  • 2. Holey-Arrays
  • 3. Modulare Arithmetik gegen NaNs
  • 4. Vollständig undefinierte Werte
  • 5. Verwenden von a new Array()

Es zeigt, dass die ersten 4 Fälle wirklich schlecht für die Leistung sind. Das Überschreiten von Grenzen ist etwas besser als die anderen 3, aber alle 4 sind ungefähr 98% langsamer als der beste Fall.
Der new Array()Fall ist fast so gut wie das rohe Array, nur ein paar Prozent langsamer.

Nathan Adams
quelle