0

大きなブール値の 2 次元配列 (23MB で合計 250 億要素の 5000X5000) を作成します。次に、ランダムな true または false ですべての要素をループしてインスタンス化します。次に、ループしてすべての要素を読み取ります。2,500 万の要素すべてが 100 ミリ秒以内に読み取られます。

23MB は大きすぎて CPU のキャッシュに収まりません。私のプログラムは単純すぎて、どのような種類のコンパイラ最適化の恩恵も受けられないと思います。そのため、プログラムが RAM から 2500 万要素を ~100ms で読み取っていると結論付けてよろしいですか?

    #include "stdafx.h"
    #include <iostream>
    #include <chrono>
    using namespace std;

    int _tmain(int argc, _TCHAR* argv[])
    {
        bool **locs;
        locs = new bool*[5000];
        for(int i = 0; i < 5000; i++)
            locs[i] = new bool[5000];
        for(int i = 0; i < 5000; i++)
            for(int i2 = 0; i2 < 5000; i2++)
                locs[i][i2] = rand() % 2 == 0 ? true : false;
        int *idx = new int [5000*5000];
        for(int i = 0; i < 5000*5000; i++)
            *(idx + i) = rand() % 4999;

        bool val;
        int memAccesses = 0;
        auto start = std::chrono::high_resolution_clock::now();
        for(int i = 0; i < 5000*5000; i++) {
            val = locs[*(idx + i)][*(idx + ++i)];
            memAccesses += 2;
        }
        auto finish = std::chrono::high_resolution_clock::now();

        std::cout << std::chrono::duration_cast<std::chrono::nanoseconds>(finish-start).count() << " ns\n";
        std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(finish-start).count() << " ms\n";
        cout << "TOTAL MEMORY ACCESSES: " << memAccesses << endl;
        cout << "The size of the array in memory is " << ((sizeof(bool)*5000*5000)/1048576) << "MB";

        int exit; cin >> exit;
        return 0;
    }

    /*
    OUTPUT IS:

        137013700 ns
        137 ms
        TOTAL MEMORY ACCESSES: 25000000
        The size of the array in memory is 23MB
    */
4

4 に答える 4

2

メモリの一部 (ブロック) は一度にプロセッサ キャッシュに格納されるため、プロセッサはそれらのアイテムにすばやくアクセスできます。ただし、その速度は、最新のメモリでは完全に妥当です。最も遅い DDR3 RAM でさえ、約 6 GB/秒でデータを転送できます。

于 2013-06-25T13:24:34.520 に答える
2

キャッシュの使用は、プログラムの複雑さとは無関係です。データが RAM から読み取られるたびに、キャッシュに入れられます。キャッシュには一定のサイズがあるため、常にその量のデータを利用できます。前のメモリ ロケーションの次のメモリ ロケーションにアクセスすると、すでにキャッシュされている可能性が高くなります。この場合、RAM はアクセスされません。

知識を広げるために、CPU キャッシュ ウィキペディアのエントリを読むことをお勧めします。

ところで：val = locs[*(idx + i)][*(idx + ++i)];これは左から右に評価されると確信していますか？私はそうではありません。これは未定義の動作です。++iアクセサー行の下に置くことをお勧めします。

//編集：

メモリから読み取った値は何も処理されません。これらの命令がまったく実行されない可能性は十分にあります。バイトコードを確認するか、(void) val;強制的に生成する命令を追加してください。

于 2013-06-25T13:23:45.513 に答える