C++プログラムで大容量のデータが不足しています

Question

私が書いたC++プログラムの問題を解決しようとしています。私は基本的に記憶が不足しています。プログラムはキャッシュシミュレータです。事前に収集したメモリアドレスを持っているファイルは次のように、あります：

スレッド住所タイプサイズ命令ポインタは
0 0x7fff60000000 1 8 0x7f058c482af3

100から500000000000ようなエントリが存在する場合があります。まず、これらのエントリをすべて読み込み、ベクトルに格納しようとしています。また、読んでいる間、私はこれらのアドレスのセットを（マップを使用して）構築し、特定のアドレスのシーケンス番号を格納します。シーケンス番号は単にファイル内のアドレス入力の位置を意味します（1つのアドレスは複数回見られます）。大きな入力の場合、プログラムは失敗し、3,000万回目のエントリでbad_allocエラーが発生します。私は記憶がなくなっていると思う。どのようにして問題を回避できるのかアドバイスしてください。このような大規模なデータを処理する別の方法がありますか？どうもありがとうございました！長い投稿を申し訳ありません。私はいくつかの文脈と私が書いている実際のコードを与えたいと思っていました。

以下は関連するコードです。 ParseTaceFile（）は各行を読み取り、アドレスとサイズを取得する StoreTokens（）を呼び出し、アドレスをベクトルとマップに実際に格納するAddAddress（）を呼び出します。クラス宣言も以下に示します。 AddAddress（）の最初のtryブロックは、実際にbad_alloc例外をスローします。アドレストレースファイルの読み込み

...

エラー...

読書キャッシュ構成ファイル...

キャッシュパラメータが読み込ま：

void AddressList::ParseTraceFile(const char* filename) { 
    std::ifstream in_file; 
    std::cerr << "Reading Address Trace File..." << std::endl; 
    in_file.exceptions(std::ifstream::failbit | std::ifstream::badbit); 
    char *contents = NULL; 
    try { 
    in_file.open(filename, std::ifstream::in | std::ifstream::binary); 
    in_file.seekg(0, std::ifstream::end); 
    std::streampos length(in_file.tellg()); 
    if (length < 0) { 
     std::cerr << "Can not read input file length" << std::endl; 
     throw ExitException(1); 
    } 
    contents = (new char[length]); 
    in_file.seekg(0, std::ifstream::beg); 
    in_file.read(contents, length); 
    in_file.close(); 
    uint64_t linecount = 0, i = 0, lastline = 0, startline = 0; 
    while (i < static_cast<uint64_t>(length)) { 
     if ((contents[i] == '\n') or (contents[i] == EOF)) { 
     contents[i] = '\0'; 
     lastline = startline; 
     startline = i + 1; 
     ++linecount; 
     if (linecount > 1) { 
      StoreTokens((contents + lastline), &linecount); 
     } 
     } 
     ++i; 
    } 
    } catch (std::bad_alloc& e) { 
    delete [] contents; 
    std::cerr << "error allocating memory while parsing" << std::endl; 
    throw; 
    } catch (std::ifstream::failure &exc1) { 
    if (!in_file.eof()) { 
     delete[] contents; 
     std::cerr << "error in reading address trace file" << exc1.what() 
      << std::endl; 
     throw ExitException(1); 
    } 
    } 
    std::cerr << "Done" << std::endl; 
} 
//=========================================================  
void AddressList::StoreTokens(char* line, uint64_t * const linecount) { 
    uint64_t address, size; 
    char *token = strtok(line, " \t"); 
    uint8_t tokencount = 0; 
    while (NULL != token) { 
    ++tokencount; 
    switch (tokencount) { 
    case 1: 
     break; 
    case 2: 
     address = strtoul(token, NULL, 16); 
     break; 
    case 3: 
     break; 
    case 4: 
     size = strtoul(token, NULL, 0); 
     break; 
    case 5: 
     break; 
    default: 
     break; 
    } 
    token = strtok(NULL, " \t"); 
    } 
    AddAddress(address, size); 
} 
//================================================================ 
void AddressList::AddAddress(const uint64_t& byteaddr, const uint64_t& size) { 

    //allocate memory for the address vector 
    try { 
    if ((sequence_no_ % kReserveCount) == 0) address_list_.reserve(kReserveCount); 

    } catch (std::bad_alloc& e) { 
    std::cerr 
     << "error allocating memory for address trace vector, address count" 
     << sequence_no_ << std::endl; 
    throw; 
    } 
    uint64_t offset = byteaddr & (CacheParam::Instance()->LineSize() - 1); 
    //lineaddress = byteaddr >> CacheParam::Instance()->BitsForLine(); 
    // this try block is for allocating memory for the address set and the queue it holds 
    try { 
    // splitter 
    uint64_t templinesize = 0; 
    do { 
     Address temp_addr(byteaddr + templinesize); 
     address_list_.push_back(temp_addr); 
     address_set_[temp_addr.LineAddress()].push(sequence_no_++); 
     templinesize = templinesize + CacheParam::Instance()->LineSize(); 
    } while (size + offset > templinesize); 
    } catch (std::bad_alloc& e) { 
    address_list_.pop_back(); 
    std::cerr 
    << "error allocating memory for address trace set, address count" 
    << sequence_no_ << std::endl; 
    throw; 
    } 
} 

//====================================================== 
typedef std::queue<uint64_t> TimeStampQueue; 
typedef std::map<uint64_t, TimeStampQueue> AddressSet; 
class AddressList { 
public: 
    AddressList(const char* tracefilename); 
    bool Simulate(uint64_t *hit_count, uint64_t* miss_count); 
    ~AddressList(); 

private: 
    void AddAddress(const uint64_t& byteaddr, const uint64_t& size); 
    void ParseTraceFile(const char* filename); 
    void StoreTokens(char* line, uint64_t * const linecount); 

    std::vector<Address> address_list_; 
    AddressSet address_set_; 
    uint64_t sequence_no_; 
    CacheMemory cache_; 

    AddressList (const AddressList&); 
    AddressList& operator=(const AddressList&); 
}; 

は、出力は次のようなものですアドレストレースセットのためのメモリ割り当て、アドレスカウント30000000

解析中にメモリを割り当て中にエラーが発生する

Answer 1

あなたのデータセットは、あなたのメモリよりはるかに大きくなると思われるので、ディスクインデックスを作成する必要があります。おそらく、データベース全体をデータベースにインポートし、インデックスを作成させるのが最も簡単です。

Answer 2

マップは、入力時に入力をソートし、検索時間を最適化し、ソートされた出力を提供します。ルックアップ機能を使用していないように聞こえるので、別の方法でリストをソートするのが最適な方法です。 Merge sortingは、メモリに収まらないコレクションをソートするのに素晴らしいです。ルックアップを行っていても、ソートされたファイルへのバイナリ検索は、各レコードが固定サイズである限り、単純なアプローチよりも高速になります。

Answer 3

私には明白なことが書いてありますが、大量のデータを効率的に保存して照会する必要性は、データベースが発明された正確な理由です。彼らはすでにあなたや私が合理的な時間内に思い付くよりも良い方法でこれらの問題をすべて解決しました。ホイールを再構築する必要はありません。