この投稿は 2 つの主要なセクションに分かれています。最初のセクションでは、元のテスト ケースと結果、およびそれに対する私の考えを紹介します。2 番目のセクションでは、変更されたテスト ケースとその結果について詳しく説明します。
このトピックの元のタイトルは、「リンクされたリストよりもはるかに高速な配列の完全反復」でした。新しいテスト結果 (セクション 2 で提示) により、タイトルが変更されました。
セクション 1: 元のテスト ケース
完全な一方向のシーケンシャル トラバーサルの場合、リンク リストと配列のパフォーマンスは類似していることが知られていますが、連続配列のキャッシュ フレンドリ性 (参照局所性) により、パフォーマンスが (わずかに) 優れている可能性があります。それが実際にどのように機能するか (Android、Java) を確認するために、上記の主張を調べ、いくつかの測定を行いました。
まず、私の素朴な仮定です。次のクラスを見てみましょう。
private static class Message {
public int value1;
public Message next;
public Message(java.util.Random r, Message nextmsg) {
value1 = r.nextInt();
next = nextmsg;
}
}
最初の測定シナリオでは、そのnextフィールドはまったく使用されません。以下のコードは、1,000,000 個のMessageインスタンスの配列を作成し、ループで配列を反復処理します。反復にかかる時間を測定します。
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message[] messages = new Message[cnt];
for (int i = 0; i < cnt; i++) {
messages[i] = new Message(r, null);
}
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
for (int i = 0; i < cnt; i++) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
Log.w("TEST", "Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
Message2 番目の測定では、代わりにオブジェクトのリンク リストを作成して測定します。
Log.i("TEST", "Preparing...");
final int cnt = 1000000;
int val = 0;
java.util.Random r = new java.util.Random();
Message current = null;
Message previous = null;
for (int i = 0; i < cnt; i++) {
current = new Message(r, previous);
previous = current;
}
previous = null;
Log.i("TEST", "Starting iterating...");
long start = SystemClock.uptimeMillis();
while (current != null) {
if (current.value1 > 564645) {
val++;
}
current = current.next;
}
Log.w("TEST","Time: " + (SystemClock.uptimeMillis() - start) + ", result: " + val);
最初のテストでは常に41 ～ 44ミリ秒が生成されますが、2 番目のテストでは80 ～ 85ミリ秒が生成されます。リンクされたリストの反復は 100% 遅いようです。
私の（おそらく欠陥のある）一連の思考と問題は次のとおりです。修正を歓迎します (実際、推奨します)。
OK、配列が連続したメモリ ブロックであることを読み取ることがよくあります。そのため、その要素に順次アクセスする方が、リンク リストの場合よりもキャッシュに適しています。しかし、私たちの場合、配列の要素はオブジェクト参照のみであり、Messageオブジェクト自体ではありません (Java では、配列に埋め込んで格納できる値型、つまり C# のような構造体はありません)。したがって、「参照の局所性」は配列要素自体にのみ適用され、これらはオブジェクトのアドレスを指定するだけです。したがって、Messageインスタンス (一般に) はメモリ内の「どこにでも」ある可能性があるため、「参照の局所性」はインスタンス自体には適用されません。この時点から、リンクされたリストの場合と同じように見えます。インスタンス自体はメモリ内の「どこにでも」存在する可能性があります。配列は、それらの参照が連続したブロックに格納されることを保証するだけです...
...そしてここにユースケースがあります: 完全なシーケンシャルトラバーサル (反復)。まず、各ケースでインスタンスへの参照を取得する方法を調べてみましょう。配列の場合、連続したブロックにあるため、非常に効率的です。しかし、連結リストの場合も問題ありません。Messageインスタンスにアクセスすると (反復するのはそのためです!)、すぐに次のインスタンスへの参照を取得できるからです。そして、Messageすでにフィールドにアクセスしたので、別のフィールド (「次」) へのアクセスはキャッシュでサポートされている必要があります (同じオブジェクトのフィールドにも参照の局所性があり、それらも連続したブロックにあります) ）。要約すると、次のように分類されるようです。
- 配列は、参照に対してキャッシュに適した反復を提供します。
Messageインスタンス自体はメモリ内の「どこにでも」ある可能性があり、これらにもアクセスする必要があります。 - リンクされたリストは、現在の
Messageインスタンスがアクセスされたときに次の要素への参照が取得されることを提供します。Messageとにかく各インスタンスにアクセスする必要があるため (配列の場合と同様)、これは「無料」です。
したがって、上記に基づいて、配列はリンクされたリストよりも優れていないように見えます。唯一の例外は、配列がプリミティブ型の場合です (ただし、そのような場合、連結リストと比較しても意味がありません)。だから私は彼らが同じように機能することを期待していましたが、大きな違いがあったのでそうではありませんでした. 実際、要素にアクセスするたびに配列のインデックス付けで範囲チェックが必要であると仮定すると、(理論的には) リンク リストの方が高速でさえある可能性があります。(配列アクセスの範囲チェックはおそらくJITで最適化されているので、その点が腑に落ちないのは承知しております。)
私の推測は次のとおりです。
100% の違いの原因は、おそらくアレイのキャッシュ フレンドリ性ではありません。代わりに、JIT は、リンクされたリスト トラバーサルの場合には実行できない最適化を実行します。範囲チェックと (VM レベルの) null チェックが排除された場合、「array-get」バイトコード命令は、リンクされたリストの場合 (? ）。
インスタンスはメモリ内の「どこにでも」ある可能性があり
Messageますが、「同時に」割り当てられているため、おそらく互いに非常に近くなっています。ただし、1,000,000 個のインスタンスをキャッシュすることはできません。それらの一部のみです。このような場合、シーケンシャル アクセスは配列とリンク リストの両方のケースでキャッシュに適しているため、違いは説明できません。Messageアクセスするインスタンスのインテリジェントな「予測」(プリフェッチ) つまり、どういうわけか、Messageインスタンス自体にはまだキャッシュフレンドリー性がありますが、それは配列アクセスの場合のみです。
更新: いくつかのコメントを受け取ったので、以下に対応したいと思います。
@評判が悪い：
リンクされたリストは、上位アドレスから下位アドレスにアクセスされます。逆の場合、つまり next が前のオブジェクトではなく、より新しいオブジェクトを指している場合
とても良いスポットです！レイアウトがテストに影響を与える可能性があるとは、この細部まで考えていませんでした。今日テストして、結果を返します。(編集: 結果はこちらです。この投稿を「セクション 2」で更新しました)。
@トーベンのコメント:
また、この演習全体はかなり役に立たないように思えます。100000回の反復で4msの改善について話している. 時期尚早の最適化のようです。これがボトルネックである状況がある場合は、それについて説明してください。調査することができます (これよりも興味深い問題であることは間違いありません)。
興味がない場合は、このトピックを無視できます (4 回投稿する代わりに)。「時期尚早の最適化」という根拠のない仮定について - SO を読みすぎて、産業レベルの開発をほとんど実行していないことを残念に思います。具体的な状況は、これらのリストを毎秒数回トラバースする必要があるシミュレーション関連のソフトウェアにあります。実際、120 ミリ秒以上のレイテンシーは、アプリの応答性に影響を与える可能性があります。
あなたがこれに込めた考えに感謝しますが、あなたの投稿から質問を見つけることができません. :) 編集: そして、配列の反復は 50% 高速です。100% 速いということは、消費される時間がゼロであることを意味します。
議論がそうでないことを意味するのに、なぜ非常に大きな違いが存在するのか疑問に思っていることは、私の投稿からかなり明白だったと確信しています。訂正していただきありがとうございます。実際、リンク リストの場合は 100% 遅いと書きたかったのです。
セクション 2: 変更されたテスト ケース
評判の悪い私にとって非常に興味深い観察がありました：
リンクされたリストは、上位アドレスから下位アドレスにアクセスされます。逆の場合、つまり next が前のオブジェクトではなく、より新しいオブジェクトを指している場合
nextポインターの方向がノードのインスタンス化順序と同じになるように、リンクされたリスト構造を変更しました。
Message current = null;
Message previous = new Message(r, null);
Message first = previous;
for (int i = 0; i < cnt; i++) {
current = new Message(r, null);
previous.next = current;
previous = current;
}
previous = current = null;
(作成アルゴリズムは最もコンパクトなものではないかもしれないことに注意してください。私はもう少し良い方法を知っていたと思います。) このリンクされたリストを反復処理するコード:
while (first != null) {
if (first.value1 > 564645) {
val++;
}
first = first.next;
}
そして今、私が得る結果は常に37〜39ミリ秒です（OK、それはまさにアレイのパフォーマンスであると言えますが、実際には、すべてのテストケースで常にわずかに高速です。） 「逆方向」の80ミリ秒の代わりにリンクされたリスト、それは 2 倍の速さです!
次に、元の配列テスト ケースでも同様のテストを行いました。配列トラバーサルを反対方向 (カウントダウン ループ) に変更しました。
for (int i = cnt - 1; i >= 0; i--) {
Message msg = messages[i];
if (msg.value1 > 564645) {
val++;
}
}
結果は常に85 ～ 90ミリ秒です。元のテスト ケースでは 40 ～ 41 ミリ秒かかりました。
現在、2 つの新しい結論 (および 1 つの質問) があるようです。
リンクされたリストと比較した場合、配列の「参照の局所性」(連続したメモリブロックによる)は「参照型」(つまりオブジェクト) 配列の場合には利点を提供しないという元の主張は正しいようです。 . これは、オブジェクト配列がオブジェクト インスタンス自体ではなく、オブジェクト インスタンスへの参照のみを保持するためです (理論的には、リンク リストの場合と同様に、メモリ内の「任意の場所」に存在する可能性があります)。
私のテストケースでは、配列シナリオの場合でも、結果は traversal の方向に依存しているようです (!)。これはどのように可能ですか？
私のテスト結果を要約するには：
「順方向」トラバーサルでは、連結リストは配列トラバーサルよりもわずかに優れています (まさに予想どおりです。インスタンスが取得されるとすぐに次の参照
Messageが得られます。つまり、アドレスを取得するために配列要素にアクセスする必要さえありません)。「後方」方向のトラバーサルでは、どちらもパフォーマンスが約 100% 低下します (また、リンク リストは配列よりもパフォーマンスがわずかに優れています)。
何か案は？
更新 1: dlthorpeは非常に貴重なコメントをしました。この「なぞなぞ」の答えを見つけるのに役立つかもしれないので、ここにコピーします。
ハードウェアがメモリ キャッシュ コントローラーに先読みページ プリフェッチを実装しているという兆候はありますか? メモリ参照に必要なメモリ ページのみをロードする代わりに、前方プログレッシブ読み取りを見越して、次に高いページもロードしますか? これにより、メモリを介した順方向の進行に対するページ ロードの待機はなくなりますが、メモリの逆方向の進行に対するページ ロードの待機はなくなりません。
[..]
根本的に異なるハードウェアでテストすることをお勧めします。ほとんどのモバイル デバイスは、何らかの形式の ARM SoC を実行しています。テスト ケースが、PC や Mac などの Intel ハードウェアで同様の偏りを示しているかどうかを確認します。古い PowerPC Mac を掘り起こすことができれば、なおさらです。これらが同様の結果を示さない場合は、ARM プラットフォームまたはその Java 実装に固有のものがあることを示しています。
[..]
アクセス パターンはほとんど連続していますが、方向は異なります。下にある何かがプリフェッチを実行しているが、一方向のみ (次の上位アドレス ブロックをプリフェッチ) で実行している場合、その方向で実行されるテストを優先して結果が歪められます。
更新 2: PC (2009 年 2 月の Core i7 Nehalem アーキテクチャ、8 GB RAM、Windows 7) でテストを実行しました。.NET 2.0 ソース コード プロジェクトで C#.NET を使用しました (ただし、マシンには .NET 4 がインストールされています)。2500 万のMessageインスタンスでの私の結果:
- リンクされたリスト: 57 ～ 60ミリ秒
- アレイ: 60 ～ 63ミリ秒
読む方向は結果に影響を与えないようでした。