Boost Spirit QI slow

Question

Boost Spirit QIでTPCHファイルを解析しようとしています。 私の実装は、Spirit QIの従業員の例（http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp）に触発されました。 データはcsv形式であり、トークンは '|'で区切られています。キャラクター。

これは動作しますが、非常に遅い（1 GBの場合は20秒）。ここで

は、ラインアイテムのファイルのための私の気の文法である：

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

問題は、文字の解析のようです。それは他のコンバージョンよりもはるかに遅いです。 可変長トークンを文字列に解析するより良い方法はありますか？

Answer 1

私は私の問題への解決策を見つけた：

別の可能な解決策は、繰り返しパーサディレクティブを使用しています。この投稿に記載されているように、Boost Spirit QI grammar slow for parsing delimited strings パフォーマンスのボトルネックは、スピリチュアルの文字列処理です。他のすべてのデータ型はかなり速いようです。

私はSpiritの気を使うのではなく、データを自分で処理することでこの問題を回避します。

私のソリューションは、csvファイルの各フィールドに機能を提供するヘルパークラスを使用しています。関数は、値を構造体に格納します。文字列はchar [] sに格納されます。パーサに、改行文字をヒットし、それを構造体を結果ベクトルに追加する関数を呼び出します。 Boostパーサーは、値を独自のベクトルに格納する代わりに、この関数を呼び出します。ここで

はTCPHベンチマークのregion.tblファイルのための私のコードです：

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

それはかなりのソリューションではありませんが、それは動作し、それがはるかに高速です。 （1 GBのTCPHデータの場合は2.2秒、マルチスレッドの場合）

Answer 2

コンパイル時に-O2を使用していますか？

ブーストライブラリには、最適化フラグの使用時に削除される冗長性が多くあります。 http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

Answer 3

この問題は、主に個別のchar要素をstd::stringコンテナに追加することによって発生します。あなたの文法によると、各std::string属性の場合、割り当てが開始されたときに割り当てが開始され、|セパレータが見つかると停止します。したがって、最初にsizeof(char)+1予約済みバイト（ヌルで終わる "\ 0"）があります。コンパイラは、アロケータ倍増アルゴリズムに応じて、std::stringというアロケータを実行する必要があります。つまり、小さな文字列の場合、メモリを頻繁に再割り当てする必要があります。つまり、文字列がサイズの2倍のメモリ割り当てにコピーされ、1,2,4,6,12,24文字の間隔で前の割り当てが解放されます。それが遅かったのも不思議ではありません。これは頻繁なmalloc呼び出しで大きな問題を引き起こします。より多くのヒープフラグメンテーション、空きメモリブロックのより大きなリンクされたリスト、そのメモリブロックの可変（小さい）サイズは、それが生涯にわたってアプリケーションの割り当てのためのメモリのより長いスキャンで問題を引き起こす。 tldr;データは断片化され、メモリに広く分散されます。

証明はありますか？次のコードは、イテレータで有効な文字が満たされるたびにchar_parserによって呼び出されます。ブースト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); 
} 

/ブースト/精神/ホーム/サポート/ 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; 
    } 
}; 

あなたが投稿補正フォローアップコード（Name[Size]をcharにあなたの構造体を変更すること）は、i基本的には、文字列Name.reserve(Size)のステートメントディレクティブを追加するのと同じです。しかし、現時点ではこれに関する指示はありません。

ソリューション：

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

私はそれをテストしていませんが、あなたが見たように10倍以上の文字列属性に対してcharパーサを高速化できると仮定します。これは、初期バッファーサイズを設定するreserve(initial_size)[ +(char_ - lit("|")) ]指示文を含む、Boost Spirit更新の最適化機能として最適です。