こんにちは、Habr！ Mathius Buusの記事「JavaScriptのワームホール」の翻訳を紹介します 。
コンピューターは面白いマシンです。 理論的には、彼らは数字を操作し、加算、乗算、減算の演算をうまく実行する理想的な機械数学者であるように思われます。
ただし、このような抽象化は誤解を招く可能性があります。 コンピューターは異なる数学演算を異なる速度で処理するという理解から私たちを遠ざけます。 JavaScript（または他の言語）で記述し、記述したアルゴリズムのパフォーマンスに注意する場合、コンピューターが内部でどのように機能するかを理解することが非常に重要です。
コンピューターの能力がわかっている場合は、最短パスまたはワームホールを使用して、予想よりもはるかに高速にプログラムを作成できます。
除算の残りを取得する操作のワームホール
これはどういう意味ですか？ 例を見てみましょう。 リングリストを実装したいと想像してください。 リングリストは固定サイズのリストで、リストのサイズよりも大きい挿入物はリストの上部に移動し、円で囲まれます。 リングリストは、特定の時間間隔の統計情報の収集、データのバッファリングなど、多くのことに非常に便利ですが、この実装を見てください。
const list = new Array(15000) function set (i, item) { // % - , // // , i list[i % list.length] = item }
このコードの実行速度はどれくらいですか？ 簡単な速度テストを実行しましょう
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
私のコンピューターでは、10億回の挿入で約4秒かかりました。 悪くない。
ただし、計算ワームホールを適用して、配列のサイズをマジックナンバーに変更しましょう。
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
パフォーマンステストをもう一度実行してみましょう。 私のコンピューターでは、テストは約1.5秒で完了しました。 単純なサイズ変更による2倍以上の増加。 これが起こる理由を理解するために、以下のことを理解する必要があります。フードの下では、コンピューターは2を基数とする数値で動作します。 そのような計算は、数値が2（2 ^ n）b 16384の倍数である場合、はるかに簡単です。b16384は2 ^ 14です。実際、コンピューターはバイナリ形式で数値を調べ、最後のnビットを取得します。
例：そのような操作が実行された場合、どうなりますか353 500％16 384？ バイナリ表現の353 500は1010110010011011100のようになります。16384== 2 ^ 14なので、最後の14ビット-10101（10010011011100）または9 346を取る必要があります。
この知識を別のワームホールに使用できます。 コンピューターの場合、最後のnビットを取得するのは非常に簡単で迅速です。 実際、2進数と（演算＆）を番号（2 ^ n）-1で生成するだけです。
const list = new Array(16384) function set (i, item) { // &( ) % 2 ^ n list[i & (list.length - 1)] = i }
コンピューターでパフォーマンステストを再度実行すると、実行時間が約1秒に短縮されるか、最初の実行に比べてパフォーマンスが4倍に向上することがわかります。 これはすべて、コンピューターの動作方法を理解しているためです。
スマートコンパイラまたはVMは、このような最適化を行うために、舞台裏で残りの部分をビット単位の操作にしたり、その逆の操作を行うことができます。 実際、最新のV8 Javascript VM（NodeJSには実装されていません）はまさにそれを行います。
数値ワームホール
もう1つの便利なモグラ塚は、数字の読み書きの仕組みを理解することです。 32ビットコンピューターの使用方法と64ビットの取得方法を覚えていますか？ そして、32ビットまでは16ビットでした。 これはどういう意味ですか？ 通常、私たちはこのように考えます-コンピューター上にあるRAMの量。 2 ^ 32 = 4294967296または4 GB。これは、32ビットコンピューターでは4 GBのメモリにしかアクセスできないことを意味します。 JSプログラムを作成するとき、通常はそれほど多くのメモリを使用しないため、それについて考える必要はありません。
ただし、32ビットコンピューターと64ビットコンピューターの違いを理解することは非常に重要です。 プロセッサが64ビットコンピューターで64ビットレジスタを受け取ったため、操作が32ビットコンピューターで32ビットレジスタしかなかった場合よりも2倍高速になりました。
このワームホールに関する情報をどのように使用できますか？
あるUint8Arrayを別のUint8Arrayにコピーする簡単なプログラムを書きましょう。 Unit8Arraysに慣れていない場合、NodeJSのバッファ、または単に「クリーン」メモリに非常に似ています。
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
繰り返しますが、パフォーマンステストを実行して速度を測定しましょう。
// 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()
私のコンピューターでは、プログラムは〜7.5秒で完了しました。 ワームホールを使用して加速するにはどうすればよいですか？ Uint8Arrayを使用すると、一度に8ビットしかコピーできませんが、64ビットコンピューターを使用すると、64ビットの情報を同時にコピーできます。 JavaScriptでこれを行うには、コピーする前にUint8ArrayをFloat64Arrayに変換します。これには費用はかかりません。
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] } }
パフォーマンステストを再度実行すると、実行時間が1秒になり、速度が8倍になります。
コピーの場合、受け入れ可能な解決策はUint8Arrayのarray.set（otherArray）メソッドを使用することです。これにより、ネイティブコードでのコピーが可能になります。これは他のワームホールよりもはるかに高速です。 参考までに、これにより、コンピューターでのテストで約0.2秒の実行結果が得られます。これは、以前のソリューションの5倍の速度です。
ワームホールに満ちた銀河銀河
上記のワームホールを使用すると、大量の実世界のアルゴリズムをはるかに高速化できます。 このようなワームホールはもっとたくさんあります。 私のお気に入りはMath.clz32です。これは、数値の32ビットバイナリ表現で先行ゼロビットの数を返すメソッドです。 このメソッドは、多くの興味深いアルゴリズムに使用できます。 これを使用して、 ビットフィールドの実装を4倍に加速しました。これにより、メモリ消費量が4倍減少し、状況によっては数字をはるかに速く並べ替えることができました。
コンピューターの基本原理を理解することで、必要な最速のプログラムを作成できます。 この知識は、JavaScriptなどの高水準言語で記述する場合でも重要です。
PS：
Olga Pereverzevaへの翻訳と翻訳の調整にご協力いただきありがとうございます