Fallen Sie nicht in die Falle einer vorzeitigen Optimierung

Donald Knuth sagte einmal die Worte, die später berühmt wurden: „Das eigentliche Problem ist, dass Programmierer, nicht dort, wo sie müssen und nicht, wenn sie brauchen, zu viel Zeit damit verbringen, sich um Effizienz zu kümmern. Vorzeitige Optimierung ist die Wurzel aller Übel (oder zumindest der meisten von ihnen) in der Programmierung. “



Der Autor des Materials, dessen Übersetzung wir heute veröffentlichen, möchte darüber sprechen, wie er einst in die Falle der vorzeitigen Optimierung geraten ist und wie er aus seiner eigenen bitteren Erfahrung verstanden hat, dass vorzeitige Optimierung die Wurzel aller Übel ist.

Spiel GeoArena Online

Vor ein paar Jahren habe ich am Web-Spiel GeoArena Online gearbeitet (dann habe ich es verkauft , die neuen Besitzer haben es auf geoarena.io gepostet). Es war ein Multiplayer-Spiel im Stil des "letzten Überlebenden". Dort kontrollierte der Spieler das Schiff und kämpfte eins zu eins gegen einen anderen Spieler.


Spiel GeoArena Online


Spiel GeoArena Online

Ein dynamisches Spiel, dessen Welt voller Partikel und Effekte ist, erfordert ernsthafte Rechenressourcen. Infolgedessen wurde das Spiel auf einigen alten Computern in besonders angespannten Momenten „langsamer“. Ich, ein Mann, dem Produktivitätsprobleme nicht gleichgültig sind, nahm die Lösung dieses Problems mit Interesse auf. „Wie beschleunige ich den clientseitigen JavaScript-Teil von GeoArena?“, Fragte ich mich.

Fast.js Bibliothek

Nachdem ich ein bisschen im Internet gesucht hatte, entdeckte ich die Bibliothek fast.js. Es war eine "Sammlung von Mikrooptimierungen, die die Entwicklung sehr schneller JavaScript-Programme vereinfachen sollen". Diese Bibliothek wurde durch die Verfügbarkeit schnellerer Implementierungen der integrierten Standardmethoden wie Array.prototype.forEach () beschleunigt .

Ich fand das äußerst interessant. GeoArena verwendete viele Arrays und führte viele Operationen mit Arrays durch. Die Verwendung von fast.js könnte mir also sehr helfen, das Spiel zu beschleunigen. Die folgenden Ergebnisse der forEach() Leistungsstudie wurden in README für fast.js aufgenommen.

 Native .forEach() vs fast.forEach() (10 items)  ✓ Array::forEach() x 8,557,082 ops/sec ±0.37% (97 runs sampled)  ✓ fast.forEach() x 8,799,272 ops/sec ±0.41% (97 runs sampled)  Result: fast.js is 2.83% faster than Array::forEach(). 

Wie kann eine in einer externen Bibliothek implementierte Methode schneller sein als ihre Standardversion? Die Sache ist, dass es einen Trick gab (sie, diese Tricks, sind überall zu finden, wo man hinschaut). Die Bibliothek war nur für die Arbeit mit nicht spärlichen Arrays geeignet.

Hier sind einige einfache Beispiele für solche Arrays:

 //  -  :   1  . const sparse1 = [0, , 1]; console.log(sparse1.length); // 3 //  -   const sparse2 = []; // ...   - .   0 - 4    . sparse2[5] = 0; console.log(sparse2.length); // 6 

Um zu verstehen, warum die Bibliothek mit spärlichen Arrays nicht normal funktionieren kann, habe ich mir den Quellcode angesehen. Es stellte sich heraus, dass die Implementierung von forEach() in fast.js auf for-Schleifen basiert. Eine schnelle Implementierung der forEach() -Methode würde ungefähr so ​​aussehen:

 //     . function fastForEach(array, f) {  for (let i = 0; i < array.length; i++) {    f(array[i], i, array);  } } const sparseArray = [1, , 2]; const print = x => console.log(x); fastForEach(sparseArray, print); //  print() 3 . sparseArray.forEach(print); //  print()  2 . 

Ein Aufruf der fastForEach() -Methode fastForEach() drei Werte aus:

 1 undefined 2 

Das Aufrufen von sparseArray.forEach() führt nur zur Schlussfolgerung von zwei Werten:

 1 2 

Dieser Unterschied ist auf die Tatsache zurückzuführen, dass JS-Spezifikationen bezüglich der Verwendung von Rückruffunktionen darauf hinweisen, dass solche Funktionen nicht für entfernte oder nicht initialisierte Array-Indizes (auch als "Löcher" bezeichnet) aufgerufen werden sollten. Die Implementierung von fastForEach() hat das Array nicht auf Löcher überprüft. Dies führte zu einer Geschwindigkeitssteigerung auf Kosten der korrekten Arbeit mit spärlichen Arrays. Dies war perfekt für mich, da in GeoArena keine spärlichen Arrays verwendet wurden.

An dieser Stelle sollte ich nur einen kurzen Test auf fast.js machen. Ich sollte die Bibliothek installieren, die Standardmethoden des Array Objekts in Methoden von fast.js ändern und die Leistung des Spiels testen. Stattdessen bewegte ich mich in eine ganz andere Richtung.

Meine Entwicklung hieß schneller.js

Der in mir lebende manische Perfektionist wollte absolut alles aus der Optimierung der Leistung des Spiels herausholen. Die Bibliothek fast.js schien mir einfach keine ausreichend gute Lösung zu sein, da ihre Verwendung das Aufrufen ihrer Methoden implizierte. Dann dachte ich: „Was ist, wenn ich die Standardmethoden von Arrays ersetze, indem ich einfach neue, schnellere Implementierungen dieser Methoden in den Code einbette? Das würde mir die Notwendigkeit von Bibliotheksmethodenaufrufen ersparen. “

Es war diese Idee, die mich zu der genialen Idee führte, einen Compiler zu erstellen, den ich dreist schneller nannte. Ich hatte vor, es anstelle von fast.js zu verwenden. Hier ist zum Beispiel das Quellcode-Snippet:

 //   const arr = [1, 2, 3]; const results = arr.map(e => 2 * e); 

Der Compiler "schneller.js" würde diesen Code in den folgenden konvertieren - schneller, aber schlechter aussehend:

 //      faster.js const arr = [1, 2, 3]; const results = new Array(arr.length); const _f = (e => 2 * e); for (let _i = 0; _i < arr.length; _i++) {  results[_i] = _f(arr[_i], _i, arr); } 

Die Erstellung von schneller.js wurde von der gleichen Idee angeregt, die fast.js zugrunde lag. Wir sprechen nämlich von Mikrooptimierungen der Leistung aufgrund der Ablehnung der Unterstützung für dünn besetzte Arrays.

Auf den ersten Blick schien mir schneller.js eine äußerst erfolgreiche Entwicklung zu sein. Hier sind einige Ergebnisse einer Leistungsstudie von schneller.js:

   array-filter large    ✓ native x 232,063 ops/sec ±0.36% (58 runs sampled)    ✓ faster.js x 1,083,695 ops/sec ±0.58% (57 runs sampled) faster.js is 367.0% faster (3.386μs) than native  array-map large    ✓ native x 223,896 ops/sec ±1.10% (58 runs sampled)    ✓ faster.js x 1,726,376 ops/sec ±1.13% (60 runs sampled) faster.js is 671.1% faster (3.887μs) than native  array-reduce large    ✓ native x 268,919 ops/sec ±0.41% (57 runs sampled)    ✓ faster.js x 1,621,540 ops/sec ±0.80% (57 runs sampled) faster.js is 503.0% faster (3.102μs) than native  array-reduceRight large    ✓ native x 68,671 ops/sec ±0.92% (53 runs sampled)    ✓ faster.js x 1,571,918 ops/sec ±1.16% (57 runs sampled) faster.js is 2189.1% faster (13.926μs) than native 

Die vollständigen Testergebnisse finden Sie hier . Sie wurden in Node v8.16.1 auf dem 15-Zoll-MacBook Pro 2018 gehalten.

Ist meine Entwicklung 2000% schneller als die Standardimplementierung? Eine solch ernsthafte Produktivitätssteigerung kann zweifellos die stärksten positiven Auswirkungen auf jedes Programm haben. Richtig?
Nein, nicht wahr.

Betrachten Sie ein einfaches Beispiel.

• Stellen Sie sich vor, dass ein durchschnittliches GeoArena-Spiel 5.000 Millisekunden (ms) Rechenzeit benötigt.
• Der Compiler schneller.js beschleunigt die Ausführung von Array-Methoden durchschnittlich um das Zehnfache (dies ist eine ungefähre Schätzung und wird auch überschätzt; in den meisten realen Anwendungen gibt es nicht einmal eine doppelte Beschleunigung).

Und hier ist die Frage, die uns wirklich interessiert: „Welcher Teil dieser 5000 ms wird für die Implementierung von Array-Methoden ausgegeben?“.

Angenommen, die Hälfte. Das heißt, 2500 ms werden für Array-Methoden aufgewendet, die restlichen 2500 ms für alles andere. Wenn ja, dann sorgt die Verwendung von schneller.js für eine enorme Leistungssteigerung.


Bedingtes Beispiel: Die Ausführungszeit des Programms wird stark reduziert

Infolgedessen stellt sich heraus, dass die gesamte Rechenzeit um 45% reduziert wurde.

Leider sind all diese Argumente sehr, sehr weit von der Realität entfernt. GeoArena verwendet natürlich viele Array-Methoden. Die tatsächliche Verteilung der Codeausführungszeit für verschiedene Aufgaben sieht jedoch wie folgt aus.


Harte Realität

Leider, was soll ich sagen.

Dies ist genau der Fehler, vor dem Donald Knuth gewarnt hat. Ich habe mich nicht darum bemüht, worauf sie angewendet werden sollen, und ich habe es nicht getan, als es sich gelohnt hat.

Hier kommt einfache Mathematik ins Spiel. Wenn etwas nur 1% der Programmausführungszeit in Anspruch nimmt, führt eine Optimierung im besten Fall nur zu einer Steigerung der Produktivität um 1%.

Genau das hatte Donald Knuth im Sinn, als er sagte "nicht dort, wo es gebraucht wird". Und wenn Sie darüber nachdenken, was „wo Sie es brauchen“, stellt sich heraus, dass dies die Teile der Programme sind, die die Leistungsengpässe darstellen. Dies sind die Codeteile, die einen wesentlichen Beitrag zur Gesamtleistung des Programms leisten. Hier wird das Konzept der "Produktivität" im weitesten Sinne verwendet. Es kann die Laufzeit des Programms, die Größe des kompilierten Codes und etwas anderes enthalten. Eine 10% ige Verbesserung in dem Teil des Programms, der die Leistung stark beeinflusst, ist besser als eine 100% ige Verbesserung in einigen kleinen Dingen.

Knut sprach auch von der Anwendung von Bemühungen "nicht wenn nötig". Der Punkt dabei ist, dass Sie etwas nur dann optimieren müssen, wenn es notwendig ist. Natürlich hatte ich einen guten Grund, über Optimierung nachzudenken. Aber denken Sie daran, dass ich mit der Entwicklung von quick.js begonnen habe und vorher nicht einmal versucht habe, die fast.js-Bibliothek in GeoArena zu testen? Minuten, die ich damit verbracht habe, fast.js in meinem Spiel zu testen, würden mir Wochen Arbeit ersparen. Ich hoffe, Sie geraten nicht in dieselbe Falle, in die ich geraten bin.

Zusammenfassung

Wenn Sie mit schneller.js experimentieren möchten, können Sie sich diese Demo ansehen. Welche Ergebnisse Sie erhalten, hängt von Ihrem Gerät und Ihrem Browser ab. Hier zum Beispiel, was in Chrome 76 auf dem 15-Zoll-MacBook Pro 2018 passiert ist.


Faster.js Testergebnisse

Vielleicht möchten Sie mehr über die tatsächlichen Ergebnisse der Verwendung von schneller.js in GeoArena erfahren. Ich habe, als das Spiel noch mir gehörte (wie gesagt, ich habe es verkauft), einige Grundlagenforschung betrieben. Als Ergebnis stellte sich Folgendes heraus:

• Die Verwendung von schneller.js beschleunigt die Ausführung des Hauptspielzyklus in einem typischen Spiel um etwa 1%.
• Aufgrund der Verwendung von schneller.js wurde die Größe des Spielpakets um 0,3% erhöht. Dies verlangsamte das Laden der Spieleseite etwas. Die Größe des Bundles hat zugenommen, da schneller.js den Standard-Funktionscode in schnelleren, aber auch längeren Code konvertiert.

Im Allgemeinen hat schneller.js Vor- und Nachteile, aber meine Entwicklung hatte keinen großen Einfluss auf die Leistung von GeoArena. Ich hätte das viel früher verstanden, wenn ich mir die Mühe gemacht hätte, das Spiel zuerst mit fast.js zu testen.

Möge meine Geschichte Ihnen als Warnung dienen.

Liebe Leser! Sind Sie in die Falle einer vorzeitigen Optimierung geraten?