ディスク上の非常に大きなファイルをスキャンするにはどうすればよいでしょうか?

StackOverflow https://stackoverflow.com/questions/2171625

質問

ディスク上に非常に大きなファイル (おそらく 4GB 以上) があると考えて、このファイルをスキャンして、特定のバイナリ パターンが発生する時間を計算したいと思います。

私の考えは次のとおりです。

  1. メモリマップファイル（CreateFileMapまたはBoost Mapped_file）を使用して、ファイルを仮想メモリにロードします。

  2. 100MB のマップされたメモリごとに、スキャンして結果を計算するスレッドを 1 つ作成します。

これは実現可能ですか?もっと良い方法はありますか?

アップデート:
1.6GB ファイルのスキャンは 11 秒以内に処理できるため、メモリ マップ ファイルは良い選択です。

ありがとう。

役に立ちましたか？

解決

複数のファイルをそれぞれ別のハード ドライブ上でスキャンする場合を除き、マルチスレッドでは処理が遅くなるだけです。そうでないと、ただ探すだけになってしまいます。

メモリ マップ ファイルを使用して簡単なテスト関数を作成しました。シングル スレッドで 1.4 Gb ファイルのスキャンに約 20 秒かかりました。2 つのスレッドがあり、それぞれがファイルの半分を占有します (一方のスレッドには 1MB チャンクでも、もう一方のスレッドには奇数)、80 秒以上かかりました。

  • 1 スレッド:20015ミリ秒
  • 2 スレッド:83985ミリ秒

そうです、2スレッドでした 四 1 スレッドよりも 1 倍遅いです。

これが私が使用したコードです。これはシングル スレッド バージョンで、1 バイトのスキャン パターンを使用したため、マップ境界をまたぐ一致を見つけるコードはテストされていません。 

HRESULT ScanForPattern(LPCTSTR pszFilename, LPBYTE pbPattern, UINT cbPattern, LONGLONG * pcFound)
{
   HRESULT hr = S_OK;

   *pcFound = 0;
   if ( ! pbPattern || ! cbPattern)
      return E_INVALIDARG;

   //  Open the file
   //
   HANDLE hf = CreateFile(pszFilename,
                          GENERIC_READ,
                          FILE_SHARE_READ, NULL,
                          OPEN_EXISTING,
                          FILE_FLAG_SEQUENTIAL_SCAN,
                          NULL);

   if (INVALID_HANDLE_VALUE == hf)
      {
      hr = HRESULT_FROM_WIN32(ERROR_FILE_NOT_FOUND);
      // catch an open file that exists but is in use
      if (ERROR_SHARING_VIOLATION == GetLastError())
         hr = HRESULT_FROM_WIN32(ERROR_SHARING_VIOLATION);
      return hr;
      }

   // get the file length
   //
   ULARGE_INTEGER  uli;
   uli.LowPart = GetFileSize(hf, &uli.HighPart);
   LONGLONG cbFileSize = uli.QuadPart;
   if (0 == cbFileSize)
      {
      CloseHandle (hf);
      return S_OK;
      }

   const LONGLONG cbStride = 1 * 1024 * 1024; // 1 MB stride.
   LONGLONG cFound  = 0;
   LPBYTE   pbGap = (LPBYTE) malloc(cbPattern * 2);

   //  Create a mapping of the file.
   //
   HANDLE hmap = CreateFileMapping(hf, NULL, PAGE_READONLY, 0, 0, NULL);
   if (NULL != hmap)
      {
      for (LONGLONG ix = 0; ix < cbFileSize; ix += cbStride)
         {
         uli.QuadPart = ix;
         UINT cbMap = (UINT) min(cbFileSize - ix, cbStride);
         LPCBYTE pb = (LPCBYTE) MapViewOfFile(hmap, FILE_MAP_READ, uli.HighPart, uli.LowPart, cbMap);
         if ( ! pb)
            {
            hr = HRESULT_FROM_WIN32(GetLastError());
            break;
            }
         // handle pattern scanning over the gap.
         if (cbPattern > 1 && ix > 0)
            {
            CopyMemory(pbGap + cbPattern - 1, &pb[0], cbPattern - 1);
            for (UINT ii = 1; ii < cbPattern; ++ii)
               {
               if (pb[ii] == pbPattern[0] && 0 == memcmp(&pb[ii], pbPattern, cbPattern))
                  {
                  ++cFound; 
                  // advance by cbPattern-1 to avoid detecting overlapping patterns
                  }
               }
            }

         for (UINT ii = 0; ii < cbMap - cbPattern + 1; ++ii)
            {
            if (pb[ii] == pbPattern[0] && 
                ((cbPattern == 1) || 0 == memcmp(&pb[ii], pbPattern, cbPattern)))
               {
               ++cFound; 
               // advance by cbPattern-1 to avoid detecting overlapping patterns
               }
            }
         if (cbPattern > 1 && cbMap >= cbPattern)
            {
            // save end of the view in our gap buffer so we can detect map-straddling patterns
            CopyMemory(pbGap, &pb[cbMap - cbPattern + 1], cbPattern - 1);
            }
         UnmapViewOfFile(pb);
         }

      CloseHandle (hmap);
      }
   CloseHandle (hf);

   *pcFound = cFound;
   return hr;
}

他のヒント

それぞれが約 100 MB のファイルを処理することを想定した 20 のスレッドを作成すると、HD は関連のないいくつかの場所から同時に読み取る必要があるため、パフォーマンスが悪化するだけである可能性があります。

HD のパフォーマンスは、シーケンシャル データを読み取るときに最高になります。したがって、巨大なファイルが断片化されていないと仮定すると、おそらく最善の方法は、1 つのスレッドだけを使用して、最初から最後まで数 MB (たとえば 4 MB) のチャンクで読み取ることでしょう。

しかし、私が何を知っているのか。ファイル システムとキャッシュは複雑です。いくつかのテストを行って、何が最も効果的かを確認してください。

メモリ マッピングを使用することもできますが、必ず使用する必要はありません。ファイルを小さな塊 (それぞれ 1 MB など) に分けて順次読み取る場合、ファイルが一度にメモリ内に存在することはありません。

検索コードが実際にハードディスクよりも遅い場合でも、必要に応じてチャンクをワーカー スレッドに渡すことができます。

1 つのスレッドでファイルを (おそらくストリームとして) 配列に読み取り、別のスレッドでそれを処理するようにします。ディスクシークがあるため、一度に複数をマップすることはできません。おそらく、ManualResetEvent を使用して、スレッドに次のタイミングを通知することになるでしょう。バイトを処理する準備ができています。プロセスコードがHDDよりも速いと仮定すると、2つのバッファーがあり、1つは埋めるため、もう1つは処理し、毎回それらを切り替えるだけです。

HD のパフォーマンスの問題だけでなく、ファイルを分割する際の副作用の管理が困難になる可能性があるため、私も 1 つのスレッドのみを使用します。ファイルを分割した場所に同じパターンが見つかったらどうなるでしょうか?

メモリ マップト ファイルを使用すると、読み取り専用ビューを使用する場合に、ファイル システムのキャッシュ メモリから (マネージド) アプリケーション メモリへのコピーを回避できるという追加の利点があります (ただし、メモリにアクセスするには byte* ポインタを使用する必要があります)。そして、多くのスレッドを作成する代わりに、1 つのスレッドを使用して、たとえば 100MB のメモリ マップされたビューをファイルに使用してファイルを順次スキャンします (ファイル全体を一度にプロセス アドレス空間にマップしないでください)。

ティム・ブレイ（と彼の読者）は、このことを著書で詳しく調査しました。 ワイドファインダープロジェクト そして ワイドファインダー2. ベンチマーク結果 マルチスレッド実装がシングルスレッド ソリューションよりも優れたパフォーマンスを発揮できることを示す 大規模な Sun マルチコア サーバー上で. 。通常の PC ハードウェアでは、マルチスレッドによってメリットが得られるとしても、それほどメリットはありません。

私なら、ダブルバッファーへの非同期読み取りでそれを行います。したがって、1 つのバッファがファイルから読み取られると、最初のバッファをスキャンしながら次のバッファの読み取りを開始します。これは、CPU と IO を並行して実行することを意味します。もう 1 つの利点は、常にデータ境界の周囲にデータが存在することです。ただし、メモリマップされたファイルでダブルバッファリングが可能かどうかはわかりません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top