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 qi的字符串處理。所有其他數據類型似乎相當快。

我通過自己處理數據而不是使用靈氣處理來避免這個問題。

我的解決方案使用幫助類，它爲csv文件的每個字段提供函數。這些函數將這些值存儲到一個結構中。字符串存儲在char []中。命中解析器一個換行符，它調用一個函數，將結構添加到結果向量中。 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？

Boosts庫有很多冗餘，使用優化標誌時會被刪除。

另一種可能的解決方案是使用重複解析器指令： 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保留字節（以null結尾的「\ 0」）。編譯器將不得不根據分配器加倍算法運行std::string的分配器！這意味着內存必須經常爲小字符串重新分配。這意味着你的字符串被複制到一個內存分配的兩倍，並且以1,2,4,6,12,24 ...字符的間隔釋放先前的分配。難怪它很慢，這導致了頻繁的malloc調用的巨大問題;更多的堆碎片，更大的空閒內存塊鏈接列表，以及那些內存塊的可變（小）尺寸，這些內存塊在其整個生命週期中會導致應用程序分配的內存更長的掃描時間。 tldr;數據變得分散並且廣泛分散在內存中。

證明？每次在迭代器中滿足有效字符時，以下代碼將由char_parser調用。來自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); 
} 

/升壓/精神/主頁/支持/ 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; 

我還沒有測試過它，但我認爲它可以加速字符串屬性超過10倍的字符分析器，就像你看到的。這將是Boost Spirit更新中的一個很好的優化功能，包括設置初始緩衝區大小的reserve(initial_size)[ +(char_ - lit("|")) ]指令。