如何对Boost Spirit Parser进行基准测试？

Question

我正在开发一个编译器，希望提高其性能。我发现约50％的时间用于解析源文件。由于源文件非常小，而且在此之后我进行了许多转换，所以我认为它是可以改进的。

我的解析器是使用Boost Spirit解析器和词法分析器（使用lexer :: pos_iterator）构建的，并且我有一个中等规模的语法。我将源代码解析成AST。

我的问题是，我不知道在解析过程中哪部分耗时最长：AST节点的复制，词法分析器，解析器规则还是内存。

我不认为这是I/O问题，因为我正在使用SSD工作，而且一开始就完全读取文件，然后只使用内存版本。

我尝试使用分析器，但需要花费时间的方法是来自Boost的一些具有数百个字符名称的方法，我不确定它们确切的作用...

那么，有没有首选方法来基准测试Boost Spirit解析器及其语法？ 或者是否有一些规则可用于验证某些特定点的效率？

谢谢

对于有兴趣的人，以下是源代码：

• 解析器
• 语法 语法 语法
• 词法分析器

- Baptiste Wicht

---

这里是ApochiQ写的一篇文章，他使用Boost.Spirit作为Epoch语言的解析器。在第10版和第11版之间，他大大提高了解析器的性能，并记录下了他所关注的内容[此处]（http://code.google.com/p/scribblings-by-apoch/wiki/OptimizingBoostSpirit）。 - Matthieu M.

@MatthieuM。是的，我知道这篇文章。很久以前我已经遵循了这篇优秀文章中的几条建议。但我不知道接下来该遵循哪些建议。 - Baptiste Wicht

你介意分享被测试的代码吗？我自己很感兴趣。 - sehe

你在代码上运行过分析器吗？ - Mats Petersson

是的@MatsPetersson，正如我在问题中所说的，我对代码进行了分析。问题在于作为热点的函数名称有数百个字符长，而我不知道它们确切的作用...这并不能给我足够的信息...对于not-sehe，我已经添加了源代码链接，但它相当大。 - Baptiste Wicht

Answer 1

我已经快速浏览了一下。

我的分析器很快告诉我，构建语法和（特别是）词法分析器对象需要相当多的资源。

实际上，在SpiritParser.cpp中仅更改一行就¹节省了40%的执行时间（从约28秒降至约17秒）：

    lexer::Lexer lexer;

进入

    static const lexer::Lexer lexer;

现在，

• 使语法静态化需要使其无状态。我通过以下方式实现：

  • 将 position_begin 移动到 qi::_a 中（使用 qi::locals），并且

  • 在适当的时候将其作为继承属性传递。

    • 例如，在 EDDIGrammar 和 ValueGrammar 语法中进行传递。

      start %= qi::eps [ qi::_a = qi::_r1 ] >> program;
      

    • 还有从ValueGrammar中被外部使用的个别规则。

  这会带来许多次优的副作用：

  • 由于lexer::pos_iterator_type没有默认输出流重载，因此规则调试已被注释掉。

  • 使用了非常复杂的替代方式来 '伪造' qi::position(position_begin) 表达式：

  auto local_pos = qi::lazy (
          boost::phoenix::construct<qi::position>(qi::_a)
      );
  

  看起来不是很理想。（理想情况下，人们希望用一个修改过的自定义解析器指令来代替qi::position，该指令知道如何从 qi::locals (?) 中获取 begin_position，这样就无需懒惰地调用解析器表达式了。）

  不管怎样，实现这些进一步的改变² 进一步缩短了大约15%的执行时间：

  static const lexer::Lexer lexer;
  static const parser::EddiGrammar grammar(lexer); 
  
  try {
      bool r = spirit::lex::tokenize_and_parse(
              position_begin, position_end,
              lexer, 
              grammar(boost::phoenix::cref(position_begin)),
              program);
  

  松散的想法：

  • 您考虑过生成静态词法分析器（生成静态分析器）吗？
  • 您考虑过使用期望点以潜在地减少回溯量吗（注意：我没有在那个领域测量任何东西）？
  • 您考虑过 Position::file 和 Position::theLine 的替代方案吗？复制字符串似乎比必要的更重。我更喜欢存储const char *。您还可以查看Boost Flyweight。
  • 在qi :: position指令中是否真的需要pre-skip？
  • （有些不太严肃的：您考虑过迁移到Spirit X3吗？它似乎承诺以move semantics的形式带来潜在的好处。）

  希望这可以帮助您。

  ---

  ^[1]在解析test/cases/*.eddi中的所有测试用例100次时，像这样（见Github）：

  for (int i=0; i<100; i++)
      for (auto& fname : argv)
  {
      eddic::ast::SourceFile program;
      std::cout << fname << ": " << std::boolalpha << parser.parse(fname, program, nullptr) << "\n";
  }
  

  随着一个简单的时间设定

  time ./test ../../test/cases/*.eddi | md5sum
  

  通过md5sum进行一致性检查。

  ^[2]我在这里创建了一个概念验证重构的pull请求：https://github.com/wichtounet/eddic/pull/52

- sehe

---

你这就叫快速扫描？非常感谢，这是个好答案。我今晚会尝试你的补丁。关于你提到的一些想法：我会尝试使用静态词法分析器（之前我不知道），我也不知道期望点可以减少回溯，我会试试的；对于位置信息，我会避免存储std::string，因为它确实很重。我会检查qi:position的预跳过。关于Spirit X3，是的，我考虑过测试它。现在我有时间了，可能会在其他更改之后尝试它。你认为它对我的解析器来说已经足够成熟了吗？ - Baptiste Wicht

@BaptisteWicht 说实话，我不认为X3适合你的项目。但是，你可以先试用一下。这肯定会让你“等待V3”而不是试图优化V2实现 :) [是的，快速主要是指属性传播的完全盲目 :< ] - sehe

我会试一下（可能需要几周时间）。无论如何，我已经合并和测试了你的PR，它工作得很好。我在我的电脑上没有像你那样取得那么大的进展，但我成功地取得了33%的改进。我也在处理你提出的其他问题。 - Baptiste Wicht

哦哈。我没想到第二部分也能“合并” :| 我只会采用 static const 词法分析器行以获得快速胜利。我怀疑整个“位置记录”可以用一种不那么复杂的方法完成（使用在解析时传递的 Phoenix 调整后的函数对象？）。无论如何，我很高兴它能起作用 :/ 我只是验证解析器仍然返回了“true”。 - sehe