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
javascript
v8
Leonardo Physh
quelle
quelle
<=
und<
sind sowohl in der Theorie als auch in der tatsächlichen Implementierung in allen modernen Prozessoren (und Interpreten) identisch.main
Code, der diese Funktion in einer Schleife aufruft, die25000
mal 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 einenundefined
Wert an, da Arrays mit der Indizierung beginnen0
.<=
, die dies<
tut , sich aber ansonsten identisch mit der Version verhälti <= this.prime_count - 1
. Dies löst sowohl das Problem "zusätzliche Iteration" als auch das Problem "nach dem Ende des Arrays".Antworten:
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 :
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
:Dies führt zu einem Array mit einer
HOLEY
Elementart 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 wirthis.primes[i]
in der Schleife innerhalb treffenisPrimeDivisible
. Keine große Sache!TL; DR Das Array
HOLEY
ist 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 sichundefined
in dieser Zeile befinden:Und das bringt uns zum eigentlichen Problem : Der
%
Operator wird jetzt mit nicht ganzzahligen Operanden verwendet!integer % someOtherInteger
kann sehr effizient berechnet werden; JavaScript-Engines können für diesen Fall hochoptimierten Maschinencode erzeugen.integer % undefined
Auf der anderen Seite ist dies weitaus weniger effizientFloat64Mod
, daundefined
es sich um ein Doppel handelt.Das Code-Snippet kann in der Tat verbessert werden, indem das
<=
in<
in diese Zeile geändert wird:... nicht weil
<=
es irgendwie ein überlegener Operator ist als<
, sondern nur weil dies die in diesem speziellen Fall gelesenen Out-of-Bounds vermeidet.quelle
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:
Was ist nun der Wert von
a[1]
? Es hat keinen Wert . (Es ist nicht einmal richtig zu sagen, dass es den Wert hatundefined
- 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,undefined
weili
das Array-Ende überschritten ist.candidate % undefined
(für jeden Wert voncandidate
) ergibtNaN
.NaN == 0
bewertet zufalse
.return true
nicht 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.
quelle
undefined
anstelle einer Zahl eingegeben wird, die zu einer anderen Berechnung führt.Object
), da jede Mischung von Datentypen im Array unterstützt werden muss. Wie oben erwähnt, hat der Code in der Schleife, die eingespeistundefined
wird, 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).Value
Objekten, die Verweise auf Werte eines beliebigen Typs enthalten können. (Ich habe den Namen erfundenValue
, aber der Punkt ist, dass die Array-Elemente nicht nur einfache Zahlen sind, sondern Objekte, die Zahlen oder andere Typen umschließen.)HOLEY
weil es mit erstellt wurdenew Array(n)
(obwohl dieser Teil des Codes im OP nicht sichtbar war).HOLEY
Arrays bleibenHOLEY
in 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.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).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):
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:
Perfekt klar, oder? Benötigt keine zusätzliche Klarstellung, oder? Der Rückgabetyp ist
Number
, richtig?Nun ... nein, nein & nein ... Es hängt davon ab, welches Argument Sie an den benannten Funktionsparameter übergeben
arr
...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):
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):
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:
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.primes
es sich um ein 'dichtes Array' handelt, das entweder rein numerisch istnew 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
primes
Länge des Arrays wird zwischengespeichert , wieprime_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
primes
hö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 einTyped Array
.Wie ich
sum
anhand 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 aString
an diesum
Funktion sollte nicht die Zeichenfolge ändern, sondern die Art und Weise, wie die Funktion JIT-kompiliert ist! Wenn Sie ein Array an übergeben,sum
sollte 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
primes
Array 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:
Ich frage mich jetzt wirklich, welche von diesen 2 es ist!
quelle
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:
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.quelle