<div dir="ltr"><div>Hi,</div><div><br></div><div>Recently I was improving performance of simple-sql-parser library which sits on top of megaparsec. <br></div><div>Main issue was memory consumption, not speed. Machine generated SQL query might weigh megabytes.</div><div>I got success with a deduplicating cache for lexer tokens. <br></div><div><br></div><div>A complex parser produces very chunky lazy text. <br></div><div>To avoid traversing these linked lists (cache locality) and copying to strict one <br></div><div>- offsets in the input Text  are analyzed before and after success return from parser => shallow substring which is deduplicated with high probability and no extra memcpy.<br></div><div></div><div><br></div><div>Another interesting idea, I would like to try, is to use ByteString for text input and mmap input byte string. <br></div><div>SQL query is 99% ASCII only and all keywords are ASCII bytes. <br></div><div>So knowing that constraint parser doesn't spend time on reconstructing characters out of impossible multibyte input,</div><div>when it expects keywords.<br></div><div><br></div><div>Megaparsec doesn't have digital search tree, which help a lot with avoiding  back tracking.</div><div><br></div><div>Thanks<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Nov 8, 2022 at 3:32 PM Olaf Klinke <<a href="mailto:olf@aatal-apotheke.de">olf@aatal-apotheke.de</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear Haskellers,<br>
<br>
megaparsec [1] is a parsing library with excellent error<br>
reporting. Being able to emit decent parse error messages is traded off<br>
against speed, however. Wouldn't it be nice to have a faster parser for<br>
your daily parsing needs, but obtain megaparsec's informative error<br>
messages for the rare cases when things go wrong? <br>
<br>
Thanks to megaparsec's parser type class, MonadParsec, you can have<br>
both: I wrote a MonadParsec instance for StateT s Maybe (s being the<br>
input stream type such as Text or ByteString) which does not do all the<br>
bookkeeping ParsecT needs to do. If you manage to write your parser<br>
only using the type class primitives, then you can specialize your<br>
parser to StateT s Maybe. Only if that returns Nothing specialize again<br>
to ParsecT Void s and parse the input again, thus obtaining a decent<br>
error message. The package faster-megaparsec [1,2] provides a<br>
convenient function to do just that. <br>
<br>
Of course StateT s Maybe can not provide all the features ParsecT has:<br>
* StateT s Maybe is always backtracking.<br>
* It does not know the offset in the stream.<br>
* It must hold the entire input stream in memory for a second pass, <br>
  so no garbage collecting the consumed input while parsing.<br>
So if your parsing relies on non-backtracking choice, stream offset or<br>
garbage-collecting input while parsing, you can not use faster-<br>
megaparsec as a drop-in replacement. <br>
<br>
Happy parsing!<br>
Olaf<br>
<br>
[1] <a href="https://hackage.haskell.org/package/megaparsec" rel="noreferrer" target="_blank">https://hackage.haskell.org/package/megaparsec</a><br>
[2] <a href="https://hackage.haskell.org/package/faster-megaparsec" rel="noreferrer" target="_blank">https://hackage.haskell.org/package/faster-megaparsec</a> <br>
[3] <a href="https://hub.darcs.net/olf/faster-megaparsec" rel="noreferrer" target="_blank">https://hub.darcs.net/olf/faster-megaparsec</a><br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="gmail_signature"><br>Best regards,<br>Daniil Iaitskov<br> <br><br><br></div>