c++ - 気力のブーストを遅くする

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 秒)。

lineitem ファイルの qi グラマーは次のとおりです。

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

問題は文字解析にあるようです。他の変換よりもはるかに遅いです。可変長トークンを文字列に解析するより良い方法はありますか?

score 5 · Accepted Answer

私は自分の問題の解決策を見つけました。この投稿で説明されているように、Boost Spirit QI文法は、区切られた文字列を解析するのに時間がかかります。パフォーマンスのボトルネックは、Spiritqiの文字列処理です。他のすべてのデータ型は非常に高速のようです。

私は、Spirit qi処理を使用する代わりに、自分でデータの処理を行うことで、この問題を回避しています。

私のソリューションでは、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秒、マルチスレッド）

score 4 · Accepted Answer

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

証拠？次のコードはchar_parser、Iterator で有効な文字が検出されるたびに呼び出されます。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/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)
    {
        c.insert(c.end(), val);
        return true;
    }
};

あなたが投稿した修正フォローアップコード（構造体を char に変更する）は、基本的に文字列ステートメントディレクティブName[Size]を追加するのと同じです。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;

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

score 0 · Accepted Answer

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

ブーストライブラリには多くの冗長性があり、最適化フラグを使用すると削除されます。

別の可能な解決策は、繰り返しパーサーディレクティブを使用することです: http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

c++ - 気力のブーストを遅くする

3 に答える 3

Related

Reference