Como examinar arquivos realmente enormes no disco?

Question

Considerando um arquivo realmente enorme (talvez mais de 4 GB) no disco, quero examinar esse arquivo e calcular os horários de um padrão binário específico ocorre.

Meu pensamento é:

1. Use o arquivo mapeado de memória (createfilemap ou boost maped_file) para carregar o arquivo na memória virtual.

2. Para cada memória mapeada de 100 MB, crie um thread para digitalizar e calcular o resultado.

Isso é viável? Existe algum método melhor para fazê -lo?

Atualizar:
O arquivo mapeado de memória seria uma boa opção, para digitalizar um arquivo de 1,6 GB, poderia ser tratado dentro de 11s.

obrigado.

Answer 1

O multithreading só tornará isso mais lento, a menos que você queira digitalizar vários arquivos com cada um em um disco rígido diferente. Caso contrário, você só vai procurar.

Escrevi uma função de teste simples usando arquivos mapeados de memória, com um único thread que um arquivo de 1,4 GB levou cerca de 20 segundos para digitalizar. Com dois threads, cada um levando metade do arquivo (até 1Mb pedaços para um thread, estranho para o outro), levou mais de 80 segundos.

• 1 Tópico: 20015 milissegundos
• 2 tópicos: 83985 milissegundos

Isso mesmo, 2 tópicos foram Quatro vezes mais lento que 1 thread!

Aqui está o código que eu usei, esta é a versão rosada única, usei um padrão de verificação de 1 bytes; portanto, o código para localizar correspondências que os limites do mapa serem não testados.

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;
}

Answer 2

Criando 20 threads, cada um supondo lidar com cerca de 100 MB do arquivo provavelmente piorará apenas o desempenho, pois o HD terá que ler de vários locais não relacionados ao mesmo tempo.

O desempenho em HD está no auge quando lê dados seqüenciais. Portanto, assumindo que seu arquivo enorme não é fragmentado, a melhor coisa a fazer provavelmente seria usar apenas um tópico e ler do início ao fim em pedaços de alguns (digamos 4) MB.

Mas o que eu sei. Os sistemas de arquivos e caches são complexos. Faça alguns testes e veja o que funciona melhor.

Answer 3

Embora você possa usar o mapeamento de memória, você não precisa. Se você ler o arquivo sequencialmente em pequenos pedaços, digamos 1 MB cada, o arquivo nunca estará presente na memória de uma só vez.

Se o seu código de pesquisa for realmente mais lento que o seu disco rígido, você ainda poderá entregar os threads de trabalhadores, se quiser.

Answer 4

Eu teria um thread leia o arquivo (possivelmente como um fluxo) em uma matriz e teria outro processo de thread. Eu não mapearia vários ao mesmo tempo por causa do disco busca. Eu provavelmente teria um ManualResetevent para contar meu tópico quando o próximo? Os bytes estão prontos para serem processados. Supondo que seu código de processo seja mais rápido do que o disco rígido, eu teria 2 buffers, um a preencher e o outro para processar e apenas alternar entre eles a cada vez.

Answer 5

Eu também iria com apenas um tópico, não apenas para problemas de desempenho em HD, mas porque você pode ter problemas para gerenciar efeitos colaterais ao dividir seu arquivo: e se houver uma ocorrência do seu padrão, exatamente onde você dividiu seu arquivo?

Answer 6

O uso de um arquivo mapeado de memória tem o benefício adicional de evitar uma cópia da memória de cache do sistema de arquivos para a memória do aplicativo (gerenciada) se você usar uma visualização somente leitura (embora precise usar ponteiros de byte* para acessar a memória). E, em vez de criar muitos threads, use um thread para digitalizar sequencialmente o arquivo usando, por exemplo, visualizações mapeadas de memória de 100 MB no arquivo (não mapeie o arquivo inteiro no espaço de endereço de processo de uma só vez).

Answer 7

Tim Bray (e seus leitores) exploraram isso em profundidade em seu Projeto Wide Finder e Amplo localizador 2. Resultados de referência Mostre que as implementações multithreaded podem superar uma solução de thread única Em um enorme servidor multicore Sun. No hardware usual do PC, o Multithreading não ganhará tanto, se é que existe.

Answer 8

Eu faria isso com leituras assíncronas em um buffer duplo. Portanto, quando um buffer for lido do arquivo, comece a ler o próximo buffer enquanto digitaliza o primeiro buffer. Isso significa que você faz CPU e IO em paralelo. Outra vantagem é que você sempre terá dados sobre os limites dos dados. No entanto, não sei se o buffer duplo é possível com arquivos mapeados de memória.