Hallo Habr! Ich präsentiere Ihnen die Übersetzung des Artikels "Wurmlöcher in JavaScript" von Mathius Buus.
Computer sind interessante Maschinen. Theoretisch scheinen sie uns ideale mechanische Mathematiker zu sein, die mit Zahlen arbeiten und Operationen der Addition, Multiplikation und Subtraktion gut ausführen.
Eine solche Abstraktion ist jedoch ziemlich irreführend. Es nimmt uns vom Verständnis ab, dass ein Computer verschiedene mathematische Operationen mit unterschiedlichen Geschwindigkeiten verarbeitet. Wenn Sie in JavaScript (oder einer anderen Sprache) schreiben und sich um die Leistung der von Ihnen geschriebenen Algorithmen kümmern, ist es sehr wichtig zu verstehen, wie Computer unter der Haube funktionieren.
Wenn wir wissen, wozu der Computer in der Lage ist, können wir die kürzesten Wege oder Wurmlöcher verwenden, um unsere Programme viel schneller als erwartet zu machen.
Wurmloch bei der Beschaffung des Restes der Division
Was genau bedeutet das? Schauen wir uns ein Beispiel an: Stellen Sie sich vor, wir möchten eine Ringliste implementieren. Eine Ringliste ist eine Liste mit fester Größe, in der Einfügungen, die größer als die Größe der Liste sind, an den Anfang der Liste und in einen Kreis verschoben werden. Ringlisten sind für viele Dinge sehr praktisch - zum Beispiel für das Sammeln von Statistiken für bestimmte Zeitintervalle, das Puffern von Daten und mehr. Sehen Sie sich jedoch diese Implementierung an:
const list = new Array(15000) function set (i, item) {
Wie schnell wird dieser Code ausgeführt? Lassen Sie uns einen einfachen Geschwindigkeitstest durchführen
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
Auf meinem Computer dauerte es ~ 4 Sekunden für 1 Milliarde Beilagen. Nicht schlecht.
Wenden wir jedoch ein rechnerisches Wurmloch an und ändern die Größe des Arrays in eine magische Zahl:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
Versuchen wir erneut, den Leistungstest auszuführen. Auf meinem Computer wurde der Test in ~ 1,5 Sekunden abgeschlossen. Mehr als doppelte Erhöhung durch einfache Größenänderung. Um zu verstehen, warum dies geschieht, müssen wir Folgendes verstehen: Unter der Haube arbeitet der Computer mit Zahlen mit Basis 2. Es ist wichtig zu wissen, ob wir den Rest der Division erhalten (Operation%). Eine solche Berechnung ist viel einfacher, wenn die Zahl ein Vielfaches von 2 (2 ^ n) b 16384 ist, es ist 2 ^ 14. Tatsächlich betrachtet der Computer die Zahl in binärer Form und nimmt einfach die letzten n Bits.
Zum Beispiel: Was passiert, wenn eine solche Operation ausgeführt wird? 353 500% 16 384? 353 500 in binärer Darstellung sieht aus wie 1010110010011011100. Seit 16384 == 2 ^ 14 - müssen wir die letzten 14 Bits nehmen - 10101 (10010011011100) oder 9 346.
Wir können dieses Wissen in Bezug auf ein anderes Wurmloch verwenden. Für einen Computer ist es sehr einfach und schnell, die letzten n Bits zu nehmen. Tatsächlich ist es nur notwendig, binär und (Operation &) mit der Zahl (2 ^ n) - 1 zu erzeugen
const list = new Array(16384) function set (i, item) {
Wenn Sie den Leistungstest erneut auf meinem Computer ausführen, werden Sie feststellen, dass sich die Ausführungszeit auf ~ 1s verringert oder die Leistung im Vergleich zum ersten Lauf um das Vierfache erhöht wird. Und das alles aufgrund des Verständnisses der Funktionsweise des Computers.
Intelligente Compiler oder VMs können diese Art der Optimierung durchführen, indem sie den Vorgang, den Rest hinter die Kulissen zu bringen, in einen bitweisen Vorgang umwandeln und umgekehrt. Tatsächlich macht die neueste V8-Javascript-VM (nicht in NodeJS implementiert) genau das.
Numerisches Wurmloch
Ein weiterer nützlicher Maulwurfshügel ist das Verstehen, wie das Lesen und Schreiben von Zahlen funktioniert. Erinnerst du dich, wie wir 32-Bit-Computer verwendet haben und wie wir 64-Bit bekommen haben? Und bis zu 32 Bit hatten wir 16 Bit. Was genau bedeutet das? Normalerweise denken wir so - wie viel RAM wir auf dem Computer haben. 2 ^ 32 = 4294967296 oder 4 GB, was bedeutet, dass wir auf einem 32-Bit-Computer nur auf 4 GB Speicher zugreifen können. Wenn wir ein JS-Programm schreiben, müssen wir normalerweise nicht darüber nachdenken, da wir normalerweise nicht so viel Speicher verwenden.
Es ist jedoch sehr wichtig, den Unterschied zwischen 32-Bit- und 64-Bit-Computern zu verstehen. Seit Prozessoren 64-Bit-Register auf 64-Bit-Computern empfangen haben, sind die Vorgänge doppelt so schnell wie auf 32-Bit-Computern, auf denen Sie nur 32-Bit-Register hatten.
Wie können wir Informationen über dieses Wurmloch verwenden?
Schreiben wir ein einfaches Programm, das ein Uint8Array in ein anderes kopiert. Wenn Sie mit Unit8Arrays nicht vertraut sind, sind sie den Puffern in NodeJS oder einfach dem "sauberen" Speicher sehr ähnlich.
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
Lassen Sie uns die Geschwindigkeit erneut messen, indem Sie einen Leistungstest ausführen.
// 1MB Uint8Arrays const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd()
Auf meinem Computer wurde das Programm in ~ 7,5 Sekunden abgeschlossen. Wie können wir ein Wurmloch verwenden, um zu beschleunigen? Mit Uint8Array kopieren wir jeweils nur 8 Bit, aber mit einem 64-Bit-Computer können wir gleichzeitig 64 Bit Informationen kopieren. Wir können dies in JavaScript tun, indem wir unser Uint8Array vor dem Kopieren in ein Float64Array konvertieren, was uns nichts kostet.
function copy (input, output) { // input.length <= output.length // 64- // , // 64- // BigInts JavaScript, BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { // 64- output64[i] = input64[i] } }
Wenn wir die Leistungstests erneut ausführen, erhalten wir eine Laufzeit von 1 Sekunde, was eine 8-fache Geschwindigkeitssteigerung bedeutet.
Eine akzeptable Lösung für das Kopieren wäre die Verwendung der Methode array.set (otherArray) für Uint8Array, mit der wir in nativen Code kopieren können - was viel schneller ist als jedes andere Wurmloch. Als Referenz ergibt dies ein Ergebnis von ~ 0,2 Sekunden Ausführung in unserem Test auf meinem Computer, was fünfmal schneller ist als die vorherige Lösung.
Eine Galaxie aus JavaScript ist voller Wurmlöcher
Wenn Sie die oben genannten Wurmlöcher verwenden, können Sie Tonnen realer Algorithmen viel schneller erstellen. Es gibt noch viel mehr solche Wurmlöcher. Mein Favorit ist Math.clz32 , eine Methode, die die Anzahl der führenden Nullbits in einer 32-Bit-Binärdarstellung einer Zahl zurückgibt. Wir können diese Methode für viele interessante Algorithmen verwenden. Ich habe es verwendet, um die Implementierung von Bitfeldern um das Vierfache zu beschleunigen, was zu einer Verringerung des Speicherverbrauchs um das Vierfache führte und es mir ermöglichte, Zahlen in einigen Situationen viel schneller zu sortieren .
Wenn Sie die Grundprinzipien des Computers verstehen, können Sie die schnellsten Programme schreiben, die wir benötigen. Dieses Wissen ist auch dann wichtig, wenn Sie in einer Hochsprache wie JavaScript schreiben.
PS:
Besonderer Dank für die Hilfe bei der Übersetzung und Anpassung der Übersetzung an Olga Pereverzeva