Parsen großer files



  • Hey,
    ich muss eine kleine Software schreiben die ein Dateiformat in ein anderes überführt. Die Dateiformate kann ich leider nicht beeinflussen.
    Programm 1 liefert eine csv ähnliche ASCII Datei mit sehr fixen Spezifikationen.
    In dieser können die Datentypen double,float,int (und als array) enthalten sein.

    Mein Ziel Dateiformat enthält die Werte in Binär und hat eine andere Form + Kompression etc.

    Die eigentliche Umwandlung ist kein Problem und läuft bereits.

    Mein Problem liegt aktuell an der Dateigröße. Es handelt sich dabei um >2GB große CSV Dateien. Meist 80 bis 100 Spalten und über 1.000.000 Zeilen.

    Da relativ häufig und viele Dateien umgewandelt werden müssen versuche ich die Geschwindigkeit entsprechend zu optimieren und genau da brauche ich etwas Hilfe.

    Ein kurzer Umriss meines Codes an den kritischen Stellen:

    int main()
    {
        std::ifstream file;
        file.open(name + ".csv");
    
        std::string fileDataS;
        fileDataS.reserve(2048);
    
        while (true)
        {				
            std::getline(file, fileDataS);
            parse::parseData(headerData, &fileDataS);
            // speicher im neuen Format
            // eof
        }
    }
    
    void parse::parseData(std::vector<BaseValue*> & vec, std::string* line)
    {
        typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
    
        static const boost::char_separator<char> sep(" ");
        tokenizer tokens(std::move(*line), sep);	
    
        std::vector<BaseValue*>::iterator vecItr = vec.begin();
    
        for (tokenizer::iterator itr = tokens.begin(); itr != tokens.end(); itr++)
        {
            const char* str;
            str = itr->data();
            switch ((*vecItr)->getType())
            {
            case UNKNOWN:
    			break;
    		case INTEGER:	((Value<int>*)(*vecItr))->getData() = atoi(str);
    			break;
    		case FLOAT:		((Value<float>*)(*vecItr))->getData() = fast_atof::atof(str);
            // Weitere Fälle
            }
        vecItr++;
        }
    }
    

    Bei BaseValue und Value handelt es sich um interne Klasse die einfach die Daten Speichert und hinterher ausgibt.

    fast_atof ist schneller als atof auf kosten der Genauigkeit. Diese reicht aber für meinen Anwendungsfall aus.

    Ich denke es werden im obigen Code noch einige unnötige Kopien der Daten erzeugt, weiß aber zurzeit nicht wie ich das verhindern kann.

    Mfg. Dominik



  • Der Umweg über std::string und std::getline() ist unnötig, du kannst direkt aus den Streams parsen. Such vielleicht mal nach Beiträgen vom Benutzer Werner Salomon, er hat diesbezüglich einige sehr gute Antworten gegeben.

    Und benutze static_cast für Klassencasts! Aber warum verwendest du nicht gleich virtuelle Funktionen, was bringt das switch ?



  • Ich hab meinen Code auf virtuelle Funktionen umgestellt:

    for (tokenizer::iterator itr = tokens.begin(); itr != tokens.end();)
    {		
    
        (*vecItr)->setData(itr);		
        vecItr++;
    }
    

    Template Spezialisierung:

    template<>
    inline void Value<int>::setData(tokenizer::iterator& str)
    {	
    	*(this->data) = atoi((*str).c_str());
    	str++;
    }
    

    Leider ist der einzige Vorteil das es schöner aussieht. In der Laufzeit hat sich quasi nichts verändert.

    Ich durchsuche aktuell noch die Beiträge von "Werner Salomon". Er hat allerdings sehr viel geschrieben, sodass dies noch etwas dauert.



  • So,
    kurzes Update meinerseits nachdem ich einige Foren Beiträge durchgelesen habe:

    Ich bin jetzt bei einer Verarbeitungs-Geschwindigkeit von rund >20 MByte/s und hab diese damit mehr als verdoppelt. Der RAM Verbrauch ist durch die Verwendung von "memory mapped files" allerdings auch auf ~100MB gestiegen.

    Falls mehr Source erwünscht ist einfach schreiben.

    Folgendes ist der aktuelle Code:

    void main()
    {
        //...
        boost::iostreams::mapped_file_source file;
        file.open(name + ".csv");
        const char* fileDataC = file.begin();	
    
        if (file.is_open())
        {	
            //... ReadHeader
            while (true)
            {
                fileDataC = parse::parseData(headerData, fileDataC);
                //... Speicher Zeile in neuem Format
                if (fileDataC >= file.end()) break;
            }
        }
       //...
    }
    
    const char* &parse::parseData(std::vector<BaseValue*> & vec, const char* line)
    {
        std::vector<BaseValue*>::iterator vecItr = vec.begin();
    
        while (true)
        {
            (*vecItr)->setData(line);				
    
            if (*(line - 1) == '\n') break;
    
            vecItr++;		
        }
        return line;
    }
    

    setData ist jetzt für jede mögliche Variable die in der Datei sein kann spezialisiert, sodass der Pointer immer korrekt verschoben wird.

    template<>
    inline void Value<double>::setData(const char* &str)
    {	
        *this->data = fast_atox::atof_cut(str);
        str++;
    }
    double atof_cut(const char* &p)
    {
        // parse Zahl
        // verschiebe p dabei bis vor nächsten nicht-Zahl
    }
    

    Bis auf einen Schritt wo getestet wird ob die Zeile zu ende ist durchlaufe ich jedes Zeichen in der Datei nur ein einziges mal.

    Hat noch irgendwer Ideen?

    Danke Nexus für den bisherigen Hinweis



  • Bist du sicher, dass Memory Mapped Files so viel bringen? So wie ich dein Problem verstehe, musst du die Datei genau einmal öffnen und von Anfang bis Schluss parsen. Du brauchst also weder Random Access noch Zugriffe über längere Zeit. Das einzige, was Schnelligkeit bringen könnte, ist in grösseren Blöcken zu lesen statt einzelne Bytes. Aber die Festplatte wird wahrscheinlich der limitierende Faktor sein, das Parsen wird vermutlich eher wenig Zeit in Anspruch nehmen (bei SSDs siehts wohl besser aus). Daher frage ich mich auch, wie viel dein fast_atof bringt.

    Wie lange dauert momentan so ein Durchgang? Eventuell wären auch mehrere Threads eine Möglichkeit, sodass du in der Zeit, die du auf I/O wartest, bereits parsen kannst.

    Aber statt lange herumzuraten, wo man noch Performance rausholen könnte, solltest du vielleicht einen Profiler bemühen.

    P.S. In C++ muss main() int zurückgeben.
    ~Bitte nicht mit dem Standard kommen, man kann mit void nicht portabel programmieren, auch wenn es einzelne Compiler unterstützen.~



  • Mein Programm nutzt auch int main() 😉
    Ich hab das nur für das Forum zusammen gekürzt unter anderem auch dass return, daher hab ich einfach ein void raus gemacht.

    Aktuell braucht das Programm rund 15 Sekunden für eine 370MB Test-Datei, was für mich ausreicht.
    Intel Amplifier XE bestätigt mir, dass ~3/4 der Zeit für das neu strukturieren und komprimieren benötigt wird, daher bin ich mit dem Parser zufrieden.

    Insgesamt wurden 18 Millionen Gleitkommazahlen (meist mehr als 10 Stellen) mit der atof Funktion konvertiert, dafür hat sie "nur" ~2.5 Sekunden benötigt. Soweit man sich auf die Angaben verlassen kann.

    Memory Mapped Files haben den Vorteil das sich das OS um das effiziente Nachladen der Datei kümmert, daher immer ein HDD Block.

    Grüße
    _Dominik


  • Mod

    _Dominik schrieb:

    Mein Programm nutzt auch int main() 😉
    Ich hab das nur für das Forum zusammen gekürzt unter anderem auch dass return, daher hab ich einfach ein void raus gemacht.

    Offtopic: In C++ entspricht ein Verlassen der main-Funktion ohne return einem return 0;



  • Nexus schrieb:

    Das einzige, was Schnelligkeit bringen könnte, ist in grösseren Blöcken zu lesen statt einzelne Bytes.

    +1
    Ist auch relativ einfach umzusetzen. Das einzige was dabei auch nur Ansatzweise tricky ist, ist zu checken ob man eh noch genug Daten gepuffert hat -- also ob eh noch ein abschliessendes Newline da ist.
    Wobei man auch das relativ elegant lösen kann.

    Aber die Festplatte wird wahrscheinlich der limitierende Faktor sein, das Parsen wird vermutlich eher wenig Zeit in Anspruch nehmen (bei SSDs siehts wohl besser aus). Daher frage ich mich auch, wie viel dein fast_atof bringt.

    Stimmt auch mit meiner Erfahrung überein.
    Und wenn der restliche Code schon 3x so lange wie das parsen dauert, zahlt es sich wohl eher sich den mal anzugucken, was man da noch rausholen kann.

    Eventuell wären auch mehrere Threads eine Möglichkeit, sodass du in der Zeit, die du auf I/O wartest, bereits parsen kannst.

    Schlaue OSe machen Read-Ahead Caching. Ich hab' dazu noch keine Tests gemacht, würde mich aber wundern wenn man lange auf sequentielle IOs warten müsste. Ausgenommen natürlich man liest schneller als der Datenträger liefern kann.
    (BTW: Der Windows Cache-Manager macht auch Read-Ahead Caching wenn man es ihm nicht extra sagt. FILE_FLAG_SEQUENTIAL_SCAN führt nur dazu dass nicht nach "komplizierteren" Patterns wie z.B. Rückwärtslesen gesucht wird.)



  • Den restlichen Code zu verändern wird schwierig, dabei handelt es sich vor allem um Cern Root Routinen die am Ende ein TTree in einem TFile speichern.


Log in to reply