Comment parcourir les fichiers vraiment énormes sur le disque?

Question

Considérant un fichier vraiment énorme (peut-être plus de 4 Go) sur le disque, je veux parcourir ce fichier et calculer les temps d'un motif binaire spécifique se produit.

Ma pensée est:

1. Utilisation fichier mappé en mémoire (CreateFileMap ou mapped_file boost) pour charger le fichier à la mémoire virtuelle.

2. Pour chaque 100MB-mémoire mappée, créer un fil pour analyser et calculer le résultat.

Est-ce faisable? Y at-il une meilleure méthode pour le faire?

Mise à jour :
fichier mappé en mémoire serait un bon choix pour scaning via un fichier 1.6GB pourrait être traitée dans les 11s.

merci.

Answer 1

multithreading ne va en faire aller plus lentement à moins que vous souhaitez analyser plusieurs fichiers avec chacun sur un disque dur. Sinon, vous allez juste chercher.

J'ai écrit une fonction de test simple en utilisant des fichiers mappés en mémoire, avec un seul thread un fichier de 1,4 Go a pris environ 20 secondes pour numériser. Avec deux fils, chacun prenant la moitié du fichier (même les morceaux 1MB à un fil, impair à l'autre), il a fallu plus de 80 secondes.

• 1 Sujet: 20015 millisecondes
• 2 fils: 83985 millisecondes

C'est vrai, 2 fils était Quatre fois plus lent que 1 fil!

Voici le code je, c'est la version mono-thread, j'ai utilisé un modèle de balayage 1 octet, de sorte que le code pour localiser les matchs qui chevauchent les limites de carte est non vérifiée.

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

Création 20 fils de discussion, chacun en supposant pour traiter quelque 100 Mo du fichier est susceptible d'aggraver seulement les performances puisque le HD devra lire plusieurs endroits non reliés en même temps.

La performance HD est à son apogée quand il lit les données séquentielles. Donc, en supposant que votre énorme fichier n'est pas fragmenté, la meilleure chose à faire serait probablement d'utiliser un seul fil et lu du début à la fin en morceaux de quelques (disons 4) MB.

Mais qu'est-ce que je sais. Les systèmes de fichiers et les caches sont complexes. Faites des tests et voir ce qui fonctionne le mieux.

Answer 3

Bien que vous pouvez utiliser le mappage de la mémoire, vous n'avez pas. Si vous lisez le fichier séquentiellement en petits morceaux, soit 1 Mo chacun, le fichier ne sera jamais présent dans la mémoire à la fois.

Si votre code de recherche est en fait plus lent que votre disque dur, vous pouvez toujours la main des morceaux hors de threads de travail si vous le souhaitez.

Answer 4

j'avoir un fil de lire le fichier (éventuellement sous forme de courant) dans un tableau et un autre processus de ce fil. Je ne reviendrai pas mapper plusieurs à la fois à cause de recherches de disque. Je serais probablement un ManualResetEvent dire à mon fils quand le prochain? octets sont prêts à traiter. En supposant que votre code de processus est plus rapide alors le hdd j'aurais 2 tampons, pour remplir un et l'autre pour traiter et juste passer entre eux à chaque fois.

Answer 5

Je vais avec un seul fil aussi, non seulement pour les problèmes de performance HD, mais parce que vous pourriez avoir du mal à gérer les effets secondaires lors de la division de votre dossier: s'il y a un événement de votre modèle à droite où vous divisez votre fichier

Answer 6

En utilisant une mémoire fichier mis en correspondance a l'avantage supplémentaire d'éviter une copie de la mémoire cache du système de fichiers à la (géré) mémoire d'application si vous utilisez une vue en lecture seule (même si vous devez utiliser un octet * pointeurs alors accéder à la mémoire ). Et au lieu de créer de nombreux threads utilisent un fil pour analyser de manière séquentielle dans le fichier en utilisant par exemple la mémoire 100MB vues cartographiées dans le fichier (ne pas mapper l'intégralité du fichier dans l'espace d'adressage du processus à la fois).

Answer 7

Tim Bray (et ses lecteurs) ont exploré cette question en profondeur dans son large Finder projet et résultats Benchmark montrent que les implémentations multithread peuvent surperformer une solution mono-thread sur une massif serveur multi-cœurs Sun . Sur le matériel habituel PC, multithreading ne vous gagnez beaucoup, voire pas du tout.

Answer 8

Je le ferais avec asynchrone lit dans un double tampon. Alors, quand une mémoire tampon a été lu à partir du fichier, commencer à lire la mémoire tampon suivante lors de la numérisation du premier tampon. Cela signifie que vous faites CPU et IO en parallèle. Un autre avantage est que vous aurez toujours des données autour des limites de données. Cependant, je ne sais pas si le double buffering est possible avec des fichiers de mémoire mappées.