Schreiben von leistungsstarkem Javascript-Code, ohne deoptimiert zu werden

10

Wenn Sie leistungsabhängigen Code in Javascript schreiben, der mit großen numerischen Arrays arbeitet (denken Sie an ein lineares Algebra-Paket, das mit ganzen Zahlen oder Gleitkommazahlen arbeitet), möchte man immer, dass die JIT so viel wie möglich hilft. Ungefähr bedeutet dies:

  1. Wir möchten immer, dass unsere Arrays gepackte SMIs (kleine Ganzzahlen) oder gepackte Doubles sind, je nachdem, ob wir Ganzzahl- oder Gleitkommaberechnungen durchführen.
  2. Wir möchten immer die gleiche Art von Dingen an Funktionen übergeben, damit diese nicht als "megamorph" bezeichnet und deoptimiert werden. Zum Beispiel möchten wir immer vec.add(x, y)mit beiden xund ygepackten SMI-Arrays oder beiden gepackten Double-Arrays anrufen .
  3. Wir möchten, dass Funktionen so weit wie möglich eingebunden werden.

Wenn man sich außerhalb dieser Fälle verirrt, tritt ein plötzlicher und drastischer Leistungsabfall auf. Dies kann aus verschiedenen harmlosen Gründen geschehen:

  1. Sie können ein gepacktes SMI-Array über eine scheinbar harmlose Operation wie das Äquivalent von in ein gepacktes Double-Array verwandeln myArray.map(x => -x). Dies ist tatsächlich der "beste" schlechte Fall, da gepackte Double-Arrays immer noch sehr schnell sind.
  2. Sie können ein gepacktes Array in ein generisches Box-Array verwandeln, indem Sie das Array beispielsweise einer Funktion zuordnen, die (unerwartet) zurückgegeben hat, nulloder undefined. Dieser schlimme Fall ist ziemlich leicht zu vermeiden.
  3. Sie können eine ganze Funktion deoptimieren, vec.add()indem Sie beispielsweise zu viele Arten von Dingen übergeben und megamorph machen. Dies kann passieren, wenn Sie eine "generische Programmierung" durchführen möchten, die vec.add()sowohl in Fällen verwendet wird, in denen Sie nicht auf Typen achten (daher werden viele Typen eingegeben), als auch in Fällen, in denen Sie maximale Leistung erzielen möchten (Es sollte zum Beispiel immer nur Boxed Doubles erhalten).

Meine Frage ist eher eine weiche Frage, wie man unter Berücksichtigung der obigen Überlegungen Hochleistungs-Javascript-Code schreibt, während der Code trotzdem schön und lesbar bleibt. Einige spezifische Unterfragen, damit Sie wissen, welche Art von Antwort ich anstrebe:

  • Gibt es irgendwo eine Reihe von Richtlinien zum Programmieren, während Sie (zum Beispiel) in der Welt der gepackten SMI-Arrays bleiben?
  • Ist es möglich, generische Hochleistungsprogrammierung in Javascript vec.add()durchzuführen, ohne ein Makrosystem zu verwenden, um Dinge wie in Callsites zu integrieren?
  • Wie modularisiert man Hochleistungscode angesichts von Dingen wie megamorphen Anrufstellen und Deoptimierungen in Bibliotheken? Wenn ich zum Beispiel das Linear Algebra-Paket gerne mit Ahoher Geschwindigkeit verwende und dann ein Paket importiere, Bdas davon abhängt A, es aber Bmit anderen Typen aufruft und es deoptimiert, läuft mein Code plötzlich (ohne dass sich mein Code ändert) langsamer.
  • Gibt es gute, einfach zu verwendende Messwerkzeuge, mit denen überprüft werden kann, was die Javascript-Engine intern mit Typen tut?
Joppy
quelle
1
Das ist ein sehr interessantes Thema und ein sehr gut geschriebener Beitrag, der zeigt, dass Sie Ihren Teil der Forschung korrekt durchgeführt haben. Ich befürchte jedoch, dass die Frage (n) für das SO-Format viel zu weit gefasst sind und dass sie unweigerlich mehr Meinungen als Fakten anziehen werden. Die Codeoptimierung ist eine sehr komplizierte Angelegenheit, und zwei Versionen einer Engine verhalten sich möglicherweise nicht gleich. Ich denke, es gibt eine der Personen, die für V8 JIT verantwortlich sind, die manchmal herumhängt, also könnten sie vielleicht eine richtige Antwort für ihren Motor geben, aber selbst für sie denke ich, dass es für ein einzelnes Q / A zu weit gefasst wäre .
Kaiido
"Meine Frage ist eher eine weiche Frage, wie man Hochleistungs-Javascript-Code schreibt ..." Nebenbei bemerkt, dass Javascript das Laichen von Hintergrundprozessen (Web-Worker) ermöglicht, und es gibt auch Bibliotheken, die darauf zugreifen Das GPU-Angebot (tensorflow.js und gpu.js) bedeutet, dass Sie sich nicht nur auf die Kompilierung verlassen müssen, um den Rechendurchsatz einer auf Javascript basierenden Anwendung zu steigern ...
Jon Trent
@ JonTrent Eigentlich habe ich in meinem Beitrag ein wenig gelogen, ich interessiere mich nicht so sehr für klassische lineare Algebra-Anwendungen, sondern mehr für Computeralgebra über die ganzen Zahlen. Dies bedeutet, dass viele vorhandene numerische Pakete sofort ausgeschlossen werden, da sie (zum Beispiel) beim Reduzieren einer Matrix durch 2 durch 2 teilen können, was in der Welt, in der ich seit (1/2) arbeite, "nicht erlaubt" ist. ist keine ganze Zahl. Ich habe Web-Worker in Betracht gezogen (insbesondere für einige lang laufende Berechnungen, die abgebrochen werden sollen), aber das Problem, das ich hier anspreche, besteht darin, die Latenz so weit zu verringern, dass ich auf Interaktionen reagieren kann.
Joppy
Für die Ganzzahlarithmetik in JavaScript betrachten Sie wahrscheinlich Code im asm.js-Stil, der ungefähr " |0hinter jeder Operation steht". Es ist nicht schön, aber das Beste, was Sie in einer Sprache tun können, die keine richtigen ganzen Zahlen hat. Sie könnten auch BigInts verwenden, aber bis heute sind sie in keiner der gängigen Engines sehr schnell (hauptsächlich aufgrund mangelnder Nachfrage).
jmrk

Antworten:

8

V8 Entwickler hier. Angesichts des großen Interesses an dieser Frage und des Fehlens anderer Antworten kann ich dies versuchen. Ich fürchte, es wird nicht die Antwort sein, auf die Sie gehofft haben.

Gibt es irgendwo eine Reihe von Richtlinien zum Programmieren, während Sie (zum Beispiel) in der Welt der gepackten SMI-Arrays bleiben?

Kurze Antwort: Es ist genau hier : const guidelines = ["keep your integers small enough"].

Längere Antwort: Es ist aus verschiedenen Gründen schwierig, umfassende Richtlinien zu geben. Im Allgemeinen sind wir der Meinung, dass JavaScript-Entwickler Code schreiben sollten, der für sie und ihren Anwendungsfall sinnvoll ist, und JavaScript-Engine-Entwickler sollten herausfinden, wie dieser Code schnell auf ihren Engines ausgeführt werden kann. Auf der anderen Seite gibt es offensichtlich einige Einschränkungen für dieses Ideal in dem Sinne, dass einige Codierungsmuster immer höhere Leistungskosten haben als andere, unabhängig von der Wahl der Motorimplementierung und den Optimierungsbemühungen.

Wenn wir über Leistungsempfehlungen sprechen, versuchen wir dies zu berücksichtigen und schätzen sorgfältig ab, welche Empfehlungen mit hoher Wahrscheinlichkeit für viele Motoren und viele Jahre gültig bleiben und auch einigermaßen idiomatisch / nicht aufdringlich sind.

Zurück zum vorliegenden Beispiel: Die interne Verwendung von Smis soll ein Implementierungsdetail sein, über das der Benutzercode nichts wissen muss. Dies macht einige Fälle effizienter und sollte in anderen Fällen nicht schaden. Nicht alle Motoren verwenden Smis (zum Beispiel AFAIK Firefox / Spidermonkey in der Vergangenheit nicht; ich habe gehört, dass sie heutzutage in einigen Fällen Smis verwenden, aber ich kenne keine Details und kann mit keiner Behörde darüber sprechen Der Grund). In V8 ist die Größe von Smis ein internes Detail und hat sich im Laufe der Zeit und der Versionen geändert. Auf 32-Bit-Plattformen, die früher der Hauptanwendungsfall waren, waren Smis immer 31-Bit-Ganzzahlen mit Vorzeichen. Auf 64-Bit-Plattformen handelte es sich früher um 32-Bit-Ganzzahlen mit Vorzeichen, was in letzter Zeit der häufigste Fall zu sein schien, bis wir in Chrome 80 die "Zeigerkomprimierung" ausgeliefert haben. für 64-Bit-Architekturen, bei denen die Smi-Größe auf die von 32-Bit-Plattformen bekannten 31 Bit gesenkt werden musste. Wenn Sie eine Implementierung auf der Annahme basieren würden, dass Smis normalerweise 32 Bit sind, würden Sie unglückliche Situationen wie bekommendas .

Zum Glück sind Double Arrays, wie Sie bereits bemerkt haben, immer noch sehr schnell. Für numerisch intensiven Code ist es wahrscheinlich sinnvoll, Doppelarrays anzunehmen / anzuvisieren. Angesichts der Verbreitung von Doubles in JavaScript ist davon auszugehen, dass alle Engines eine gute Unterstützung für Doubles und Double Arrays bieten.

Ist es möglich, generische Hochleistungsprogrammierung in Javascript durchzuführen, ohne ein Makrosystem zu verwenden, um Dinge wie vec.add () in Callsites zu integrieren?

"generisch" steht im Allgemeinen im Widerspruch zu "Hochleistung". Dies hat nichts mit JavaScript oder bestimmten Engine-Implementierungen zu tun.

"Generischer" Code bedeutet, dass Entscheidungen zur Laufzeit getroffen werden müssen. Jedes Mal, wenn Sie eine Funktion ausführen, muss Code ausgeführt werden, um beispielsweise zu bestimmen, xob es sich um eine Ganzzahl handelt. Wenn ja, nehmen Sie diesen Codepfad. Ist xeine Zeichenfolge? Dann springen Sie hierher. Ist es ein Objekt? Hat es .valueOf? Nein? Dann Vielleicht .toString()? Vielleicht in der Prototypenkette? Nennen Sie das und starten Sie von Anfang an mit dem Ergebnis neu. " "Hochleistungs" -optimierter Code basiert im Wesentlichen auf der Idee, all diese dynamischen Überprüfungen zu löschen. Dies ist nur möglich, wenn die Engine / der Compiler eine Möglichkeit hat, Typen im Voraus abzuleiten: Wenn sie beweisen kann (oder mit ausreichender Wahrscheinlichkeit davon ausgehen kann), dass xes sich immer um eine Ganzzahl handelt, muss sie nur Code für diesen Fall generieren ( durch eine Typprüfung geschützt, wenn unbewiesene Annahmen vorlagen).

Inlining ist zu all dem orthogonal. Eine "generische" Funktion kann weiterhin eingebunden werden. In einigen Fällen kann der Compiler möglicherweise Typinformationen in die Inline-Funktion übertragen, um dort den Polymorphismus zu reduzieren.

(Zum Vergleich: C ++ ist eine statisch kompilierte Sprache und verfügt über Vorlagen zur Lösung eines verwandten Problems. Kurz gesagt, der Programmierer weist den Compiler explizit an, spezielle Kopien von Funktionen (oder ganzen Klassen) zu erstellen, die für bestimmte Typen parametrisiert sind Für einige Fälle eine gute Lösung, aber nicht ohne eigene Nachteile, zum Beispiel lange Kompilierungszeiten und große Binärdateien. JavaScript hat natürlich keine Vorlagen. Sie könnten evalein System erstellen, das etwas ähnlich ist, aber dann Sie Es würde ähnliche Nachteile geben: Sie müssten zur Laufzeit das Gleiche tun wie der C ++ - Compiler, und Sie müssten sich um die Menge an Code sorgen, die Sie generieren.)

Wie modularisiert man Hochleistungscode angesichts von Dingen wie megamorphen Anrufstellen und Deoptimierungen in Bibliotheken? Wenn ich zum Beispiel das Linear-Algebra-Paket A mit hoher Geschwindigkeit verwende und dann ein Paket B importiere, das von A abhängt, B es jedoch mit anderen Typen aufruft und es deoptimiert, läuft mein Code plötzlich (ohne dass sich mein Code ändert) langsamer .

Ja, das ist ein allgemeines Problem mit JavaScript. V8 hat bestimmte integrierte Funktionen (z. B. Array.sort) intern in JavaScript implementiert , und dieses Problem (das wir als "Typ-Feedback-Verschmutzung" bezeichnen) war einer der Hauptgründe, warum wir uns vollständig von dieser Technik entfernt haben.

Für numerischen Code gibt es jedoch nicht allzu viele Typen (nur Smis und Doubles), und wie Sie bemerkt haben, sollten sie in der Praxis eine ähnliche Leistung aufweisen, so dass die Verschmutzung durch Typrückkopplungen in der Tat ein theoretisches Problem darstellt und in einigen Fällen auch möglich ist Es ist auch ziemlich wahrscheinlich, dass Sie in linearen Algebra-Szenarien keinen messbaren Unterschied sehen.

Außerdem gibt es im Motor viel mehr Situationen als "ein Typ == schnell" und "mehr als ein Typ == langsam". Wenn eine bestimmte Operation sowohl Smis als auch Doubles gesehen hat, ist das völlig in Ordnung. Das Laden von Elementen aus zwei Arten von Arrays ist ebenfalls in Ordnung. Wir verwenden den Begriff "megamorph" für die Situation, in der eine Last so viele verschiedene Typen gesehen hat, dass es aufgegeben wird, sie einzeln zu verfolgen, und verwenden stattdessen einen allgemeineren Mechanismus, der sich besser auf eine große Anzahl von Typen skalieren lässt - eine Funktion, die solche Lasten enthält werde immer noch optimiert. Eine "Deoptimierung" ist der sehr spezifische Vorgang, bei dem optimierter Code für eine Funktion weggeworfen werden muss, da ein neuer Typ angezeigt wird, der zuvor noch nicht gesehen wurde, und der optimierte Code daher nicht für die Verarbeitung ausgestattet ist. Aber auch das ist in Ordnung: Kehren Sie einfach zu nicht optimiertem Code zurück, um mehr Typfeedback zu sammeln und später erneut zu optimieren. Wenn dies ein paar Mal passiert, besteht kein Grund zur Sorge. es wird nur in pathologisch schlimmen Fällen zum Problem.

Also die Zusammenfassung von allem, was ist: Mach dir keine Sorgen . Schreiben Sie einfach vernünftigen Code und lassen Sie den Motor damit umgehen. Und mit "vernünftig" meine ich: Was für Ihren Anwendungsfall Sinn macht, ist lesbar, wartbar, verwendet effiziente Algorithmen, enthält keine Fehler wie das Lesen über die Länge von Arrays hinaus. Im Idealfall ist das alles, und Sie müssen nichts weiter tun. Wenn es macht Sie fühlen sich besser zu tun , etwas , und / oder wenn Sie tatsächlich Performance - Probleme zu beobachten, kann ich zwei Ideen bieten:

Die Verwendung von TypeScript kann helfen. Große Fettwarnung: Die TypeScript-Typen zielen auf die Entwicklerproduktivität und nicht auf die Ausführungsleistung ab (und wie sich herausstellt, haben diese beiden Perspektiven sehr unterschiedliche Anforderungen an ein Typsystem). Das heißt, es gibt einige Überschneidungen: Wenn Sie beispielsweise Dinge konsequent mit Anmerkungen versehen number, warnt Sie der TS-Compiler, wenn Sie versehentlich nullein Array oder eine Funktion eingeben, die nur Zahlen enthalten / bearbeiten soll. Natürlich ist weiterhin Disziplin erforderlich: Eine einzige number_func(random_object as number)Notluke kann stillschweigend alles untergraben, da die Richtigkeit der Typanmerkungen nirgendwo erzwungen wird.

Die Verwendung von TypedArrays kann ebenfalls hilfreich sein. Sie haben einen etwas höheren Overhead (Speicherverbrauch und Zuweisungsgeschwindigkeit) pro Array als normale JavaScript-Arrays (wenn Sie also viele kleine Arrays benötigen, sind reguläre Arrays wahrscheinlich effizienter) und sind weniger flexibel, weil sie nicht wachsen können oder nach der Zuordnung verkleinern, bieten jedoch die Garantie, dass alle Elemente genau einen Typ haben.

Gibt es gute, einfach zu verwendende Messwerkzeuge, mit denen überprüft werden kann, was die Javascript-Engine intern mit Typen tut?

Nein, und das ist beabsichtigt. Wie oben erläutert, möchten wir nicht, dass Sie Ihren Code speziell auf die Muster abstimmen, die V8 heute besonders gut optimieren kann, und wir glauben auch nicht, dass Sie dies wirklich tun möchten. Diese Dinge können sich in beide Richtungen ändern: Wenn es ein Muster gibt, das Sie gerne verwenden würden, könnten wir es in einer zukünftigen Version optimieren (wir haben zuvor mit der Idee gespielt, 32-Bit-Ganzzahlen ohne Box als Array-Elemente zu speichern). . aber die Arbeit daran hat noch nicht begonnen, also keine Versprechen); und manchmal, wenn es ein Muster gibt, für das wir in der Vergangenheit optimiert haben, entscheiden wir uns möglicherweise dafür, dieses zu streichen, wenn es anderen, wichtigeren / wirkungsvolleren Optimierungen im Wege steht. Auch Dinge wie Inlining-Heuristiken sind bekanntermaßen schwer zu korrigieren. Die richtige Inlining-Entscheidung zur richtigen Zeit zu treffen, ist daher ein Bereich laufender Forschung und entsprechender Änderungen des Engine- / Compiler-Verhaltens. Das macht dies zu einem weiteren Fall, in dem es für alle (Sie) unglücklich wäreund uns), wenn Sie viel Zeit damit verbracht haben, Ihren Code zu optimieren, bis eine Reihe aktueller Browserversionen ungefähr die Inlining-Entscheidungen trifft, die Sie für am besten halten (oder wissen?), und dann ein halbes Jahr später zurückkommen, um die damals aktuellen Browser zu erkennen haben ihre Heuristik geändert.

Natürlich können Sie jederzeit die Leistung Ihrer gesamten Anwendung messen - letztendlich kommt es darauf an, nicht welche Entscheidungen speziell die Engine intern getroffen hat. Hüten Sie sich vor Mikrobenchmarks, da diese irreführend sind: Wenn Sie nur zwei Codezeilen extrahieren und diese vergleichen, besteht die Möglichkeit, dass das Szenario ausreichend unterschiedlich ist (z. B. unterschiedliche Typrückmeldungen), sodass die Engine sehr unterschiedliche Entscheidungen trifft.

jmrk
quelle
2
Vielen Dank für diese ausgezeichnete Antwort, bestätigt es viele meiner Vermutungen darüber , wie die Dinge funktionieren, und vor allem , wie sie soll an die Arbeit. Gibt es übrigens Blog-Beiträge usw. zu dem von Ihnen erwähnten Problem "Typ-Feedback" Array.sort()? Ich würde gerne ein bisschen mehr darüber lesen.
Joppy
Ich glaube nicht, dass wir über diesen speziellen Aspekt gebloggt haben. Es ist im Wesentlichen das, was Sie in Ihrer Frage selbst beschrieben haben: Wenn Buildins in JavaScript implementiert sind, sind sie "wie eine Bibliothek" in dem Sinne, dass die Leistung leiden kann, wenn verschiedene Codeteile sie mit unterschiedlichen Typen aufrufen - manchmal nur ein wenig. manchmal mehr. Es war nicht das einzige und wohl nicht einmal das größte Problem mit dieser Technik; Ich wollte meistens nur sagen, dass ich mit dem allgemeinen Problem vertraut bin.
jmrk