大きなstd :: listの繰り返しが非常に遅いのはなぜですか？

Question

タイトルが示すように、スタックとしてstd :: listを使用し、リストのすべての要素を反復処理するプログラムに問題がありました。リストが非常に大きくなったとき、プログラムは長すぎました。

これについて良い説明はありますか？スタック/キャッシュの動作ですか？

（リストをstd :: vectorおよびstd :: deque（ちなみに驚くべきデータ構造）に変更することで問題を解決し、すべてが突然より速くなりました）

編集：私はバカではなく、リストの中央にある要素にアクセスしません。リストで行った唯一のことは、要素の削除/追加を最初/最後に行い、リストのすべて要素を反復処理することでした。 そして、私は常にイテレータを使用してリストを反復しました。

Answer 1

リストにはひどい（存在しない）キャッシュの局所性があります。すべてのノードは新しいメモリ割り当てであり、どこでも可能です。そのため、あるノードから次のノードへのポインタをたどるたびに、メモリ内の新しい無関係な場所にジャンプします。はい、それはパフォーマンスをかなり傷つけます。キャッシュミスは、キャッシュヒットよりも2桁遅い場合があります。 vectorまたはdequeでは、ほとんどすべてのアクセスがキャッシュヒットになります。ベクトルは、単一の連続したメモリブロックであるため、繰り返し処理を行うのは、取得する速度と同じです。 dequeはいくつかの小さなメモリブロックであるため、キャッシュミスが発生することがありますが、まれに発生する可能性があり、キャッシュヒットがほとんど発生するため、反復は非常に高速になります。

リストはほとんどすべてのキャッシュミスになります。また、パフォーマンスが低下します。

実際には、リンクリストはパフォーマンスの観点から正しい選択となることはほとんどありません。

編集： コメントが指摘したように、リストに関する別の問題はデータの依存関係です。現代のCPUは操作をオーバーラップするのが好きです。しかし、次の命令がこの命令の結果に依存している場合、それはできません。

ベクトルを反復処理する場合、問題はありません。メモリをチェックインする必要なく、次のアドレスを計算してその場で読み取ることができます。現在アドレス x で読んでいる場合、次の要素はアドレス x + sizeof（T）にあります（Tは要素タイプです）。そのため、そこには依存関係がなく、CPUは次の要素またはその次の要素の読み込みをすぐに開始できますが、以前の要素を処理します。そうすれば、必要なときにデータを準備でき、RAMのデータにアクセスするコストをさらに抑えることができます。

リストで、ノード i からノード i + 1 へのポインターをたどり、 i + 1 がロードされ、 i + 2 を探す場所すらわかりません。データに依存しているため、CPUはノードを一度に1つずつ読み取るように強制され、将来のノードの読み取りを開始できません。ノードの場所がまだわからないためです。

リストがすべてのキャッシュミスではなかった場合、これは大きな問題にはなりませんでしたが、キャッシュミスが多数発生するため、これらの遅延はコストがかかります。

Answer 2

これは、リストの使用時に大量のキャッシュミスが発生するためです。ベクトルを使用すると、周囲の要素はプロセッサキャッシュに保存されます。

Answer 3

次の stackoverflowスレッドをご覧ください。

Answer 4

キャッシュの問題があります。ベクター内のすべてのデータは連続したチャンクに格納され、各リスト要素は個別に割り当てられ、メモリの非常にランダムな場所に格納されることがあります。より多くのキャッシュミスが発生します。ただし、他の回答で説明されている問題の1つに遭遇することは間違いありません。

Answer 5

単純な答えは、ベクトルの繰り返しはまったく繰り返されないためです。配列のベースから開始し、要素を次々に読み取ります。

これはCではなくC ++とマークされていますが、カバーの下で同じことをしているので、配列を任意に大きく割り当ててrealloc（）することで配列の先頭と末尾に要素を追加できることを指摘する価値があります部屋が足りなくなった場合、2つのコンパニオン配列間でingとmemmove（）ingを実行します。非常に高速です。

配列の先頭に要素を追加するコツは、先頭で配列にポインターを進め、先頭に要素を追加するときにバックアップすることで、配列の論理的な開始にバイアスをかけることです。 （スタックの実装方法）

まったく同じ方法で、負の添え字をサポートするようにCを作成できます。

C ++は、ベクターSTLクラスを使用してこれをすべて行いますが、カバーの下で何が起こっているかを覚えておく価値があります。

Answer 6

[編集：修正しました。 std :: listにはoperator []がありません。ごめんなさい。]

説明から判断するのは難しいですが、アイテムにランダムにアクセスしようとしているのではないかと思われます（インデックスなど）：

for(int i = 0; i < mylist.size(); ++i) { ... mylist[i] ... }

イテレータを使用する代わりに：

for(list::iterator i = mylist.begin(); i != mylist.end(); ++i) { ... (*i) ... }

両方の「ベクター」 ＆amp; ＆quot; deque＆quot;ランダムアクセスが得意であるため、どちらもこれらのタイプに対して適切に機能します。両方の場合でO（1）です。しかし、「リスト」はランダムアクセスが得意ではありません。インデックスを使用してリストにアクセスするには、イテレータを使用する場合のO（1）に対してO（n ^ 2）時間かかります。