Boost Spirit QI langsam

Question

Ich versuche, TPCH-Dateien mit Boost Spirit QI zu analysieren. Meine Implementierung inspiriert durch das Mitarbeiterbeispiel von Spirit QI (http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp). Die Daten sind im CSV-Format und die Token sind durch ein '|' Charakter.

Es funktioniert, aber es ist sehr langsam (20 Sek. Für 1 GB).

Hier ist mein Qi grammer für die lineitem Datei:

struct lineitem { 
    int l_orderkey; 
    int l_partkey; 
    int l_suppkey; 
    int l_linenumber; 
    std::string l_quantity; 
    std::string l_extendedprice; 
    std::string l_discount; 
    std::string l_tax; 
    std::string l_returnflag; 
    std::string l_linestatus; 
    std::string l_shipdate; 
    std::string l_commitdate; 
    std::string l_recepitdate; 
    std::string l_shipinstruct; 
    std::string l_shipmode; 
    std::string l_comment; 
}; 

BOOST_FUSION_ADAPT_STRUCT(lineitem, 
    (int, l_orderkey) 
    (int, l_partkey) 
    (int, l_suppkey) 
    (int, l_linenumber) 
    (std::string, l_quantity) 
    (std::string, l_extendedprice) 
    (std::string, l_discount) 
    (std::string, l_tax) 
    (std::string, l_returnflag) 
    (std::string, l_linestatus) 
    (std::string, l_shipdate) 
    (std::string, l_commitdate) 
    (std::string, l_recepitdate) 
    (std::string, l_shipinstruct) 
    (std::string, l_shipmode) 
    (std::string, l_comment)) 

vector<lineitem>* lineitems=new vector<lineitem>(); 

phrase_parse(state->dataPointer, 
    state->dataEndPointer, 
    (*(int_ >> "|" >> 
    int_ >> "|" >> 
    int_ >> "|" >> 
    int_ >> "|" >> 
    +(char_ - '|') >> "|" >> 
    +(char_ - '|') >> "|" >> 
    +(char_ - '|') >> "|" >> 
    +(char_ - '|') >> "|" >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' >> 
    +(char_ - '|') >> '|' 
    )), space, *lineitems 
); 

Das Problem scheint der Charakter-Analyse zu sein. Es ist viel langsamer als andere Konvertierungen. Gibt es eine bessere Möglichkeit, variable Länge Tokens in Zeichenfolgen zu analysieren?

Answer 1

ich eine Lösung für mein Problem gefunden. Wie in diesem Beitrag Boost Spirit QI grammar slow for parsing delimited strings beschrieben, ist der Performance-Engpass die String-Handhabung von Spirit Qi. Alle anderen Datentypen scheinen ziemlich schnell zu sein.

Ich vermeide dieses Problem, indem ich die Daten selbst handhabe, anstatt das Spirit Qi Handling zu verwenden.

Meine Lösung verwendet eine Hilfsklasse, die Funktionen für jedes Feld der CSV-Datei bietet. Die Funktionen speichern die Werte in einer Struktur. Zeichenfolgen werden in einem Zeichen [] gespeichert. Wenn der Parser ein Zeilenumbruchzeichen erhält, ruft er eine Funktion auf, die die Struktur zum Ergebnisvektor hinzufügt. Der Boost-Parser ruft diese Funktionen auf, anstatt die Werte allein in einem Vektor zu speichern.

Hier ist mein Code für die region.tbl Datei des TCPH Benchmark:

struct region{ 
    int r_regionkey; 
    char r_name[25]; 
    char r_comment[152]; 
}; 

class regionStorage{ 
public: 
regionStorage(vector<region>* regions) :regions(regions), pos(0) {} 
void storer_regionkey(int const&i){ 
    currentregion.r_regionkey = i; 
} 

void storer_name(char const&i){ 
    currentregion.r_name[pos] = i; 
    pos++; 
} 

void storer_comment(char const&i){ 
    currentregion.r_comment[pos] = i; 
    pos++; 
} 

void resetPos() { 
    pos = 0; 
} 

void endOfLine() { 
    pos = 0; 
    regions->push_back(currentregion); 
} 

private: 
vector<region>* regions; 
region currentregion; 
int pos; 
}; 


void parseRegion(){ 

    vector<region> regions; 
    regionStorage regionstorageObject(&regions); 
    phrase_parse(dataPointer, /*< start iterator >*/  
    state->dataEndPointer, /*< end iterator >*/ 
    (*(lexeme[ 
    +(int_[boost::bind(&regionStorage::storer_regionkey, &regionstorageObject, _1)] - '|') >> '|' >> 
    +(char_[boost::bind(&regionStorage::storer_name, &regionstorageObject, _1)] - '|') >> char_('|')[boost::bind(&regionStorage::resetPos, &regionstorageObject)] >> 
    +(char_[boost::bind(&regionStorage::storer_comment, &regionstorageObject, _1)] - '|') >> char_('|')[boost::bind(&regionStorage::endOfLine, &regionstorageObject)] 
    ])), space); 

    cout << regions.size() << endl; 
} 

Es ist keine schöne Lösung, aber es funktioniert, und es ist viel schneller. (2,2 Sekunden für 1 GB TCPH-Daten, Multithread)

Answer 2

Verwenden Sie -O2 beim Kompilieren?

Boosts-Bibliotheken weisen eine große Redundanz auf, die bei Verwendung von Optimierungsflags entfernt werden.

Eine andere mögliche Lösung ist Repetition Parser Richtlinie verwenden: http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

Answer 3

Das Problem kommt hauptsächlich von einzelnen Elementen char zu std::string Container. Gemäß Ihrer Grammatik beginnt die Zuordnung für jedes std::string Attribut, wenn ein Zeichen erfüllt ist, und stoppt, wenn Sie ein Trennzeichen | finden. Also, zuerst gibt es sizeof(char)+1 reservierte Bytes (Null-terminiert "\ 0"). Der Compiler muss den Allokator von std::string abhängig vom Doubling-Algorithmus der Allokatoren ausführen! Das bedeutet, dass der Speicher für kleine Strings sehr häufig neu zugewiesen werden muss. Dies bedeutet, dass Ihre Zeichenfolge in eine Speicherzuweisung kopiert wird, deren Größe verdoppelt wird und die vorherige Zuweisung in Intervallen von 1,2,4,6,12,24 ... Zeichen freigegeben wird. Kein Wunder, dass es langsam war, dies verursacht große Probleme mit den häufigen malloc-Anrufen; mehr Heap-Fragmentierung, eine größere verknüpfte Liste von freien Speicherblöcken, variable (kleine) Größen von diesen Speicherblöcken, die ihrerseits Probleme verursachen, wenn der Speicher für die Zuordnungen der Anwendung während seiner gesamten Lebensdauer länger gescannt wird. tldr; Die Daten werden fragmentiert und im Speicher weit verstreut.

Nachweis? Der folgende Code wird von der jedes Mal aufgerufen, wenn ein gültiges Zeichen in Ihrem Iterator erfüllt ist. Von Boost 1.54

/boost/spirit/home/qi/char/char_parser.hpp

if (first != last && this->derived().test(*first, context)) 
{ 
    spirit::traits::assign_to(*first, attr_); 
    ++first; 
    return true; 
} 
return false; 

/boost/spirit/home/qi/detail/assign_to.hpp

// T is not a container and not a string 
template <typename T_> 
static void call(T_ const& val, Attribute& attr, mpl::false_, mpl::false_) 
{ 
    traits::push_back(attr, val); 
} 

/boost/Geist/home/support/container.hpp

template <typename Container, typename T, typename Enable/* = void*/> 
struct push_back_container 
{ 
    static bool call(Container& c, T const& val) 
    { 
     c.insert(c.end(), val); 
     return true; 
    } 
}; 

Die Korrektur Follow-up-Code, den Sie geschrieben (das Ändern Ihrer Struktur Name[Size] char) i S ist im Prinzip das Gleiche wie eine Zeichenfolge Name.reserve(Size) Anweisung Anweisung hinzufügen. Dafür gibt es derzeit keine Richtlinie.

Die Lösung:

/boost/spirit/home/support/container.hpp

template <typename Container, typename T, typename Enable/* = void*/> 
struct push_back_container 
{ 
    static bool call(Container& c, T const& val, size_t initial_size = 8) 
    { 
     if (c.capacity() < initial_size) 
      c.reserve(initial_size); 
     c.insert(c.end(), val); 
     return true; 
    } 
}; 

/boost/spirit/home/qi/char/char_parser.hpp

if (first != last && this->derived().test(*first, context)) 
{ 
    spirit::traits::assign_to(*first, attr_); 
    ++first; 
    return true; 
} 
if (traits::is_container<Attribute>::value == true) 
    attr_.shrink_to_fit(); 
return false; 

Ich habe es nicht getestet, aber ich nehme an, es kann Char-Parser über String-Attribute um mehr als 10x beschleunigen, wie Sie gesehen haben. Es wäre eine großartige Optimierungsfunktion in einem Boost Spirit-Update, einschließlich einer reserve(initial_size)[ +(char_ - lit("|")) ] Direktive, die die anfängliche Puffergröße festlegt.