Fragen zur Performanceverbesserung

[seppi]

Hallo zusammen,
Ich arbeite seit einiger Zeit mit Python und bin gerade dabei ein etwas größeres Prgramm auf die Beine zu stellen.
Die Aufgabe des Programms ist es eine sehr sehr große (3-9GB / 100 Mio. Zeilen) Textdatei zu parsen und die erhaltenen Werte bestimmten Prüfungen zu unterziehen. Da dieser Vorgang jedoch mehrere Stunden dauert, bin ich sehr stark daran interessiert diesen Prozess bestmöglich zu optimieren. Bisher wird die Textdatei über Python mit einer for-Schleife iteriert und über ctypes werden die enthaltenen Werte geparsed.

konzeptioneller Aufbau der for-Schleife:

Code: Alles auswählen

file = open(datei, 'r')
for line in file:
  elemente = ctypes(line)
  tu_etwas(elemente.eins)
  tu_etwas_anderes(elemente.zwei)
  ...

Falls es hier bereits Verbesserungen gibt, nur raus damit . Meine Frage bezieht sich jedoch eigentlich nicht allzu sehr auf die for-schleife, da ich meine gelesen zu haben, dass dies der schnellste Weg in Python ist eine Datei dieser größe zu verarbeiten. Die eigentliche Anfrage steht jedoch unter dem Begriff Multithreading. Und zwar habe ich bisher noch keine große Kenntnis in dieser Sache gewonnen, da ich bisher eher kleine Programme geschrieben habe, welche keine Parallelisierung benötigten. Jedoch würde es sich hier nicht anbieten die verschiedenen Berechnungen in einzelnen Threads auszulagern? Es müsste jedoch am Ende jeder Zeile gewartet werden, bis alle Threads abgearbeitet sind, da sich kommende Berechnungen häufig auf die Zeile davor beziehen.

Müsste ja dann im Prinzip ungefähr so aussehen:

Code: Alles auswählen

file = open(datei, 'r')
for line in file:
  elemente = ctypes(line)
  thread.tu_etwas(elemente.eins).start()
  thread.tu_etwas_anderes(elemente.zwei).start()
  thread.join()
  ...

Was mich ebenfalls sehr irritiert, ist die Windows CPU-Last Anzeige während des Prozesses. Da ich bisher wie erwähnt keinerlei threading in meinem Programm benutze, sollte das Programm doch eigentlich nur auf einem Thread und somit einer CPU laufen. Windows sagt mir jedoch, dass mein Programm auf 2 Threads läuft. Bei Betrachtung der Auslastung der Kerne stehen alle Kerne bei einem Dualcore auf 50% bei einem Quadcore auf 25%. Lässt in mir den Verdacht aufkommen, dass das Programm nur auf einem Kern mit 100% läuft und Windows hier irgend ein Quatsch anzeigt. Wenn ich richtig informiert bin, kann ein Thread auch nicht auf mehrere CPUs aufgeteilt werden und da ich nur ein Thread erstellt habe würde sich meine Vermutung, dass ein Kern immer voll ausgelastet wird bestätigen. Nur die Windows Anzeige spricht dagegen.

Ich hoffe ihr könnt mir einige Anregungen und Hilfestellungen geben. Danke!

[CM]

Hallo und willkommen im Forum,

Zur Frage der Anzeige unter Windows kann ich nichts sagen, doch ich vermute was Du suchst ist eher das multiprocessing-modul.

Bei einfachen Operationen und vielen Files (Summe > 5 GB-Minimum) hat es bei mir nur Minuten (bis > 10) gedauert die Arbeit zu erledigen. Dein Problem ist aber anders gelagert und wenn Du selber nicht mit der Anleitung zurecht kommst, bräuchten wir in jedem Fall noch Informationen darüber wie die verschiedenen Aufgaben zueinander stehen (muß in jeder Zeile gewartet werden, bis die Aufgabe abgeschlossen ist? müssen die Prozesse synchron sein? etc.)

Es gibt auch ein threading-Modul und eigentlich würde ich auch eher an Threading als Multiprossesing denken (in der C-Welt jedenfalls), aber aufgrund des GIL in Python (siehe Link), würde ich raten, daß Du hier wenig Zeitgewinn bekommst.

Gruß,
Christian

[jens]

vielleicht wirds auch schneller mit pypy und dem JIT Ein test wäre es wert.

EDIT:

Bei Betrachtung der Auslastung der Kerne stehen alle Kerne bei einem Dualcore auf 50% bei einem Quadcore auf 25%. Lässt in mir den Verdacht aufkommen, dass das Programm nur auf einem Kern mit 100% läuft und Windows hier irgend ein Quatsch anzeigt.

Ja, da hast du recht. Der Taskmanager zeigt die Auslastung normalerweise zusammengefasst an und nicht auf CPU-Kern aufgeteilt. Du kannst allerdings unter Ansicht / CPU-Verlauf das umstellen

btw. sysinternals "Process Explorer" ist netter! Damit kannst du auch unterscheiden, ob dein Programm von IO-Last gebremst wird...

[deets]

@jens

Wenn er schon etwas in C programmiert hat, dass er ueber ctypes anbindet, wohl kaum.

[seppi]

EDIT:

Bei Betrachtung der Auslastung der Kerne stehen alle Kerne bei einem Dualcore auf 50% bei einem Quadcore auf 25%. Lässt in mir den Verdacht aufkommen, dass das Programm nur auf einem Kern mit 100% läuft und Windows hier irgend ein Quatsch anzeigt.

Ja, da hast du recht. Der Taskmanager zeigt die Auslastung normalerweise zusammengefasst an und nicht auf CPU-Kern aufgeteilt. Du kannst allerdings unter Ansicht / CPU-Verlauf das umstellen

Das habe ich auch gemacht, Taskmanager zeigt gleichmäßige Verteilung auf alle cores an. Keine Cpu auf 100% Auslastung.

[jens]

Das habe ich auch gemacht, Taskmanager zeigt gleichmäßige Verteilung auf alle cores an. Keine Cpu auf 100% Auslastung.

Das wird IMHO wohl daran liegen, weil Windows einen Prozess ständig von einem Kern auf den anderen verschiebt...

Wie gesagt, nimm mal den sysinternals "Process Explorer", damit kannst du besser sehen was an Last ansteht...
Wobei wenn ein Kern voll ausgenutzt wird, dann liefert die Festplatte die Daten schnell genug...

Man müsste halt überlegen, wie man die Aufgabe auf mehrere Kerne Verteilen kann. Können denn die Zeilen in der Datei unabhängig voneinander verarbeitet werden? z.B. CPU-Kern-1 Zeile 1,3,5,... und Kern-2 Zeile 2,4,6,...

[seppi]

Das habe ich auch gemacht, Taskmanager zeigt gleichmäßige Verteilung auf alle cores an. Keine Cpu auf 100% Auslastung.

Das wird IMHO wohl daran liegen, weil Windows einen Prozess ständig von einem Kern auf den anderen verschiebt...

Wie gesagt, nimm mal den sysinternals "Process Explorer", damit kannst du besser sehen was an Last ansteht...
Wobei wenn ein Kern voll ausgenutzt wird, dann liefert die Festplatte die Daten schnell genug...

Man müsste halt überlegen, wie man die Aufgabe auf mehrere Kerne Verteilen kann. Können denn die Zeilen in der Datei unabhängig voneinander verarbeitet werden? z.B. CPU-Kern-1 Zeile 1,3,5,... und Kern-2 Zeile 2,4,6,...

Hi,
also meiner Meinung nach, kann ich die Zeilen so ohne weiteres nicht von mehreren Kernen berechnen lassen. Das Problem ist, z.B. dass jede Zeile eine Uhrzeit enthält und ich die Differenz zwischen den beiden Zeitpunkten überwachen muss.

Ich weiß einfach selbst nicht wo der Flaschenhals ist, ich versuche das mit eurer Hilfe gerade herauszufinden. Ich habe mal ein Screenshot von der I/O Auslastung mit dem Process Explorer gemacht und daneben mit HdDiskPerf den Datendurchsatz auf der Festplatte. Ich hoffe das hilft ...



EDIT:
Also nur um das nochmal klarzustellen: Das Parsen und Aufteilen der Zeileninformationen läuft in ctypes, das wäre natürlich ohne weiteres von mehreren Kernen zu bewerkstelligen. Jedoch die Berechnungen und Prüfungen die danach ablaufen, beziehen sich immer auf bereits gesammelte Daten von vorhergehenden Zeilen. Daher kann ich nicht Zeile x von Kern x und Zeile x+1 von Kern y bearbeiten lassen, da sonst Kern y auf Kern x warten müsste. Hoffe das ist verständlich

[jens]

Dann vielleicht nicht pro Zeile aufteilen, sondern dir ganze Datei in Blöcken zerlegen?

[seppi]

Dann vielleicht nicht pro Zeile aufteilen, sondern dir ganze Datei in Blöcken zerlegen?

Leider auch keine Möglichkeit, da ich nicht nur Informationen aus der letzten sondern unter Umständen auch aus weiter vorhergehenden Zeilen brauche. Ich muss bei der Bearbeitung einer Zeile, alles wissen was davor geschehen ist. Es müssen also alle Zeilen die davor waren fertig berechnet/ausgewertet worden sein.

[jens]

Dann hast du IMHO wenig Möglichkeiten zu parallelisieren. Evtl. das eigentliche Parsen der Daten... Aber das könnte nur was bringen, wenn es maßgeblich zur gesamt Auslastung beiträgt...

[deets]

Also wenn du nicht *alle* Zeilen brauchst, dann solltest du ueber eine Datenbank nachdenken. Denn dann kannst du parallelisieren, indem du eine Zeile beim einlesen als "in progress" markierst (in der DB, irgendein Kriterium musst du ja haben), und wenn dann andere Zeilen darauf zugreifen wollen, muessen sie erstmal warten, bis die abgearbeitet wurde.

Das ganze dann mit multiprocessing. Und irgendeine LRU-Strategie wirst du ja auch schon haben, denn *alle* Zeilen koennen's wohl kaum sein, die du brauchst, sonst waeren die 9GB ja ein Problem.

[Boa]

Hallo,

Wenn du die Performance verbessern willst ist es vorher ratsam herauszufinden wo es hängt. Irgendetwas zu verbessern und zu hoffen dass dadurch das Programm schneller wird ist keine effiziente Methode. Lass das Programm mit einem Profiler durchlaufen und stelle das Ergebnis graphisch dar. Dann weißt du wo du ansetzen kannst:
http://code.google.com/p/jrfonseca/wiki/Gprof2Dot

Beachte dass das Profiling entsprechend länger dauert.

[seppi]

Also wenn du nicht *alle* Zeilen brauchst, dann solltest du ueber eine Datenbank nachdenken. Denn dann kannst du parallelisieren, indem du eine Zeile beim einlesen als "in progress" markierst (in der DB, irgendein Kriterium musst du ja haben), und wenn dann andere Zeilen darauf zugreifen wollen, muessen sie erstmal warten, bis die abgearbeitet wurde.

Das ganze dann mit multiprocessing. Und irgendeine LRU-Strategie wirst du ja auch schon haben, denn *alle* Zeilen koennen's wohl kaum sein, die du brauchst, sonst waeren die 9GB ja ein Problem.

Nein eine LRU-Strategie (wenn ich das richtig verstanden habe) benötige/benutze ich nicht, da ich gar nicht so viele Daten zwischenspeichern muss. Etwas was ich bisher vergessen habe zu erwähnen ist, dass jede Zeile sofort in eine HTML Datei geschrieben wird.
Für die Berechnungen, die ich erwähnt habe, ist nicht jede Zeile wichtig, ich muss nur die Zeilen abspeichern für die eine gewisse Bedingung eintrifft.

Das ganze ist etwas schwer zu erklären ich probier es nochmal mit einem kurzen Beispiel:

Textdatei:
zeitstempel GeräteID Datenfeld
0.00 1A0 00
1.00 1A0 01
2.30 1A0 00
3.50 1A0 00
5.60 1A0 00

Mein programm geht jetzt Zeile für Zeile durch und bekommt von der ctype lib die einzelnen elemente (zeitstempel, GeräteID, Datenfeld) geliefert. Jetzt gibt es z.B. eine Prüfung, dass wenn die GeräteID sich ändert diese Änderung abgespeichert werden muss. Also wird Zeile 2 mit allen Elementen abgespeichert. Außerdem wird jede Zeile in eine HTML Tabelle geschrieben, welche später zur Betrachtung dient. Es gibt noch andere Berechnungen wie z.B. die erwähnte Differenz zwischen Zeitstempeln. Aber alles nicht allzu aufwendig. Aber insgesamt sind es 4 unterschiedliche Berechnungen, daher wollte ich nochmal nachfragen welchen Vorteil das multiprocessing modul bei dieser Anzahl der Berechnungen im Vergleich zum threading modul besitzt. Wenn ich pro Zeile 4 Threads erstelle, werden diese doch vom OS auf die Kerne aufgeteilt. Außerdem habe ich mit threading doch eine erheblich einfachere Programmierung, da ich doch leichter auf die Daten der anderen Threads zugreifen kann.

Aber vielleicht ist eine Datenbank wirklich ein guter Ansatz. Die könnte ich doch dann auch in einer HTML Datei leicht anzeigen lassen, oder? Nehm ich dafür dann einfach eine SQL Datenbank?

[seppi]

Hallo,

Wenn du die Performance verbessern willst ist es vorher ratsam herauszufinden wo es hängt. Irgendetwas zu verbessern und zu hoffen dass dadurch das Programm schneller wird ist keine effiziente Methode. Lass das Programm mit einem Profiler durchlaufen und stelle das Ergebnis graphisch dar. Dann weißt du wo du ansetzen kannst:
http://code.google.com/p/jrfonseca/wiki/Gprof2Dot

Beachte dass das Profiling entsprechend länger dauert.

Hi Boa,
danke das mit dem profiling habe ich bereits gemacht. Ich habe so gut ich es konnte den Code bei den am meisten aufgerufenen Funktionen verbessert. Ein großer Anteil beim Profiling nimmt bei mir die has_key abfrage weg. Laut meiner Recherche ist das jedoch der beste Weg um auf ein Dictionary zuzugreifen. Das stimmt doch, oder?

[Boa]

Wenn du nur jeweils eine Zeile brauchst musst du diese nicht im RAM abspeichern. Da kannst du folgende For Schleife verwenden:

Code: Alles auswählen

import fileinput
for line in fileinput.input(['myfile']):
  do_something(line)

Aber vielleicht ist eine Datenbank wirklich ein guter Ansatz. Die könnte ich doch dann auch in einer HTML Datei leicht anzeigen lassen, oder? Nehm ich dafür dann einfach eine SQL Datenbank?

In HTML kannst du nicht direkt auf Datenbanken zugreifen. Dafür kann man aber mit PHP sehr leicht HTML Tabellen aus einer Datenbank erstellen, wenn man sich ein bisschen damit auskennt.

[jens]

Ich meine in wäre besser. Also mal nachgesehen:

Code: Alles auswählen

def test_has_key():
    """Stupid test function"""
    d = {"abc": 1}
    for i in xrange(10):
        d.has_key("abc")
        d.has_key("nein")

def test_in():
    """Stupid test function"""
    d = {"abc": 1}
    for i in xrange(10):
        "abc" in d
        "nein" in d

if __name__ == '__main__':
    from timeit import Timer
    t = Timer("test_has_key()", "from __main__ import test_has_key")
    print "has_key:", t.timeit()

    t = Timer("test_in()", "from __main__ import test_in")
    print "in:", t.timeit()

Ausgabe:

Code: Alles auswählen

has_key: 2.53848695257
in: 1.52560327654

Bin mir nicht sicher, ob eine Datenbank wirklich schneller ist. Wenn es darum geht, das man eine Zeile immer in Relation zur vorherigen analysiert. Wo soll da eine Datenbank das ganze beschleunigen?

Warum werden eigentlich die Zeilen per ctypes aufgebröselt? Wie sehen die denn wirklich aus? Tut's auch eine einfaches line.split(" ") ?

[seppi]

Ich meine in wäre besser. Also mal nachgesehen:

Code: Alles auswählen

def test_has_key():
    """Stupid test function"""
    d = {"abc": 1}
    for i in xrange(10):
        d.has_key("abc")
        d.has_key("nein")

def test_in():
    """Stupid test function"""
    d = {"abc": 1}
    for i in xrange(10):
        "abc" in d
        "nein" in d

if __name__ == '__main__':
    from timeit import Timer
    t = Timer("test_has_key()", "from __main__ import test_has_key")
    print "has_key:", t.timeit()

    t = Timer("test_in()", "from __main__ import test_in")
    print "in:", t.timeit()

Ausgabe:

Code: Alles auswählen

has_key: 2.53848695257
in: 1.52560327654

Bin mir nicht sicher, ob eine Datenbank wirklich schneller ist. Wenn es darum geht, das man eine Zeile immer in Relation zur vorherigen analysiert. Wo soll da eine Datenbank das ganze beschleunigen?

Warum werden eigentlich die Zeilen per ctypes aufgebröselt? Wie sehen die denn wirklich aus? Tut's auch eine einfaches line.split(" ") ?

ctypes verwende ich aufgrund der Datentypenumwandlung. Die Zeitstempel benötige ich als int, damit ich sie gleich zur Differenz verwenden kann und keine Datentypkonvertierung in Python vornehmen muss. Eine Zeile sieht so aus wie ich es im letzten Kommentar geschrieben habe. line.split(" "), würde in den meisten Fällen gehen jedoch gibt es auch einige Ausnahmefälle. Außerdem habe ich beides probiert und ctypes war bei mir deutlich schneller.

[deets]

Bin mir nicht sicher, ob eine Datenbank wirklich schneller ist. Wenn es darum geht, das man eine Zeile immer in Relation zur vorherigen analysiert. Wo soll da eine Datenbank das ganze beschleunigen?

Datenbank war sehr weit gemeint, gar nicht speziell SQL. Aber wenn es um Beschleunigung durch parallelisierung geht, dann geht das nunmal nur mit multi-process, und damit brauchst du einen externen Service, der dir sagt, ob eine bestimmte Zeile vorhanden ist, was ihre Werte sind usw. Das kann auch nur ein einziger Prozess sein, der diese Frage beantwortet, zB der Parent. Aber irgendsowas braucht man.

[CM]

Eine Alternative wäre u. U. auch Umschreiben in hf5 und der Gebrauch von PyTables. Von der bisher beschriebenen Datenstruktur her *könnte* das sinnvoll sein.

Nur: Können wir weiter spekulieren ohne Code zu sehen?

[seppi]

Code kann ich leider nicht veröffentlichen.