ここでJavaScript の出力バッファリングについて読んでいて、ウェブページに 1 から 1,000,000 を印刷するのが最も速いと著者が言うスクリプトに頭を悩ませようとしていました。(ヘッダーの「100 万回の勝利のスクリプト」までスクロールします。) 少し調べた後、いくつか質問があります。
(これはおそらく CS101 だと思いますが、私は独学のハッカーの 1 人であり、この集団の知恵から恩恵を受けることを望んでいました。ありがとう!)
著者がこのアルゴリズムに対して行っているいくつかの最適化があります。これらのそれぞれについて、基盤となるメカニズム (Javascript、CPU、レジスター、キャッシュ、ビデオ カードなど) がどのように利用されているかをかなり深く理解する必要があります。彼が行っている重要な最適化は 2 つあると思います (残りは単なるアイシングです)。
バッファリングについて明示的に質問されたので、すぐにバッファリングについて説明します。彼が利用している整数演算には、パフォーマンス上の利点が 2 つあります。整数の加算は、文字列操作よりも 1 回の操作あたりのコストが低く、使用するメモリも少なくなります。
JavaScript と Web ブラウザーがブラウザーで整数から表示グリフへの変換をどのように処理するかはわかりません。そのため、整数を document.write に渡すと、文字列と比較した場合にペナルティが生じる可能性があります。ただし、彼は (1,000,000 / 1000) の document.write 呼び出しと 1,000,000 - 1,000 の整数の追加を実行しています。これは、メッセージをディスプレイに送信する操作よりも、メッセージを形成する操作の方が約 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 がディスプレイを更新する間、長時間待機します。
特定のアルゴリズム (インターネット ルーティング用のパケット ルーティングを記述するなど) を使用して、非常に具体的で明確に定義されたプラットフォームを対象としていない限り、通常、これを数学的に決定することはできません。通常、経験的に見つけます。値を推測して試し、結果を記録してから、別の値を選択します。管理しているボトルネックに基づいて、どこから開始し、どの範囲を調査するかについて、経験に基づいた推測を行うことができます。
これが機能するかどうかはわかりませんが、テストしていませんが、コンピューターのアンダーピニングはバイナリであり、ワードサイズは通常2 の倍数 (ただし、常にそうとは限りません!)。たとえば、64 バイトは 60 バイトよりも最適である可能性が高く、1024 は 1000 よりも最適である可能性が高くなります。に注意してください) 残りの Web ページ レンダリング メカニズムと同じスレッド内で、javascript をシリアルに実行します。これは、javascript が何らかの作業を行ってバッファを埋め、その後 document.write 呼び出しが戻るまで長時間待機することを意味します。Chrome のように、javascript が別のプロセスとして非同期に実行された場合、速度が大幅に向上する可能性があります。もちろん、これはボトルネックを使用するアルゴリズムではなく、ボトルネックの原因を攻撃することですが、それが最善の選択肢である場合もあります。
私が望むほど簡潔ではありませんが、良い出発点になることを願っています。バッファリングは、コンピューティングにおけるあらゆる種類のパフォーマンスの問題にとって重要な概念です。コードが使用している基本的なメカニズム (ハードウェアとソフトウェアの両方) を十分に理解することは、パフォーマンスの問題を回避または対処するのに非常に役立ちます。
1m の数字を印刷する際に最も遅いのは、ブラウザーがページを再描画することだと思います。したがって、document.write() を呼び出す回数が少ないほど良いでしょう。もちろん、これは大きな文字列の連結に対してバランスをとる必要があります (割り当てとコピーが必要なため)。
適切なバッファ サイズの決定は、実験によってわかります。
他の例では、バッファリングは自然な境界に沿って整列するのに役立ちます。下記は用例です
他のシステムの自然な境界に合わせると、多くの場合、パフォーマンスが向上します。
だから、これが本当に最速だとは思わないので、これは私を夢中にさせてきました。そこで、誰でも遊べる私の実験を紹介します。書き方が間違っていたのかもしれませんが、バッファを使用する代わりに一度にすべてを実行する方が実際には高速な操作のように見えます。または、少なくとも私の実験では。
<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>
それについて考える 1 つの方法は、document.write() への 1 回の呼び出しが非常に高価であると考えることです。ただし、配列を作成してその配列を文字列に結合することはできません。したがって、document.write() の呼び出し回数を減らすと、数値の書き込みに必要な全体的な計算時間が効果的に短縮されます。
バッファーは、コストの異なる 2 つの作業を結び付けようとする方法です。
配列の計算と入力には、小さな配列の場合は小さなコストがかかり、大きな配列の場合は大きなコストがかかります。document.write は、書き込みのサイズに関係なく大きな一定のコストを持ちますが、より大きな入力に対しては o(n) よりも小さくなります。
そのため、書き込みのために大きな文字列をキューに入れるか、それらをバッファリングすると、全体的なパフォーマンスが向上します。
ところで、記事の素敵な発見。