Análisis de archivos de texto multinúcleo

Question

Tengo una máquina de cuatro núcleos y me gustaría escribir un código para analizar un archivo de texto que aproveche los cuatro núcleos.El archivo de texto contiene básicamente un registro por línea.

El multiproceso no es mi fuerte, así que me pregunto si alguien podría darme algunos patrones que pueda usar para analizar el archivo de manera óptima.

Lo primero que pienso es leer todas las líneas en algún tipo de cola y luego activar subprocesos para sacar las líneas de la cola y procesarlas, pero eso significa que la cola tendría que existir en la memoria y estos son archivos bastante grandes, así que No estoy muy interesado en esa idea.

Mi siguiente pensamiento es tener algún tipo de controlador que lea una línea y le asigne un hilo para analizar, pero no estoy seguro de si el controlador terminará siendo un cuello de botella si los hilos procesan las líneas más rápido de lo que pueden. leerlos y asignarlos.

Sé que probablemente haya otra solución más sencilla que ambas, pero por el momento no la veo.

Answer 1

Yo iría con tu idea original.Si le preocupa que la cola pueda volverse demasiado grande, implemente una zona de amortiguación para ella (es decir,Si supera las 100 líneas, deje de leer el archivo y si supera las 20, comience a leer nuevamente.Necesitaría hacer algunas pruebas para encontrar las barreras óptimas).Haga que cualquiera de los subprocesos pueda ser potencialmente el "subproceso lector", ya que tiene que bloquear la cola para extraer un elemento de todos modos. También puede verificar si se ha alcanzado la "región de búfer bajo" y comenzar a leer nuevamente.Mientras hace esto, los otros hilos pueden leer el resto de la cola.

O si lo prefieres, haz que un hilo lector asigne las líneas a otros tres. procesador hilos (a través de sus propias colas) e implementar un estrategia de robo de trabajo.Nunca he hecho esto así que no sé lo difícil que es.

Answer 2

La respuesta de Mark es la solución más simple y elegante.¿Por qué crear un programa complejo con comunicación entre subprocesos si no es necesario?Genera 4 hilos.Cada hilo calcula el tamaño del archivo/4 para determinar su punto de inicio (y punto de parada).Luego, cada hilo puede funcionar de forma totalmente independiente.

El solo La razón para agregar un hilo especial para manejar la lectura es si espera que algunas líneas tarden mucho en procesarse. y espera que estas líneas estén agrupadas en una sola parte del archivo.Agregar comunicación entre subprocesos cuando no la necesita es una muy mala idea.Aumenta en gran medida la posibilidad de introducir un cuello de botella inesperado y/o errores de sincronización.

Answer 3

Esto eliminará los cuellos de botella que supone tener un solo hilo realizando la lectura:

open file
for each thread n=0,1,2,3:
    seek to file offset 1/n*filesize
    scan to next complete line
    process all lines in your part of the file

Answer 4

Mi experiencia es con Java, no con C#, así que me disculpo si estas soluciones no se aplican.

La solución inmediata que se me ocurre sería tener un ejecutor que ejecute 3 subprocesos (usando Executors.newFixedThreadPool, decir).Para cada línea/registro leído del archivo de entrada, ejecute un trabajo en el ejecutor (usando ExecutorService.submit).El ejecutor pondrá en cola las solicitudes por usted y las asignará entre los 3 subprocesos.

Probablemente existan mejores soluciones, pero es de esperar que funcionen.:-)

Hora estimada de llegada:Se parece mucho a la segunda solución de Wolfbyte.:-)

ETA2: System.Threading.ThreadPool Suena como una idea muy similar en .NET.Nunca lo he usado, ¡pero puede que valga la pena!

Answer 5

Dado que el cuello de botella generalmente estará en el procesamiento y no en la lectura cuando se trata de archivos, elegiría el productor-consumidor patrón.Para evitar el bloqueo, miraría las listas libres de bloqueo.Como estás usando C#, puedes echar un vistazo a Julian Bucknall. Lista sin bloqueo código.

Answer 6

@lomaxx

@Derek y Marcos:Ojalá hubiera una manera de aceptar 2 respuestas.Voy a tener que terminar usando la solución de Wolfbyte porque si divido el archivo en n secciones existe la posibilidad de que un hilo encuentre un lote de transacciones "lentas", sin embargo, si estuviera procesando un archivo donde cada proceso Se garantizaba que requeriría la misma cantidad de procesamiento, entonces realmente me gusta su solución de simplemente dividir el archivo en fragmentos y asignar cada fragmento a un subproceso y terminar con ello.

No hay problema.Si las transacciones "lentas" agrupadas son un problema, entonces la solución de colas es el camino a seguir.Dependiendo de qué tan rápida o lenta sea la transacción promedio, es posible que también desee considerar la posibilidad de asignar varias líneas a la vez a cada trabajador.Esto reducirá la sobrecarga de sincronización.Del mismo modo, es posible que necesites optimizar el tamaño del búfer.Por supuesto, ambas son optimizaciones que probablemente sólo deberías hacer después de crear el perfil.(No tiene sentido preocuparse por la sincronización si no es un cuello de botella).

Answer 7

Si el texto que está analizando se compone de cadenas y tokens repetidos, divida el archivo en fragmentos y, para cada fragmento, puede hacer que un subproceso lo analice previamente en tokens que consten de palabras clave, "puntuación", cadenas de identificación y valores.Las comparaciones y búsquedas de cadenas pueden ser bastante costosas y pasar esto a varios subprocesos de trabajo puede acelerar la parte puramente lógica/semántica del código si no tiene que realizar búsquedas y comparaciones de cadenas.

Los fragmentos de datos previamente analizados (donde ya realizó todas las comparaciones de cadenas y los "tokenizó") luego se pueden pasar a la parte del código que realmente analizaría la semántica y el orden de los datos tokenizados.

Además, menciona que le preocupa que el tamaño de su archivo ocupe una gran cantidad de memoria.Hay un par de cosas que puedes hacer para reducir tu presupuesto de memoria.

Divida el archivo en trozos y analícelo.Lea solo tantos fragmentos como esté trabajando a la vez más algunos para "lectura anticipada" para que no se detenga en el disco cuando termine de procesar un fragmento antes de pasar al siguiente.

Alternativamente, los archivos grandes pueden mapearse en memoria y cargarse "bajo demanda".Si tiene más subprocesos trabajando en el procesamiento del archivo que CPU (normalmente subprocesos = 1,5-2X CPU es un buen número para aplicaciones de paginación de demanda), los subprocesos que se están deteniendo en IO para el archivo asignado en memoria se detendrán automáticamente desde el sistema operativo hasta su la memoria está lista y los otros subprocesos continuarán procesándose.