Web ブラウザで 1 ～ 1,000,000 (スペースで区切って) を印刷する場合、これが最速の JavaScript である理由は何ですか?
https://stackoverflow.com/questions/137534
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
JavaScript の出力バッファリングについて読んでいました ここ, そして、著者が Web ページに 1 ～ 1,000,000 を印刷するのが最も速いと言っているスクリプトを理解しようとしていました。(ヘッダー「当選 100 万の数字のスクリプト」まで下にスクロールします。) 少し勉強した後、いくつかの質問があります。
- このスクリプトが他のアプローチと比べて非常に効率的なのはなぜですか?
- バッファリングによって処理が高速化されるのはなぜですか?
- 使用する適切なバッファ サイズはどのように決定すればよいでしょうか?
- このスクリプトをさらに最適化できる何か工夫をしている人はいますか?
(これがおそらく CS101 であることはわかっていますが、私は独学で学んだ猛烈なハッカーの 1 人であり、これに関して集団の知恵から恩恵を受けることを期待していました。ありがとう！）
解決
このスクリプトが他のアプローチと比べて非常に効率的なのはなぜですか?
作者はこのアルゴリズムに対していくつかの最適化を行っています。これらのそれぞれは、基礎となるメカニズムがどのように利用されているかについてかなり深い理解を必要とします (例:Javascript、CPU、レジスタ、キャッシュ、ビデオカードなど)。彼が行っている重要な最適化は 2 つあると思います (残りは単なるアイシングです)。
- 出力のバッファリング
- 文字列操作ではなく整数演算を使用する
バッファリングについては、明示的に質問されているので、すぐに説明します。彼が利用している整数計算には、パフォーマンス上の 2 つの利点があります。整数加算は文字列操作よりも 1 回の操作あたりのコストが低く、使用するメモリも少なくなります。
JavaScript と Web ブラウザーがブラウザー内で整数から表示グリフへの変換をどのように処理するかはわかりません。そのため、文字列と比較した場合、document.write に整数を渡す場合にペナルティが発生する可能性があります。ただし、1,000,000 ～ 1,000 回の整数加算を実行するのに対し、(1,000,000 / 1000) 回の document.write 呼び出しを実行しています。これは、メッセージを作成するためにメッセージをディスプレイに送信するよりも、およそ 3 桁多くの操作を実行していることを意味します。したがって、document.write に整数と文字列を送信する場合のペナルティは、整数を操作するパフォーマンス上の利点を相殺する 3 桁を超える必要があります。
バッファリングによって処理が高速化されるのはなぜですか?
これが機能する理由の詳細は、使用しているプラットフォーム、ハードウェア、実装によって異なります。いずれにせよ、ボトルネックを引き起こすリソースに対してアルゴリズムのバランスをとることがすべてです。
たとえば、ファイル I/O の場合、回転ディスクが一度に一定量しか書き込めないという事実を利用するバッファーが役立ちます。作業が少なすぎると、ディスクの回転時にスピンドルのヘッドの下を通過する利用可能なビットをすべて使用できなくなります。あまりにも多くの時間を与えすぎると、ディスクが書き込みを完了するまでアプリケーションは待機 (またはスリープ状態) する必要があり、次のレコードの書き込み準備にかかる時間が費やされる可能性があります。ファイル I/O の理想的なバッファ サイズを決定する主な要素には、次のようなものがあります。セクター サイズ、ファイル システム チャンク サイズ、インターリーブ、ヘッド数、回転速度、面密度などです。
CPU の場合、重要なのはパイプラインをフル状態に保つことです。CPU に与える仕事が少なすぎると、CPU はユーザーからのタスクの実行を待つ間、NO OP の回転に時間を費やすことになります。CPU に多くの負荷を与えすぎると、ディスクやビデオ カードなど、並行して実行できる他のリソースにリクエストをディスパッチできなくなる可能性があります。これは、後で CPU が何もせずにこれらが返されるのを待たなければならないことを意味します。CPU でのバッファリングの主な要因は、(CPU に) 必要なものすべてをできるだけ FPU/ALU の近くに置くことです。一般的なアーキテクチャでは、これは次のようになります (近い順に)。レジスタ、L1 キャッシュ、L2 キャッシュ、L3 キャッシュ、RAM。
画面に 100 万個の数字を書き込む場合は、ビデオ カードを使用して画面上にポリゴンを描画することになります。このように考えてみてください。新しい数値が追加されるたびに、ビデオ カードは画面上にポリゴンを描画するために 100,000,000 回の操作を実行する必要があるとします。極端な例として、一度に 1 つの数値をページ上に配置し、それをビデオ カードに書き出させる場合、これを 1,000,000 の数値に対して行うと、ビデオ カードは 10^14 の演算、つまり 100 兆の演算を実行する必要があります。逆に、100 万の番号全体を取得してビデオ カードに一度に送信した場合、必要な操作は 1 億回だけです。最適なポイントはその中間です。これを一度に 1 つずつ実行すると、CPU は 1 単位の作業を実行し、GPU が表示を更新する間、長時間待機します。最初に 1M 項目文字列全体を書き込むと、CPU が高速に動作している間、GPU は何もしません。
使用するバッファ サイズはどのように決定しますか?
特定のアルゴリズム（例:インターネット ルーティングのパケット ルーティングを作成する場合)、通常、これを数学的に決定することはできません。通常、それは経験的に見つかります。値を推測し、試して結果を記録し、別の値を選択します。管理しているボトルネックに基づいて、どこから始めるべきか、どの範囲を調査すべきかについて、経験に基づいた推測を行うことができます。
このスクリプトをさらに最適化できる何か工夫をしている人はいますか?
これが機能するかどうかはわかりませんし、テストもしていませんが、コンピュータのアンダーピニングはバイナリであり、ワードサイズは 通常 2 の倍数です (ただし、常にそうとは限りません)。たとえば、60 バイトよりも 64 バイトが最適である可能性が高く、1000 バイトよりも 1024 が最適である可能性が高くなります。この問題に特有のボトルネックの 1 つは、これまでのほとんどのブラウザ (Google Chrome は私が知っている限り最初の例外) では、JavaScript が他の Web ページ レンダリング メカニズムと同じスレッド内でシリアルに実行されることです。これは、JavaScript がバッファーを埋める作業を行った後、document.write 呼び出しが戻るまで長時間待機することを意味します。Chrome のように、JavaScript が別のプロセスとして非同期で実行された場合、速度が大幅に向上する可能性があります。もちろん、これはボトルネックを使用するアルゴリズムではなく、ボトルネックの原因を攻撃することになりますが、場合によってはそれが最善の選択肢となります。
私が望んでいるほど簡潔ではありませんが、良い出発点になれば幸いです。バッファリングは、コンピューティングにおけるあらゆる種類のパフォーマンス問題にとって重要な概念です。コードが使用している基礎となるメカニズム (ハードウェアとソフトウェアの両方) をよく理解することは、パフォーマンスの問題を回避または解決するのに非常に役立ちます。
他のヒント
100 万個の数字を出力する際に最も遅いのは、ブラウザがページを再描画することだと思います。そのため、document.write() を呼び出す回数は少ないほど良いでしょう。もちろん、これは大規模な文字列連結に対してバランスを取る必要があります (割り当てとコピーが必要となるため)。
適切なバッファ サイズは実験を通じて決定します。
他の例では、バッファリングは自然な境界に沿って位置を揃えるのに役立ちます。ここではいくつかの例を示します
- 32 ビット CPU は 32 ビットをより効率的に転送できます。
- TCP/IP パケットには最大サイズがあります。
- ファイル I/O クラスには内部バッファがあります。
- TIFF などの画像は、データとともにストリップに保存される場合があります。
他のシステムの自然な境界に合わせると、多くの場合、パフォーマンス上の利点が得られます。
それについて考える1つの方法は、document.write（）の1回の呼び出しが非常に高価であると考えることです。ただし、配列を作成してその配列を文字列に結合することはできません。したがって、document.write（）の呼び出し回数を減らすと、数値を書き込むのに必要な全体的な計算時間が実質的に短縮されます。
バッファは、2つの異なるコストの作業を結び付けようとする方法です。
配列の計算と入力は、小さな配列の場合はコストが低く、大きな配列の場合はバグが大きくなります。 document.writeは、書き込みのサイズに関係なく一定の大きなコストがかかりますが、入力が大きい場合はo（n）未満になります。
したがって、書き込みのために大きな文字列をキューに入れたり、バッファリングすると、全体的なパフォーマンスが向上します。
ちなみに記事を見つけてください。
だから、これは私を狂気に駆り立てています。本当に最速だとは思いません。だから誰もが遊ぶことができる私の実験です。おそらく私はそれを間違っているか何かを書いたかもしれませんが、バッファを使用する代わりに一度にすべてを実行することは実際にはより速い操作であるように見えます。または少なくとも私の実験では。
<html>
<head>
<script type="text/javascript">
function printAllNumberBuffered(n, bufferSize)
{
var startTime = new Date();
var oRuntime = document.getElementById("divRuntime");
var oNumbers = document.getElementById("divNumbers");
var i = 0;
var currentNumber;
var pass = 0;
var numArray = new Array(bufferSize);
for(currentNumber = 1; currentNumber <= n; currentNumber++)
{
numArray[i] = currentNumber;
if(currentNumber % bufferSize == 0 && currentNumber > 0)
{
oNumbers.textContent += numArray.join(' ');
i = 0;
}
else
{
i++;
}
}
if(i > 0)
{
numArray.splice(i - 1, bufferSize - 1);
oNumbers.textContent += numArray.join(' ');
}
var endTime = new Date();
oRuntime.innerHTML += "<div>Number: " + n + " Buffer Size: " + bufferSize + " Runtime: " + (endTime - startTime) + "</div>";
}
function PrintNumbers()
{
var oNumbers = document.getElementById("divNumbers");
var tbNumber = document.getElementById("tbNumber");
var tbBufferSize = document.getElementById("tbBufferSize");
var n = parseInt(tbNumber.value);
var bufferSize = parseInt(tbBufferSize.value);
oNumbers.textContent = "";
printAllNumberBuffered(n, bufferSize);
}
</script>
</head>
<body>
<table border="1">
<tr>
<td colspan="2">
<div>Number: <input id="tbNumber" type="text" />Buffer Size: <input id="tbBufferSize" type="text" /><input type="button" value="Run" onclick="PrintNumbers();" /></div>
</td>
</tr>
<tr>
<td style="vertical-align:top" width="30%">
<div id="divRuntime"></div>
</td>
<td width="90%">
<div id="divNumbers"></div>
</td>
</tr>
</table>
</body>
</html>
