부스트 스피릿 QI 느림

Question

부스트 스피릿 QI로 TPCH 파일을 구문 분석하려고합니다. 내 구현은 Spirit QI (http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp)의 직원 예제에서 영감을 받았습니다. 데이터는 CSV 형식이며 토큰은 '|'로 구분됩니다. 캐릭터.

매우 느립니다 (1GB의 경우 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의 문자열 처리입니다. 다른 모든 데이터 유형은 매우 빠릅니다.

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 초, 다중 스레드)

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 특성에 대해 char이 충족 될 때 할당이 시작되고 | 구분 기호가 발견되면 할당이 중지됩니다. 따라서 처음에는 sizeof(char)+1 예약 된 바이트 (널 종료 "\ 0")가 있습니다. 컴파일러는 할당 자 배증 알고리즘에 따라 std::string의 할당자를 실행해야합니다! 즉, 작은 문자열의 경우 메모리를 자주 다시 할당해야합니다. 즉, 문자열이 1,2 배 크기의 메모리 할당에 복사되고 이전 할당은 1,2,4,6,12,24 ... 문자 간격으로 해제됩니다. 느린 것은 당연한 일이며, 이것은 malloc 호출이 빈번하게 발생하는 큰 문제를 일으 킵니다. 더 많은 힙 조각화, 사용 가능한 메모리 블록의 더 큰 링크 된 목록, 그 메모리 블록의 가변 (작은) 크기로 인해 수명주기 동안 응용 프로그램의 할당에 대한 메모리 검색 시간이 길어지는 문제가 발생합니다. tldr; 데이터가 단편화되어 메모리에 널리 분산됩니다.

증명? 다음 코드는 Iterator에서 유효한 문자가 만날 때마다 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); 
} 

/부스트/정신/홈/지원/당신이 게시 보정 후속 코드 (Name[Size]를 숯불하기 위해 구조체를 변경)

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

container.hpp 전 기본적으로 문자열 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 배 이상 큰 문자 분석기를 사용할 수 있다고 가정합니다. 이것은 초기 버퍼 크기를 설정하는 reserve(initial_size)[ +(char_ - lit("|")) ] 지시문을 포함하여 부스트 스피리트 업데이트의 훌륭한 최적화 기능입니다.