Análise de arquivo de texto multicore

Question

Eu tenho uma máquina quad core e gostaria de escrever algum código para analisar um arquivo de texto que aproveite todos os quatro núcleos.O arquivo de texto contém basicamente um registro por linha.

Multithreading não é meu forte, então estou me perguntando se alguém poderia me fornecer alguns padrões que eu possa usar para analisar o arquivo da maneira ideal.

Meu primeiro pensamento é ler todas as linhas em algum tipo de fila e, em seguida, criar threads para retirar as linhas da fila e processá-las, mas isso significa que a fila teria que existir na memória e esses arquivos são bastante grandes, então eu ' não estou muito entusiasmado com essa ideia.

Meu próximo pensamento é ter algum tipo de controlador que leia uma linha e atribua a ele um thread para análise, mas não tenho certeza se o controlador acabará sendo um gargalo se os threads processarem as linhas mais rápido do que pode leia e atribua-os.

Eu sei que provavelmente existe outra solução mais simples do que essas duas, mas no momento simplesmente não estou vendo.

Answer 1

Eu seguiria sua ideia original.Se você está preocupado com a possibilidade de a fila ficar muito grande, implemente uma zona de buffer para ela (ou seja,Se ficar acima de 100 linhas, pare de ler o arquivo e se ficar abaixo de 20, comece a ler novamente.Você precisaria fazer alguns testes para encontrar as barreiras ideais).Faça com que qualquer um dos threads possa ser potencialmente o "thread do leitor", pois ele precisa bloquear a fila para extrair um item de qualquer maneira. Ele também pode verificar se a "região de buffer baixo" foi atingida e começar a ler novamente.Enquanto isso, os outros threads podem ler o restante da fila.

Ou, se preferir, faça com que um tópico do leitor atribua as linhas a três outros processador threads (por meio de suas próprias filas) e implementar um estratégia de roubo de trabalho.Nunca fiz isso, então não sei o quão difícil é.

Answer 2

A resposta de Mark é a solução mais simples e elegante.Por que construir um programa complexo com comunicação entre threads se não for necessário?Gerar 4 tópicos.Cada thread calcula o tamanho do arquivo/4 para determinar seu ponto inicial (e ponto final).Cada thread pode então funcionar de forma totalmente independente.

O apenas A razão para adicionar um thread especial para lidar com a leitura é se você espera que algumas linhas demorem muito para serem processadas e você espera que essas linhas sejam agrupadas em uma única parte do arquivo.Adicionar comunicação entre threads quando você não precisa dela é uma muito má ideia.Você aumenta muito a chance de introduzir gargalos inesperados e/ou bugs de sincronização.

Answer 3

Isso eliminará os gargalos de ter um único thread fazendo a leitura:

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

Minha experiência é com Java, não com C#, então peço desculpas se essas soluções não se aplicam.

A solução imediata que consigo imaginar seria ter um executor que execute 3 threads (usando Executors.newFixedThreadPool, dizer).Para cada linha/registro lido do arquivo de entrada, execute um trabalho no executor (usando ExecutorService.submit).O executor enfileirará as solicitações para você e as alocará entre os 3 threads.

Provavelmente existem soluções melhores, mas espero que isso resolva o problema.:-)

Hora prevista de chegada:Parece muito com a segunda solução da Wolfbyte.:-)

HEC2: System.Threading.ThreadPool parece uma ideia muito semelhante no .NET.Nunca usei, mas pode valer a pena!

Answer 5

Como o gargalo geralmente estará no processamento e não na leitura ao lidar com arquivos, eu escolheria o produtor-consumidor padrão.Para evitar o bloqueio, eu examinaria listas livres de bloqueio.Como você está usando C#, você pode dar uma olhada no tutorial de Julian Bucknall Lista sem bloqueio código.

Answer 6

@lomaxx

@Derek e Marcos:Eu gostaria que houvesse uma maneira de aceitar 2 respostas.Vou ter que acabar com a solução da Wolfbyte porque se eu dividir o arquivo em n seções, há a possibilidade de um thread encontrar um lote de transações "lentas", no entanto, se eu estivesse processando um arquivo onde cada processo era garantido que exigiria uma quantidade igual de processamento, então eu realmente gosto da sua solução de apenas dividir o arquivo em pedaços e atribuir cada pedaço a um thread e terminar com ele.

Sem problemas.Se transações "lentas" em cluster forem um problema, então a solução de enfileiramento é o caminho a seguir.Dependendo de quão rápida ou lenta é a transação média, você também pode querer atribuir várias linhas de cada vez para cada trabalhador.Isso reduzirá a sobrecarga de sincronização.Da mesma forma, pode ser necessário otimizar o tamanho do buffer.Claro, ambas são otimizações que você provavelmente só deve fazer após a criação do perfil.(Não adianta se preocupar com a sincronização se não for um gargalo.)

Answer 7

Se o texto que você está analisando for composto de strings e tokens repetidos, divida o arquivo em pedaços e para cada pedaço você pode ter um thread pré-analisando-o em tokens que consistem em palavras-chave, "pontuação", strings de ID e valores.Comparações e pesquisas de strings podem ser bastante caras e passá-las para vários threads de trabalho pode acelerar a parte puramente lógica/semântica do código se não for necessário fazer pesquisas e comparações de strings.

Os pedaços de dados pré-analisados ​​(onde você já fez todas as comparações de strings e os "tokenizou") podem então ser passados ​​para a parte do código que realmente examinaria a semântica e a ordem dos dados tokenizados.

Além disso, você mencionou que está preocupado com o tamanho do seu arquivo, ocupando uma grande quantidade de memória.Existem algumas coisas que você pode fazer para reduzir seu orçamento de memória.

Divida o arquivo em partes e analise-o.Leia apenas quantos pedaços você estiver trabalhando por vez, mais alguns para "ler adiante", para não travar no disco ao terminar de processar um pedaço antes de passar para o próximo.

Alternativamente, arquivos grandes podem ser mapeados na memória e carregados por “demanda”.Se você tiver mais threads trabalhando no processamento do arquivo do que CPUs (geralmente threads = 1,5-2X CPU é um bom número para aplicativos de paginação sob demanda), os threads que estão paralisando no IO para o arquivo mapeado na memória serão interrompidos automaticamente no sistema operacional até que seu a memória está pronta e os outros threads continuarão a processar.