Nov 17

Zero to 60 MPH in 2 seconds!

By Joel de Guzman Add comments

Wanna make a blazingly fast rule? Use BOOST_AUTO! Check it out here. The code defines a named rule using C++0x auto when available and falls back to some template wizardry on older compilers. This code:

BOOST_AUTO(comment, "/*" >> *(char_ - "*/") >> "*/");  

defines a rule named comment that can be used just like any parser. If you have a compiler that can handle the new auto keyword, this code is equivalent to:

auto comment = "/*" >> *(char_ - "*/") >> "*/";  

Now you can use this `comment` rule to parse:

bool r = parse(iter, end, comment);

Unlike Spirit rules, however, this one is a lot more efficient in terms of speed (no indirection), code size (virtually zero code bloat) and memory usage (the size of the comment rule above is just 8 bytes on MSVC. Just the footprint needed for the static strings, almost. The expression has zero overhead thanks to Boost.Proto). It is very suitable for skip-parsers, for example (if you want to know the actual type, you can use BOOST_TYPEOF). Be aware though that this is only good for non-recursive rules. There is no way to define recursive rules using this. But then, there are lots of rules that really aren’t recursive anyway. For example, we often need to break overly complex rules into manageable parts.So… there ya go… have fun!

(UPDATE: See the comments below. It turns out that MSVC segfaults. Provided below is a workaround)

25 Responses to “Zero to 60 MPH in 2 seconds!”

  1. Christoph Duelli says:

    Is it possible to use that approach with grammars?
    I need to put the skipper’s type into the template after all.
    Would something like:

    auto comment = "/*" >> *(char_ - "*/") >> "*/"; 
    typedef typeof(comment) skipper;
    

    work? (using gcc)

    So far I am using a grammar as skipper:

    template 
    struct skip_grammar : qi::grammar
    {
      skip_grammar() : skip_grammar::base_type(start)
      {
        using qi::iso8859_1::char_;
        using qi::iso8859_1::space;
        using qi::eol;
    
        start =
          space                            // tab/space/cr/lf
          | ("/*" >> *(char_ - "*/") >> "*/")  // C-style comments
          | ("//" >> *(char_ - eol) >> eol)    // C++-style comments
        ;
      }
      qi::rule start;
    };
    

    Is that even worse (compared to “only” a rule as skipper)?

    And: talking about efficiency: how much faster would that be? 😉

    • Joel de Guzman says:

      Yes, it is definitely possible as long as your grammar is non-recursive and is self contained (e.g. no references or pointers that could dangle). As for performance, your mileage may vary. When in doubt, it’s always good to test and measure 🙂

  2. Adam Merz says:

    I just tried this with MSVC10 Beta 2 and boost 1.41 beta 1. It works fantastic in debug builds, but for release builds I get an access violation inside qi::parse, no matter how simple or complex the grammar/rule. I don’t know if this is a codegen bug with MSVC, or if there’s undefined behavior occurring somewhere inside spirit, but this trick is effectively useless for me. :-[

    Any thoughts?

    • Joel de Guzman says:

      Check. I can repro this on VC9 as well. I just submitted a workaround for Spirit. See the cpp file again [ http://svn.boost.org/svn/boost/trunk/libs/spirit/example/qi/typeof.cpp ]. I added BOOST_SPIRIT_AUTO. Now it has to be used like this:

      BOOST_SPIRIT_AUTO(qi, comment, "/*" >> *(char_ - "*/") >> "*/");

      The macro BOOST_SPIRIT_AUTO(domain, rule_name, expression) will be added into Spirit soon. The parameters are 1) domain: can be qi or karma. 2) rule_name: the name of your rule. 3) expression: the RHS expression.

      • Adam Merz says:

        Thanks for replying, Joel. Hartmut and I had some fun on IRC muddling over this issue. :-]

        BOOST_SPIRIT_AUTO looks like a step in the right direction, for sure. The problem is that when using BOOST_AUTO (while the “rules” are still raw proto expressions), the expressions are composable. For example, the following compiles:

        BOOST_AUTO(comment_pre, lit("/*"));
        BOOST_AUTO(comment_mid, char_ - "*/");
        BOOST_AUTO(comment_post, lit("*/"));
        BOOST_AUTO(comment, comment_pre >> *comment_mid >> comment_post);
        parse(iter, end, comment);
        

        But after the transform done by BOOST_SPIRIT_AUTO, operators cease to work on the expressions, so the following does not compile:

        BOOST_SPIRIT_AUTO(qi, comment_pre, lit("/*"));
        BOOST_SPIRIT_AUTO(qi, comment_mid, char_ - "*/");
        BOOST_SPIRIT_AUTO(qi, comment_post, lit("*/"));
        BOOST_SPIRIT_AUTO(qi, comment, comment_pre >> *comment_mid >> comment_post);
        

        Any hints on working around this one? :-]

        • Joel de Guzman says:

          Fixed. Check the cpp program again. Here’s the relevant code:

          #define BOOST_SPIRIT_AUTO(domain_, name, expr)                                  \
              typedef BOOST_TYPEOF(expr) name##expr_type;                                 \
              BOOST_SPIRIT_ASSERT_MATCH(boost::spirit::domain_::domain, name##expr_type); \
              BOOST_AUTO(name, boost::proto::deep_copy(expr));                            \
              /**/
          

          Take note that BOOST_SPIRIT_ASSERT_MATCH and domain_ are not strictly needed anymore. They are there for validating the expressions ASAP only. Without them, you can have an invalid Spirit (but valid proto) expression. Somewhere down the line, when you finally compile the expression into a Spirit parser, the meta-compiler will choke and you will have to figure out which of your micro-rules was erroneous. I’d keep them probably in debug mode for sanity testing and #ifdef them out on release mode to make the code compile faster.

          • Joel de Guzman says:

            Oh BTW, I now have a name for such critters: “micro rules” :-).

          • Adam Merz says:

            Fantastic, works perfectly. Thanks, Joel. :-]

          • Joel de Guzman says:

            Also, take note that when you use BOOST_SPIRIT_AUTO(domain, name, expr),
            you’ll have 1) the named micro-rule ‘name’ and 2) a typedef ‘name_expr_type’ -its type. That typedef will be quite useful too.

          • Michael Caisse says:

            The resulting typedef of the micro-rule doesn’t match the actual type of the rule. This patch seems to do the trick:

            #define BOOST_SPIRIT_AUTO(domain_, name, expr)                                  \
                typedef boost::proto::result_of::deep_copy<BOOST_TYPEOF(expr)>::type name##_expr_type; \
                BOOST_SPIRIT_ASSERT_MATCH(                                                  \
                    boost::spirit::domain_::domain, name##_expr_type);                      \
                BOOST_AUTO(name, boost::proto::deep_copy(expr));                            \
            
  3. Joel de Guzman says:

    @Michael, I applied your patch. Thanks!

  4. Rob says:

    I think that name##_type would be more reasonable. When using that typedef to describe the skipper used by a grammar or rule, the _expr part looks odd. Here’s how I think things ought to be:

    BOOST_SPIRIT_AUTO(qi, foo, ...);
    template <class It>
    struct g : qi::grammar<It,foo_type>
    {
    };
    
    • Joel de Guzman says:

      Agreed. The only problem with name##_type (and name##_expr_type, for that matter) is if the name ends with an underscore, which will result in a type with double underscores-illegal C++ name.

      • Rob Stewart says:

        You could provide two versions:

        #define BOOST_SPIRIT_AUTO(_domain, _name, _expression);
        #define BOOST_SPIRIT_AUTO_TYPED(_domain, _name, _type, _expression);
        

        The former would create an ugly name like unspecified_type_for##name and use it to call the latter. The latter would then be defined like this:

        #define BOOST_SPIRIT_AUTO_TYPED(_domain, _name, _type, _expression)           \
           typedef boost::proto::result_of::deep_copy<BOOST_TYPEOF(_expression)>::type\
              _type;                                                                  \
           BOOST_SPIRIT_ASSERT_MATCH(boost::spirit::_domain::domain, _name##_type);   \
           BOOST_AUTO(_name, boost::proto::deep_copy(_expression))
        
  5. Rob Stewart says:

    You should note that micro-rules cannot be named (there’s no name() member function) and they don’t appear in debug output (you can’t call qi::debug() with a micro-rule).

  6. Valentin says:

    Just out of curiosity:

    As mentioned above, BOOST_AUTO-ing subexpressions may lead to access violations or other unwanted results: Nodes in the boost::proto expression tree may hold child nodes by reference. Those child nodes may be temporary objects created on stack and go out of scope as soon as the auto variable has been assigned. Whenever a terminal node carries some value, say a char pointer, there is no guarantee that this value is still accessible at later times.

    Now I am rather surprised to see that there are compilers other than MSVC, where the BOOST_AUTO trick still works. Can you tell me why?

    Obviously, a workaround is to enforce a a deep copy, as in the BOOST_SPIRIT_AUTO macro. But then a lot of copy constructors are recursively invoked recursively each time two such expressions are composed to form a new one. Will the compiler be able to optimize away, or are there negative effects on the performance whenever the parser is constructed.(compared to using ugly some #define for small subrules)?

    Valentin

    • Joel de Guzman says:

      > Now I am rather surprised to see that there are compilers other than MSVC,
      > where the BOOST_AUTO trick still works. Can you tell me why?

      That’s what “undefined behavior” means. It may or may not work. There is no guarantee.

      > Will the compiler be able to optimize away, or are there negative effects on
      > the performance whenever the parser is constructed.(compared to using ugly
      > some #define for small subrules)?

      Yes. Modern compilers are very smart. I’ve yet to see the copies not being optimized away.

      • Domagoj Saric says:

        >> Will the compiler be able to optimize away, or are there
        >> negative effects on the performance whenever the parser
        >> is constructed.(compared to using ugly
        >> some #define for small subrules)?
        >
        > Yes. Modern compilers are very smart. I’ve yet to see
        > the copies not being optimized away.

        Unfortunately not quite. MSVC++ 10, (one of) the best optimizers in my experience, is not able to optimize the copying. When optimizing for size (/Oxs) I always see the call to proto::deep_copy, when optimizing for speed (/Oxt) some of the deep_copy calls for simpler expressions get inlined which sometimes translates to the copy being avoided (ironically producing smaller code than Oxs for those cases)…

        The claim to ‘zero-overhead thanks to Proto’ also unfortunately does not hold (if the comparison is made to hand written code)…As pointed out in the recent related discussions on spirit.general, for truly zero overhead a more compile-time approach (e.g. metafunctions or passing compile-time known parameters through non-type template parameters) would need to be employed because expression templates are after all a hybrid compile+runtime/static+dynamic technique and even for such simple expressions as above the compiler still generates non-trivial construction code for an object that occupies space and holds references to its subparts (while none of that is actually necessary)…

        • Joel de Guzman says:

          Yes, I am referring to “simpler expressions”, which is the main intent of this exercise anyway.

          You do have valid points. I should have made it clear that with more complex expressions, the optimizer gets confused and fails to optimize. YMMV.

      • Leo Goodstadt says:

        I have started to get occasional (but consistent) access violations using “auto” rules under -std=c++11 -O2 in gcc 4.7. This is in tested code which worked well under gcc 4.6 and gcc 4.5. Writing out the full rule type caused these bugs to go away.

        Does this mean we should use BOOST_SPIRIT_AUTO even for compilers which support auto?

        Thanks
        Leo

        • Joel de Guzman says:

          For Spirit2, well, unfortunately, yes. But hang on a little bit more. I fixed the situation with Spirit3. With Spirit-3 you can use auto all you want.

Leave a Reply to Joel de Guzman

preload preload preload