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

Roman Cheplyaka roma at ro-che.info
Sat Mar 3 11:17:47 CET 2012


* Omari Norman <omari at smileystation.com> [2012-03-02 23:30:22-0500]
> 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).
> 
> On the other hand, I notice that attoparsec and polyparse backtrack by
> default, and attoparsec claims to be faster than Parsec (I can't remember
> if polyparse makes this claim).

Attoparsec's goal is to be fast in practice. It achieves this goal by
making some compromises -- e.g. being potentially asymptotically slower
and admitting potential memory leaks, because of the unrestricted
backtracking.
Often this doesn't happen or isn't significant, but I believe users
should be aware of this.

I think the speed benefit of not restricting backtracking comes just
from allocating less continuations. Bryan, can you confirm?

Although Polyparse permits backtracking by default, it is still closer to
Parsec in that it allows controlled backtracking.

-- 
Roman I. Cheplyaka :: http://ro-che.info/



More information about the Haskell-Cafe mailing list