用g ++/bison/boost :: variant编写的解析器编译速度很慢

Question

我编写了一个带有bison的verilog解析器,并使用boost :: variant存储每个规则的每个变体的所有差异情况.我使用一个小例子,BNF表达式来显示我的数据结构:

expression :
  primary
  | expression + expression
primary :
  (expression)
  | number

存储它的数据结构是:

typedef boost::variant<
  std::shared_ptr<exp1>,
  std::shared_ptr<exp2>,
> expression
typedef boost::variant<
  std::shared_ptr<prim1>,
  std::shared_ptr<prim2>,
> primary

class exp1/2和prim1/2用于存储表达式和primary中的两个不同的case:

class exp1 : public BaseClass {
  public :
    std::shared_ptr<primary> mem1;
    exp1(std::shared_ptr<primary> i1):
    mem1(i1)
    {}
}

为简化起见,我只显示exp1,而exp2和prim1/2是相似的.在野牛文件中,规则及其操作如下所示:

expression :
  primary  {
   $$= std::make_shared<expression>(std::make_shared<exp1>($1));
  }

这样的解决方案导致两个问题:

1编译是veeeeeeeeeeeery慢,用g ++ 4.8.4花费差不多1分钟
2运行时间不是很快

我有一个用ocaml和ocamlyacc编写的类似解析器,它支持非常优化的变量规范,并且用1秒编译,并且运行速度与上面提到的g ++版本非常相似.

我使用boost :: variant的风格有什么问题吗？

==============

我使用构造函数接受shared_ptrs将所有变量更改为类:

class ComponentBase {
};
Class VariantBase{
};
class prim1;
class prim2;
class exp1;
class exp2;
class expression : public VariantBase {
  expression (shared_ptr<ComponentBase> i1):
    VariantBase(i1) {}
}
class primary : public VariantBase {
  primary (shared_ptr<ComponentBase> i1):
    VariantBase(i1) {}
}

然后编译没有任何改进.似乎yacc生成的代码是缓慢的来源.

有什么建议吗？

Answer 1

更新在升压精神续齐演示,而不是(因为我没有在柔性/野牛精通),见下面的块报价

如果您的AST使用共享指针,我建议运行时性能不是问题.

如果您的AST使用变体,我建议编译时性能不是问题.(因此没有理由担心:))

shared_ptrs在概念上违背了变体.Shared_ptrs 通过生命周期管理的节点动态分配来促进运行时多态性.

变体有助于静态多态性和自动存储持续时间.

去运行时多态性

如果您对运行时多态AST节点(在AST上的转换中通常非常方便)很好,那么我建议您不要使用这些变体.相反,使它们成为同一节点层次结构的一部分.

粗略素描:

去静态多态性

删除运行时多态(和变体头,最好)将减少编译时间.当有许多模板实例化组合要进行内联和优化时,编译时间会增加.

UPDATE

• c++14 Spirit X3 (Swift编译,快速运行)
• c++11 Spirit Qi (编译速度慢)
• c++03 Spirit Qi (编译速度慢)

这演示了为更简单的AST删除共享指针和运行时多态性.

上面提到的模板实例化+内联的爆炸性解释了"老式"Qi实现编译速度慢,可能比原始代码慢.X3版本没有这个问题.