Hello,

Our existing parsing code is quite different than any other parser
APIs I've seen in Haskell. I want to be able to experiment with other
parser libraries, but the notational differences makes this quite
hard.

This set of patches changes that.  It uses the same underlying parser
abstractions that darcs has been using for years, but it exposes the
API in a way that is consistent with other parser libraries.  Very few
functions had to be rewritten from scratch.  Most notably,
linesStartingWithEndingWith and linesStartingWith had to be
substantially rewritten.  The tests pass and I think the code is
correct.  Of course, mores can't hurt.  Volunteers to write tests will
be loudly praised.

I wanted to run darcs-benchmark before sending the patches in, but
that takes more than 8 hours on this machine if I recall correctly.
I'll try to get those numbers as soon as possible.  Because it's using
the same underlying implementation and algorithms as previously I
don't expect to see any significant change in performance.

There are further cleanups, tuneups, and such that can be done, most
notably reducing calls to pack/unpack, but I felt it was important to
get the initial refactor out for review earlier instead of later.

I've modeled the combinators after attoparsec and I hope to try using
attoparsec as a drop in replacement to see if there is any noticable
difference.  I expect attoparsec to be slower for darcs, but it may
have new features that open doors for new opportunities.

Thanks,
Jason

11 patches for repository http://darcs.net:

Sun Jul 25 01:56:10 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * tune the patch parser
  This patch is based on a few observations:
    * alterInput (const foo), completly replaces the parser's input
    * after peekInput, the above trick avoids redundant processing
    * best to leave a packed ByteString packed

Sun Jul 25 05:06:51 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * add utility functions to ReadMonads
  The intention of these functions is that in the future we will be able
  to use more conventional notation to express parsers in the darcs source.

Sun Jul 25 06:31:32 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read and ReadMonads to remove peekInput from Read

Sun Jul 25 06:56:58 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Patchy to not use peekInput

Sun Jul 25 07:16:05 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * remove peekInput from Real.  peekInput no longer exported from ReadMonads

Sun Jul 25 07:18:55 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * cleanup import list of Patchy

Sun Jul 25 07:29:11 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports alterInput and clean up a few warnings

Sun Jul 25 07:44:03 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read to use myLex'

Sun Jul 25 07:46:18 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports myLex, clean up imports in Real

Sun Jul 25 09:33:59 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read to not rely on 'work'

Sun Jul 25 10:51:20 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports maybeWork fix other modules to match

Attachments

• tune-the-patch-parser.dpatch
• unnamed

On Sun, Jul 25, 2010 at 18:08:36 +0000, Jason Dagit wrote:
> This set of patches changes that.  It uses the same underlying parser
> abstractions that darcs has been using for years, but it exposes the
> API in a way that is consistent with other parser libraries.  Very few
> functions had to be rewritten from scratch.  Most notably,
> linesStartingWithEndingWith and linesStartingWith had to be
> substantially rewritten.  The tests pass and I think the code is
> correct.  Of course, mores can't hurt.  Volunteers to write tests will
> be loudly praised.

It sounds like this patch presents a good opportunity to develop some
parser-specific tests in our unit and functional testing suites.

For example, do we already have generate/parse roundtrip QuickChecks?
Could we have tests that target individual functions used by the parser?

These aren't questions specifically for Jason, just sort of thinking
aloud about chances to usefully extend our test coverage

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, please try +44 (0)1273 64 2905.

If I may send this one your way, Ganesh...

The benchmark is still running, but it has produce partial results and the results look quite promising.  Whatsnew is improved 
quite a bit.  Unrevert might be slightly slower and everything else seems to be unaffected:


==============  ==========  ========  ================  ========  =============  ========  ===================  ========
                unmodified      sdev  refactoredparser      sdev  op unmodified      sdev  op refactoredparser      sdev
==============  ==========  ========  ================  ========  =============  ========  ===================  ========
            wh      46.1ms  (10.4ms)            18.4ms   (3.2ms)         50.0ms   (8.2ms)               17.5ms   (2.3ms)
        wh mod     117.0ms  (35.5ms)           106.0ms   (6.6ms)        138.1ms  (18.1ms)              106.7ms   (6.0ms)
         wh -l      67.0ms   (2.5ms)            54.2ms   (4.8ms)         69.8ms   (7.5ms)               53.7ms   (4.5ms)
    record mod    ~562.6ms  (35.0ms)          ~587.4ms  (37.1ms)       ~560.9ms  (39.7ms)             ~578.6ms  (36.8ms)
    revert mod     134.2ms  (16.8ms)           169.5ms  (15.3ms)        143.4ms  (14.1ms)              156.3ms  (14.9ms)
(un)revert mod     334.6ms   (9.2ms)           411.5ms  (17.7ms)        366.5ms  (34.6ms)              392.9ms  (14.4ms)
    get (full)    ?7m48.5s    (3.6s)          ?7m50.0s   (10.4s)       ?7m43.1s    (2.3s)             ?7m34.3s    (7.5s)
    get (lazy)      ?17.9s    (2.3s)            ?17.5s    (3.7s)         ?15.1s    (0.3s)               ?14.7s    (0.8s)
      pull 100       ?3.1s    (0.1s)             ?3.5s    (0.5s)          ?3.1s    (0.2s)                ?3.2s    (0.3s)
     pull 1000      ?20.4s    (0.7s)            ?21.3s    (0.6s)         ?21.1s    (0.7s)               ?21.9s    (1.2s)
         check      ?14.5s    (0.1s)            ?16.3s    (0.0s)         ?14.5s    (0.0s)               ?16.3s    (0.0s)
        repair      ?14.5s    (0.0s)            ?16.3s    (0.0s)         ?14.5s    (0.1s)               ?16.3s    (0.0s)
      annotate       ?8.9s    (0.0s)            ?13.0s    (0.1s)          ?8.9s    (0.0s)               ?17.5s    (6.9s)
==============  ==========  ========  ================  ========  =============  ========  ===================  ========

I have created a ticket requesting more tests: issue1899

On Mon, Jul 26, 2010 at 00:17:08 +0000, Jason Dagit wrote:
> The benchmark is still running, but it has produce partial results and
> the results look quite promising.  Whatsnew is improved quite a bit.
> Unrevert might be slightly slower and everything else seems to be
> unaffected:

That's very interesting.

It may be helpful to target the parser specifically with some stress
tests, ie. instead of benchmarking, build a suite of increasingly
large/complex patches and also of patch bundles.  Save time and learn
more? [then again, the benchmarking also implicitly tells us how
important (or not) parsing performance actually is... for example, we
could learn that it actually doesn't matter, so we can afford to just go
for the cleanest/nicest code we can get]

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, please try +44 (0)1273 64 2905.

Why would whatsnew be affected by changes to the patch parser? Petr tells 
me that the benchmarks don't have anything in pending, so it can't be 
that.

The benchmark suite finished.  It took over 24 hours.  I have pasted the 
output into the wiki, but it's somewhat suspect because I was using my 
computer during that 24 hour period on and off.  Should the benchmark 
suite really take 30 hours?

http://wiki.darcs.net/Benchmarks/ParserRefactor

Jason Dagit <bugs@darcs.net> writes:
> The benchmark suite finished.  It took over 24 hours.  I have pasted the 
> output into the wiki, but it's somewhat suspect because I was using my 
> computer during that 24 hour period on and off.  Should the benchmark 
> suite really take 30 hours?
Is that on a Mac? It seems that darcs on OSX has serious trouble with
filesystem performance: doing a full get of GHC takes nearly half an
hour in your benchmarks: on a standard Linux box, it takes about 20
*seconds* (that would also explain why it takes 30 hours for you).

Yours,
   Petr.

On Mon, Jul 26, 2010 at 17:45:57 +0000, Jason Dagit wrote:
> The benchmark suite finished.  It took over 24 hours.  I have pasted the 
> output into the wiki, but it's somewhat suspect because I was using my 
> computer during that 24 hour period on and off.  Should the benchmark 
> suite really take 30 hours?
> 
> http://wiki.darcs.net/Benchmarks/ParserRefactor

We should be down to 15 hours thanks to dropping the non-op repos in
darcs-benchmark 0.1.8.3, but still a pain.

darcs-benchmark run --fast should also eliminate some of the slower
benchmarks (full darcs get and darcs annotate).  Hmm, patch parsing
could play some role in darcs annotate.

Alternatively, you can select which benchmarks you want to run by
passing in the only flag, eg.

darcs benchmark run darcs-before darcs-after / ghc-hashed --only annotate

Also, you commented [1]:
> From your ticket updates I get the impression it also doesn't
> currently benchmark anything we care about.  I thought that was the
> point of darcs-benchmark.

I believe you're referring to the comment in which I said it would be
useful to think about some parser-intensive benchmarks [2].

We need to be more precise about "benchmark anything we care about".
Right now, the benchmarking is very general, ie. we time some common
operations, get, pull, record, wh.  Some questions which would arise
from your comment are

* For general purposes: that *sounds* like something we care about,
  although if you have ideas on how to improve the benchmarks to be
  more meaningful from a darcs-user perspective, I'm all ears.

* For parser-hacking purposes: is it worthwhile to benchmark
  something more highly targeted? The highly-targeted benchmarks
  could perhaps be artificial and have little real world consequence,
  but they could help us to tune the hell out of the parser.

In other words "what we care about" depends on the context.

Anyway, there are two ways I can think to extend the suite: either add
new benchmarks (sequences of commands with some subsequence being
timed), or add new repositories to the zoo which display
interesting/pathological characteristics...

[1] http://irclog.perlgeek.de/darcs/2010-07-26#i_2613228
[2] http://bugs.darcs.net/msg11869

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, please try +44 (0)1273 64 2905.

> or add new repositories to the zoo which display
> interesting/pathological characteristics...

Would you be opposed to a repository created like this:
 a) download linux kernel tarball
 b) untar it
 c) darcs init in kernel source
 d) darcs add --recursive .

That would create a massive pending.  The downside is that it's huge.  I think last time I 
did that the pending file had some 30k filepaths in it.  With that repository, when you do 
'echo d | darcs record', it really stresses our path munging code, our diffing code, and 
our pending reading code.  To display the first patch it tries to build up every patch 
that is mentioned in pending, including calculating the diffs.  Or at least, that's what 
it did about a year ago.  I don't know that it stresses the parser in an interesting way.  
Mainly because hunks are not stored in the pending.  So it would stress filepath parsing 
and I know that all the character escaping we do is really costly on that pathological 
example.

Reading the inventory and changes from a big repository are good ways to benchmark the 
patchinfo parser.  I suspect that won't challenge the actual patch parser though.  I think 
to challenge it you would need to display the patches.  Perhaps some xml output from 
changes would do that?  Perhaps it's enough to just do 'darcs changes -s'.

I think the main places where the parser needs to be fast is reading hunk lines (which 
means optimizing linesStartingWith), reading patchinfos, and picking the correct patch 
type in readPrim.  For the latter, what I mean, is that it branches based on primitive 
patch type but it has to look at the next token to figure out which branch to take. We 
could do some sort of statistics over some existing repos (say ghc, darcs, and xmonad) and 
figure out which repository types are the most common and put those at the top of the 
alternatives.  So, if hunk patches are the most common that option should come first as 
it's the path that will be taken most often.

I hope that helps or gives some ideas.

On Wed, Jul 28, 2010 at 04:00:11 +0000, Jason Dagit wrote:
> Would you be opposed to a repository created like this:
>  a) download linux kernel tarball
>  b) untar it
>  c) darcs init in kernel source
>  d) darcs add --recursive .

I would not be opposed (rather the contrary), but if it gets horrible in
terms of hugeness, I'd like to see extra infrastructure (A) so that users
can explicitly opt-in and (B) so that you can have per-repository sets
of tests.  I may be thinking about this is in the wrong terms by the way,
but that's the current way I'd approach the problem.

Also you'll want to be careful to stick to the same tarball so that we
don't have a moving target.

-- 
Eric Kow <http://www.nltg.brighton.ac.uk/home/Eric.Kow>
For a faster response, please try +44 (0)1273 64 2905.

Eric Kow <bugs@darcs.net> writes:

> Eric Kow <kowey@darcs.net> added the comment:
>
> On Wed, Jul 28, 2010 at 04:00:11 +0000, Jason Dagit wrote:
>> Would you be opposed to a repository created like this:
>>  a) download linux kernel tarball
>>  b) untar it
>>  c) darcs init in kernel source
>>  d) darcs add --recursive .
>
> I would not be opposed (rather the contrary), but if it gets horrible in
I am opposed, however. It is something darcs-benchmark was not designed
for, and most benchmarks would be completely meaningless in such a
repo. I would concede if darcs-benchmark was extended with "non-repo"
benchmarks (that would create their own repository, e.g.) -- touching a
few thousand files in a couple directories programatically is sure
simpler than tarring up such a huge code base. Even if you wanted to add
content to the files, it wouldn't be anything really complex. Even if
you insist on providing a tarball, this repository would need specific
benchmarks, different from other repositories, benchmarks that wouldn't
make much sense in the others. We currently have no way to say that
(although it can be certainly done).

(I still think synthetic repositories would work better here.)

Yours,
   Petr.

On Wed, 28 Jul 2010, Jason Dagit wrote:

> Reading the inventory and changes from a big repository are good ways to benchmark the
> patchinfo parser.  I suspect that won't challenge the actual patch parser though.  I think
> to challenge it you would need to display the patches.  Perhaps some xml output from
> changes would do that?  Perhaps it's enough to just do 'darcs changes -s'.

One point about the patch parser: the patch format itself is a poor 
representation as each line has to be read individually. Igloo designed an 
alternative based on byte offsets instead, which we should move to 
eventually.

Ganesh

Ganesh, while I agree the current patch 
format is suboptimal, I think fixing it 
is beyond the scope of refactoring here. 
I also think that having a parser which 
uses a more conventional API will help 
support the change you are suggesting. My 
thought is that what you suggest is 
important, but not relavent to this patch 
bundle. 

Could you please create a new issue with 
a link to the format you are proposing?

Thanks!
Jason

I was just responding to the discussion of benchmarking and further 
improving the current parser, which is also not directly relevant to this 
bundle. Any submitted patches that improve the current parser should 
certainly get reviewed.

> Sun Jul 25 09:56:10 BST 2010  Jason Dagit <dagit@codersbase.com>
>   * tune the patch parser
>   This patch is based on a few observations:
>     * alterInput (const foo), completly replaces the parser's input
>     * after peekInput, the above trick avoids redundant processing
>     * best to leave a packed ByteString packed


BC.unpack xs == "<" vs BC.singleton '<' (new)

is the latter really better?  I'd like to see the generated 
code or get word from a ByteString expert.

You've removed initial calls to 'work myLex' in many places - isn't 
this behaviour changing? OTOH the tests pass...

the whole 'alterInput' thing feels messy. Since it's barely used
after the whole chain of patches I won't worry further about that.

> Sun Jul 25 13:06:51 BST 2010  Jason Dagit <dagit@codersbase.com>
>   * add utility functions to ReadMonads
>   The intention of these functions is that in the future we will be 
able
>   to use more conventional notation to express parsers in the darcs 
source.

Generally fine.

Are the rather ugly separate definitions of bindSM 
etc necessary for performance? If so it's a shame GHC can't 
handle this better. My uninformed speculation would be that the 
definitions (whether in the typeclass or not) would get inlined 
as small anyway.

I also have concerns about the existence of try - see below.

> Sun Jul 25 14:31:32 BST 2010  Jason Dagit <dagit@codersbase.com>
>   * refactor Read and ReadMonads to remove peekInput from Read

> -          Nothing -> do s <- peekInput
> -                        case myLex s of
> -                          Just (ps', r) | ps' == BC.pack "merger" ->
> -                                          alterInput (const r) >>
> -                                          (liftM (Just . seal) $ 
readMerger True)
> -                                        | ps' == BC.pack "regrem" ->
> -                                          alterInput (const r) >>
> -                                          (liftM (Just . seal) $ 
readMerger False)
> -                          _ -> liftM (fmap (mapSeal PP)) $ readPatch' 
want_eof
> +          Nothing -> choice [ liftM (Just . seal) $ try $ readMerger 
True
> +                            , liftM (Just . seal) $ try $ readMerger 
False
> +                            , liftM (fmap (mapSeal PP)) $ try $ 
readPatch' want_eof
> +                            , return Nothing ]

The final return Nothing and the try in the previous case seem 
to be new here; it's correct since try foo <|> return Nothing = 
foo, but seems gratuitous.

I like the fact that each parser piece is now self-contained 
(knows about its own intro text). However doesn't it lead to 
myLex being called repeatedly where previously it was only 
being called once or sometimes twice? We should be sure this is 
benchmarked adequately and not a problem in practice before we 
go down that route.

Also, doesn't the use of try introduce a memory leak, since the 
old string has to be held onto until we know whether the entire 
sub-parser succeeded? Previously we would commit once we'd 
checked the first token.

I'm replying inside the bug tracker, which doesn't have a "reply" feature.  For this reason, I'm inserting "> " 
manually on the lines.  My apologies if the formatting is weird because of that.

> > Sun Jul 25 09:56:10 BST 2010  Jason Dagit <dagit@codersbase.com>
> >   * tune the patch parser
> >   This patch is based on a few observations:
> >     * alterInput (const foo), completly replaces the parser's input
> >     * after peekInput, the above trick avoids redundant processing
> >     * best to leave a packed ByteString packed
> 
> 
> BC.unpack xs == "<" vs BC.singleton '<' (new)
> 
> is the latter really better?  I'd like to see the generated 
> code or get word from a ByteString expert.

Looking at the generated code shouldn't be too difficult.  Have you ever used ghc-core?  It's a wrapper around 
ghc specifically for displaying the generated code.

Here is an example command line that you can run from the top of the repo:

cd src && ghc-core -- -XScopedTypeVariables -XUndecidableInstances -O2 -I. ../dist/build/autogen/Version.hs 
Darcs/Patch/Read.hs | less -R

Where "Darcs/Patch/Read.hs" is whatever file you want to look at.  You will of course need to do a cabal build 
first to generate dist/build/autogen/Version.hs.  You might also want to look in the cabal file to see if there 
are flags you want to pass to GHC.  I found, through trial and error, which extensions are needed to get as far 
as Read.hs.  GHC will tell you which extensions to add if you get it wrong.  Once its buffered into less you can 
search for "Darcs\.Patch\.Read\." and it should bring you to the first function in that module.  From there, 
reading the core is up to you :)  For me, it wasn't that helpful because I had a hard time mapping core to code 
in Read.hs.

Now, let me reason about why this is a good thing from a higher level than core.

xs is not a constant.  It's some token in the input stream.  The unpack is going to convert it to [Char] no 
matter what it is.  From then on we have to do traditional [Char] comparisons on it (here just (==)).  The 
alternative, is to take the constant character '<' and turn it into a bytestring where we can use the highly 
optimized bytestring functions to compare it with xs.  The next logical step, is to float the packing of '<' to 
a high enough level that the bytestring representation is just a constant within the module and it need only be 
computed once per program run.  Compare that to unpacking xs for each comparison.  I don't know if GHC did the 
floating for me, but I'd be happy to send another patch with that change if it would make you fee better about 
it.

Now, one more attempt at justifying it.  Don Stewart tells me that if you have a packed bytestring, you always 
want to leave it that way.  Minimizing unpacking is an automatic win in his book.

> You've removed initial calls to 'work myLex' in many places - isn't 
> this behaviour changing? OTOH the tests pass...

It is potentially a behavior changing change.  The trick here, is that with the existing parser, you can call 
the parsing functions without consuming input.  That's how the existing parser works.  It does a peekInput to 
get the remaining input.  Then it applies a parser function, such as myLex to that string.  This will Maybe 
return a result.  When myLex is used this way, it doesn't consume the parsers input.  You have pass myLex to the 
work parser to do that.  This result can then be used in comparisons.  After it picks the next code path, it 
commits to the decision by doing 'work myLex'.

The way things are done now is also error prone.  If the part that applies myLex is updated, then the 
corresponding 'work myLex' also must be updated to consume exactly the same thing.  It also means that we have 
to apply myLex to the input twice.  Once to get the next token and inspect it, and once later to throw it away.  
Which leads to the next comment.
 
> the whole 'alterInput' thing feels messy. Since it's barely used
> after the whole chain of patches I won't worry further about that.

I suspect you're referring to the idiom where I use 'alterInput (const s)' where s is the remaining input after 
myLex foo?  It just avoids one extra lexing on the input.  If you spend enough time with the definitions I'm 
confident that you'll agree.  I'm not the only one using that trick in the source code.  See here:
$ ack "alterInput \(const"
Darcs/Patch/Patchy.hs
216:                              Just s' -> alterInput (const s') >> ifstr

> > Sun Jul 25 13:06:51 BST 2010  Jason Dagit <dagit@codersbase.com>
> >   * add utility functions to ReadMonads
> >   The intention of these functions is that in the future we will be 
> able
> >   to use more conventional notation to express parsers in the darcs 
> source.
> 
> Generally fine.
> 
> Are the rather ugly separate definitions of bindSM 
> etc necessary for performance? If so it's a shame GHC can't 
> handle this better. My uninformed speculation would be that the 
> definitions (whether in the typeclass or not) would get inlined 
> as small anyway.

I'm really not sure.  I don't have any microbenchmarks available for the parser and the core is a bit much to 
read for me.  I can tell you this is exactly how attoparsec does it, and I know Bryan used criterion to 
benchmark it.

The reason I did it that way, is alluded to in the comment in that section, reproduced here:
-- The following instances allow us to use more conventional
-- interfaces provided by other parser libraries. The instances are
-- defined using bindSM, returnSM, and failSM to avoid any infinite,
-- or even unneccessary, recursion of instances between between
-- ParserM and Monad.  Other recursive uses will be fine, such as
-- (<|>) = mplus.

When I was working through this code, someone in #haskell suggested that if my instances for things like 
Applicative used the Monad instance I might get into some trouble.  I admit, I didn't even try it the other way.  
I don't even know if the INLINEs are needed.  If it bothers you, I can try removing it on the grounds that it's 
a premature optimization.  On the other hand, we know the parser is a bottle neck at times.  So we might as well 
optimize what we can when it's not going to be a maintenance nightmare (which I don't think the code you're 
referring to is, I think it's just not as pretty as it could be).

> I also have concerns about the existence of try - see below.
> 
> > Sun Jul 25 14:31:32 BST 2010  Jason Dagit <dagit@codersbase.com>
> >   * refactor Read and ReadMonads to remove peekInput from Read
> 
> > -          Nothing -> do s <- peekInput
> > -                        case myLex s of
> > -                          Just (ps', r) | ps' == BC.pack "merger" ->
> > -                                          alterInput (const r) >>
> > -                                          (liftM (Just . seal) $ 
> readMerger True)
> > -                                        | ps' == BC.pack "regrem" ->
> > -                                          alterInput (const r) >>
> > -                                          (liftM (Just . seal) $ 
> readMerger False)
> > -                          _ -> liftM (fmap (mapSeal PP)) $ readPatch' 
> want_eof
> > +          Nothing -> choice [ liftM (Just . seal) $ try $ readMerger 
> True
> > +                            , liftM (Just . seal) $ try $ readMerger 
> False
> > +                            , liftM (fmap (mapSeal PP)) $ try $ 
> readPatch' want_eof
> > +                            , return Nothing ]
> 
> The final return Nothing and the try in the previous case seem 
> to be new here; it's correct since try foo <|> return Nothing = 
> foo, but seems gratuitous.

If I recall correctly, I added that "return Nothing" while getting some tests to pass.  It's not the only such 
"return Nothing" so I could be mistaken.  I do recall adding one to fix a bug though.  This particular parser is 
written so that it always returns something, even if that something is Nothing.  That's somewhat of a weird 
thing to do with parsec-style parsers, but with the existing darcs parser it did make some sense.  Ideally, we 
refactor this parser so that it either fails or returns a non-Maybe value.  I didn't do that yet but there is no 
reason why other than trying not to do too much all at once.

Also, I think you're mistaken about "try foo <|> return Nothing = foo".  If the foo parser succeeds, it does 
equal foo.  When foo fails, the foo parser does not return so then the try causes the parser monad to rewind the 
input and "return Nothing" to the caller.  We have to differentiate between failing in the parser monad (no 
value is produced and that path of computation is aborted) and returning Nothing as the result of successful 
parser.  It's the difference between "Parser a" and "Parser (Maybe a)".  The parser above is in the latter 
category.

> I like the fact that each parser piece is now self-contained 
> (knows about its own intro text). However doesn't it lead to 
> myLex being called repeatedly where previously it was only 
> being called once or sometimes twice? We should be sure this is 
> benchmarked adequately and not a problem in practice before we 
> go down that route.

I have tried to provide the output of darcs-benchmark.  Please let me know if that is not sufficient evidence.  
My understanding is that darcs-benchmark is intended to cover the use cases that Real Users(tm) care about.

As per your concern, yes we probably could get better performance by allowing a 1 token peek, meaning you do 
extract the next token and return it.  Attoparsec (my current target parser library) does not support this so I 
chose not to expose that from ReadMonads.hs.

So the current parser does this inside of readPrim:
  1. It grabs all the remaining input, called s
  2. lexes s, and unpacks the result, say s'
  3. compares s' against each patch type to find the matching parser
  4. when it finds the matching parser p, it throws away s' and s (s is just a reference to remaining input, 
which does stay in memory)
  5. p is invoked on the remaining input, which is still equal to s
  6. p applies myLex to remaining input

The new parser does this inside of readPrim:
  1. gets the remaining input, called s (by def. of try function)
  2. applies some parser p, which lexes on s and compares with what it requires
  3. if lexing on s fails then we throw away our reference to s and go to 1
  4. if p found the input it requires, no redundant lexing of input is required as p is the right parser for 
this input (redundant lexing is avoided by throwing away the lexed part with alterInput)

We remove the redundant lexing in part 3, and replace it with a) redundantly fetching a reference to s (this 
should be fast), and b) lexing the next token from s for each parser.  If you compare that with the steps above, 
you will see that my version does n lexes and comparisons where n is the number of patch types, or tokens to 
look for.  The existing parser does 2 lexes and n comparisons, but it also unpacks the token so it's doing 
[Char] comparison instead of fast bytestring comparison.  As mentioned before, unpacking is bad.  Also remember 
that n here is small because we only have a few patch types to consider.

To help mitigate these O(n) lexes, we could rearrange the order that we compare the tokens thus reducing the 
average case.  I think I mentioned this previously in this ticket.  Or, I could add token peeking, although 
when/if I switch to attoparsec I'm not sure how I would implement that.  Perhaps, it can be added to attoparsec 
using the same trick I use at the end of this email to be able to push the trys further down.

I also suspect that picking the correct patch parser is not, typically, where the bottle neck is.  
linesStartingWith will be a bottle neck anytime there is a large hunk or binary patch.  I think you can see that 
linesStartingWith is probably our most performance bound parser.

> Also, doesn't the use of try introduce a memory leak, since the 
> old string has to be held onto until we know whether the entire 
> sub-parser succeeded? Previously we would commit once we'd 
> checked the first token.

You might be right about it introducing memory leaks.  This is why you ideally use try as close to the leaves as 
possible (if you think of the paths of execution in your parser as a tree of alternatives).

The existing parser, does a peek at the start.  That reference could span the entire body of readPrim, although 
in practice once you get to the "case ... of" line the reference to s can probably be marked as dead.  I don't 
know how smart the gc is about detecting an unused reference with in a scope.

In the way I have written it, the trys are not scoped over the entire body of readPrim, so that helps push the 
trys down a bit.  In the failure case of those alternatives the potential leak can be collected immediately.  In 
the success case, it's a bit trickier.  I think in that case, you can't throw it away until you get to the end 
of the parser you passed to try.  I guess that's the leak you were thinking of.

In the case of a large hunk patch, that would mean you are holding the rest of the input in memory while 
building up two separate lists of ByteString representing the old and new lines in the hunk.  Then you would 
return from the hunk parser and as try returns the gc would finally be able to collect the part of the remaining 
input that corresponds to the large hunk (but not the two lists of bytestring).  So, one way to work around 
this, would be to rewrite the readHunk like this, and check for Nothing in readPrim:

readHunk :: ParserM m => FileNameFormat -> m (Maybe (Prim C(x y)))
readHunk x = do
  x <- try (Just <$> lexString "hunk") <|> return Nothing
  case x of
    Nothing -> return Nothing
    Just _ -> do
      fi <- myLex'
      l <- int
      have_nl <- skipNewline
      if have_nl
         then do linesStartingWith ' ' -- skipping context
                 old <- linesStartingWith '-'
                 new <- linesStartingWith '+'
                 linesStartingWith ' ' -- skipping context
                 return $ Just $ hunk (fn2fp $ readFileName x fi) l old new
         else return $ Just $ hunk (fn2fp $ readFileName x fi) l [] []

I could do the same thing to the other parsers, such as readBinary.  Maybe I could even find a prettier way to 
write the above or make a new combinator for it by making a variation of lexString.

But anyway, that should fix any space leakiness that my changes could have possibly introduced.

So, if I implement the above space leak fix, do you plan to accept the patches?  I ask because if you are not 
planning to accept them I won't bother with the fix :)

Thanks for the review,
Jason

Hi,

Jason Dagit <bugs@darcs.net> writes:
> So, if I implement the above space leak fix, do you plan to accept the
> patches?  I ask because if you are not planning to accept them I won't
> bother with the fix :)

one thing before the patches are pushed -- from your darcs-benchmark
output, I gather the new parser is more than a factor of 2 slower than
the old one and this is directly reflected in darcs pull performance. I
would be wary of pushing this set unless we know for sure that this drop
in performance will be eventually (before next stable darcs) reversed.

(I am not completely on top of this set, so if that has already been
addressed and I am looking at the wrong darcs-benchmark output, please
ignore this. I was looking at
http://wiki.darcs.net/Benchmarks/ParserRefactor)

Yours,
   Petr.

Petr,

Unfortunately, darcs-benchmark has the annoying habit of combining 
previous runs with your current runs.  That means that all the 
benchmarks on that page are suspect :(  Given that the runs were taking 
> 24 hours, I had used my computer a lot during some parts of the 
benchmarks.

I had assumed that by moving my benchmarking to a new directory and 
using a ram disk that I would get clean numbers for the ramdisk part.  I 
just happened to run 'darcs-benchmark report' in a new clean ramdisk and 
discovered it had all my previous times in there :(  Eventually I found 
that darcs-benchmark stores things in ~/.darcs-benchmark.  I've removed 
this directory and I'm trying the ramdisk run again on an optimized 
version of my patches.  Less unpacking, fewer trys.

I'll report these new _clean_ timings later.

Jason

Some preliminary numbers from a clean run:

darcs-unmodified get (full) [darcs]: ...!..!..!..              ?13.5s (1.2s) 10.0M 3x
darcs-unmodified get (lazy) [darcs]: !..!..!..!..!..!..!..              ~1933.7ms (141.5ms) 3.0M 6x
darcs-unmodified pull 100 [darcs]: !.......................                ~1497.4ms (43.7ms) 8.0M 7x
darcs-unmodified pull 1000 [darcs]: ............               ?11.1s (1.5s) 33.0M 3x
darcs-unmodified check [darcs]: ............                   ?14.5s (0.0s) 23.0M 3x
darcs-unmodified repair [darcs]: ............                  ?14.5s (0.0s) 24.0M 3x
darcs-unmodified annotate [darcs]: ............                ?9.1s (0.7s) 194.0M 3x

darcs-refactoredparser2 get (full) [darcs]: ...!..!..!..       ?12.9s (0.5s) 9.0M 3x
darcs-refactoredparser2 get (lazy) [darcs]: !..!..!..!..!..!..!..       ~1878.5ms (19.7ms) 3.0M 6x
darcs-refactoredparser2 pull 100 [darcs]: !.......................         ~1491.8ms (2.4ms) 6.0M 7x
darcs-refactoredparser2 pull 1000 [darcs]: ............        ?10.0s (0.0s) 35.0M 3x
darcs-refactoredparser2 check [darcs]: ............            ?15.8s (0.4s) 22.3M 3x

Either my previous benchmarks were just wrong or my new optimizations have brought the times back down.

I'll continue testing and benchmarking before I submit new patches, but it looks like any performance 
problems are fixable before the next stable release.

I'll address one specific point quickly, as I want to take time to reply 
to the rest properly.

On Wed, 4 Aug 2010, Jason Dagit wrote:

> So, if I implement the above space leak fix, do you plan to accept the 
> patches?  I ask because if you are not planning to accept them I won't 
> bother with the fix :)

I think there are two issues to consider here: whether your use of try is 
ok, and whether it's a good idea to expose try in our parser code at all, 
for fear that someone will come along later and make seemingly innocuous 
use of it causing a serious problem.

IMO the latter point is one that should be discussed a bit more widely. My 
general impression - and I'm by no means an expert - about the existence 
of try in parser libraries is that it can be quite problematic. Here it 
would be changing the interface of the parsing library away from one which 
pretty much enforces a single pass scan. On the other hand, the benefits 
in compositionality are nice, as we can see from your patches. So I'm 
torn, but I think other people should get involved in the decision, and 
that we should perhaps investigate what parser libraries out there offer 
it.

Ganesh

>
> I'll address one specific point quickly, as I want to take time to reply
> to the rest properly.
>
> On Wed, 4 Aug 2010, Jason Dagit wrote:
>
> > So, if I implement the above space leak fix, do you plan to accept the
> > patches?  I ask because if you are not planning to accept them I won't
> > bother with the fix :)
>
> I think there are two issues to consider here: whether your use of try is
> ok, and whether it's a good idea to expose try in our parser code at all,
> for fear that someone will come along later and make seemingly innocuous
> use of it causing a serious problem.
>
> I've actually realized now that my definition of mplus has a 'try' baked
right in.  That is, it's like a two parameter version of try.  Maybe that's
what you were getting at when you said, "try foo <|> return Nothing = foo".
 So while that statement isn't completely accurate as I explained
previously, it does capture how mplus and try are similar.  The parser ended
up this way because our parsers are of the form ByteString -> Maybe (a,
ByteString).  In the failure case, you can't know how much string was
consumed before the failure.  I think it would have to be ByteString ->
(Maybe a, ByteString) for try and mplus to be significantly different.  The
immediate result, is that I can stop exposing try.  I don't know if that
version of my parser will be compatible with other parser libraries (which
was one of the initial motivating points of this refactor).  I assume that
in parsec/attoparsec that try and mplus are significantly different.  I
would need a chance to read the source code to determine if this is true.

My benchmarks suggest that mplus is not introducing a space leak that is
detectable in normal usage patterns, eg., by darcs-benchmark:
http://wiki.darcs.net/Benchmarks/ParserRefactor

I deleted the old suspect benchmarks and all that remains is my benchmark on
a ramdisk.

As I have time I'll do a benchmark with trys in there.

>
> IMO the latter point is one that should be discussed a bit more widely. My
> general impression - and I'm by no means an expert - about the existence
> of try in parser libraries is that it can be quite problematic. Here it
> would be changing the interface of the parsing library away from one which
> pretty much enforces a single pass scan. On the other hand, the benefits
> in compositionality are nice, as we can see from your patches. So I'm
> torn, but I think other people should get involved in the decision, and
> that we should perhaps investigate what parser libraries out there offer
> it.
>
> While peekInput allows us to write code that does not leak, it also makes
it really easy to write leaky code.  All you have to do is peek and then
look at the result later after applying some other parsers and you have a
leak.  Your objection to try seems to be that try is doing this for you in a
controlled way (really I mean encapsulated way).  So, try automatically
creates a leak, but the scope and size of the leak is also more predictable
because it's only the scope of the try.  The leak also goes away once the
parser finishes.  On the other hand, with try the leak is inescapable.

I would consider alterInput to be unsafe because it allows arbitrary updates
to the parser's state.  I would call that a leaky abstraction or abstraction
violation.  My software engineering sensibilities tell me it's evil.

In summary:
  * the leaks created by try/mplus seem to be unavoidable as long as we
expose them
  * the leaks created by mplus do not seem to be noticeable, probably
because they are short lived in our parser
  * alterInput is evil
  * peekInput allows code that is even leakier than try

I would say that, as long as darcs isn't using more memory or being slower
that the new parser API is an improvement.

As for other libraries, these are the ones I know of:
  * parsec2 and parsec3
  * parsimony
  * attoparsec
  * uu parser lib (I don't think we can use this based on a comment by the
author on Haskell-Cafe)

Happy and alex could potentially apply, but it seems that our consumption of
whitespace and our token sets seem to vary depending on where we are in the
input stream.  We may also lose control over knowing if we have back
tracking in our parser.

One of the things I wanted to accomplish by refactoring the parser is the
ability when parsing from files to track how much of the input has been
consumed and be able to later re-open the file and seek back to that point
in the stream and start reading again from there.  Granted, I don't know
which of the above parser libraries actually support this.  I know
attoparsec does not support it.  I may need to implement that in the parser
we use instead of using an existing library.  Implementing it is easier if
alterInput doesn't exist.  I should say, with uncontrolled use of alterInput
I don't know how I would implement it.  I suspect it wouldn't be possible.

Jason

Attachments

• unnamed

Latest iteration of this patch bundle.  Most notabe change is the
removal of try.  The other additions are clean ups really.  Some of
those clean ups reduce the amount of packing/unpacking which I hope to
have some performance impact but not likely to be noticable.

I've also updated the benchmarks.  They are no longer suspect and they
were created on a ramdisk to reduce disk IO wait times (which on the
mac seem to be excessive).

http://wiki.darcs.net/Benchmarks/ParserRefactor

Thanks,
Jason

16 patches for repository http://darcs.net:

Sun Jul 25 01:56:10 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * tune the patch parser
  This patch is based on a few observations:
    * alterInput (const foo), completly replaces the parser's input
    * after peekInput, the above trick avoids redundant processing
    * best to leave a packed ByteString packed

Sun Jul 25 05:06:51 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * add utility functions to ReadMonads
  The intention of these functions is that in the future we will be able
  to use more conventional notation to express parsers in the darcs source.

Sun Jul 25 06:31:32 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read and ReadMonads to remove peekInput from Read

Sun Jul 25 06:56:58 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Patchy to not use peekInput

Sun Jul 25 07:16:05 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * remove peekInput from Real.  peekInput no longer exported from ReadMonads

Sun Jul 25 07:18:55 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * cleanup import list of Patchy

Sun Jul 25 07:29:11 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports alterInput and clean up a few warnings

Sun Jul 25 07:44:03 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read to use myLex'

Sun Jul 25 07:46:18 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports myLex, clean up imports in Real

Sun Jul 25 09:33:59 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * refactor Read to not rely on 'work'

Sun Jul 25 10:51:20 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * ReadMonads no longer exports maybeWork fix other modules to match

Sat Aug  7 08:34:21 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * remove all uses of try from parser code

Sat Aug  7 09:01:48 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * micro optimizations to parser code
  These micro-optimizations should always be safe; prefering ByteString
  over String and reducing packing/unpacking.

Sat Aug  7 09:03:42 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * remove try combinator from ReadMonads

Sat Aug  7 09:05:42 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * fix conflict in Bundle

Sat Aug  7 09:08:37 PDT 2010  Jason Dagit <dagit@codersbase.com>
  * remove redundant imports in Patchy and Real

Attachments

• tune-the-patch-parser.dpatch
• unnamed

We discussed this on IRC. Conclusion is that we'll live with the mplus 
risk, especially given that it already exists in maybeWork. Jason will 
also put more effort into reversing the slowdowns in the benchmarks.

I've read the rest of the patches and am happy with them.

This patch bundle (with 16 patches) was just applied to the repository http://darcs.net/.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_.html#bundle-7bd53756258957825b8bddf1fe02dcd756358a5c

This patch bundle (with 11 patches) was just applied to the repository http://darcs.net/.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_.html#bundle-99f080fe3f9f285c5abf9e21e1fa219b854cdc7b

This patch bundle (with 11 patches) was just applied to the repository http://darcs.net/reviewed.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_reviewed.html#bundle-99f080fe3f9f285c5abf9e21e1fa219b854cdc7b

This patch bundle (with 16 patches) was just applied to the repository http://darcs.net/reviewed.
This message was brought to you by DarcsWatch
http://darcswatch.nomeata.de/repo_http:__darcs.net_reviewed.html#bundle-7bd53756258957825b8bddf1fe02dcd756358a5c