Parsen von Multicore-Textdateien

Question

Ich habe eine Quad-Core-Maschine und möchte Code schreiben, um eine Textdatei zu analysieren, die alle vier Kerne nutzt.Die Textdatei enthält grundsätzlich einen Datensatz pro Zeile.

Multithreading ist nicht meine Stärke, daher frage ich mich, ob mir jemand einige Muster geben könnte, mit denen ich die Datei möglicherweise optimal analysieren kann.

Mein erster Gedanke ist, alle Zeilen in eine Art Warteschlange einzulesen und dann Threads zu starten, um die Zeilen aus der Warteschlange zu ziehen und zu verarbeiten, aber das bedeutet, dass die Warteschlange im Speicher vorhanden sein müsste und es sich um ziemlich große Dateien handelt, also Ich bin von dieser Idee nicht so begeistert.

Meine nächsten Gedanken sind, eine Art Controller zu haben, der eine Zeile einliest und ihr einen Thread zum Parsen zuweist, aber ich bin mir nicht sicher, ob der Controller am Ende einen Engpass darstellt, wenn die Threads die Zeilen schneller verarbeiten, als er kann lesen und zuordnen.

Ich weiß, dass es wahrscheinlich eine andere, einfachere Lösung als diese beiden gibt, aber im Moment sehe ich sie einfach nicht.

Answer 1

Ich würde Ihrer ursprünglichen Idee folgen.Wenn Sie befürchten, dass die Warteschlange zu groß werden könnte, richten Sie eine Pufferzone dafür ein (d. h.Wenn mehr als 100 Zeilen vorhanden sind, wird das Lesen der Datei beendet. Wenn weniger als 20 Zeilen vorhanden sind, wird der Lesevorgang erneut gestartet.Sie müssten einige Tests durchführen, um die optimalen Barrieren zu finden.Machen Sie es so, dass jeder der Threads potenziell der „Leser-Thread“ sein kann, da er die Warteschlange sperren muss, um ein Element trotzdem herauszuziehen. Außerdem kann er prüfen, ob der „Bereich mit niedrigem Puffer“ erreicht wurde, und erneut mit dem Lesen beginnen.Währenddessen können die anderen Threads den Rest der Warteschlange auslesen.

Oder wenn Sie es vorziehen, weisen Sie einen Leser-Thread die Zeilen drei anderen zu Prozessor Threads (über ihre eigenen Warteschlangen) und implementieren a arbeitsraubende Strategie.Ich habe das noch nie gemacht, daher weiß ich nicht, wie schwer es ist.

Answer 2

Marks Antwort ist die einfachere und elegantere Lösung.Warum ein komplexes Programm mit Inter-Thread-Kommunikation erstellen, wenn dies nicht notwendig ist?Erzeuge 4 Threads.Jeder Thread berechnet „size-of-file/4“, um seinen Startpunkt (und Stopppunkt) zu bestimmen.Jeder Thread kann dann völlig unabhängig arbeiten.

Der nur Der Grund für das Hinzufügen eines speziellen Threads für das Lesen liegt darin, dass Sie damit rechnen, dass die Verarbeitung einiger Zeilen sehr lange dauert Und Sie gehen davon aus, dass diese Zeilen in einem einzigen Teil der Datei geclustert sind.Das Hinzufügen von Inter-Thread-Kommunikation, wenn Sie sie nicht benötigen, ist eine sehr schlechte Idee.Sie erhöhen die Wahrscheinlichkeit erheblich, dass es zu einem unerwarteten Engpass und/oder Synchronisierungsfehlern kommt.

Answer 3

Dadurch werden Engpässe beseitigt, die dadurch entstehen, dass ein einzelner Thread das Lesen übernimmt:

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

Ich habe Erfahrung mit Java, nicht mit C#, daher entschuldige ich mich, wenn diese Lösungen nicht zutreffen.

Die unmittelbare Lösung, die mir spontan einfällt, wäre, einen Executor zu haben, der 3 Threads ausführt (unter Verwendung von Executors.newFixedThreadPool, sagen).Für jede Zeile/jeden Datensatz, der aus der Eingabedatei gelesen wird, lösen Sie einen Job beim Executor aus (mit ExecutorService.submit).Der Executor stellt Anfragen für Sie in die Warteschlange und verteilt sie auf die drei Threads.

Wahrscheinlich gibt es bessere Lösungen, aber hoffentlich reicht das aus.:-)

voraussichtliche Ankunftszeit:Klingt sehr nach der zweiten Lösung von Wolfbyte.:-)

ETA2: System.Threading.ThreadPool klingt nach einer sehr ähnlichen Idee in .NET.Ich habe es noch nie benutzt, aber es könnte sich für Sie lohnen!

Answer 5

Da der Engpass im Allgemeinen in der Verarbeitung und nicht im Lesen beim Umgang mit Dateien liegt, würde ich mich für Folgendes entscheiden Produzent-Konsument Muster.Um eine Sperrung zu vermeiden, würde ich mir Listen ohne Sperren ansehen.Da Sie C# verwenden, können Sie sich Julian Bucknalls ansehen Sperrfreie Liste Code.

Answer 6

@lomaxx

@Derek & Mark:Ich wünschte, es gäbe eine Möglichkeit, zwei Antworten zu akzeptieren.Am Ende muss ich mich für die Lösung von Wolfbyte entscheiden, denn wenn ich die Datei in n Abschnitte aufteile, besteht die Möglichkeit, dass ein Thread auf einen Stapel „langsamer“ Transaktionen stößt, wenn ich jedoch eine Datei verarbeite, bei der jeder Prozess ausgeführt wird garantiert den gleichen Verarbeitungsaufwand erforderte, dann gefällt mir Ihre Lösung, die Datei einfach in Blöcke aufzuteilen, jeden Block einem Thread zuzuweisen und damit fertig zu sein, wirklich gut.

Keine Sorge.Wenn geclusterte „langsame“ Transaktionen ein Problem darstellen, ist die Warteschlangenlösung die richtige Wahl.Abhängig davon, wie schnell oder langsam die durchschnittliche Transaktion ist, möchten Sie möglicherweise auch die Zuweisung mehrerer Zeilen gleichzeitig an jeden Mitarbeiter in Betracht ziehen.Dadurch wird der Synchronisierungsaufwand reduziert.Ebenso müssen Sie möglicherweise Ihre Puffergröße optimieren.Natürlich handelt es sich bei beiden Optimierungen um Optimierungen, die Sie wahrscheinlich erst nach der Profilerstellung durchführen sollten.(Es macht keinen Sinn, sich Gedanken über die Synchronisierung zu machen, wenn es sich dabei nicht um einen Engpass handelt.)

Answer 7

Wenn der Text, den Sie analysieren, aus sich wiederholenden Zeichenfolgen und Token besteht, teilen Sie die Datei in Abschnitte auf. Für jeden Abschnitt könnte ein Thread ihn vorab in Token analysieren lassen, die aus Schlüsselwörtern, „Interpunktion“, ID-Zeichenfolgen und Werten bestehen.String-Vergleiche und -Suchen können ziemlich teuer sein und die Weitergabe an mehrere Arbeitsthreads kann den rein logischen/semantischen Teil des Codes beschleunigen, wenn die String-Suchen und -Vergleiche nicht durchgeführt werden müssen.

Die vorab analysierten Datenblöcke (bei denen Sie bereits alle Zeichenfolgenvergleiche durchgeführt und sie „tokenisiert“ haben) können dann an den Teil des Codes übergeben werden, der sich tatsächlich mit der Semantik und Reihenfolge der tokenisierten Daten befasst.

Sie erwähnen außerdem, dass Sie Bedenken haben, dass Ihre Datei viel Speicher belegt.Es gibt ein paar Dinge, die Sie tun können, um Ihr Speicherbudget zu reduzieren.

Teilen Sie die Datei in Stücke auf und analysieren Sie sie.Lesen Sie jeweils nur so viele Blöcke ein, wie Sie gleichzeitig bearbeiten, plus ein paar zum „Vorlesen“, damit Sie nicht auf der Festplatte stehen bleiben, wenn Sie mit der Verarbeitung eines Blocks fertig sind, bevor Sie mit dem nächsten Block fortfahren.

Alternativ können große Dateien dem Speicher zugeordnet und bei Bedarf geladen werden.Wenn Sie mehr Threads haben, die an der Verarbeitung der Datei arbeiten als CPUs (normalerweise sind Threads = 1,5-2X CPUs eine gute Zahl für Demand-Paging-Apps), werden die Threads, die bei E/A für die speicherzugeordnete Datei ins Stocken geraten, automatisch vom Betriebssystem angehalten, bis sie beendet sind Der Speicher ist bereit und die anderen Threads werden weiter verarbeitet.