Tăng cường tinh thần QI chậm

Question

Tôi cố gắng phân tích các tệp TPCH bằng Boost Spirit QI. Thực hiện của tôi lấy cảm hứng từ ví dụ của nhân viên về Thần Khí QI (http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp). Dữ liệu ở định dạng csv và mã thông báo được phân cách bằng dấu '|' tính cách.

Nó hoạt động nhưng rất chậm (20 giây cho 1 GB).

Đây là ngữ pháp khí của tôi cho các tập tin chi tiết đơn hàng:

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

Vấn đề có vẻ là phân tích nhân vật. Nó chậm hơn nhiều so với các chuyển đổi khác. Có cách nào tốt hơn để phân tích mã thông báo có độ dài biến thành chuỗi không?

Answer 1

Tôi tìm thấy một giải pháp cho vấn đề của tôi. Như được mô tả trong bài đăng này Boost Spirit QI grammar slow for parsing delimited strings nút cổ chai hiệu suất là chuỗi xử lý Spirit qi. Tất cả các loại dữ liệu khác có vẻ khá nhanh.

Tôi tránh vấn đề này thông qua việc tự xử lý dữ liệu thay vì sử dụng xử lý Spirit qi.

Giải pháp của tôi sử dụng lớp trợ giúp cung cấp các chức năng cho mọi trường của tệp csv. Các hàm lưu trữ các giá trị vào một cấu trúc. Các chuỗi được lưu trữ trong một char [] s. Số lần truy cập trình phân tích cú pháp một ký tự dòng mới, nó gọi một hàm bổ sung cấu trúc cho vectơ kết quả. Trình phân tích cú pháp Boost gọi các hàm này thay vì lưu trữ các giá trị vào một vectơ riêng của nó.

Đây là mã của tôi cho các tập tin region.tbl của Benchmark TCPH:

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

Nó không phải là một giải pháp khá nhưng nó hoạt động và nó là nhanh hơn nhiều. (2,2 giây cho dữ liệu TCPH 1 GB, đa luồng)

Answer 2

Bạn đang sử dụng -O2 khi biên dịch?

Tăng thư viện có nhiều dự phòng bị xóa khi sử dụng cờ tối ưu hóa.

Một giải pháp khả thi là sử dụng lặp lại Parser Chỉ thị: http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html

Answer 3

Vấn đề chủ yếu xuất phát từ việc thêm từng thành phần char vào std::string vùng chứa. Theo ngữ pháp của bạn, đối với mỗi thuộc tính std::string phân bổ bắt đầu khi một char được đáp ứng và dừng lại khi bạn tìm thấy dấu cách |. Vì vậy, lúc đầu có sizeof(char)+1 byte được đặt trước (null-terminated "\ 0"). Trình biên dịch sẽ phải chạy trình phân bổ của std::string tùy thuộc vào thuật toán nhân đôi phân bổ! Điều đó có nghĩa là bộ nhớ phải được cấp lại rất thường xuyên cho các chuỗi nhỏ. Điều này có nghĩa là chuỗi của bạn được sao chép vào cấp phát bộ nhớ gấp đôi kích thước của nó và phân bổ trước đó được giải phóng, với khoảng thời gian là 1,2,4,6,12,24 ... ký tự. Không có thắc mắc nó đã được làm chậm, điều này gây ra vấn đề lớn với các cuộc gọi malloc thường xuyên; phân mảnh heap nhiều hơn, một danh sách liên kết lớn hơn của các khối bộ nhớ miễn phí, các kích thước biến (nhỏ) của các khối bộ nhớ đó đến lượt nó gây ra các vấn đề với việc quét bộ nhớ lâu hơn cho phân bổ của ứng dụng trong suốt toàn bộ vòng đời của nó. tldr; dữ liệu bị phân mảnh và phân tán rộng rãi trong bộ nhớ.

Bằng chứng? Mã sau đây được gọi là char_parser mỗi lần một ký tự hợp lệ được đáp ứng trong Iterator của bạn. Từ Tăng 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); 
} 

/tăng/tinh thần/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; 
    } 
}; 

Mã theo dõi sửa đổi bạn đã đăng (thay đổi cấu trúc thành char Name[Size]) i về cơ bản giống như thêm một chuỗi chỉ thị câu lệnh Name.reserve(Size). Tuy nhiên, hiện tại không có chỉ thị nào cho điều này.

Giải pháp:

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

Tôi chưa thử nghiệm nhưng tôi cho rằng nó có thể tăng tốc các trình phân tích cú pháp char trên các thuộc tính chuỗi bằng hơn 10 lần như bạn đã thấy. Nó sẽ là một tính năng tối ưu hóa tuyệt vời trong bản cập nhật Boost Spirit, bao gồm chỉ thị reserve(initial_size)[ +(char_ - lit("|")) ] đặt kích thước bộ đệm ban đầu.