[Haskell-cafe] Impact of "try" on Parsec performance

[Antoine Latter]

On Fri, Mar 2, 2012 at 10:30 PM, Omari Norman <omari at smileystation.com> wrote:
> The Parsec documentation says that Parsec performs best on predictive
> grammars, and Parsec does not backtrack by default to improve performance
> (though this also improves error messages).
>

A big thing that parsec strives to do is to "forget" consumed portions
of the input as quickly as possible, allowing it to be collected.

Using 'try' forces the program to hold on to input for longer than
would be required if the grammar were factored to avoid 'try'.

> The Parsec documentation says there is a penalty for using try and suggests
> left-factoring grammars when possible. Real World Haskell says that
> excessive use of try can degrade Parsec performance quite significantly. On
> the other hand, some of the combinators provided with Parsec, such as
> notFollowedBy, use try.
>

The assumption is that 'notFollowedBy' is primarily used with 'short'
parsers, which means the amount of input we need to preserve is less
(also, I think using 'try' is the only way to implement
'notFollowedBy').

> So my question is: what is the practical impact of using try? I ask because
> as a novice I have a simple grammar that could, perhaps, be factored to
> avoid use of try, but it's quite a brain puzzle for me and I wonder if it
> would ever be worth it. Does it matter how many characters "try" would have
> to store, or how often it would run?
>

I guess you could test running a parser which always fails without
consuming input both underneath a 'try' and not, to see what
non-storage overhead 'try' has.

I'm guessing the overhead would be minimal, but I have not measured it.

Antoine