Wurmlöcher in JavaScript

Published on October 30, 2018

Wurmlöcher in JavaScript

Hi, Habr! Ich präsentiere Ihnen die Übersetzung des Artikels "Wurmlöcher in JavaScript" von Mathius Buus.



Computer sind interessante Maschinen. Theoretisch scheinen sie ideale mechanische Mathematiker zu sein, die mit Zahlen arbeiten und die Operationen Addition, Multiplikation und Subtraktion gut ausführen.


Eine solche Abstraktion täuscht jedoch. Es führt uns weg von dem Verständnis, dass ein Computer verschiedene mathematische Operationen mit unterschiedlichen Geschwindigkeiten ausführt. Wenn Sie in JavaScript (oder in einer anderen Sprache) schreiben und sich Gedanken über die Leistung der von Ihnen geschriebenen Algorithmen machen, ist es sehr wichtig zu verstehen, wie Computer unter der Haube funktionieren.


Wenn wir wissen, was ein Computer kann, können wir Verknüpfungen oder Wurmlöcher verwenden, um unsere Programme viel schneller zu machen als erwartet.


Wurmloch bei der Erlangung des Restes der Division


Was heißt das genau? 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, bei der die Einfügungen größer als die Größe der Liste sind, an den Anfang der Liste und in einem Kreis verschoben werden. Ringlisten sind für viele Zwecke sehr praktisch, z. B. für das Erfassen von Statistiken zu bestimmten Zeitintervallen, Datenpufferung und mehr. Sehen Sie sich jedoch diese Implementierung an:


const list = new Array(15000)
function set (i, item) {
  // Оператор % - деление по модулю, возвращает остаток от деления
  // числа слева от него на число справа
  // использование этого оператора здесь, привязывает цикл с переменной i к размеру списка
  list[i % list.length] = 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 ca. 4 Sekunden bis 1 Milliarde Einsätze. Nicht schlecht.


Wenden wir jedoch das rechnerische Maulwurfloch an und ändern Sie 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
}

Führen Sie den Leistungstest erneut aus. Auf meinem Computer lief der Test in ~ 1,5 Sekunden. Mehr als die doppelte Steigerung durch einfaches Ändern der Größe. Um zu verstehen, warum dies der Fall ist, müssen wir Folgendes verstehen: Unter der Haube arbeitet der Computer mit Zahlen mit der Basis 2. Es ist wichtig zu wissen, ob wir den Rest der Division erhalten (% Operation). Diese Berechnung ist viel einfacher durchzuführen, wenn die Zahl ein Vielfaches von 2 (2 ^ n) ist. 16384 ist 2 ^ 14. Tatsächlich betrachtet der Computer die Zahl in binärer Form und nimmt nur die letzten n Bits.


Zum Beispiel: Was passiert bei einer solchen Operation? 353,500% 16,384? 353.500 in der Binärdarstellung sieht wie 1010110010011011100 aus. Seit 16384 == 2 ^ 14 - müssen wir die letzten 14 Bits nehmen - 10101 (10010011011100) oder 9 346.


Wir können dieses Wissen auf ein anderes Wurmloch anwenden. Es ist sehr einfach und schnell für einen Computer, die letzten n Bits zu übernehmen. In der Tat ist es nur notwendig, ein binäres und (Operation &) mit der Nummer (2 ^ n) - 1 auszuführen


const list = new Array(16384)
function set (i, item) {
  // Использование быстрого оператора &(бинарное И) вместо % с длиной списка 2 ^ n
  list[i & (list.length - 1)] = i
}

Wenn Sie den Leistungstest erneut auf meinem Computer ausführen, werden wir feststellen, dass sich die Ausführungszeit auf ~ 1s verringert oder die Leistung um das Vierfache gegenüber dem ersten Start erhöht wird. Und das alles, wenn Sie verstehen, wie der Computer funktioniert.


Intelligente Compiler oder VM sind in der Lage, diese Optimierung durchzuführen, indem sie hinter der Bühne bitweise arbeiten und wieder zurück. Tatsächlich macht die letzte V8-Javascript-VM (nicht in NodeJS implementiert) genau dies.


Numerische Wurmlöcher


Ein weiteres nützliches Wurmloch ist das Verständnis, wie Zahlen gelesen und geschrieben werden. Erinnern Sie sich, wie wir 32-Bit-Computer verwendet haben und wie haben wir 64 Bit erhalten? Und bis zu 32 Bit hatten wir 16 Bit. Was heißt das genau? Normalerweise denken wir so, wie viel RAM wir auf dem Computer haben. 2 ^ 32 = 4294967296 oder 4 GB, was bedeutet, dass auf einem 32-Bit-Computer nur 4 GB Speicher verfügbar sind. 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. Da die Prozessoren 64-Bit-Register auf 64-Bit-Computern erhalten haben, war die Leistung der Operationen zweimal so hoch wie auf 32-Bit-Computern, auf denen Sie nur 32-Bit-Register hatten.


Wie können wir Informationen über diesen Maulwurfshügel verwenden?
Lassen Sie uns ein einfaches Programm schreiben, das einen Uint8Array in einen anderen kopiert. Wenn Sie mit Unit8Arrays nicht vertraut sind, sind sie den Puffern in NodeJS sehr ähnlich oder einfach „reinem“ Speicher.


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 erneut die Geschwindigkeit messen, indem Sie einen Leistungstest durchfü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 lief das Programm in ~ 7,5 Sekunden. Wie können wir den Maulwurf zur Beschleunigung nutzen? Mit Uint8Array kopieren wir jeweils nur 8 Bit, haben aber einen 64-Bit-Computer - wir können 64 Bit Informationen gleichzeitig kopieren. Wir können dies in Javascript tun, indem Sie unser Uint8Array vor dem Kopieren in 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 Sie die Leistungstests erneut ausführen, erhalten Sie eine Laufzeit von 1 Sekunde, was die Geschwindigkeit um das Achtfache erhöht.


Eine akzeptable Lösung zu kopieren, wäre die Verwendung der array.set (otherArray) -Methode für Uint8Array, die uns das Kopieren in nativem Code ermöglicht - was viel schneller ist als alle anderen Mole. Als Referenz erhalten Sie in unserem Test auf meinem Computer ~ 0,2 Sekunden Ausführung, was fünfmal schneller ist als bei der vorherigen Lösung.


Die Galaxie Javascript ist voll von Nippeln


Die Verwendung des oben erwähnten Wurmlochs hilft Ihnen, Tonnen von echten Algorithmen viel schneller zu erstellen. Es gibt noch viele solche Wurmlöcher. Mein Favorit ist Math.clz32 , eine Methode, die die Anzahl der führenden Null-Bits in einer 32-Bit-Binärdarstellung einer Zahl zurückgibt. Wir können diese Methode für eine Vielzahl interessanter Algorithmen verwenden. Ich habe es verwendet, um die Implementierung von Bitfeldern um das Vierfache zu beschleunigen , was den Speicherverbrauch ebenfalls um das Vierfache verringerte und mir erlaubte, die 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 wichtig, auch wenn Sie in einer Hochsprache wie JavaScript schreiben.


PS:


Vielen Dank für die Hilfe bei der Übersetzung und Korrektur der Übersetzung für Olga Pereverzeva