Very interesting idea!

I think the big thing would be to measure it with GHC HEAD so you can see how effectively the sparks are being converted into threads.

Is there a package and test case somewhere we can try out?

At this point the parser is just a proof of concept. For those brave enough, however, I've put the code on github: http://github.com/akborder/HsMakefileParser/ The "test.mk" file provides some test cases. To get an input big enough to measure multiple thread performances, you can concatenate that file a few thousand times: the timings in my previous message were obtained parsing a 3000x concatenation (final size: 1.1 MB).

ekmett:

Hi Anakim,   Nice to see someone else working in this space.   I have also been working on a set of parallel parsing techniques, which can use small Parsec parsers for local context sensitivity.   See the second set of slides in http://comonad.com/reader/2009/ iteratees-parsec-and-monoid/ for an overview of how I'm doing something similar to feed Parsec independent chunks. Note that this approach bypasses the need for a separate sequential scan, which otherwise floods your cache, and lets you get closer to the performance limit imposed by Amdahl's law.   The code in the second set of slides can be adapted to your case: load everything into a lazy bytestring or fingertree of strict bytestrings, then for each strict bytestring chunk in parallel, scan it for the first newline, and then start an iteratee based parsec parser from that point. I use the iteratee based parsec parsers so that when I glue the partial parses together I can feed the unparsed data on the left side of the first newline in each chunk to the parser I'm joining on the left. I provide a monoid for the purpose of gluing together these partial parses, which encapsulates this behavior. 

You can get quite a long way by using bytestring-mmap and strict bytestrings. The first ensures your IO overhead will be low, and the second ensures you don't migrate work needlessly.

ekmett:

On Wed, Sep 9, 2009 at 12:16 PM, Don Stewart wrote:

ekmett: > Hi Anakim, >   > Nice to see someone else working in this space. >   > I have also been working on a set of parallel parsing techniques, which can use > small Parsec parsers for local context sensitivity. >   > See the second set of slides in http://comonad.com/reader/2009/ > iteratees-parsec-and-monoid/ for an overview of how I'm doing something similar > to feed Parsec independent chunks. Note that this approach bypasses the need > for a separate sequential scan, which otherwise floods your cache, and lets you > get closer to the performance limit imposed by Amdahl's law. >   > The code in the second set of slides can be adapted to your case: load > everything into a lazy bytestring or fingertree of strict bytestrings, then for > each strict bytestring chunk in parallel, scan it for the first newline, and > then start an iteratee based parsec parser from that point. I use the iteratee > based parsec parsers so that when I glue the partial parses together I can feed > the unparsed data on the left side of the first newline in each chunk to the > parser I'm joining on the left. I provide a monoid for the purpose of gluing > together these partial parses, which encapsulates this behavior. 

You can get quite a long way by using bytestring-mmap and strict bytestrings. The first ensures your IO overhead will be low, and the second ensures you don't migrate work needlessly.

  I'm actually using bytestring-mmap in a toy compiler which uses these techniques, though at present I'm using System.IO.Posix.MMap.Lazy rather than the strict version.   As for migrating work, maybe I'm not understanding your point, but my whole goal was to migrate the chunking and parsing out to other cores, so the behavior of parMap rwhnf'ing the monoidal reduction over the chunks seems to be exactly what I want. I could perhaps get better results by trying to assign the same thread contiguous ranges of the input though, and controlling the choice of core used to merge chunks more intelligently by maybe doing something like mixing up pseq and par to group runs onto the same core where possible.  

Oh, I just find strict structures easier when determining in which thread work is happening. Appropriate use of rnf and friends is also fine. -- Don

Actually you can still do the same trick, you just need a smarter delimiter -- ironically the same one I use in Kata. ;) Look for non-backslashed newlines rather than newlines in general and start there. You need a little bit of book-keeping in case a backslash and newline straddle the chunk boundary but it bundles up and gets hidden from you by the monoid. As for the triple quoting or mixed mode languages, I have three options that I've explored: 1.) I have a set of parser combinators that I've been working on that parse fully monoidally, which are sufficient for context-free attribute grammars which can tackle that problem head on. But you give up the monadic sugar that makes parsec so syntactically sweet. (Though I need to change its name since another project named parsimony just appeared on hackage!) 2.) You can define a reversible lexer, whereby given a list of tokens you can generate the original input string, but then you spend a lot of time gluing string fragments together when you started with a perfectly good bytestring. 3.) My favorite option, using the iteratee backed parsec parser from the post you can 'slice' the input bytestring between two cursor positions efficiently. When you start parsing in a superposition of states and the only marker flips your mode rather than cleanly starts or starts it, especially when one is boring like a triple quoted string, just mark the location of the start of your lexer, and maintain two token lists, flipping their roles at each transition. All you wind up doing is grabbing a few extra bytestring slices and lexing the body of your string using the general purpose lexer just in case. Nicely if you have edge cases that cannot occur in one sublanguage or the other, then you can use that to collapse out of the superposition of states into a single state. I'm using this approach for parsing CDATA sections in XML monoidally, which has the same issue. -Edward Kmett On Wed, Sep 9, 2009 at 3:58 PM, Anakim Border wrote:

Hi Edward,

I read your slides a few weeks ago when they were posted on Reddit and found your approach very interesting. In fact it provided the inspiration for the parser I've written.

I did not use the same strategy, however, because parsing makefiles poses its own challenges. The make syntax is actually the union of two different languages, one for defining targets and one for commands. It's easy to identify commands following target definitions (they belong to lines starting with a tab), but if you jump to the middle of a makefile you can't decide, for example, if you are inside a define block (that should be parsed like a command) because the lines in its body are not marked by any specific prefix. Thus the need for a sequential scan. All this may seem rather involved and specific to an unusual format, but one encounters the same problem when parsing here-documents in shell scripts or multi line (triple-quoted) comments in Python.

The cache trashing effect you mention is certainly an issue I did not foresee. I guess a possible solution would be to base parMap on different 'par' primitive; one that sparks a number of computations equal to the number of available OS threads and then blocks until at least one of them is done.

-- AB