Analisi di file di testo multicore

Question

Ho una macchina quad core e vorrei scrivere del codice per analizzare un file di testo che sfrutti tutti e quattro i core.Il file di testo contiene fondamentalmente un record per riga.

Il multithreading non è il mio forte, quindi mi chiedo se qualcuno potrebbe darmi alcuni schemi che potrei utilizzare per analizzare il file in modo ottimale.

Il mio primo pensiero è leggere tutte le righe in una sorta di coda e quindi avviare i thread per estrarre le righe dalla coda ed elaborarle, ma ciò significa che la coda dovrebbe esistere in memoria e questi sono file abbastanza grandi, quindi ' Non sono così entusiasta dell'idea.

Il mio prossimo pensiero è quello di avere una sorta di controller che legga in una riga e gli assegni un thread da analizzare, ma non sono sicuro che il controller finirà per essere un collo di bottiglia se i thread elaborano le righe più velocemente di quanto può leggerli e assegnarli.

So che probabilmente esiste un'altra soluzione più semplice di entrambe, ma al momento non la vedo.

Answer 1

Seguirei la tua idea originale.Se temi che la coda possa diventare troppo grande, implementa una zona buffer per essa (ad es.Se supera le 100 righe, interrompe la lettura del file e se scende sotto le 20, ricomincia a leggere.Dovresti fare alcuni test per trovare le barriere ottimali).Fai in modo che uno qualsiasi dei thread possa potenzialmente essere il "thread di lettura" in quanto deve bloccare la coda per estrarre un elemento in ogni caso può anche controllare se la "regione di buffer basso" è stata colpita e ricominciare a leggere.Mentre lo fa gli altri thread possono leggere il resto della coda.

Oppure, se preferisci, chiedi a un thread di lettura di assegnare le righe ad altri tre processore thread (tramite le proprie code) e implementare a strategia di furto del lavoro.Non l'ho mai fatto quindi non so quanto sia difficile.

Answer 2

La risposta di Mark è la soluzione più semplice ed elegante.Perché creare un programma complesso con comunicazione inter-thread se non è necessario?Genera 4 thread.Ogni thread calcola la dimensione del file/4 per determinare il suo punto iniziale (e il punto finale).Ogni thread può quindi funzionare in modo del tutto indipendente.

IL soltanto il motivo per aggiungere un thread speciale per gestire la lettura è se prevedi che alcune righe richiedano molto tempo per l'elaborazione E ti aspetti che queste righe siano raggruppate in un'unica parte del file.Aggiungere la comunicazione tra thread quando non è necessaria è un'operazione pessima idea.Aumenti notevolmente la possibilità di introdurre colli di bottiglia imprevisti e/o bug di sincronizzazione.

Answer 3

Ciò eliminerà i colli di bottiglia derivanti dalla lettura di un singolo thread:

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

La mia esperienza è con Java, non con C#, quindi mi scuso se queste soluzioni non si applicano.

La soluzione immediata che mi viene in mente sarebbe quella di avere un esecutore che esegua 3 thread (usando Executors.newFixedThreadPool, Dire).Per ogni riga/record letto dal file di input, avvia un lavoro presso l'esecutore (utilizzando ExecutorService.submit).L'esecutore metterà in coda le richieste per te e le assegnerà tra i 3 thread.

Probabilmente esistono soluzioni migliori, ma si spera che riescano a risolvere il problema.:-)

ETA:Sembra molto simile alla seconda soluzione di Wolfbyte.:-)

ETA2: System.Threading.ThreadPool sembra un'idea molto simile in .NET.Non l'ho mai usato, ma potrebbe valerne la pena!

Answer 5

Poiché il collo di bottiglia sarà generalmente nell'elaborazione e non nella lettura quando si ha a che fare con i file, opterei per il file produttore-consumatore modello.Per evitare il blocco, guarderei gli elenchi dei blocchi gratuiti.Dato che stai usando C# puoi dare un'occhiata a Julian Bucknall Elenco senza blocchi codice.

Answer 6

@lomaxx

@Derek e Marco:Vorrei che ci fosse un modo per accettare 2 risposte.Dovrò optare per la soluzione di Wolfbyte perché se divido il file in n sezioni c'è la possibilità che un thread incontri un batch di transazioni "lente", tuttavia se stavo elaborando un file in cui ogni processo era garantito che richiedesse la stessa quantità di elaborazione, quindi mi piace molto la tua soluzione di dividere semplicemente il file in blocchi e assegnare ciascun blocco a un thread e finirlo.

Nessun problema.Se le transazioni "lente" in cluster rappresentano un problema, la soluzione di accodamento è la strada da percorrere.A seconda della velocità o della lentezza della transazione media, potresti anche voler assegnare più righe alla volta a ciascun lavoratore.Ciò ridurrà il sovraccarico della sincronizzazione.Allo stesso modo, potrebbe essere necessario ottimizzare la dimensione del buffer.Naturalmente, entrambe queste sono ottimizzazioni che probabilmente dovresti fare solo dopo la profilazione.(Non ha senso preoccuparsi della sincronizzazione se non è un collo di bottiglia.)

Answer 7

Se il testo che stai analizzando è costituito da stringhe e token ripetuti, suddividi il file in blocchi e per ogni blocco potresti avere un thread pre-analizzato in token costituiti da parole chiave, "punteggiatura", stringhe ID e valori.I confronti e le ricerche di stringhe possono essere piuttosto costosi e trasmetterli a diversi thread di lavoro può accelerare la parte puramente logica/semantica del codice se non deve eseguire ricerche e confronti di stringhe.

I blocchi di dati pre-analizzati (dove hai già eseguito tutti i confronti tra stringhe e li hai "tokenizzati") possono quindi essere passati alla parte del codice che esaminerebbe effettivamente la semantica e l'ordinamento dei dati tokenizzati.

Inoltre, dici che sei preoccupato per la dimensione del tuo file che occupa una grande quantità di memoria.Ci sono un paio di cose che potresti fare per ridurre il budget della memoria.

Dividere il file in blocchi e analizzarlo.Leggi solo il numero di blocchi su cui stai lavorando alla volta più alcuni per la "lettura anticipata" in modo da non bloccarti sul disco quando finisci di elaborare un pezzo prima di passare al pezzo successivo.

In alternativa, file di grandi dimensioni possono essere mappati in memoria e caricati "a richiesta".Se hai più thread che lavorano sull'elaborazione del file rispetto alle CPU (in genere thread = 1,5-2X CPU è un buon numero per le app di paging su richiesta), i thread che sono in stallo sull'I/O per il file mappato in memoria si interromperanno automaticamente dal sistema operativo fino al loro la memoria è pronta e gli altri thread continueranno a essere elaborati.