Re: further thoughts on adaptive parse algorithms

Frank Birbacher wrote:
> Hi!
>
> Tobias Schwinger wrote:
>
> > Another interesting idea is to apply "loop unrolling" to Kleene if many
> > matches are expected: Instead of
> >
> >   *a
> >
> > we could write
> >
> >     *(a >> a >> a >> a >> a >> a >> a >> a)
> >  >> !(a >> a >> a >> a)
> >  >> !(a >> a)
> >  >> ! a
> >
> > and if "a" is a parser that doesn't have to save the iterator position
> > per se, we'd reduce iterator copying down to asymptotically 1/8th in
> > this case.
>
>
> To me it looks like the 'a' parser could probably be invoked
> 4 times failing before the whole thing is done. 

So what? It's just a matter of scale. With e.g. 100 repetitions we are talking 
about ~80 iterator copies vs. ~4 failed parses (rough averages)...

> Is this worth the trouble? 

It pretty much comes down to whether there are cases where we expect kleene to 
match often enough.

> Let's see.
>
> If 'a' was a primitive, then you would not need much optimizing. The
> standard '*a' would give a nice tight loop.

Do I understand you correctly. Are you saying that a loop with two copy ops is 
better than a loop with one copy op plus sorta-duffing?

> If 'a' was a complex parser then you would trade some iterator copying
> for retrying this complex parser a few times.

...where especially complex parsers usually fail much quicker than they succeed. But right - it doesn't make much sense, here. 

> To me the unrolling approach doesn't look promising. Did I miss something?

Once there is enough infrastructure it's pretty easy to implement a hard-wired 
version, say a comment skipper, and find out what it brings.

Note that it was not intended to be used globally - the user would have to 
enable it.


Another thought on the self-calibrating Kleene: 

The average number of repetitive matches might also be interesting for 
std::vector::reserve-kind-of operations when gathering data from the input...


Regards,

Tobias



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642