Boost Spirit QI 慢

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

问题似乎出在字符解析上。它比其他转换方式慢得多。 有没有更好的方法将可变长度的标记解析成字符串？

- Rseilbeck

---

我曾经也遇到过同样的问题。似乎灵气不能有效地处理可变长度的字符串。有人有解决方案吗？ - muehlbau

Answer 1

我找到了解决方法。正如在这篇文章Boost Spirit QI grammar slow for parsing delimited strings中所描述的那样，性能瓶颈是Spirit qi的字符串处理。所有其他数据类型似乎都很快。

我通过自己处理数据而避免了这个问题，而不是使用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;
}

这并不是一个美观的解决方案，但它能够工作，而且速度更快。（1GB TCPH数据，多线程，只需2.2秒）

- Rseilbeck

Answer 2

主要问题来自于将单个char元素附加到std::string容器中。根据您的语法，对于每个std::string属性，当遇到字符时开始分配，当找到|分隔符时停止分配。因此，一开始有sizeof(char)+1个保留字节（以空字符"\0"结尾）。编译器将根据分配器的加倍算法运行std::string的分配器！这意味着对于小字符串，内存必须经常重新分配。这意味着您的字符串被复制到一个大小为其两倍的内存分配中，并且先前的分配被释放，在1、2、4、6、12、24...个字符的间隔中进行。难怪它很慢，这会导致频繁的malloc调用，更多的堆碎片化，更大的空闲内存块链表，这些内存块的变量（小）大小在应用程序的整个生命周期内会导致长时间的内存扫描的问题。简而言之，数据在内存中变得分散和广泛分布。

证明？以下代码由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);
}

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

你发表的更正后续代码（将您的结构体更改为字符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("|") ) ]指令来设置初始缓冲区大小。

- etcimon

Answer 3

你在编译时使用了 -O2 吗？

当使用优化标志时，Boost库中有很多冗余内容会被删除。

另一个可能的解决方案是使用重复解析器指令： http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

- MasterID