qtforum.de

Hallo.
Ich habe große Text-Dateien die ich einlesen und Parsen will. Das Parsen ist ganz simpel, in jeder Zeile stehen n Integers oder Doubles als Klartext, und ich will das in Doubles konvertieren. Das funktioniert auch schon alles, hab auch schon ne Funktion die ein QByteArray nimmt und entsprechend verwurstet.

Code: Alles auswählen

while (!file.atEnd()) {
   parseLine(file.readLine(), ++lineNr);
}
// ca. 14,5 Sekunden für 1 Mio Zeilen mit jeweils drei Zahlen

Mein Problem: Ich würde gerne mehrere Zeilen auf einmal (parallel) parsen, denn das Ganze dauert gerne auch mal seine 3 Minuten bei 100% Auslastung auf einem Core. Das ganze sollte möglichst so ablaufen, dass er sobald ein Platz im globalen ThreadPool frei ist die nächste Zeile einlesen und in nem Thread parsen soll (Erst alles einlesen und dann mit QtConcurrent::mapped() parsen will ich vermeiden, weil ich nicht unbedingt 500MB Speicher für die Liste mit QByteArrays verpulvern will.)

Ich hab das dann mal mit nem einfachen Loop und QtConcurrent::run() probiert, aber das scheint nicht darauf ausgelegt zu sein und läuft mit 80-95% Auslastung auf allen Kernen (Dualcore) langsamer als der Serielle Ansatz mit 100% auf einem Kern. Oo

Code: Alles auswählen

while (!file.atEnd()) {
   QtConcurrent::run(this, &Loader::parseLine, file.readLine(), ++lineNr);
}
// ca. 23,5 Sekunden für 1 Mio Zeilen mit jeweils drei Zahlen

Verzweifelte Versuche den Overhead zu minimieren wie z.B. in nem Dauerloop immer nur dann run() aufzurufen wenn ein Platz im Threadpool frei ist oder immer nur maxThreads auf einmal zu starten und dann jedesmal warten bis alle Fertig sind bevor die nächsten gestartet werden haben natürlich alles nur noch schlimmer gemacht.

Was meint Ihr, kann man das irgendwie hinkriegen dass immer nur eine Zeile gelesen wird wenn ein Thread zum Parsen bereit steht oder muss ich doch ein 500MB File cachen nur um maped() verwenden zu können?

Dieses einfache auslesen braucht auf deinem Prozessor länger, als die Daten von der Festplatte zu holen? Was hast du für einen Prozessor und was für Festplattengeschwindigkeit?

Wow, konstruktiv, danke.
Wen es interessiert, es ist noch ein Intel Core 2 Duo E6300 mit nur 2x 1.86GHz und ne Western Digital Caviar Blue mit 7200rpm und 8.9ms Zugriffszeit an SATA II. HD-Tach Werte mess ich jetzt aber nicht auch noch.

ParseLine löscht erst alle überflüssigen Leerzeichen, Separatorzeichen und Kommentare, splited das Ergebnis in ne Liste aus QByteArrays, nimmt sich die gewünschten Einträge und konvertiert diese ByteArrays in richtige Zahlen, packt das in nen Struct und fügt den dann Threadsicher in ne Cacheliste ein.
Das modifizierte simplified und split brauchen jeweils ca. 20%, das threadsichere einfügen ca. 5% und das toDouble konvertieren ca. 55% der Laufzeit. Das sind aber nur gerundete Mittelwerte für eine Datei mit drei Spalten.
Wenn man das Einlesen noch mitbetrachtet kommt es ungefähr auf den selben Wert wie simplified und split, also ja, konvertieren dauert fast dreimal so lang wie einlesen.

Also nochmal: Es ist unrealistisch, daß ein aktueller Prozessor für das einfache zerlegen eines Strings länger braucht, als eine normale Festplatte Daten nachliefern kann.

Naja - es kommt einfach drauf an wie man die Zeile zerlegt... so nach dem Motto - warum einfach wenns auch umständlich geht. Man müsste mal die parseLine() - Funktion sehen.
Wenn es wirklich schnell gehen soll würde ich wohl eher direkt auf den char* - Daten arbeiten und nichts splitten usw.

So, hier mal ein Minimalbeispiel mit Zeitmessung und Ausgabe

Code: Alles auswählen

#include <cstdlib>
#include <ctime>
#include <QtCore/QFile>
#include <QtCore/QList>
#include <QtCore/QTime>

int main(int argc, char *argv[]) {
   srand(time(NULL));
   QFile file("testfile.txt");

   // create
   qDebug("Creating testfile...");
   file.open(QIODevice::WriteOnly | QIODevice::Text);
   for (int i=0; i<1000000; ++i) {
      file.write(QByteArray::number(rand()/1000.0, 'e') + " ");
      file.write(QByteArray::number(rand()/1000.0, 'e') + " ");
      file.write(QByteArray::number(rand()/1000.0, 'e') + "\n");
   }
   file.close();
   qDebug("Starting Test");

   // read
   QTime time;
   QList<QByteArray> cache;
   file.open(QIODevice::ReadOnly | QIODevice::Text);
   time.start();
   for (int i=0; i<1000000; ++i) {
      cache << file.readLine();
   }
   qDebug("readLine: %dms", time.elapsed());
   file.close();

   // convert
   time.start();
   for (int i=0; i<1000000; ++i) {
      //parseLine(cache[i], i);
      QByteArray line = cache[i].simplified();
      QList<QByteArray> list = line.split(' ');
      list[0].toDouble();
      list[1].toDouble();
      list[2].toDouble();
   }
   qDebug("toDouble: %dms", time.elapsed());

   return 0;
}

Das ist jetzt nicht dynamisch sondern alles hart reingecoded, aber es ist ein gutes und realistisches Beispiel und so braucht das Parsen gut dreimal so lang wie das ReadLine auf meinem Laptop mit ner 5400rpm Platte und nem 1,73GHz Singlecore.
Die tatsächliche parseLine sieht ähnlich aus, nur halt dynamischer. Ich poste sie am Ende für die dies interessiert.

Ein Kumpel von mir hat mal einen Parser für das gleiche Problem in C geschrieben und der Geschwindigkeitsunterschied zur Qt-Lösung ist minimal (meist ist meiner wenige milisekunden schneller, aber wir haben auch beide noch ein paar postprocessing-Schritte mitgemessen. Wenn ich toDouble durch strtod ersetze quetsch ich tatsächlich noch 1 Prozent Performance raus aber hab keine ok-Variable mehr, und die brauch ich z.B.). Ich hab das ganze nochmal mit Qt geschrieben weil er ihn niemals fertiggestellt hat (War noch fast alles statisch dran, kaum dynamisch).
Hat mich auch verwundert, aber die Qt funktionen sind kaum langsamer als C. Daumen hoch, Trolle!

so, hier noch die ausführliche parseLine Funktion, vllt kommen dann ja endlich mal Tipps zum Topic...

Code: Alles auswählen

void Loader::parseLine(QByteArray rawLine, int nr) {
   // strip comments and redundant separators and blanks
   QByteArray line = simplified(rawLine, sepChar, comChar);
   if (line.size() == 0) {
      return;
   }
   QList<QByteArray> list = line.split(sepChar);
   if (list.size() < minColumns) {
      qWarning("Skipped line %d: Expected %d data items but only found %d. (%d: \"%s\")", nr, minColumns, list.size(), nr, line.data());
      return;
   }

   bool ok;
   Data* newData = new Data;

   newData->x = list[xColumn-1].toDouble(&ok);
   if (!ok) {
      qWarning("Skipped line %d: X value (data item %d) is not a valid number. (%d: \"%s\")", nr, xColumn, nr, line.data());
      delete newData;
      return;
   }
   newData->y = list[yColumn-1].toDouble(&ok);
   if (!ok) {
      qWarning("Skipped line %d: Y value (data item %d) is not a valid number. (%d: \"%s\")", nr, yColumn, nr, line.data());
      delete newData;
      return;
   }
   double zTemp;
   if (zColumns.isEmpty()) {
      for (int i=0; i<list.size(); i++) {
         if (i != (xColumn-1) && i != (yColumn-1)) {
            zTemp = list[i].toDouble(&ok);
            if (!ok) {
               qWarning("Skipped line %d: Z value (data item %d) is not a valid number. (%d: \"%s\")", nr, i+1, nr, line.data());
               delete newData;
               return;
            }
            if (!newData->z.contains(zTemp)) {
               newData->z << zTemp;
            }
         }
      }
   }
   else {
      for (int i=0; i<zColumns.size(); i++) {
         zTemp = list[i].toDouble(&ok);
         if (!ok) {
            qWarning("Skipped line %d: Z value (data item %d) is not a valid number. (%d: \"%s\")", nr, zColumns[i], nr, line.data());
            delete newData;
            return;
         }
         if (!newData->z.contains(zTemp)) {
            newData->z << zTemp;
         }
      }
   }
   appendCache(newData);
}

Und bevor noch weitere Fragen kommen hier noch ein paar aufgerufene Funktionen und so:

Code: Alles auswählen

struct Data {
   double x;
   double y;
   QList<double> z;
};

QByteArray simplified(QByteArray in, char sep, char com) {
   if (in.size() == 0)
      return in;
   QByteArray result(in.size(), ' ');
   const char *from = in.data();
   const char *fromend = from + in.size();
   int outc = 0;
   char *to = result.data();
   forever {
      while (from!=fromend && (*from==sep || isspace(uchar(*from))))
         from++;
      while (from!=fromend && ((*from!=sep && *from!=com) && !isspace(uchar(*from))))
         to[outc++] = *from++;
      if (from!=fromend && *from!=com)
         to[outc++] = sep;
      else
         break;
   }
   if (outc > 0 && to[outc-1] == sep)
      outc--;
   result.resize(outc);
   return result;
}

void MatrixLoader::appendCache(Data *newData) {
   mutex->lock();
   cacheList << newData;
   mutex->unlock();
}

Ganz allgemein, leider nur für Linux. Mit 'valgrind --tool=cllagrind' bekommt man eine sehr gute zeilenweise Aufschlüsselung wo die CPU-Zeit verbraten wird.
Ich denke dass der Overhead zum parallelisieren größer ist als der Gewinn dadurch. Man müsste es aber darauf ankommen lassen. Eine Idee wäre ein paar Workerthreads, eine QSemaphore die anzeigt wie viele Zeilen im Puffer sind und die Workers warten auf diese Semaphore und natürlich eine Thread-safe getLine() Methode. fertig - ganz ohne QtConcurrent. Müsste man mal ausprobieren, kostet nicht viel Zeit zum Programmieren.

Ein paar Kleinigkeiten zum Code
- simplified und parseLine sollten eine const Ref anstatt eine Value übergeben bekommen - das spart ein paar detach() - Aufrufe
- das Splitten danach ist unschön - alles was Du dazu wissen musst ist doch in simplified() schon vorhanden - also gleich dort splitten und eine QList<QByteArray> zurückgeben
- QList<QByteArray> list sollte const sein (wieder wegen der detach() - Geschichte)
- wie groß wird z? Wenn es sehr groß wird ist z.contains() evtl. sehr zeitaufwändig
- im else-Zweig gehst Du über zColumns.size(), benutzt aber nirgends zColumns - ist das so korrekt?

Ah, danke, das mit Valgrind werd ich mal ausprobieren. Das mit den Semaphoren dann auch mal, aber wenn du dem schon so kritisch gegenüberstehst wird das dann wohl mein letzter Versuch sein...

- Das mit den constant references werde ich machen, danke für den Tip!
- Das mit dem Spliten kommt daher, dass ich zuerst nur die QByteArray-eigenen Funktionen simplified und split benutzt hab. Als ich das Simplified dann für meine Zwecke erweitert hab dachte ich mir auch schon, dass man das Split auch noch gleich mit reinmixen könnte, hatte das aber erstmal hintenangeschoben. Werd das dann wohl doch mal angehen...
- Z wird nicht groß, das sollte meistens zwischen 1 und 3, maximal vllt 10 sein. Es bringt aber einiges, da je nach Wahl der Spalten gerne mal jeder zweite Wert doppelt wäre. Ich hatte da zuerst Bedenken, weil mit contains ja Doubles auf Gleichheit überprüft werden, aber es funktioniert, also scheint Qt da von selbst qFuzzyCompare zu verwenden oder so...
- Oi, mit den zColumns hast du recht, da hat sich doch glatt der copy-paste-Fehlerteufel eingeschlichen (seltsam, wann ist das denn passiert, das war irgendwann mal richtig...

). Richtig müsste es natürlich list[zColumns-1] statt list heißen.

Danke nochmal für die Tipps, Verbesserungsvorschläge und Bugsuche, das hat mir echt weitergeholfen

Das mit den double-Compare funktioniert hier da Du keine Berechnung durchführst und ein QString("5.012").toDouble() ja immer das gleiche Ergebnis zurückliefert. Würdest Du einmal 5.012 berechnen und einmal per toDouble() dann würde es mit ziemlicher Sicherheit nicht funktionieren.

qtforum.de

Große Dateien parallel zeilenweise parsen.

Große Dateien parallel zeilenweise parsen.

t

Re: t