Analyse de fichiers texte multicœurs

Question

J'ai une machine quadricœur et j'aimerais écrire du code pour analyser un fichier texte qui tire parti des quatre cœurs.Le fichier texte contient essentiellement un enregistrement par ligne.

Le multithreading n'est pas mon fort, donc je me demande si quelqu'un pourrait me donner des modèles que je pourrais utiliser pour analyser le fichier de manière optimale.

Mes premières pensées sont de lire toutes les lignes dans une sorte de file d'attente, puis de faire tourner les threads pour extraire les lignes de la file d'attente et les traiter, mais cela signifie que la file d'attente devrait exister en mémoire et ce sont des fichiers assez volumineux, donc je' Je ne suis pas tellement enthousiasmé par cette idée.

Mes prochaines pensées sont d'avoir une sorte de contrôleur qui lira une ligne et lui assignera un thread à analyser, mais je ne sais pas si le contrôleur finira par être un goulot d'étranglement si les threads traitent les lignes plus rapidement qu'il ne le peut. lisez-les et assignez-les.

Je sais qu'il existe probablement une autre solution plus simple que les deux, mais pour le moment, je ne la vois tout simplement pas.

Answer 1

J'irais avec votre idée originale.Si vous craignez que la file d'attente devienne trop volumineuse, implémentez une zone tampon pour celle-ci (c'est-à-direS'il dépasse 100 lignes, arrêtez de lire le fichier et s'il descend en dessous de 20, recommencez la lecture.Vous auriez besoin de faire des tests pour trouver les barrières optimales).Faites en sorte que n'importe lequel des threads puisse potentiellement être le "thread de lecteur", car il doit verrouiller la file d'attente pour extraire un élément de toute façon, il peut également vérifier si la "région tampon faible" a été atteinte et recommencer la lecture.Pendant ce temps, les autres threads peuvent lire le reste de la file d'attente.

Ou si vous préférez, demandez à un fil de lecture d'attribuer les lignes à trois autres processeur threads (via leurs propres files d'attente) et implémenter un stratégie de vol de travail.Je n'ai jamais fait ça donc je ne sais pas à quel point c'est difficile.

Answer 2

La réponse de Mark est la solution la plus simple et la plus élégante.Pourquoi construire un programme complexe avec une communication inter-thread si ce n'est pas nécessaire ?Générez 4 fils de discussion.Chaque thread calcule la taille du fichier/4 pour déterminer son point de départ (et son point d'arrêt).Chaque thread peut alors fonctionner de manière totalement indépendante.

Le seulement la raison d'ajouter un fil de discussion spécial pour gérer la lecture est si vous vous attendez à ce que le traitement de certaines lignes prenne très longtemps et vous vous attendez à ce que ces lignes soient regroupées dans une seule partie du fichier.L'ajout d'une communication inter-thread lorsque vous n'en avez pas besoin est un très mauvaise idée.Vous augmentez considérablement le risque d’introduire un goulot d’étranglement inattendu et/ou des bugs de synchronisation.

Answer 3

Cela éliminera les goulots d'étranglement liés au fait qu'un seul thread effectue la lecture :

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

Mon expérience concerne Java, pas C#, donc je m'excuse si ces solutions ne s'appliquent pas.

La solution immédiate à laquelle je peux penser serait d'avoir un exécuteur qui exécute 3 threads (en utilisant Executors.newFixedThreadPool, dire).Pour chaque ligne/enregistrement lu à partir du fichier d'entrée, lancez une tâche sur l'exécuteur (en utilisant ExecutorService.submit).L'exécuteur mettra les demandes en file d'attente pour vous et les répartira entre les 3 threads.

Il existe probablement de meilleures solutions, mais j’espère qu’elles feront l’affaire.:-)

ETA :Cela ressemble beaucoup à la deuxième solution de Wolfbyte.:-)

ETA2 : System.Threading.ThreadPool cela ressemble à une idée très similaire dans .NET.Je ne l'ai jamais utilisé, mais cela vaut peut-être la peine !

Answer 5

Étant donné que le goulot d'étranglement réside généralement dans le traitement et non dans la lecture lors du traitement de fichiers, j'opterais pour le producteur-consommateur modèle.Pour éviter le verrouillage, je consulterais les listes de verrouillage gratuit.Puisque vous utilisez C#, vous pouvez jeter un oeil à Julian Bucknall Liste sans verrouillage code.

Answer 6

@lomaxx

@Derek et Mark :J'aimerais qu'il y ait un moyen d'accepter 2 réponses.Je vais devoir choisir la solution de Wolfbyte car si je divise le fichier en n sections, il est possible qu'un thread rencontre un lot de transactions "lentes". Cependant, si je traitais un fichier où chaque processus était garanti de nécessiter une quantité égale de traitement, alors j'aime vraiment votre solution consistant simplement à diviser le fichier en morceaux et à attribuer chaque morceau à un thread et à en finir avec lui.

Pas de soucis.Si les transactions « lentes » en cluster posent problème, la solution de mise en file d’attente est la solution.En fonction de la rapidité ou de la lenteur de la transaction moyenne, vous pouvez également envisager d'attribuer plusieurs lignes à la fois à chaque travailleur.Cela réduira la surcharge de synchronisation.De même, vous devrez peut-être optimiser la taille de votre tampon.Bien entendu, ces deux optimisations ne devraient probablement être effectuées qu’après le profilage.(Inutile de s'inquiéter de la synchronisation si ce n'est pas un goulot d'étranglement.)

Answer 7

Si le texte que vous analysez est composé de chaînes et de jetons répétés, divisez le fichier en morceaux et pour chaque morceau, vous pouvez demander à un thread de le pré-analyser en jetons constitués de mots-clés, de "ponctuations", de chaînes d'identification et de valeurs.Les comparaisons et les recherches de chaînes peuvent être assez coûteuses et les transmettre à plusieurs threads de travail peut accélérer la partie purement logique/sémantique du code s'il n'est pas nécessaire d'effectuer les recherches et les comparaisons de chaînes.

Les morceaux de données pré-analysés (où vous avez déjà effectué toutes les comparaisons de chaînes et les avez « tokenisés ») peuvent ensuite être transmis à la partie du code qui examinerait réellement la sémantique et l'ordre des données tokenisées.

De plus, vous mentionnez que vous êtes préoccupé par la taille de votre fichier occupant une grande quantité de mémoire.Il y a plusieurs choses que vous pouvez faire pour réduire votre budget mémoire.

Divisez le fichier en morceaux et analysez-le.Lisez uniquement autant de morceaux sur lesquels vous travaillez à la fois, plus quelques-uns pour la « lecture anticipée », afin de ne pas vous bloquer sur le disque lorsque vous avez terminé de traiter un morceau avant de passer au morceau suivant.

Alternativement, les fichiers volumineux peuvent être mappés en mémoire et chargés « à la demande ».Si vous avez plus de threads travaillant sur le traitement du fichier que de processeurs (généralement threads = 1,5-2X CPU est un bon nombre pour les applications de pagination à la demande), les threads qui bloquent sur IO pour le fichier mappé en mémoire s'arrêteront automatiquement du système d'exploitation jusqu'à ce que leur la mémoire est prête et les autres threads continueront à être traités.