Boost Spirit QI медленный
Я пытаюсь проанализировать файлы TPCH с помощью Boost Spirit QI.
Моя реализация вдохновлена примером сотрудника Spirit QI ( http://www.boost.org/doc/libs/1_52_0/libs/spirit/example/qi/employee.cpp ).
Данные представлены в формате csv, а токены разделены знаком ‘|’ персонаж.
Работает, но очень медленно (20 с на 1 ГБ).
Вот моя грамматика ци для файла lineitem:
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
);
Проблема, кажется, в разборе символов. Это намного медленнее, чем другие преобразования.
Есть ли лучший способ разобрать токены переменной длины в строки?
Решение
Я нашел решение своей проблемы. Как описано в этом посте Boost Spirit QI грамматика медленная для анализа строк с разделителями
узким местом в производительности является обработка строк Spirit qi. Все остальные типы данных выглядят довольно быстро.
Я избегаю этой проблемы, выполняя обработку данных самостоятельно, а не используя обработку Spirit qi.
Мое решение использует вспомогательный класс, который предлагает функции для каждого поля файла CSV. Функции хранят значения в структуре. Строки хранятся в символе []. Поражает синтаксический анализатор символом новой строки, он вызывает функцию, которая добавляет структуру к результирующему вектору.
Парсер Boost вызывает эту функцию вместо того, чтобы сохранять значения в векторе самостоятельно.
Вот мой код для файла region.tbl теста 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(®ions);
phrase_parse(dataPointer, /*< start iterator >*/
state->dataEndPointer, /*< end iterator >*/
(*(lexeme[
+(int_[boost::bind(®ionStorage::storer_regionkey, ®ionstorageObject, _1)] - '|') >> '|' >>
+(char_[boost::bind(®ionStorage::storer_name, ®ionstorageObject, _1)] - '|') >> char_('|')[boost::bind(®ionStorage::resetPos, ®ionstorageObject)] >>
+(char_[boost::bind(®ionStorage::storer_comment, ®ionstorageObject, _1)] - '|') >> char_('|')[boost::bind(®ionStorage::endOfLine, ®ionstorageObject)]
])), space);
cout << regions.size() << endl;
}
Это не очень хорошее решение, но оно работает и работает намного быстрее. (2,2 секунды для 1 ГБ данных TCPH, многопоточные)
Другие решения
Проблема в основном исходит от добавления человека char элементы к std::string контейнер. Согласно вашей грамматике, для каждого std::string Атрибут распределения начинается, когда встречается символ и заканчивается, когда вы найдете | разделитель. Итак, сначала есть sizeof(char)+1 зарезервированные байты (заканчивающиеся нулем «\ 0»). Компилятор должен будет запустить распределитель std::string в зависимости от алгоритма удвоения распределителей! Это означает, что память должна перераспределяться очень часто для маленьких строк. Это означает, что ваша строка копируется в выделенную память, удвоенную по размеру, а предыдущее выделение освобождается с интервалами в 1,2,4,6,12,24 … символов. Не удивительно, что это было медленно, это вызывает огромные проблемы с частыми вызовами malloc; большая фрагментация кучи, больший связанный список свободных блоков памяти, переменные (малые) размеры этих блоков памяти, что, в свою очередь, вызывает проблемы с более длительным сканированием памяти для выделения приложения в течение всего срока его службы. tldr; данные становятся фрагментированными и широко рассредоточенными в памяти.
Доказательство? Следующий код вызывается 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);
}
/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;
Я не проверял это, но я предполагаю, что это может ускорить анализаторы символов по строковым атрибутам более чем в 10 раз, как вы видели. Это было бы отличной функцией оптимизации в обновлении Boost Spirit, включая reserve(initial_size)[ +( char_ - lit("|") ) ] директива, которая устанавливает начальный размер буфера.
Вы используете -O2 при компиляции?
У библиотек Boots много избыточности, которые удаляются при использовании флагов оптимизации.
Другое возможное решение — использовать директиву Repetition Parser:
http://www.boost.org/doc/libs/1_52_0/libs/spirit/doc/html/spirit/qi/reference/directive/repeat.html
detector