std::pair<int, int> と 2 つの int を持つ構造体

Question

ACM の例では、動的プログラミング用に大きなテーブルを構築する必要がありました。各セルに 2 つの整数を保存する必要があったので、 std::pair<int, int>. 。ただし、それらの巨大な配列を割り当てるには 1.5 秒かかりました。

std::pair<int, int> table[1001][1001];

その後、このコードを次のように変更しました

struct Cell {
    int first;
    int second;
}

Cell table[1001][1001];

割り当てには 0 秒かかりました。

この大きな時間差は何が説明されるのでしょうか?

Answer 1

std :: pair＆lt; int、int＆gt; :: pair（）コンストラクターは、フィールドをデフォルト値（ int の場合はゼロ）とで初期化しますstruct Cell にはありません（自動生成されたデフォルトのコンストラクターは何もしないため）。

初期化には、各フィールドへの書き込みが必要であり、比較的時間がかかる大量のメモリアクセスが必要です。 struct Cell を使用すると、代わりに何も実行されず、何もしないのが少し速くなります。

Answer 2

これまでの回答では、問題の大きさを完全には説明していません。

sharptoothが指摘したように、ペアソリューションは値をゼロに初期化します。 Lemurikが指摘したように、ペアソリューションはメモリの連続ブロックを初期化するだけではなく、テーブル内のすべての要素に対してペアコンストラクターを呼び出しています。ただし、それでも1.5秒かかります。他に何かが起こっています。

ここに私のロジックがあります：

たとえば、1.33ghzで実行している古代のマシンを使用している場合、1.5秒は2e9クロックサイクルです。構築する2e6ペアがあるので、各ペアコンストラクターはなんとか1000サイクルかかります。 2つの整数をゼロに設定するコンストラクターを呼び出すのに1000サイクルはかかりません。キャッシュミスにより、どのくらい時間がかかるかわかりません。数が100サイクル未満である場合、それを信じます。

これらすべてのCPUサイクルがどこに向かっているのかを見るのは面白いと思いました。必要な無駄のレベルを達成できるかどうかを確認するために見つけることができた、最も古くて古いC ++コンパイラを使用しました。そのコンパイラはVC ++ v6でした。デバッグモードでは、理解できないことを行います。テーブル内の各アイテムのペアコンストラクターを呼び出す大きなループがあります-十分に公平です。そのコンストラクターは2つの値をゼロに設定します-十分に公平です。しかし、その直前に、68バイト領域のすべてのバイトを0xccに設定します。その領域は、大きなテーブルが始まる直前です。次に、その領域の最後の要素を0x28F61200で上書きします。ペアコンストラクターのすべての呼び出しはこれを繰り返します。おそらくこれはコンパイラーによる何らかの種類のブックキーピングなので、実行時にポインターエラーをチェックするときにどの領域が初期化されるかを知っています。これが何であるかを正確に知りたい。

とにかく、それは余分な時間がどこに向かっているのかを説明するでしょう。明らかに、別のコンパイラはこれほど悪くないかもしれません。確かに、最適化されたリリースビルドはそうではありません。

Answer 3

それはstd :: pairの作成方法だと思います。ペアコンストラクターを1001x1001回呼び出す際のオーバーヘッドは、メモリ範囲を単に割り当てる場合よりも大きくなります。

Answer 4

これらはすべて非常に優れた推測ですが、誰もが知っているように、推測は信頼できません。

ただランダムに言うと思います 一時停止します 1.5 秒以内ですが、かなり早くする必要があります。各寸法を約 3 倍にすると、10 秒以上かかるようになり、一時停止しやすくなります。

または、デバッガでそれを取得し、ペア コンストラクター コードで分割し、シングル ステップで動作を確認することもできます。

いずれにせよ、質問に対して単なる推測ではなく、明確な答えが得られるでしょう。

Answer 5

これは、C ++を記述し、STLを慎重に使用する必要があることを示す良い例です。何か考えはありますか？

私のプロジェクトは、C＆amp; C ++コードレベルベンチマークテストツールに取り組んでいます。このツールでは、多くのコードサンプルを作成して、「良い」ものを見つけます。コードと「悪い」とはコーディング習慣。 C9B.Mの詳細については、 http://effodevel.googlecode.com をご覧ください。計画中。このようなケースをたくさん経験したことがある方は、プロジェクトに参加してください。