使用 Boost::spirit 编写的解析器的性能问题
Performance issue with parser written with Boost::spirit
我想解析一个如下所示的文件(FASTA-like 文本格式):
>InfoHeader
"Some text sequence that has a line break after every 80 characters"
>InfoHeader
"Some text sequence that has a line break after every 80 characters"
...
例如:
>gi|31563518|ref|NP_852610.1| microtubule-associated proteins 1A/1B light chain 3A isoform b [Homo sapiens]
MKMRFFSSPCGKAAVDPADRCKEVQQIRDQHPSKIPVIIERYKGEKQLPVLDKTKFLVPDHVNMSELVKI
IRRRLQLNPTQAFFLLVNQHSMVSVSTPIADIYEQEKDEDGFLYMVYASQETFGFIRENE
我用 boost::spirit 为此编写了一个解析器。解析器正确地将 header 行和以下文本序列存储在 std::vector< std::pair< string, string >>
中,但对于较大的文件(100MB 的文件需要 17 秒)需要很长时间。作为比较,我编写了一个没有 boost::spirit 的程序(只是 STL 函数),它只是将 100MB 文件的每一行复制到 std::vector
中。整个过程不到一秒钟。用于比较的 "program" 没有达到目的,但我认为解析器不应该花费那么长的时间...
我知道周围还有很多其他 FASTA 解析器,但我很好奇为什么我的代码很慢。
.hpp 文件:
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::vector< std::pair<std::string, std::string> > fastaVector;
private:
fastaVector fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const fastaVector::const_iterator getBeginIterator() const;
const fastaVector::const_iterator getEndIterator() const;
private:
void parse();
};
和 .cpp 文件:
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/phoenix_bind.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_fusion.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/qi.hpp>
#include "fastaReader.hpp"
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
template <typename Iterator, typename Skipper>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::fastaVector(), qi::locals<string>, Skipper> {
qi::rule<Iterator> infoLineStart;
qi::rule<Iterator> inputEnd;
qi::rule<Iterator> lineEnd;
qi::rule<Iterator, string(), Skipper> infoLine;
qi::rule<Iterator, string(), Skipper> seqLine;
qi::rule<Iterator, FastaReader::fastaVector(), qi::locals<string>, Skipper> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta, "fasta") {
using boost::spirit::standard::char_;
using boost::phoenix::bind;
using qi::eoi;
using qi::eol;
using qi::lexeme;
using qi::_1;
using qi::_val;
using namespace qi::labels;
infoLineStart = char_('>');
inputEnd = eoi;
/* grammar */
infoLine = lexeme[*(char_ - eol)];
seqLine = *(char_ - infoLineStart);
fasta = *(infoLineStart > infoLine[_a = _1]
> seqLine[bind(&FastaGrammar::addValue, _val, _a, _1)]
)
> inputEnd
;
infoLineStart.name(">");
infoLine.name("sequence identifier");
seqLine.name("sequence");
}
static void addValue(FastaReader::fastaVector & fa, const string & info, const string & seq) {
fa.push_back(make_pair(info, seq));
}
};
FastaReader::FastaReader(const fs::path & f) {
this->file = f;
this->parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::fastaVector::const_iterator FastaReader::getBeginIterator() const {
return this->fV.cbegin();
}
const FastaReader::fastaVector::const_iterator FastaReader::getEndIterator() const {
return this->fV.cend();
}
void FastaReader::parse() {
if ( this->file.empty() ) throw string("FastaReader: No file specified.");
if ( ! fs::is_regular_file(this->file) ) throw (string("FastaReader: File not found: ") + this->file.string());
typedef boost::spirit::istream_iterator iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type, boost::spirit::ascii::space_type> fastaGr;
fs::ifstream fin(this->file);
if ( ! fin.is_open() ) {
throw (string("FastaReader: Access denied: ") + this->file.string());
}
fin.unsetf(ios::skipws);
iterator_type begin(fin);
iterator_type end;
pos_iterator_type pos_begin(begin, end, this->file.string());
pos_iterator_type pos_end;
fastaGr fG;
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
qi::phrase_parse(pos_begin, pos_end, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::string str) {
cerr << "error message: " << str << endl;
}
}
因此语法执行以下操作:
它查找“>”符号,然后存储所有后续字符,直到检测到 EOL。在 EOL 之后,文本序列开始并在检测到“>”符号时结束。然后通过调用 FastaReader::addValue()
.
将两个字符串(header 行和文本序列)存储在 std::vector 中
我使用带有 -O2 和 -std=c++11 标志的 g++ 版本 4.8.2 编译了我的程序。
那么我的代码中的性能问题在哪里?
下一个:
第 1 步。清理 + 分析
您应该避免他们引入类型擦除的许多规则。
如果你的输入是正常的,你可以不用 skipper(无论如何,行尾很重要,所以跳过它们是没有意义的)。
使用融合适应而不是助手来构建新对:
这还不是最优的,但是干净多了:
$ ./test1
Measuring: Parsing.
00:00:22.681605
通过减少移动部件和间接方式稍微提高效率:
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<std::string, std::string> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
qi::rule<Iterator, FastaReader::Data()> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
fasta = *('>' >> *~char_('\n') >> '\n'
>> *~char_('>'))
>> *eol
>> eoi
;
BOOST_SPIRIT_DEBUG_NODES((fasta));
}
};
FastaReader::FastaReader(const fs::path & f) : file(f) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef boost::spirit::istream_iterator iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
fs::ifstream fin(this->file);
if (!fin) {
throw std::runtime_error(string("FastaReader: Access denied: ") + this->file.string());
}
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{fin >> std::noskipws}, {}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
std::ios::sync_with_stdio(false);
FastaReader reader("input.txt");
//for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
这仍然很慢。让我们看看需要这么长时间:
这很漂亮,但几乎没有告诉我们我们需要知道的东西。然而,这确实如此:前 N 时间消费者是
所以大部分时间花在了 istream 迭代和 multi-pass 适配器上。您可能会争辩说,可以通过偶尔(每一行?)刷新一次来优化多通道适配器,但实际上,我们不希望被绑定到整个流和(流)缓冲区上的运算符。
所以,尽管让我们改用映射文件:
下一个:
上一个:
下一个:
第 2 步。使用 mmap
更快
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<std::string, std::string> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
qi::rule<Iterator, FastaReader::Data()> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
fasta = *('>' >> *~char_('\n') >> '\n'
>> *~char_('>'))
>> *eol
>> eoi
;
BOOST_SPIRIT_DEBUG_NODES((fasta));
}
};
FastaReader::FastaReader(const fs::path & f) : file(f) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
io::mapped_file_source mmap(file.c_str());
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{mmap.data()}, iterator_type{mmap.end()}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
//for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
事实上,在我的系统上它大约快 3 倍(输入为 229 MiB):
$ ./mapped_file_source
Measuring: Parsing.
00:00:07.385787
下一个:
上一个:
下一个:
第 3 步:使用零拷贝加快 MOAR
让我们避免分配!如果我们将文件映射移动到 FastaReader class,我们可以直接指向映射中的数据,而不是一直复制字符串。
使用 boost::string_ref 例如此处描述:C++: Fast way to read mapped file into a matrix 你可以做到
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include <boost/filesystem/path.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
namespace io = boost::iostreams;
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<boost::string_ref, boost::string_ref> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
io::mapped_file_source mmap;
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
namespace boost { namespace spirit { namespace traits {
template <typename It>
struct assign_to_attribute_from_iterators<boost::string_ref, It, void> {
static void call(It f, It l, boost::string_ref& attr) { attr = boost::string_ref { f.base(), size_t(std::distance(f.base(),l.base())) }; }
};
} } }
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
using boost::phoenix::construct;
using boost::phoenix::begin;
using boost::phoenix::size;
entry = ('>' >> raw[ *~char_('\n') ] >> '\n' >> raw[ *~char_('>') ]);
fasta = *entry >> *eol >> eoi ;
BOOST_SPIRIT_DEBUG_NODES((fasta)(entry));
}
private:
qi::rule<Iterator, FastaReader::Data()> fasta;
qi::rule<Iterator, FastaReader::Entry()> entry;
};
FastaReader::FastaReader(const fs::path & f) : file(f), mmap(file.c_str()) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{mmap.data()}, iterator_type{mmap.end()}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
这确实已经快了 4.8 倍:
$ ./test3 | head -n4
Measuring: Parsing.
00:00:04.577123
>gi|31563518|ref|NP_852610.1| microtubule-associated proteins 1A/1B light chain 3A isoform b [Homo sapiens]
MKMRFFSSPCGKAAVDPADRCKEVQQIRDQHPSKIPVIIERYKGEKQLPVLDKTKFLVPDHVNMSELVKI
IRRRLQLNPTQAFFLLVNQHSMVSVSTPIADIYEQEKDEDGFLYMVYASQETFGFIRENE
下一个:
上一个:
Return to
第 4 步:删除位置迭代器
由于您不使用它,我们可以删除有状态迭代器,这可能会抑制很多优化(并且在 the profiler output 中间接可见)
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include <boost/filesystem/path.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
namespace io = boost::iostreams;
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<boost::string_ref, boost::string_ref> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
io::mapped_file_source mmap;
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
namespace boost { namespace spirit { namespace traits {
template <typename It>
struct assign_to_attribute_from_iterators<boost::string_ref, It, void> {
static void call(It f, It l, boost::string_ref& attr) { attr = boost::string_ref { f, size_t(std::distance(f,l)) }; }
};
} } }
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
using boost::phoenix::construct;
using boost::phoenix::begin;
using boost::phoenix::size;
entry = ('>' >> raw[ *~char_('\n') ] >> '\n' >> raw[ *~char_('>') ]);
fasta = *entry >> *eol >> eoi ;
BOOST_SPIRIT_DEBUG_NODES((fasta)(entry));
}
private:
qi::rule<Iterator, FastaReader::Data()> fasta;
qi::rule<Iterator, FastaReader::Entry()> entry;
};
FastaReader::FastaReader(const fs::path & f) : file(f), mmap(file.c_str()) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef FastaGrammar<iterator_type> fastaGr;
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
iterator_type first(mmap.data()), last(mmap.end());
qi::phrase_parse(first, last, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
现在速度 74.8x。
$ time ./test | head -n4
Measuring: Parsing.
00:00:00.194432
我想解析一个如下所示的文件(FASTA-like 文本格式):
>InfoHeader
"Some text sequence that has a line break after every 80 characters"
>InfoHeader
"Some text sequence that has a line break after every 80 characters"
...
例如:
>gi|31563518|ref|NP_852610.1| microtubule-associated proteins 1A/1B light chain 3A isoform b [Homo sapiens]
MKMRFFSSPCGKAAVDPADRCKEVQQIRDQHPSKIPVIIERYKGEKQLPVLDKTKFLVPDHVNMSELVKI
IRRRLQLNPTQAFFLLVNQHSMVSVSTPIADIYEQEKDEDGFLYMVYASQETFGFIRENE
我用 boost::spirit 为此编写了一个解析器。解析器正确地将 header 行和以下文本序列存储在 std::vector< std::pair< string, string >>
中,但对于较大的文件(100MB 的文件需要 17 秒)需要很长时间。作为比较,我编写了一个没有 boost::spirit 的程序(只是 STL 函数),它只是将 100MB 文件的每一行复制到 std::vector
中。整个过程不到一秒钟。用于比较的 "program" 没有达到目的,但我认为解析器不应该花费那么长的时间...
我知道周围还有很多其他 FASTA 解析器,但我很好奇为什么我的代码很慢。
.hpp 文件:
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::vector< std::pair<std::string, std::string> > fastaVector;
private:
fastaVector fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const fastaVector::const_iterator getBeginIterator() const;
const fastaVector::const_iterator getEndIterator() const;
private:
void parse();
};
和 .cpp 文件:
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/phoenix_bind.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_fusion.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/qi.hpp>
#include "fastaReader.hpp"
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
template <typename Iterator, typename Skipper>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::fastaVector(), qi::locals<string>, Skipper> {
qi::rule<Iterator> infoLineStart;
qi::rule<Iterator> inputEnd;
qi::rule<Iterator> lineEnd;
qi::rule<Iterator, string(), Skipper> infoLine;
qi::rule<Iterator, string(), Skipper> seqLine;
qi::rule<Iterator, FastaReader::fastaVector(), qi::locals<string>, Skipper> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta, "fasta") {
using boost::spirit::standard::char_;
using boost::phoenix::bind;
using qi::eoi;
using qi::eol;
using qi::lexeme;
using qi::_1;
using qi::_val;
using namespace qi::labels;
infoLineStart = char_('>');
inputEnd = eoi;
/* grammar */
infoLine = lexeme[*(char_ - eol)];
seqLine = *(char_ - infoLineStart);
fasta = *(infoLineStart > infoLine[_a = _1]
> seqLine[bind(&FastaGrammar::addValue, _val, _a, _1)]
)
> inputEnd
;
infoLineStart.name(">");
infoLine.name("sequence identifier");
seqLine.name("sequence");
}
static void addValue(FastaReader::fastaVector & fa, const string & info, const string & seq) {
fa.push_back(make_pair(info, seq));
}
};
FastaReader::FastaReader(const fs::path & f) {
this->file = f;
this->parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::fastaVector::const_iterator FastaReader::getBeginIterator() const {
return this->fV.cbegin();
}
const FastaReader::fastaVector::const_iterator FastaReader::getEndIterator() const {
return this->fV.cend();
}
void FastaReader::parse() {
if ( this->file.empty() ) throw string("FastaReader: No file specified.");
if ( ! fs::is_regular_file(this->file) ) throw (string("FastaReader: File not found: ") + this->file.string());
typedef boost::spirit::istream_iterator iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type, boost::spirit::ascii::space_type> fastaGr;
fs::ifstream fin(this->file);
if ( ! fin.is_open() ) {
throw (string("FastaReader: Access denied: ") + this->file.string());
}
fin.unsetf(ios::skipws);
iterator_type begin(fin);
iterator_type end;
pos_iterator_type pos_begin(begin, end, this->file.string());
pos_iterator_type pos_end;
fastaGr fG;
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
qi::phrase_parse(pos_begin, pos_end, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::string str) {
cerr << "error message: " << str << endl;
}
}
因此语法执行以下操作:
它查找“>”符号,然后存储所有后续字符,直到检测到 EOL。在 EOL 之后,文本序列开始并在检测到“>”符号时结束。然后通过调用 FastaReader::addValue()
.
我使用带有 -O2 和 -std=c++11 标志的 g++ 版本 4.8.2 编译了我的程序。
那么我的代码中的性能问题在哪里?
下一个:
第 1 步。清理 + 分析
您应该避免他们引入类型擦除的许多规则。
如果你的输入是正常的,你可以不用 skipper(无论如何,行尾很重要,所以跳过它们是没有意义的)。
使用融合适应而不是助手来构建新对:
这还不是最优的,但是干净多了:
$ ./test1
Measuring: Parsing.
00:00:22.681605
通过减少移动部件和间接方式稍微提高效率:
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<std::string, std::string> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
qi::rule<Iterator, FastaReader::Data()> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
fasta = *('>' >> *~char_('\n') >> '\n'
>> *~char_('>'))
>> *eol
>> eoi
;
BOOST_SPIRIT_DEBUG_NODES((fasta));
}
};
FastaReader::FastaReader(const fs::path & f) : file(f) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef boost::spirit::istream_iterator iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
fs::ifstream fin(this->file);
if (!fin) {
throw std::runtime_error(string("FastaReader: Access denied: ") + this->file.string());
}
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{fin >> std::noskipws}, {}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
std::ios::sync_with_stdio(false);
FastaReader reader("input.txt");
//for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
这仍然很慢。让我们看看需要这么长时间:
这很漂亮,但几乎没有告诉我们我们需要知道的东西。然而,这确实如此:前 N 时间消费者是
所以大部分时间花在了 istream 迭代和 multi-pass 适配器上。您可能会争辩说,可以通过偶尔(每一行?)刷新一次来优化多通道适配器,但实际上,我们不希望被绑定到整个流和(流)缓冲区上的运算符。
所以,尽管让我们改用映射文件:
下一个:
上一个:
下一个:
第 2 步。使用 mmap
更快
#include <boost/filesystem/path.hpp>
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<std::string, std::string> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
qi::rule<Iterator, FastaReader::Data()> fasta;
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
fasta = *('>' >> *~char_('\n') >> '\n'
>> *~char_('>'))
>> *eol
>> eoi
;
BOOST_SPIRIT_DEBUG_NODES((fasta));
}
};
FastaReader::FastaReader(const fs::path & f) : file(f) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
io::mapped_file_source mmap(file.c_str());
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{mmap.data()}, iterator_type{mmap.end()}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
//for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
事实上,在我的系统上它大约快 3 倍(输入为 229 MiB):
$ ./mapped_file_source
Measuring: Parsing.
00:00:07.385787
下一个:
上一个:
下一个:
第 3 步:使用零拷贝加快 MOAR
让我们避免分配!如果我们将文件映射移动到 FastaReader class,我们可以直接指向映射中的数据,而不是一直复制字符串。
使用 boost::string_ref 例如此处描述:C++: Fast way to read mapped file into a matrix 你可以做到
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include <boost/filesystem/path.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
namespace io = boost::iostreams;
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<boost::string_ref, boost::string_ref> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
io::mapped_file_source mmap;
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/classic_position_iterator.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
namespace boost { namespace spirit { namespace traits {
template <typename It>
struct assign_to_attribute_from_iterators<boost::string_ref, It, void> {
static void call(It f, It l, boost::string_ref& attr) { attr = boost::string_ref { f.base(), size_t(std::distance(f.base(),l.base())) }; }
};
} } }
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
using boost::phoenix::construct;
using boost::phoenix::begin;
using boost::phoenix::size;
entry = ('>' >> raw[ *~char_('\n') ] >> '\n' >> raw[ *~char_('>') ]);
fasta = *entry >> *eol >> eoi ;
BOOST_SPIRIT_DEBUG_NODES((fasta)(entry));
}
private:
qi::rule<Iterator, FastaReader::Data()> fasta;
qi::rule<Iterator, FastaReader::Entry()> entry;
};
FastaReader::FastaReader(const fs::path & f) : file(f), mmap(file.c_str()) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef boost::spirit::classic::position_iterator2<iterator_type> pos_iterator_type;
typedef FastaGrammar<pos_iterator_type> fastaGr;
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
pos_iterator_type first(iterator_type{mmap.data()}, iterator_type{mmap.end()}, file.string());
qi::phrase_parse<pos_iterator_type>(first, {}, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
这确实已经快了 4.8 倍:
$ ./test3 | head -n4
Measuring: Parsing.
00:00:04.577123
>gi|31563518|ref|NP_852610.1| microtubule-associated proteins 1A/1B light chain 3A isoform b [Homo sapiens]
MKMRFFSSPCGKAAVDPADRCKEVQQIRDQHPSKIPVIIERYKGEKQLPVLDKTKFLVPDHVNMSELVKI
IRRRLQLNPTQAFFLLVNQHSMVSVSTPIADIYEQEKDEDGFLYMVYASQETFGFIRENE
下一个:
上一个:
Return to
第 4 步:删除位置迭代器
由于您不使用它,我们可以删除有状态迭代器,这可能会抑制很多优化(并且在 the profiler output 中间接可见)
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include <boost/filesystem/path.hpp>
#include <boost/utility/string_ref.hpp>
#include <boost/iostreams/device/mapped_file.hpp>
namespace io = boost::iostreams;
namespace fs = boost::filesystem;
class FastaReader {
public:
typedef std::pair<boost::string_ref, boost::string_ref> Entry;
typedef std::vector<Entry> Data;
private:
Data fV;
fs::path file;
public:
FastaReader(const fs::path & f);
~FastaReader();
const fs::path & getFile() const;
const Data::const_iterator begin() const;
const Data::const_iterator end() const;
private:
io::mapped_file_source mmap;
void parse();
};
#include <iomanip>
#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/filesystem/fstream.hpp>
#include <boost/filesystem/operations.hpp>
#include <boost/filesystem/path.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/fusion/adapted/std_pair.hpp>
//#include "fastaReader.hpp"
#include <boost/iostreams/device/mapped_file.hpp>
using namespace std;
namespace fs = boost::filesystem;
namespace qi = boost::spirit::qi;
namespace pt = boost::posix_time;
namespace io = boost::iostreams;
namespace boost { namespace spirit { namespace traits {
template <typename It>
struct assign_to_attribute_from_iterators<boost::string_ref, It, void> {
static void call(It f, It l, boost::string_ref& attr) { attr = boost::string_ref { f, size_t(std::distance(f,l)) }; }
};
} } }
template <typename Iterator>
struct FastaGrammar : qi::grammar<Iterator, FastaReader::Data()> {
FastaGrammar() : FastaGrammar::base_type(fasta) {
using namespace qi;
using boost::phoenix::construct;
using boost::phoenix::begin;
using boost::phoenix::size;
entry = ('>' >> raw[ *~char_('\n') ] >> '\n' >> raw[ *~char_('>') ]);
fasta = *entry >> *eol >> eoi ;
BOOST_SPIRIT_DEBUG_NODES((fasta)(entry));
}
private:
qi::rule<Iterator, FastaReader::Data()> fasta;
qi::rule<Iterator, FastaReader::Entry()> entry;
};
FastaReader::FastaReader(const fs::path & f) : file(f), mmap(file.c_str()) {
parse();
}
FastaReader::~FastaReader() {}
const fs::path & FastaReader::getFile() const {
return this->file;
}
const FastaReader::Data::const_iterator FastaReader::begin() const {
return this->fV.cbegin();
}
const FastaReader::Data::const_iterator FastaReader::end() const {
return this->fV.cend();
}
void FastaReader::parse() {
if (this->file.empty()) throw std::runtime_error("FastaReader: No file specified.");
if (! fs::is_regular_file(this->file)) throw std::runtime_error(string("FastaReader: File not found: ") + this->file.string());
typedef char const* iterator_type;
typedef FastaGrammar<iterator_type> fastaGr;
static const fastaGr fG{};
try {
std::cerr << "Measuring: Parsing." << std::endl;
const pt::ptime startMeasurement = pt::microsec_clock::universal_time();
iterator_type first(mmap.data()), last(mmap.end());
qi::phrase_parse(first, last, fG, boost::spirit::ascii::space, this->fV);
const pt::ptime endMeasurement = pt::microsec_clock::universal_time();
pt::time_duration duration (endMeasurement - startMeasurement);
std::cerr << duration << std::endl;
} catch (std::exception const& e) {
cerr << "error message: " << e.what() << endl;
}
}
int main() {
FastaReader reader("input.txt");
for (auto& e : reader) std::cout << '>' << e.first << '\n' << e.second << "\n\n";
}
现在速度 74.8x。
$ time ./test | head -n4
Measuring: Parsing.
00:00:00.194432