Boost Spirit QI slow

Question

Provo ad analizzare i file TPCH con Boost Spirit QI. La mia implementazione è stata ispirata dall'esempio impiegato di Spirit QI (http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp). I dati sono in formato csv ei token sono delimitati da un '|' carattere.

Funziona ma è molto lento (20 secondi per 1 GB).

Qui è la mia grammatica qi per il file LineItem:

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 
); 

Il problema sembra essere il parsing dei caratteri. È molto più lento di altre conversioni. Esiste un modo migliore per analizzare i token di lunghezza variabile nelle stringhe?

Answer 1

ho trovato una soluzione al mio problema. Come descritto in questo post Boost Spirit QI grammar slow for parsing delimited strings il collo di bottiglia delle prestazioni è la gestione delle stringhe di Spirit qi. Tutti gli altri tipi di dati sembrano essere abbastanza veloci.

Evito questo problema effettuando la gestione dei dati da solo invece di utilizzare la gestione dello spirito qi.

La mia soluzione utilizza una classe di supporto che offre funzioni per ogni campo del file csv. Le funzioni memorizzano i valori in una struttura. Le stringhe sono memorizzate in un carattere [] s. Colpisce il parser di un carattere di nuova riga, chiama una funzione che aggiunge la struttura al vettore risultato. Il parser Boost chiama queste funzioni invece di memorizzare i valori in un vettore da solo.

Ecco il mio codice per il file region.tbl del Benchmark TCPH:

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; 
} 

Non è una bella soluzione, ma funziona ed è molto più veloce. (2,2 secondi per 1 GB di dati TCPH, multithreading)

Answer 2

Si sta utilizzando -O2 durante la compilazione?

Le librerie di boost hanno molta ridondanza che viene rimossa quando si usano i flag di ottimizzazione.

Un'altra possibile soluzione è utilizzare la direttiva Parser Ripetizione: http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

Answer 3

Il problema deriva principalmente dall'aggiunta di singoli elementi char al contenitore std::string. In base alla grammatica, per ogni attributo std::string l'allocazione inizia quando viene raggiunto un char e si arresta quando si trova un separatore |. Quindi, all'inizio ci sono i byte riservati sizeof(char)+1 (null-terminated "\ 0"). Il compilatore dovrà eseguire l'allocatore di std::string a seconda dell'algoritmo di raddoppiamento degli allocatori! Ciò significa che la memoria deve essere riassegnata molto frequentemente per stringhe di piccole dimensioni. Ciò significa che la stringa viene copiata in una allocazione di memoria doppia della sua dimensione e l'allocazione precedente viene liberata, ad intervalli di 1,2,4,6,12,24 ... caratteri. Non c'è da stupirsi che sia stato lento, questo causa enormi problemi con le frequenti chiamate di malloc; più frammentazione dell'heap, una più grande lista collegata di blocchi di memoria liberi, dimensioni variabili (piccole) di quei blocchi di memoria che a sua volta causano problemi con una scansione più lunga della memoria per le allocazioni dell'applicazione durante l'intera vita. TLDR; i dati diventano frammentati e ampiamente dispersi nella memoria.

Prova? Il codice seguente viene chiamato dallo char_parser ogni volta che un carattere valido viene soddisfatto in Iterator. Da 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/spirito/home/supporto/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; 
    } 
}; 

Il codice di follow-up di correzione hai postato (cambiare la struct a char Name[Size]) i In pratica è come aggiungere una direttiva di istruzioni Name.reserve(Size). Tuttavia, al momento non esiste una direttiva per questo.

La soluzione:

/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; 

Non l'ho provato ma presumo che possa velocizzare i parser di carbone sugli attributi di stringa di oltre 10x come hai visto. Sarebbe un'ottima funzionalità di ottimizzazione in un aggiornamento Boost Spirit, inclusa una direttiva reserve(initial_size)[ +(char_ - lit("|")) ] che imposta la dimensione del buffer iniziale.