用boost x3编译时间

Question

我正试图掌握一个新的精神X3 (升压1.61.0)。

我的机器是一个运行Linux的MacBook Pro (i7-4750HQ)。

使用了版本2的精神，我习惯了大量的编译时间，但这感觉不对。对于表达式解析器的以下第一步，编译需要20多个步骤。

我认为X3会更快，那么这合理吗？我的代码不太理想吗？

编译器设置(clang 3.8.0)

clang++ -c -pipe -std=c++14 -ftemplate-depth=512 -g -w -Wall -Wno-unused-parameter -fPIC 

代码：

//#define BOOST_SPIRIT_X3_DEBUG
#include <iostream>

#include <boost/spirit/home/x3.hpp>
#include <boost/spirit/home/x3/support/ast/variant.hpp>
#include <boost/fusion/include/adapt_struct.hpp>

#include <string>
#include <vector>

//--------------------------------------------------------------------------------------------------
namespace client { namespace ast
{
    namespace fusion = boost::fusion;
    namespace x3 = boost::spirit::x3;

    struct number : x3::variant<int, double> {
        using base_type::base_type;
        using base_type::operator=;
    };

    struct add_ast;
    struct mult_ast;
    struct block_ast;
    struct function;

    struct expr_ast : x3::variant<
            number,
            x3::forward_ast<function>,
            x3::forward_ast<add_ast>,
            x3::forward_ast<mult_ast>,
            x3::forward_ast<block_ast>
        > {
        using base_type::base_type;
        using base_type::operator=;
    };

    struct add_ast {
        expr_ast lhs;
        bool     add;
        expr_ast rhs;
    };

    struct mult_ast {
        expr_ast lhs;
        bool     mult;
        expr_ast rhs;
    };

    struct block_ast {
        expr_ast body;
    };

    struct function {
        std::string           name;
        std::vector<expr_ast> params;
    };
}}

//--------------------------------------------------------------------------------------------------
BOOST_FUSION_ADAPT_STRUCT(client::ast::add_ast,
    (client::ast::expr_ast, lhs),
    (bool, add),
    (client::ast::expr_ast, rhs)
)
BOOST_FUSION_ADAPT_STRUCT(client::ast::mult_ast,
    (client::ast::expr_ast, lhs),
    (bool, mult),
    (client::ast::expr_ast, rhs)
)
BOOST_FUSION_ADAPT_STRUCT(client::ast::block_ast,
    (client::ast::expr_ast, body)
)
BOOST_FUSION_ADAPT_STRUCT(client::ast::function,
    (std::string, name),
    (std::vector<client::ast::expr_ast>, params)
)

//--------------------------------------------------------------------------------------------------
namespace client { namespace parser
{
    namespace x3 = boost::spirit::x3;

    const x3::rule<class expr,       ast::expr_ast> expr       = "expr";
    const x3::rule<class add_expr,   ast::expr_ast> add_expr   = "add_expr";
    const x3::rule<class mult_expr,  ast::expr_ast> mult_expr  = "mult_expr";
    const x3::rule<class block_expr, ast::expr_ast> block_expr = "block_expr";

    auto const number   = x3::rule<class number, ast::number> {"number"}
                        = (x3::int_ >> !x3::lit('.')) | x3::double_;

    auto const fct_name = x3::rule<class fct_name, std::string> {"fct_name"}
                        = x3::lexeme[ *x3::alpha >> *(x3::alnum | x3::char_('_')) ];

    auto const function = x3::rule<class function, ast::function> {"function"}
                        = fct_name >> x3::lit("(") >> -expr % ',' >> ")";

    auto const simple_expr = x3::rule<class simple_expr, ast::expr_ast> {"simple_expr"}
                           = function | number;

    auto const block_term = x3::rule<class block_term, ast::block_ast> {"block_term"}
                          = "(" >> expr >> ")";

    auto const mult_term = x3::rule<class mult_term, ast::mult_ast> {"mult_term"}
                         = block_expr
                           >> ((x3::lit("*") >> x3::attr(true)) | (x3::lit("/") >> x3::attr(false)))
                           >> mult_expr;

    auto const add_term = x3::rule<class add_term, ast::add_ast> {"add_term"}
                        = mult_expr
                          >> ((x3::lit("+") >> x3::attr(true)) | (x3::lit("-") >> x3::attr(false)))
                          >> add_expr;

    auto const block_expr_def = block_term | simple_expr;
    auto const mult_expr_def  = mult_term | block_expr;
    auto const add_expr_def   = add_term | mult_expr;
    auto const expr_def       = add_expr;

    BOOST_SPIRIT_DEFINE(expr, add_expr, mult_expr, block_expr);
}}

//--------------------------------------------------------------------------------------------------
namespace client { namespace ast
{
    struct printer
    {
        typedef std::string result_type;

        std::string operator()(const expr_ast &ast) const
        {
            return boost::apply_visitor(printer(), ast);
        }
        std::string operator()(const number &value) const
        {
            return boost::apply_visitor(printer(), value);
        }

        std::string operator()(const add_ast &expr) const {
            return "(" + boost::apply_visitor(printer(), expr.lhs) + (expr.add?" + ":" - ")
                   + boost::apply_visitor(printer(), expr.rhs) + ")";
        }

        std::string operator()(const mult_ast &expr) const {
            return "(" + boost::apply_visitor(printer(), expr.lhs) + (expr.mult?" * ":" / ")
                   + boost::apply_visitor(printer(), expr.rhs) + ")";
        }

        std::string operator()(const block_ast &expr) const {
            return boost::apply_visitor(printer(), expr.body);
        }

        std::string operator()(const function &fct) const
        {
            std::string result = fct.name + "(";
            for (std::size_t i = 0; i < fct.params.size(); ++i) {
                result += printer()(fct.params[i]);
                if (i != fct.params.size() - 1)
                    result += ",";
            }
            result += ")";
            return result;
        }

        std::string operator()(int const& value) const
        {
            return std::to_string(value);
        }
        std::string operator()(double const& value) const
        {
            return std::to_string(value);
        }
    };
}}

//--------------------------------------------------------------------------------------------------
int main()
{
    std::vector<std::string> storage = {
        "foo()", "-foo()",
        "f1_2()",
        "foo_bar ()",
        "foo( bar (42, baz()))",
        "foo(5)", "foo(-5)",
        "foo(1.1, foo(4.21e-2, 4., 6))",
        "1.1", "-1.1",
        "1 * 1",
        "foo(1 * 1) * bar(42)",
        "foo(2 + 5.5, bar()*3.4-7)",
        "foo(2 + 5.5, bar(baz(-5/foo())) * 3.4 - 7)",
        "4 + 5 * 6",
        "1+2+3+4*5*6*-7+-8*+9-0",
        "(foo())",
        "foo() * ((1+2)+3*(2+3))",
        "(1+2)*3", "1+2*3",
        "foo"
    };

    using boost::spirit::x3::ascii::space;

    for (const auto &item : storage) {
        using client::parser::expr; // Our grammar
        client::ast::expr_ast ast; // Our tree

        std::string::const_iterator iter = item.begin();
        std::string::const_iterator end = item.end();
        bool r = phrase_parse(iter, end, expr, space, ast);

        if (r && iter == end)
        {
            std::cout << "Ok: " << item << " result: " << client::ast::printer()(ast) << std::endl;
        }
        else
        {
            std::cout << "Fail: " << item << std::endl;
        }
    }
}

Answer 1

虽然这实际上可能是精神X3中的一个回归，比如@sehe，但它建议使用当前版本有一个解决办法：

将参与递归表达式的所有规则更改如下：

const x3::rule<class block_term, ast::block_ast> block_term = "block_term";
auto const block_term_def = x3::rule<class block_term, ast::block_ast> {"block_term"}
                      = "(" >> expr >> ")";

BOOST_SPIRIT_DEFINE(block_term)

这大大减少了编译时间，解析器运行良好。解析器的性能似乎是一样的(非常不科学的测试！)

Answer 2

在我看来，这是一个严重的倒退。

在我的机器上花了很长时间：

• gcc 5:在4分钟30分钟后慢慢地使用越来越多的内存，最多达到3 3GiB，然后是20多岁的汇编程序阶段： g++-5 -std=c++14 -Wall -pedantic -Wextra -fsanitize=undefined，地址-Wno-未使用的-g -O3 -isystem /home/sehe/定制/nonius/包括-isystem /home/sehe/定制/boost_1_1_0 -pthread -march=native test.cpp -c -o test.o test.cpp:119:62:警告：‘；^g+-5 -std=c++14 -Wall -pedantic -Wextra -fsanitize=undefined，地址-Wno-未使用的-g -O3 -isystem /home/sehe/定制/nonius/包括-isystem /home/sehe/定制/boost_1_60_0 -pthread -march=native test.o -o test -L /home/sehe/定制/boost_1_60_0/stage/lib/ -Wl，-rpath，/home/sehe/定制/boost_1_60_0/stage/lib -lboost_system -lboost_regex -lboost_thread -lboost_iostreams -lboost_serialization -lboost_filesystem -lboost_chrono -lrt -lboost_unit_test_framework -lpugixml -lssl -lcrypto -lxml2 Real4m50.427s用户4m48.248s sys 0m1.856s
• clang 3.6:失败，模板实例化深度超过 /home/sehe/custom/boost_1_60_0/boost/spirit/home/x3/support/context.hpp|30 col 25\致命错误:递归模板实例化超过最大深度256

这就直接暗示了是什么原因造成的。

我的第一个预感是，x3::variant可能会导致编译器更积极地内联，但用boost替换：：变体并没有提供太多帮助：

g++-5 -std=c++14 -Wall -pedantic -Wextra -fsanitize=undefined,address -Wno-unused -g -O3 -isystem /home/sehe/custom/nonius/include -isystem /home/sehe/custom/boost_1_60_0 -pthread -march=native test.cpp -c -o test.o
test.cpp:135:62: warning: extra ‘;’ [-Wpedantic]
     BOOST_SPIRIT_DEFINE(expr, add_expr, mult_expr, block_expr);
                                                              ^
g++-5 -std=c++14 -Wall -pedantic -Wextra -fsanitize=undefined,address -Wno-unused -g -O3 -isystem /home/sehe/custom/nonius/include -isystem /home/sehe/custom/boost_1_60_0 -pthread -march=native test.o -o test -L /home/sehe/custom/boost_1_60_0/stage/lib/ -Wl,-rpath,/home/sehe/custom/boost_1_60_0/stage/lib -lboost_system -lboost_regex -lboost_thread -lboost_iostreams -lboost_serialization -lboost_filesystem -lboost_chrono -lrt -lboost_unit_test_framework  -lpugixml -lssl -lcrypto -lxml2

real    3m55.728s

在起诉方面没有区别：

Ok: foo() result: foo()
Fail: -foo()
Ok: f1_2() result: f1_2()
Ok: foo_bar () result: foo_bar()
Ok: foo( bar (42, baz())) result: foo(bar(42,baz()))
Ok: foo(5) result: foo(5)
Ok: foo(-5) result: foo(-5)
Ok: foo(1.1, foo(4.21e-2, 4., 6)) result: foo(1.100000,foo(0.042100,4.000000,6))
Ok: 1.1 result: 1.100000
Ok: -1.1 result: -1.100000
Ok: 1 * 1 result: (1 * 1)
Ok: foo(1 * 1) * bar(42) result: (foo((1 * 1)) * bar(42))
Ok: foo(2 + 5.5, bar()*3.4-7) result: foo((2 + 5.500000),((bar() * 3.400000) - 7))
Ok: foo(2 + 5.5, bar(baz(-5/foo())) * 3.4 - 7) result: foo((2 + 5.500000),((bar(baz((-5 / foo()))) * 3.400000) - 7))
Ok: 4 + 5 * 6 result: (4 + (5 * 6))
Ok: 1+2+3+4*5*6*-7+-8*+9-0 result: (1 + (2 + (3 + ((4 * (5 * (6 * -7))) + ((-8 * 9) - 0)))))
Ok: (foo()) result: foo()
Ok: foo() * ((1+2)+3*(2+3)) result: (foo() * ((1 + 2) + (3 * (2 + 3))))
Ok: (1+2)*3 result: ((1 + 2) * 3)
Ok: 1+2*3 result: (1 + (2 * 3))
Fail: foo

我会在精神邮件列表中报告这一点：http://boost.2283326.n4.nabble.com/spirit-general-f2672582.html

Answer 3

PR650 X3:跳过上下文中的规则定义注入在Boost 1.77中减少了编译时间。这是14秒前和2秒后(仅解析包含1秒对我来说)。

放缓的原因是在替代解析器中嵌套使用内部创建的规则(如auto const somerule = x3::rule<...>{} = ...; )。

像auto const somerule = rule_placeholder = ... may call rule_placeholder ...;这样创建的规则可以递归地调用自己。为了支持规则定义本身，通过替代解析器嵌套多个解析器会创建大量的唯一解析器，不仅导致大量模板实例化(实际上非常快)，而且导致编译器前端( Clang )传递给编译器后端( LLVM )的大量代码生成，这在Clang中是一个巨大的瓶颈(优化和去复制LLVM IR也需要时间)。

在修复之后，auto const somerule = x3::rule<...>{} = ...;被认为不能递归地调用自己，因为它们创建了一个占位符，如果没有黑客，就不能在同一个表达式中引用它。