Design/structure X3 parser more like Qi parser

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
37 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Design/structure X3 parser more like Qi parser

Sandro Pirkwieser

Hi,

 

so far we used Spirit Qi for our parsers. Mainly due to large compilation times we were eager to experiment with X3.

It seems that there are two ways of designing a parser: (1) make the whole parser static, or (2) embed it in a function/method.

The disadvantages of (1) are that one always has to pay the costs of initializing the static parser, and the rather loose encapsulation in a namespace.

In case of (2) the parser is created each time (though it might be saved/cached), code reuse is more difficult (only the "main rule"), and only simple parsers are possible (without circular references).

When dealing with larger and complex parsers, these things matter. Having the parser encapsulated in a class would solve these issues, as was the case for Qi.

Unfortunately we were not able to do this with X3, as on the one hand 'auto' cannot be used for members (and stating the actual type would be unhandy), and on the other hand when having the rule and the definition separated the linking via BOOST_SPIRIT_DEFINE does not seem to work in this context.

 

We found the recommendation regarding the xxx.hpp, xxx.cpp and xxx_def.hpp structure by Joel, but is it possible to structure/design an X3 parser having the above issues in mind?

What are your experiences with X3 when it comes to designing/structuring larger, complex parsers?

 

Best regards,

Sandro


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Mikael Asplund

Hi!

 

We have a fairly large parser with c-like expression handling, configuration files and source files. We made a library with a Parser class that have a few methods that are called, depending on grammar, and an ast.h for all the types of the resulting trees. Also error handling type leaks and bit, etc. Not a whole lot of other stuff is part of the interface, but some visibility leakage.

 

When it comes to encapsulation and initialization, everything is in a parser namespace of course, and we're using the standard .h/.cpp/_def.h setup per grammar, which are called from the parser class's methods.

 

As I'm parsing tokens, where I use global variables for the tokens I compare with, I needed to have them all constructed before the rules that capture and compare with them are initialized. Which is easy when you have just one file, you just defined the tokens up top. Not so easy when you have multiple files that want to use the same tokens. My solution is to have them a the top of one file, and have all other files use rules which initialize from functions, by not using the standard macro. See earlier post on the list (search for "Fixes for BOOST_SPIRIT_DEFINE", or check link below).

 

https://sourceforge.net/p/spirit/mailman/message/34947312/

 

Barring some linking issues and such, it's working fine for us.

 

  /Mikael

 

From: Sandro Pirkwieser [mailto:[hidden email]]
Sent: Friday, December 2, 2016 12:33
To: [hidden email]
Subject: [Spirit-general] Design/structure X3 parser more like Qi parser

 

Hi,

 

so far we used Spirit Qi for our parsers. Mainly due to large compilation times we were eager to experiment with X3.

It seems that there are two ways of designing a parser: (1) make the whole parser static, or (2) embed it in a function/method.

The disadvantages of (1) are that one always has to pay the costs of initializing the static parser, and the rather loose encapsulation in a namespace.

In case of (2) the parser is created each time (though it might be saved/cached), code reuse is more difficult (only the "main rule"), and only simple parsers are possible (without circular references).

When dealing with larger and complex parsers, these things matter. Having the parser encapsulated in a class would solve these issues, as was the case for Qi.

Unfortunately we were not able to do this with X3, as on the one hand 'auto' cannot be used for members (and stating the actual type would be unhandy), and on the other hand when having the rule and the definition separated the linking via BOOST_SPIRIT_DEFINE does not seem to work in this context.

 

We found the recommendation regarding the xxx.hpp, xxx.cpp and xxx_def.hpp structure by Joel, but is it possible to structure/design an X3 parser having the above issues in mind?

What are your experiences with X3 when it comes to designing/structuring larger, complex parsers?

 

Best regards,

Sandro


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Michael Powell-2
In reply to this post by Sandro Pirkwieser
On Fri, Dec 2, 2016 at 6:33 AM, Sandro Pirkwieser
<[hidden email]> wrote:

> Hi,
>
>
>
> so far we used Spirit Qi for our parsers. Mainly due to large compilation
> times we were eager to experiment with X3.
>
> It seems that there are two ways of designing a parser: (1) make the whole
> parser static, or (2) embed it in a function/method.
>
> The disadvantages of (1) are that one always has to pay the costs of
> initializing the static parser, and the rather loose encapsulation in a
> namespace.
>
> In case of (2) the parser is created each time (though it might be
> saved/cached), code reuse is more difficult (only the "main rule"), and only
> simple parsers are possible (without circular references).

Just thinking out loud, but something like this might work for you.
Unless possibly the grammar(s) need to be reentrant.

void some_method() {

    static your_grammar g;

    auto result = g.parse(...);

}

> When dealing with larger and complex parsers, these things matter. Having
> the parser encapsulated in a class would solve these issues, as was the case
> for Qi.
>
> Unfortunately we were not able to do this with X3, as on the one hand 'auto'
> cannot be used for members (and stating the actual type would be unhandy),
> and on the other hand when having the rule and the definition separated the
> linking via BOOST_SPIRIT_DEFINE does not seem to work in this context.
>
>
>
> We found the recommendation regarding the xxx.hpp, xxx.cpp and xxx_def.hpp
> structure by Joel, but is it possible to structure/design an X3 parser
> having the above issues in mind?
>
> What are your experiences with X3 when it comes to designing/structuring
> larger, complex parsers?
>
>
>
> Best regards,
>
> Sandro
>
>
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> Spirit-general mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-general
>

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

sehe
In reply to this post by Sandro Pirkwieser
On 02-12-16 12:33, Sandro Pirkwieser wrote:
> The disadvantages of (1) are that one always has to pay the costs of
> initializing the static parser
Well. Seeing how many parts are constexpr (or can be in c++17) that cost
is likely imaginary.

If you don't care for parser performance and somehow mind a lot about
skipping static initializers (when is this a use-case?), you can always
use function-local scoped rules, using `x3::any_parser` to type-erase
any rule that needs to be reentrant. I think `x3::any_parser` is a close
cousing to `qi::rule` in that respect.

> When dealing with larger and complex parsers, these things matter.
> Having the parser encapsulated in a class would solve these issues, as
> was the case for Qi.

I fail to see why encapsulating parsers in a class changes much. I think
that's in the mind.

If you want you can trivially wrap entire (sub)grammars in a Qi-like
grammar struct: quick sketch
https://gist.github.com/sehe/7149067e6d5ef7edb36edb1867f110bc (note that
inspecting the assembly and `nm -C` output shows no static
initialization code has been generated)

As a third option, it could be good to note that the previous is pretty
close to a custom X3 parser. If you make the implementation inline and
change the interface slightly, you have a native X3 parser object
(sample:
https://stackoverflow.com/questions/37669936/spirit-qi-how-can-i-write-a-nonterminal-parser/37823837#37823837)

I feel the best results are to be had mixing and matching the above. I'd
probably concentrate on any_parser (for pimpl-ing the definitions) and
custom X3 parsers, because I like how they can keep you a bit away from
paying the MACRO/explicit instantiation tax.

> so far we used Spirit Qi for our parsers. Mainly due to large
> compilation times we were eager to experiment with X3.
If you don't mind my asking, what have been other limitiations you have
run into?

Personally I miss other things the most (like qi::lazy, qi::locals and
inherited attributes). Basically anything that could make a parser
stateful is harder in X3, and even with `x3::with<>` the semantics are
subtly different in unfortunate ways.

Oh, and sometimes phoenix was pretty nice for expressing semantic
actions, but that's largely syntactic sugar.

Cheers,

Seth


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

cppljevans
On 12/02/2016 04:29 PM, Seth wrote:
> On 02-12-16 12:33, Sandro Pirkwieser wrote:
[snip]

>> so far we used Spirit Qi for our parsers. Mainly due to large
>> compilation times we were eager to experiment with X3.
> If you don't mind my asking, what have been other limitiations you have
> run into?
>
> Personally I miss other things the most (like qi::lazy, qi::locals and
> inherited attributes). Basically anything that could make a parser
> stateful is harder in X3, and even with `x3::with<>` the semantics are
> subtly different in unfortunate ways.
>

Seth, would you happen to know why it was decided to not have
inherited attributes in X3?  Maybe compile times would suffer too much?

TIA.

-regards,
Larry





------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Parsing a set number of repetitions

Sebastian Gsänger
Hi,

I'm struggling to find a satisfying solution for this seemingly simple
problem:
Given a number of repetitions to follow, i want the parser to succeed
only if this number is matched exactly.
I tried the following, which succesfully fails if there are too little
occurences:

steps = step % +qi::eol;
step  = qi::omit[qi::int_[qi::_a = qi::_1] > qi::eol]
         > atoms(qi::_a);
atoms = qi::repeat(qi::_r1)[qi::eol > atom];

With too many atoms, it parses the first step, fails the second and ends.
In this specific case, i could rewrite the steps-rule to be more
explicit in it's expectations, but i'd like to reuse this concept for
formats where this is not possible.
Is there a way to fail the 'step' rule inside of itself given a mismatch
of 'qi::_a' and the size of the parsed vector?
I also tried to use phoenix, as in:

steps = step % +qi::eol;
step  = qi::omit[qi::int_[qi::_a = qi::_1] > qi::eol]
         > atoms[qi::_b = phx::stl::size(qi::_1)]
         > qi::eps(qi::_a == qi::_b)
atoms = atom % qi::eol;

This does not compile though:
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:
candidate: constexpr boost::phoenix::stl::size::size()
          struct size
                 ^~~~
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:  
candidate expects 0 arguments, 1 provided
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:
candidate: constexpr boost::phoenix::stl::size::size(const
boost::phoenix::stl::size&)
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:  
no known conversion for argument 1 from 'const _1_type {aka const
boost::phoenix::actor<boost::spirit::argument<0> >}' to 'const
boost::phoenix::stl::size&'
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:
candidate: constexpr
boost::phoenix::stl::size::size(boost::phoenix::stl::size&&)
/usr/include/boost/phoenix/stl/container/container.hpp:735:16: note:  
no known conversion for argument 1 from 'const _1_type {aka const
boost::phoenix::actor<boost::spirit::argument<0> >}' to
'boost::phoenix::stl::size&&'

What am i missing?

Thank you,
Sebastian

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Sandro Pirkwieser
In reply to this post by sehe
Hi,

@Mikael: thanks for your report and the "trick" with the init function.
@Michael: yes, it would certainly work for some parsers, and I already used that style, but I think in this way the parser (grammar) is more trapped than encapsulated.
@Seth: Thanks for all your info, I will reply to your points in the remainder.

I'm still concerned about the basic structure of an X3 parser, but it remains open whether it is because of my current knowledge or the way X3 was designed and is intended to use.
The main concern: with Qi one achieves a straightforward and clean encapsulation in a grammar (sub-)class, yet it is easy to use such a parser as a subparser in a larger one via including it as a class member.
In X3 the encapsulation can only be "approximated", and it seems the more achieving this goal decreases the possibility of reusage and integration into another parser.
It seems that our current design, along the guidelines of Qi, is somewhat contrary to that of X3.

Regarding your recommendation, do you know of further info/doc about x3::any_parser and deriving from x3::parser_base? They are not covered by the official docs, as their usage is probably not intended(?).

Until now we encountered no other limitations, but an unfortunate result instead.
To get started I transformed a rather simple parser, which parses CSV input, from Qi to X3. The field separator is not fixed, hence it can be set with `x3::with<>`.
As an upside the compile time is reduced to one third, which is quite impressive, but as a downside the runtime is up to twice as much.
In order to rule out an overhead due to `x3::with<>` the separator was fixed, but it had no measurable effect. There were also two semantic actions in use, which basically added up single chars, which could be omitted by a bit of reformulating. But again, no effect on the runtime.
This parser was thought of as a teaser for X3, but adding up the mentioned structural issues and the experiments leaves us with doubts whether we should pursue it further.

Best regards,
Sandro

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today.http://sdm.link/xeonphi
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

sehe
On 07-12-16 17:30, Sandro Pirkwieser wrote:
> In X3 the encapsulation can only be "approximated", and it seems the more achieving this goal decreases the possibility of reusage and integration into another parser.

I don't look at it that way. In my mind, Qi had a few red-tape classes
required because of language limitations. This, incidentally,
contributed to very long compile times, because of all the template
machinery that went under the hood.

In X3, the policy clearly changed: it favours using C++ language
features as much as possible. This simultaneously cuts compile times and
(more importantly?) _learning curve_.

Instead of having to work with the idiosyncrasies of a handful special
purpose boost libraries you get 80% of the way with /just regular C++/.
Key example is, of course, semantic actions, which are "simple lambdas".

Yes, this comes at the cost of some syntactic sugar that Qi had, but it
makes the library less intrusive and more easilly extended.

> x3::any_parser and deriving from x3::parser_base? They are not covered by the official docs, as their usage is probably not intended(?)
Both are simply not documented then (not checked). They are very much
intended to be used.

> As an upside the compile time is reduced to one third, which is quite impressive, but as a downside the runtime is up to twice as much.
If you can share this in a minimal slefcontained example then ew might
review it


------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today.http://sdm.link/xeonphi
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Parsing a set number of repetitions

Sebastian Gsänger
In reply to this post by Sebastian Gsänger
Hi,

seems i misunderstood the lazyness in phoenix :)
boost::phoenix::stl::size seems to expect real containers that are
evaluated lazyly,
while my aim was to evaluate lazy containers in an unlazy-fashion (e.g.
via phx::bind).
Or something like that...
Should anyone be interested in my solution (focus on the atoms rule):

template<typename Iterator>
struct xyz_parse_grammar: qi::grammar<Iterator, Vipster::Molecule(),
qi::blank_type>
{
     xyz_parse_grammar(): xyz_parse_grammar::base_type(mol, "XYZ")
     {
         name = +qi::alnum;
         atom = name
                   >> qi::double_
                   >> qi::double_
                   >> qi::double_;
         atoms = (atom % qi::eol)
                     > qi::eps(qi::_r1 ==
phx::bind(&std::vector<Vipster::Atom>::size, qi::_val));
         comment = *(qi::char_ - qi::eol) > qi::eol;
         step %= qi::omit[qi::int_[qi::_a = qi::_1] > qi::eol]
                     > comment
                     > atoms(qi::_a);
         steps = step% +qi::eol;
         mol = steps;
     }
     qi::rule<Iterator, Vipster::Molecule(), qi::blank_type> mol;
     qi::rule<Iterator, std::vector<Vipster::Step>(), qi::blank_type> steps;
     qi::rule<Iterator, Vipster::Step(), qi::locals<int>,
qi::blank_type> step;
     qi::rule<Iterator, std::string(), qi::blank_type> comment;
     qi::rule<Iterator, std::vector<Vipster::Atom>(int), qi::blank_type>
atoms;
     qi::rule<Iterator, Vipster::Atom(), qi::blank_type> atom;
     qi::rule<Iterator, std::string(), qi::blank_type> name;
}

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today.http://sdm.link/xeonphi
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Sandro Pirkwieser
In reply to this post by sehe
Hi,

the new structure certainly also has its pros, and was perhaps necessary to achieve the fast compile times. Still, as highlighted in the previous mail, reusing parsers when one does not like/want having them in a namespace seems tricky at the least, if even possible in a meaningful way.
But before we get lost in this topic, I want to follow up on another one: a runtime comparison between an equivalent Qi and X3 parser.
The CSV parser mentioned in the last mail is attached in the Qi and X3 variant, which you can find in main_qi.cpp and main_x3.cpp, respectively, along with some hardcoded input strings in input.hpp.
Initially I tried to offer it via Coliru (with input.hpp inlined), but the Qi variant seems too much to handle (execution expired).
The examples are compiled with
g++ -std=c++14 -Wall -pedantic -o main_qi main_qi.cpp -O2
and
g++ -std=c++14 -Wall -pedantic -o main_x3 main_x3.cpp -O2

The binaries are executed with the number of iterations and output the runtime and the success, e.g.:

./main_qi 100000
Total time: 8798ms
#parsed: 100000, success: 100000

./main_x3 100000
Total time: 17005ms
#parsed: 100000, success: 100000

The Qi version is parameterized by giving the field separator to the constructor, for X3 there are several versions: one where `x3::with<>` is used, closest resembling the Qi variant, one where the field separator is fixed, and one where also no semantic actions (via lambdas) are used. Each parser lies in its namespace.

Since for each of the given input strings the Qi parser peforms better, I'm wondering whether the "translation" from Qi to X3 is correct and what is causing this rather unexpected result.

Best regards,
Sandro

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today.http://sdm.link/xeonphi
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general

input.hpp (64K) Download Attachment
main_qi.cpp (5K) Download Attachment
main_x3.cpp (12K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

sehe
On 12-12-16 13:17, Sandro Pirkwieser wrote:
Since for each of the given input strings the Qi parser peforms better, I'm wondering whether the "translation" from Qi to X3 is correct and what is causing this rather unexpected result.
First, on the performance. I agree that it disappoints. I'd rate that a regression. It appears as though `parse_into_container` involves a lot of redundant copying where Qi doesn't do that.  Anyone who can have a look at that, please use my version (linked) below, which is A LOT cleaner but doesn't perform significantly better.

The binaries are executed with the number of iterations and output the runtime and the success, e.g.:

./main_qi 100000
Total time: 8798ms
#parsed: 100000, success: 100000

./main_x3 100000
Total time: 17005ms
#parsed: 100000, success: 100000

I've cleaned the stuff up. (By the way, the Qi grammar seemed also pretty overcomplicated).
And I used Nonius to get benchmarks. The "baseline" (exactly your code after fixing minimal compilation issues) score like this interactive chart.

The code cleanup can be found at

    git clone https://gist.github.com/7dc223f00d8cc46d8be566756b7fdf03.git

After cleanup, the Qi version is still a lot faster.


The resultant X3 neatly expresses why I don't think modularity of X3 is any problem. It employs only one or two tricks, which **exploit** the fact that X3 is actually /just c++ code/ and behaves as such:

namespace csv {
    template <typename Sep>
    auto make_csv_parser(Sep fieldSep) {
        using namespace boost::spirit::x3;

        using R = rule<struct _, CsvString>;

        auto unescaped = R{"raw"}    = *(~char_("\"\r\n") - fieldSep);
        auto escaped   = R{"quoted"} = *(~char_('"') | '"' >> char_('"'));
        auto lineBreak = eol;

        auto field = R{"field"} =
            (*lit(' ') >> ('"' > escaped > '"') >> *lit(' '))
            | unescaped; // the order is important because unescaped can consume zero characters

        auto record = rule<struct _, CsvRecordInformation>{ "record" } =
            field % fieldSep;

        auto file   = rule<struct _, CsvFileInformation>{ "file" } =
            ((!eoi > record) % lineBreak) > -lineBreak > eoi;

        return file;
    };
}

Interestingly, that's already not requiring any semantic action, nor using `with<>`.
See how vanilla c++14 allows a lot more power in more elegant/simple ways? Here's how you'd derive the version with a fixed delimiter and no semantic actions:

namespace csv_fixed_separator_no_semantic_actions {
    using namespace boost::spirit::x3;
    auto static const file = csv::make_csv_parser(ascii::lit(',')); // just making a point
}

The benchmark driver actually ensures all the features are intact (by comparing a digest of the data) and also that the resulting containers contain exactly the same data as when parsed using Qi.

Hope this helps someone spot an improvement/cause of the poor performance.

Cheers,
Seth

Some related resources:

Final text benchmark report:

clock resolution: mean is 17.8377 ns (40960002 iterations)

benchmarking x3 new
collecting 100 samples, 1 iterations each, in estimated 10.2235 ms
mean: 876.397 μs, lb 870.347 μs, ub 901.83 μs, ci 0.95
std dev: 53.9835 μs, lb 5.06288 μs, ub 126.228 μs, ci 0.95
found 7 outliers among 100 samples (7%)
variance is severely inflated by outliers

benchmarking qi dynamic
collecting 100 samples, 3723 iterations each, in estimated 1489.2 μs
mean: 139.493 ns, lb 139.444 ns, ub 139.558 ns, ci 0.95
std dev: 0.287948 ns, lb 0.22991 ns, ub 0.352594 ns, ci 0.95
found 17 outliers among 100 samples (17%)
variance is unaffected by outliers


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

cppljevans
On 12/13/2016 11:56 AM, Seth wrote:
> On 12-12-16 13:17, Sandro Pirkwieser wrote:
>> Since for each of the given input strings the Qi parser peforms better, I'm wondering whether the "translation" from Qi to X3 is correct and what is causing this rather unexpected result.
> First, on the performance. I agree that it disappoints. I'd rate that a
> regression. It appears as though `parse_into_container` involves a lot
> of redundant copying where Qi doesn't do that.  Anyone who can have a
> look at that, please use my version (linked) below, which is A LOT
> cleaner but doesn't perform significantly better.
[snip]
> The code cleanup can be found at
>
>     git clone https://gist.github.com/7dc223f00d8cc46d8be566756b7fdf03.git
>
> After cleanup, the Qi version is still a lot faster
> <http://stackoverflow-sehe.s3.amazonaws.com/e44a2c1d-356f-4773-bb51-22d307621a29/stats.html>.
>

I want to make sure I'm reading that graph correctly.
It says that the average time using 'x3 new' is 870,000 ns; whereas
the average time using 'qi dynamic' is only 137 ns?

BTW, thanks doing this :)

-regards,
Larry



------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Michael Powell-2
On Tue, Dec 13, 2016 at 4:55 PM, Larry Evans <[hidden email]> wrote:

> On 12/13/2016 11:56 AM, Seth wrote:
>> On 12-12-16 13:17, Sandro Pirkwieser wrote:
>>> Since for each of the given input strings the Qi parser peforms better, I'm wondering whether the "translation" from Qi to X3 is correct and what is causing this rather unexpected result.
>> First, on the performance. I agree that it disappoints. I'd rate that a
>> regression. It appears as though `parse_into_container` involves a lot
>> of redundant copying where Qi doesn't do that.  Anyone who can have a
>> look at that, please use my version (linked) below, which is A LOT
>> cleaner but doesn't perform significantly better.
> [snip]
>> The code cleanup can be found at
>>
>>     git clone https://gist.github.com/7dc223f00d8cc46d8be566756b7fdf03.git
>>
>> After cleanup, the Qi version is still a lot faster
>> <http://stackoverflow-sehe.s3.amazonaws.com/e44a2c1d-356f-4773-bb51-22d307621a29/stats.html>.

"A lot"? You are being too modest...

> I want to make sure I'm reading that graph correctly.
> It says that the average time using 'x3 new' is 870,000 ns; whereas
> the average time using 'qi dynamic' is only 137 ns?
>
> BTW, thanks doing this :)
>
> -regards,
> Larry
>
>
>
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> Spirit-general mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-general

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

sehe
On 13-12-16 22:55, Larry Evans wrote:
I want to make sure I'm reading that graph correctly.
It says that the average time using 'x3 new' is 870,000 ns; whereas
the average time using 'qi dynamic' is only 137 ns?

Yes. Note you can use the drop-down to see the individual samples, so you can sense the spread of them too.

Note also you can hide data series by clicking the legend labels.

On 13-12-16 22:04, Michael Powell wrote:
After cleanup, the Qi version is still a lot faster
>> <http://stackoverflow-sehe.s3.amazonaws.com/e44a2c1d-356f-4773-bb51-22d307621a29/stats.html>.
"A lot"? You are being too modest...

Well. I did start off with the bad news because I think it's a performance /bug/.
I agree that the performance doesn't entice a move to X3 for this particular grammar :)

I haven't understood it fully but the profiler results seem to point at `parse_into_container` and `std::....::basic_string::aux_replace` (quoting from memory)


BTW, thanks doing this 

-regards,
Larry
And thanks to Sandro for coming through with the interesting sample code to manifest this behaviour.


Seth


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

gillesb68

QI seems mature, but X3 look promising. However, I experiment an embarrassing matter on QI (see the ticket no https://svn.boost.org/trac/boost/ticket/12497) and would like to draw your attention to it, since I think that both QI and X3 have the same behavior. Fixing it would change your mind a little. 


Gilles

De : Seth <[hidden email]>
Envoyé : 13 décembre 2016 16:31
À : Spirit General Mailing List
Objet : Re: [Spirit-general] Design/structure X3 parser more like Qi parser
 
On 13-12-16 22:55, Larry Evans wrote:
I want to make sure I'm reading that graph correctly.
It says that the average time using 'x3 new' is 870,000 ns; whereas
the average time using 'qi dynamic' is only 137 ns?

Yes. Note you can use the drop-down to see the individual samples, so you can sense the spread of them too.

Note also you can hide data series by clicking the legend labels.

On 13-12-16 22:04, Michael Powell wrote:
After cleanup, the Qi version is still a lot faster
>> <http://stackoverflow-sehe.s3.amazonaws.com/e44a2c1d-356f-4773-bb51-22d307621a29/stats.html>.
"A lot"? You are being too modest...

Well. I did start off with the bad news because I think it's a performance /bug/.
I agree that the performance doesn't entice a move to X3 for this particular grammar :)

I haven't understood it fully but the profiler results seem to point at `parse_into_container` and `std::....::basic_string::aux_replace` (quoting from memory)


BTW, thanks doing this 

-regards,
Larry
And thanks to Sandro for coming through with the interesting sample code to manifest this behaviour.


Seth


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Gilles
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

sehe
On 13-12-16 22:49, Gilles BRUNET wrote:
>
> Fixing it would change your mind a little.
>
>
> Gilles

Please don't hijack conversation threads. You can post a new topic instead


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Sandro Pirkwieser
In reply to this post by sehe

Thank you Seth for your work and the really nice presentation of the results.

Credits for the cleanup, too. Definitely helps for further analysis.

 

So, when measuring the time of the parse() calls only, then the ratio of X3/Qi – according to your plots – is several thousand (above 6K).

I also repeated the tests of measuring the whole runtime, iterating e.g. 1000 times over testdata[]. There the ratio is (still) somewhat above 2.

When profiling, I also noticed the boost::spirit::detail::parse_into_container<>() calls, which are visible with -O1, scoring above 90%.

 

Best  regards,

Sandro


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

cppljevans
In reply to this post by sehe
On 12/13/2016 11:56 AM, Seth wrote:
[snip]

> The resultant X3 neatly expresses why I don't think modularity of X3 is
> any problem. It employs only one or two tricks, which **exploit** the
> fact that X3 is actually /just c++ code/ and behaves as such:
>
>     namespace csv {
>         template <typename Sep>
>         auto make_csv_parser(Sep fieldSep) {
>             using namespace boost::spirit::x3;
>
>             using R = rule<struct _, CsvString>;
>
>             auto unescaped = R{"raw"}    = *(~char_("\"\r\n") - fieldSep);
>             auto escaped   = R{"quoted"} = *(~char_('"') | '"' >>
>     char_('"'));
>             auto lineBreak = eol;
>
>             auto field = R{"field"} =
>                 (*lit(' ') >> ('"' > escaped > '"') >> *lit(' '))
>                 | unescaped; // the order is important because unescaped
>     can consume zero characters
>
>             auto record = rule<struct _, CsvRecordInformation>{ "record" } =
>                 field % fieldSep;
>
>             auto file   = rule<struct _, CsvFileInformation>{ "file" } =
>                 ((!eoi > record) % lineBreak) > -lineBreak > eoi;
>
>             return file;
>         };
>     }
>
[snip]
This doesn't use BOOST_SPIRIT_DEFINE, and I don't think it can
because that would generate one or more parse_rule's template functions
within the make_csv_parser function.  Is that right?
If so, then wouldn't that make this method slower to compile than if
BOOST_SPIRIT_DEFINE could be used?

-regards,
Larry




------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

cppljevans
On 12/18/2016 08:50 AM, Larry Evans wrote:

> On 12/13/2016 11:56 AM, Seth wrote:
> [snip]
>> The resultant X3 neatly expresses why I don't think modularity of X3 is
>> any problem. It employs only one or two tricks, which **exploit** the
>> fact that X3 is actually /just c++ code/ and behaves as such:
>>
>>     namespace csv {
>>         template <typename Sep>
>>         auto make_csv_parser(Sep fieldSep) {
>>             using namespace boost::spirit::x3;
>>
>>             using R = rule<struct _, CsvString>;
>>
>>             auto unescaped = R{"raw"}    = *(~char_("\"\r\n") - fieldSep);
>>             auto escaped   = R{"quoted"} = *(~char_('"') | '"' >>
>>     char_('"'));
>>             auto lineBreak = eol;
>>
>>             auto field = R{"field"} =
>>                 (*lit(' ') >> ('"' > escaped > '"') >> *lit(' '))
>>                 | unescaped; // the order is important because unescaped
>>     can consume zero characters
>>
>>             auto record = rule<struct _, CsvRecordInformation>{ "record" } =
>>                 field % fieldSep;
>>
>>             auto file   = rule<struct _, CsvFileInformation>{ "file" } =
>>                 ((!eoi > record) % lineBreak) > -lineBreak > eoi;
>>
>>             return file;
>>         };
>>     }
>>
> [snip]
> This doesn't use BOOST_SPIRIT_DEFINE, and I don't think it can
> because that would generate one or more parse_rule's template functions
> within the make_csv_parser function.  Is that right?
> If so, then wouldn't that make this method slower to compile than if
> BOOST_SPIRIT_DEFINE could be used?
>
In contrast, the following:

https://github.com/cppljevans/spirit/blob/ExagonLinkingError/workbench/x3/rule_defns/parse_rule_crtp.cpp

shows a *prototype* of how to emulate the qi method in a revised x3
*and* use something like BOOST_SPIRIT_DEFINE.

This parse_rule_crtp prototype modifies the spirit
parse_rule by returning a rule_definition instead of using a
rule_definition within it's body.  This returned
rule_definition is then used in the gram_base::rule::parse
function.  It also defines specializations of parse_rule in
the *derived* class and uses CRTP to invoke those
specializations in the gram_base::rule::parse function.

This use of BOOST_SPIRIT_DEFINE avoids the extra compile time
needed by make_csv_parser method above; hence, Seth, I'm wondering
what the advantage of *not* using the BOOST_SPIRIT_DEFINE method
for associating a rule with it's rule_definition?

As the comments at the top indicate, I question (as Seth did in an
earlier post) whether there's any advantage to this method.
Hence, Sandro, could you provide some use-case for this feature?

-regards,
Larry





------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Design/structure X3 parser more like Qi parser

Sandro Pirkwieser
Hi Larry,

> This doesn't use BOOST_SPIRIT_DEFINE, and I don't think it can because
> that would generate one or more parse_rule's template functions within
> the make_csv_parser function.  Is that right?
> If so, then wouldn't that make this method slower to compile than if
> BOOST_SPIRIT_DEFINE could be used?

yes, to my knowledge using BOOST_SPIRIT_DEFINE inside a function, e.g. make_csv_parser, is not possible.
But I don't know whether this influences compile time.

> In contrast, the following:
> https://github.com/cppljevans/spirit/blob/ExagonLinkingError/workbench/x3/rule_defns/parse_rule_crtp.cpp
> shows a *prototype* of how to emulate the qi method in a revised x3
> *and* use something like BOOST_SPIRIT_DEFINE.
> This parse_rule_crtp prototype modifies the spirit parse_rule by returning a rule_definition instead of using a rule_definition within it's body.
> This returned rule_definition is then used in the gram_base::rule::parse function.
> It also defines specializations of parse_rule in the *derived* class and uses CRTP to invoke those specializations in the gram_base::rule::parse function.

> This use of BOOST_SPIRIT_DEFINE avoids the extra compile time needed by make_csv_parser method above;
> hence, Seth, I'm wondering what the advantage of *not* using the BOOST_SPIRIT_DEFINE method for associating a rule with it's rule_definition?

> As the comments at the top indicate, I question (as Seth did in an earlier post) whether there's any advantage to this method.
> Hence, Sandro, could you provide some use-case for this feature?

The main topic (aside the more recent performance analysis) was the question to "better" (at least in my view) encapsulate an X3 parser than with namespaces, i.e. more in the style of a Qi parser. There a larger, more complex parser can be built by incorporating several smaller ones as class members, yet retaining a nice encapsulation. Something that does not seem possible with X3.
An alternative, using parsers defined in functions (as for make_csv_parser), is not always an option though, as such parsers cannot be recursive (rule A is defined via rule B and vice versa).

Your prototype allows using BOOST_SPIRIT_DEFINE inside a struct, hence would definitely come closer to the Qi like encapsulation.
I haven't tried it yet, but is it also possible to use parameters, like the field separator fort the CSV parser? As it can't be given at the time of construction, as for make_csv_parser(), one could probably use x3::with<>.

Best regards,
Sandro

------------------------------------------------------------------------------
Developer Access Program for Intel Xeon Phi Processors
Access to Intel Xeon Phi processor-based developer platforms.
With one year of Intel Parallel Studio XE.
Training and support from Colfax.
Order your platform today.http://sdm.link/intel
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
12
Loading...