Seite 1 von 3

Verfasst: Dienstag 8. Juli 2008, 22:26
von BastiL
Ich habe den Ausdruck grade nicht hier, poste ich morgen. Die Anwendung ist sehr speziell. Wir haben sehr große Files und gute Rechenaustattung. Daher ist es kein Problem. das File auf einmal einzulesen. Performence ist aber wichtig... Das heißt aber nicht das es vielleicht auch anders geht. Da ich aber wie schon gesagt das File aufteilen will werde ich nicht drumherum kommen, alles im Speicher vorzuhalten....

Grüße

Verfasst: Dienstag 8. Juli 2008, 22:32
von rayo
Nein alles brauchst du ja nicht im Speicher.

Falls du aus der einen Datei 3 Dateien machen willst kannst du folgendermassen vorgehen:
Lese 100MB ein, suche das Pattern, falls nicht gefunden schreibe es in die neue Datei 1, falls schon gefunden schreibe den 1. Teil in Datei 1, den Rest ab dem Pattern in Datei 2. Lese die nächsten 100MB ein und suche weiter (mit der Erwähnten überschneidung natürlich, FilePointer zurücksetzen)
Mit dem gleichen Schema kannst du auch den zweiten Teil der grossen Datei aufsplitten.

Somit hast du nur immer 100MB im Speicher, der Rest geht direkt wieder auf die Harddisk.

Das ganze geht natürlich nur wenn man den Regex in 2 einzelne Teile austeilen kann ohne dass er länger zum suchen hat.

Gruss

Verfasst: Dienstag 8. Juli 2008, 22:40
von Michael Schneider
Hi BastiL!
BastiL hat geschrieben:Den Anfangs- und Endteil zu suchen habe ich versucht - erstaunlicherweise ist die Suchdauer DEUTLICH länger....
Das mag sein, aber Du musst die Ladezeit schon mit einrechnen. Und ich bin überzeugt, dass es länger dauert, >2GB in den Speicher zu laden, als vom Anfang bis Start und vom Ende bis zum Endpunkt und das dazwischen vom OS kopieren zu lassen oder häppchenweise umzuschaufeln.
BastiL hat geschrieben:Aber eigentlich kommen wir vom Thema ab - das Matchen ist nicht das Problem. Das Problem ist das Einlesen einer Datei mit mehr als 2GB "auf einen Rutsch" (f = read(Inputfile)) - da gibt es ein Limit in Python...
Wie Du sagst, das ist das Problem. Das hängt schon vom Dateisystem ab, denn z.B. mit FAT kannst Du unter Umständen nur max. 2GB adressieren. Das ist also kein Problem von Python, es sei denn Du nennst mir ein anderes Programm, mit dem Du mehr als 2GB auf Deinem Rechner einlesen kannst.
Das zu Deinem Thema.

Und nun zum Thema, dass es ABSURD ist, für eine minimale Anwendung 2 GB durch den Speicher zu jagen. Das belastet Deine Ressource ebenso immens wie unnötig. Insbesondere, wenn Du den String dann nur an 2 Stellen trennen möchtest und diese sogar noch sehr stark eingegrenzt sind. Du verrennst Dich da in einen völlig unpragmatischen Lösungsansatz.

Im Namen der Vernunft ;-): lass ab von Deinem Plane und poste das Pattern, dann gibt es hier sicher Fachleute, die elegantere UND schnellere Lösungen anbieten können.

Michel

Verfasst: Mittwoch 9. Juli 2008, 02:10
von epsilon
@ BastiL:

schau' dir mal mmap an ;)

http://effbot.org/tag/python.mmap
http://docs.python.org/lib/module-mmap.html

EDIT:

auf 32-bit Betriebssystemen kannst du damit allerdings auch nur 2 bis 3 GB-files verarbeiten. In dem Fall kannst du dir mal Pytables anschauen (http://www.pytables.org/moin). Siehe features 'Support of files bigger than 2 GB' (http://www.pytables.org/moin/MainFeatures)

Verfasst: Mittwoch 9. Juli 2008, 05:31
von BlackJack
@BastiL: Wie epsilon schon angedeutet hat, kann das einlesen von 2GB in den Speicher auch schon daran scheitern, dass bei 32-Bit Betriebssystemen der Adressraum eines einzelnen Prozesses in der Regel auf 2 bis 3 Gigabyte beschränkt ist, auch wenn mehr Speicher installiert sein sollte.

Wenn Du die Datei aufteilen möchtest belastest Du mit dem kompletten Einlesen den Speicher und die Dateisystem-Caches völlig unnötig mit der gesamten Datei. Wenn Du dann noch vorhaben solltest Dir von dem `match`-Objekt den Treffer als Zeichenkette zu holen, ist Dir hoffentlich klar, dass Du damit eine zweite Zeichenkette im Speicher erzeugst, die fast so gross ist wie die erste, eben nur abzüglich der paar MB vorn und hinten.

Eine ordentliche Lösung, die die Datei Stückweise verarbeitet, kann auch gar nicht so viel langsamer sein, weil die Laufzeit eigentlich vom Datentransfer zwischen Platte und RAM dominiert sein sollte. Wenn Du entsprechende Laufzeittests machst, musst Du immer die Caches vorher löschen, um aussagekräftige Ergebnisse zu bekommen. Nicht dass Du reguläre Ausdrücke mit Python-Schleifen bei Daten vergleichst, die schon längst im Speicher stehen.

Und spätestens wenn so eine "alles in den Speicher laden"-Lösung aus irgend welchen Gründen den verfügbaren Speicher sprengt und ausgelagert werden muss, hat man verloren was die Geschwindigkeit angeht.

Verfasst: Mittwoch 9. Juli 2008, 07:03
von epsilon
BlackJack hat geschrieben:Eine ordentliche Lösung, die die Datei Stückweise verarbeitet, kann auch gar nicht so viel langsamer sein, weil die Laufzeit eigentlich vom Datentransfer zwischen Platte und RAM dominiert sein sollte.
Du scheinst Recht zu haben. Laut meinem Testscript¹ ist der Unterschied minimal:

mem: 6.38910222054 Sekunden
mmap: 6.37096810341 Sekunden
0,1 MB-weise: 6.49766802788 Sekunden
10 MB-weise: 6.51032304764 Sekunden
100 MB-weise: 6.54638910294 Sekunden

Testdatei war ein XML-Dump des Wiktionary (157 MB), aus welcher ich die einzelnen Artikel extrahiert hab'.

¹ http://ubuntuusers.de/paste/390058/

PS: wobei das sicherlich alles andere als ein optimaler Test ist...

Verfasst: Mittwoch 9. Juli 2008, 09:30
von BastiL
Hallo zusammen,

ich habe 64 Bit Linux. Umgang mit Files größer 5 GB ist bei uns an der Tagesordnung. Nur mit Python bearbeite ich so etwas zum ersten Mal.

Ich poste mal einen Auszug aus meinem Code mit dem Pattern:

Code: Alles auswählen

def Extract(File):
   Part = re.search(r'\(0 "Grid:"\).*(?s)(?=\(0 "Thread variables:"\))', File, re.I)
   return Part

f = open(sys.argv[1], "r")
print "lese " + sys.argv[1] + "..."
Casefile = f.read()
f.close()

Mittelteil = Extract(Casefile)
Teil1 =  Casefile[0:Netz.start(0)]
Teil2 = Casefile[Netz.end(0):len(Casefile)]
Was sicher nicht optimal ist, ist den langen regex durch kopieren auf Mittelteil kurz doppelt im Speicher zu haben. Aber es hat funktioniert und mir ist nichts besseres eingefallen. Jetzt ist wie gesagt das Problem, dass f.read bei Files > 2GB aussteigt. ich freue mich über Vorschläge.

Edit: Möglicherweise liegen die Performenceunterschiede am "r". Da das File Binärcode enthält wäre wohl "rb" die bessere Wahl, oder?

Verfasst: Mittwoch 9. Juli 2008, 09:55
von EyDu
epsilon hat doch schon eine Lösung gepostet, übernimm diese doch einfach. Wenn du Binärdaten verwendets, solltest du zum Öffnen in jedem Fall "rb" benutzen. Einfach nur "r" kann mit unter sogar falsche Ergebnisse liefern.

@epsilon: Warum benutzt du eigentlich immer Fußnoten, du kannst auch Links direkt im Text unterbringen :wink:

Verfasst: Mittwoch 9. Juli 2008, 10:20
von rayo
Hi

Also ich hab jetzt mal ein Beispiel gemacht ohne regulären Ausdruck.
Ist jedoch ungetestet! und hat einen grossen Fehler drin ;)

Durch die 25 Bytes, die überlappend sind, wird zuviel in den Part1 und Part2 geschrieben. Aber grundsätzlich sollte es so funktionieren, mit ein paar Index anpassungen geht das auch ohne die 25 Bytes die überlappen.

Das Beispiel ist nur der Wegweiser, wie es ohne die komplette Datei geht.

Beispiel

Ach ja ob "r" oder "rb": "rb" hat nur unter Windows einen Einfluss, unter Unix macht das keinen Unterschied, da bei Windows mit "r" ein \n zu \r\n wird mit "rb" nicht. Bei Unix bleibt \n auch ein \n, also kein Problem.

Gruss

Verfasst: Donnerstag 10. Juli 2008, 21:22
von BastiL
Danke. Ich werde das ganze mal ausprobieren. Melde mich dann nach den Tests nochmal.

Verfasst: Samstag 12. Juli 2008, 13:11
von epsilon
EyDu hat geschrieben:@epsilon: Warum benutzt du eigentlich immer Fußnoten, du kannst auch Links direkt im Text unterbringen :wink:
Ich finde so geht es schneller, als wenn ich erst meine Hand den ganzen Weg zurück zur Maus bewegen muss ;)

Verfasst: Montag 21. Juli 2008, 06:59
von BastiL
Hallo zusammen,

ich habe endlich mal die Gelegenheit gehbat, mir das für eine meiner Beispieldateien anzuchauen. Mit dem Benchmark von epsilon bekomme ich für meine Beispieldatei mit meinem regulären Ausdruck folgendes:

mem: 114.707464933 Sekunden
mmap: 113.919741154 Sekunden
104857 Byte: 1291.05129695 Sekunden
10485760 Byte: 1293.54394603 Sekunden
104857600 Byte: 1293.17202592 Sekunden

Die Datei die ich jetzt benutzt habe ist knapp unter 2GB, deshalb werde ich gleich noch meinen bisherigen Algo laufen lassen und die Ergebnisse dazu auch noch posten. Der ist nämlich nochmal einiges schneller als mem....

Grüße

Verfasst: Montag 21. Juli 2008, 07:33
von BastiL
So, mit meinem Skript bekomme ich für dieselbe Datei:

Gesamtzeit: 10.3644731045 Sekunden

Das ganze läuft wie gesagt nur für Files < 2GB. Offensichtlich ist nicht nur das Laden in den Speicher ein Nadelöhr (bei meinen Files ungefähr Faktor 10) sondern auch noch die Art und Weise wie die reguläre Ausdruck behandelt wird (ich lese das File gleich ein wie die" mem"-Funktion von epsilon...)

Verfasst: Montag 21. Juli 2008, 08:34
von epsilon
@ BastiL:

hast du Lust dein Testskript hier zu posten? Irgendwie kann ich mir nicht erklären, wieso das Einlesen in n-byte Blöcken mehr als 10-mal langsamer sein soll, als das direkte Einlesen der Datei oder der Verwendung von mmap. (Bei mir war ja alles ungefähr gleich schnell; siehe weiter oben)

So, mit meinem Skript bekomme ich für dieselbe Datei:

Gesamtzeit: 10.3644731045 Sekunden
Den Code würde ich auch mal gerne sehen, wenn es dir nichts aus macht.
Irgendwas muss ich falsch machen ;)

Verfasst: Montag 21. Juli 2008, 09:34
von BastiL
Mein Testscript entspricht Deinem, ich habe lediglich die RegEx geändert (nur den Teil zwischen den ''). Mein Code sieht so aus:

Code: Alles auswählen

#!/usr/bin/python
# encoding: UTF-8

import sys, re, time

# Suchfunktionen
def Extract_Binary(File):
   Binary = re.search(r'\(0 "Grid:"\).*(?s)(?=\(0 "Thread variables:"\))', File, re.I)
   return Binary

# lese File in den Hauptspeicher
StartTime = time.time()
f = open(Test.file, "r")
print "lese Test.file"
File = f.read()
f.close()

print "analysiere "
   Binaer = Extract_Binary(File)
print "Binärteil extrahiert"

print 'Gesamtzeit: ', time.time() - StartTime, 'Sekunden'
Wie ich oben schon geschrieben habe kann das an der speziellen Struktur meiner Files liegen. Dieses Tempo bekomme ich auch nur hin, wenn ich genau so matche - wenn ich von Dateianfang bis zum Auftreten von "(0 Grid)" suche dauert das auch deutlich länger.... Es ist aber auch denkbar, dass die großen Unterschiede erst bei großen Files (>> 1GB) auftreten.

Verfasst: Montag 21. Juli 2008, 10:07
von BlackJack
@epsilon: Kannst Du Deinen Benchmark vielleicht noch einmal Verfügbar machen? Der Paste ist anscheinend nach der Umstellung von ubuntuusers weg.

@BastiL: Wie sieht's mit der Zeit aus, wenn Du auch wirklich die Daten extrahierst und in eine Datei schreibst?

Verfasst: Montag 21. Juli 2008, 10:31
von BastiL
Das mit der Zeit für extrahieren und Schreiben müsste ich mir ansehen. Das ist allerdings im benchmark von Epsilon auch nicht dabei, das ist auch die reine Suchzeit. Das Schreiben geht gefühlt auf jeden Fall schneller als das Suchen, die gesamte Programmlaufzeit liegt für meinen Code unter 30 Sekunden.

Verfasst: Montag 21. Juli 2008, 10:47
von epsilon
Über den Cache von Google ist das Skript noch verfügbar (Hier mit Formatierung)

Das Skript hatte noch einen bug, wodurch in byteweise() immer die Selbe Anzahl an Bytes eingelesen wurde. Der Unterschied ist allerdings gering (falls es überhaupt einen Unterschied gibt):

mem: 6.33056998253 Sekunden
mmap: 6.20173692703 Sekunden
104857 Byte: 6.86206698418 Sekunden
10485760 Byte: 6.63443303108 Sekunden
104857600 Byte: 6.43973302841 Sekunden

Verfasst: Montag 21. Juli 2008, 19:14
von BastiL
Irgendwie hat mir das bisher nicht so ganz weitergeholfen. Was ich im Moment v.a. nicht verstehe ist der große Performenceunterschied zwischen meinem Skript und der "mem" Variante im Benchmark von epsilon. Das Einlesen ist ja genau gleich, anscheinend liegt das im Matchen es re? Ich muss da mal ein paar Tests fahren... Habt Ihr noch Ideen?

Verfasst: Dienstag 22. Juli 2008, 02:59
von epsilon
BastiL hat geschrieben:[...] Was ich im Moment v.a. nicht verstehe ist der große Performenceunterschied zwischen meinem Skript und der "mem" Variante im Benchmark von epsilon. Das Einlesen ist ja genau gleich, anscheinend liegt das im Matchen es re? Ich muss da mal ein paar Tests fahren... Habt Ihr noch Ideen?
Das kann ich mir ehrlich gesagt auch nicht erklären. Das Einzige, was ich mir denken könnte, ist dass du nicht den selben Regulären Ausdruck verwendet hast (hast du auch die Flags ausgetauscht? Also dein 're.I' gegen mein 're.S | re.U' ? Wenn nicht, teste das mal.).

Dann frage ich mich noch, wie du in 10 Sekunden 2 GB einlesen und den RE drüber laufen lassen willst? (Ich brauche alleine für das einlesen von 1 GB 30 Sekunden, und das ist das reine einlesen. Vielleicht hast du aber auch nur 'ne besser Festplatte als ich ;))

Dann frage ich mich noch: Hast auch (wie ich) für jeden Test eine andere file verwendet, bzw. vor jedem Test den Cache gelöscht? Benen' doch mal deine Testfile um und teste mit ihr dein Testskript, nachdem du meine 'mem' Funktion verwend hast.

BastiL hat geschrieben:Irgendwie hat mir das bisher nicht so ganz weitergeholfen.
Hast du überhaupt getestet, ob man mit mmap auf einem 64-Bit System größere Dateien als 2 bis 3 GB adressieren kann? Vom speed her darf ja mmap eigentlich gar nicht langsamer sein als das direkte, komplette Einlesen in den Speicher (wenn man auf jede Stelle in der file sowieso nur einmal mit dem RE zugreift). In meinen Tests war mmap sogar ein wenig schneller als das Einlesen in den Speicher.