¿Cómo escanear archivos realmente grandes en el disco?

Question

Considerando un archivo realmente enorme (tal vez más de 4 GB) en el disco, quiero escanear este archivo y calcular los tiempos de un patrón binario específico.

Mi pensamiento es:

1. archivo mapeado en memoria Uso (CreateFileMap o impulsar mapped_file) para cargar el archivo a la memoria virtual.

2. Para cada 100MB de memoria mapeada, cree un hilo para escanear y calcule el resultado.

¿Es esto posible? ¿Hay algún método mejor para hacerlo?

actualización:
archivo asignado en memoria serían una buena opción, para escaneando a través de un archivo de 1,6 GB podría ser manejado dentro de 11s.

gracias.

Answer 1

El subprocesamiento múltiple solo hará que esto vaya más lento a menos que desee escanear varios archivos con cada uno en un disco duro diferente. De lo contrario, solo vas a buscar.

Escribí una función de prueba simple usando archivos mapeados en memoria, con una sola hebra un archivo de 1.4 Gb tomó aproximadamente 20 segundos para escanear. Con dos subprocesos, cada uno de los cuales tomaba la mitad del archivo (incluso trozos de 1 MB en un hilo, impar para el otro), tardó más de 80 segundos.

• 1 hilo: 20015 milisegundos
• 2 hilos: 83985 milisegundos

Así es, 2 hilos era cuatro veces más lento que 1 hilo!

Aquí está el código que utilicé, esta es la versión de una sola hebra, utilicé un patrón de escaneo de 1 byte, por lo que el código para localizar coincidencias que se extienden a lo largo de los límites del mapa no se ha probado.

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

Aunque puede usar la asignación de memoria, no es necesario. Si lee el archivo secuencialmente en pequeños fragmentos, digamos 1 MB cada uno, el archivo nunca estará presente en la memoria de una sola vez.

Si su código de búsqueda es realmente más lento que su disco duro, aún puede entregar trozos a hilos de trabajo si lo desea.

Answer 3

Crear 20 hilos, cada uno suponiendo que maneja unos 100 MB del archivo es probable que solo empeore el rendimiento ya que el HD tendrá que leer desde varios lugares no relacionados al mismo tiempo.

El rendimiento de HD está en su punto máximo cuando lee datos secuenciales. Entonces, suponiendo que su gran archivo no está fragmentado, lo mejor que puede hacer es usar solo un hilo y leer de principio a fin en porciones de unos pocos (digamos 4) MB.

Pero, ¿qué sé yo? Los sistemas de archivos y las memorias caché son complejos. Haga algunas pruebas y vea qué funciona mejor.

Answer 4

El uso de un archivo mapeado en memoria tiene la ventaja adicional de evitar una copia de la memoria caché del sistema de archivos a la memoria de la aplicación (administrada) si usa una vista de solo lectura (aunque debe usar punteros byte * para acceder al memoria). Y en lugar de crear muchos subprocesos, utilice un subproceso para escanear de forma secuencial el archivo utilizando, por ejemplo, 100MB de memoria de vistas mapeadas en el archivo (no mapee el archivo completo en el espacio de direcciones de proceso a la vez).

Answer 5

Lo haría con lecturas asincrónicas en un doble buffer. Entonces, cuando se haya leído un búfer desde el archivo, comience a leer el siguiente búfer mientras escanea el primer búfer. Esto significa que usted hace CPU e IO en paralelo. Otra ventaja es que siempre tendrá datos alrededor de los límites de datos. Sin embargo, no sé si el doble buffering es posible con los archivos de memoria mapeados.

Espero que esto ayude.

Saludos,

Sebastiaan

Answer 6

me gustaría ir con sólo un hilo demasiado, no sólo para los problemas de rendimiento de alta definición, sino porque es posible que tenga problemas para manejar los efectos secundarios cuando se divide el archivo: ¿y si hay una ocurrencia de su patrón justo donde divide su archivo?

Answer 7

Me gustaría tener un hilo leer el archivo (posiblemente como una secuencia) en una matriz y tener otro hilo procesarlo. No trazaría varios mapas a la vez debido a las búsquedas en disco. Probablemente tendré un ManualResetEvent para contar mi hilo cuando sea el siguiente? los bytes están listos para ser procesados Suponiendo que su código de proceso es más rápido que el disco duro, tendría 2 almacenamientos intermedios, uno para llenar y el otro para procesar y simplemente cambiar entre ellos cada vez.

Answer 8

Tim Bray (y sus lectores) exploraron esto en profundidad en su Wide Finder Project y Wide Finder 2. Benchmark results muestran que las implementaciones multiproceso pueden superar el rendimiento de una solución de un único subproceso en un servidor masivo Sun multinúcleo. En el hardware de PC habitual, el multihilo no te hará ganar tanto, en todo caso.