Re: Design/structure X3 parser more like Qi parser

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
<http://stackoverflow-sehe.s3.amazonaws.com/c534503c-b843-4203-a016-bf4505f29c3a/stats.html>.

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>.


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:

  * https://github.com/rmartinho/nonius

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
[email protected]
https://lists.sourceforge.net/lists/listinfo/spirit-general