<br><br>
<div class="gmail_quote">On Wed, Sep 9, 2009 at 12:16 PM, Don Stewart <span dir="ltr">&lt;<a href="mailto:dons@galois.com">dons@galois.com</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid">ekmett:<br>
<div class="im">&gt; Hi Anakim,<br>&gt;  <br>&gt; Nice to see someone else working in this space.<br>&gt;  <br>&gt; I have also been working on a set of parallel parsing techniques, which can use<br>&gt; small Parsec parsers for local context sensitivity.<br>
&gt;  <br>&gt; See the second set of slides in <a href="http://comonad.com/reader/2009/" target="_blank">http://comonad.com/reader/2009/</a><br>&gt; iteratees-parsec-and-monoid/ for an overview of how I&#39;m doing something similar<br>
&gt; to feed Parsec independent chunks. Note that this approach bypasses the need<br>&gt; for a separate sequential scan, which otherwise floods your cache, and lets you<br>&gt; get closer to the performance limit imposed by Amdahl&#39;s law.<br>
&gt;  <br>&gt; The code in the second set of slides can be adapted to your case: load<br>&gt; everything into a lazy bytestring or fingertree of strict bytestrings, then for<br>&gt; each strict bytestring chunk in parallel, scan it for the first newline, and<br>
&gt; then start an iteratee based parsec parser from that point. I use the iteratee<br>&gt; based parsec parsers so that when I glue the partial parses together I can feed<br>&gt; the unparsed data on the left side of the first newline in each chunk to the<br>
&gt; parser I&#39;m joining on the left. I provide a monoid for the purpose of gluing<br>&gt; together these partial parses, which encapsulates this behavior. <br><br></div>You can get quite a long way by using bytestring-mmap and strict<br>
bytestrings. The first ensures your IO overhead will be low, and the<br>second ensures you don&#39;t migrate work needlessly.</blockquote></div>
<div style="TEXT-ALIGN: left"> </div>
<div style="TEXT-ALIGN: left">I&#39;m actually using bytestring-mmap in a toy compiler which uses these techniques, though at present I&#39;m using <font face="courier new,monospace">System.IO.Posix.MMap.Lazy<font face="arial,helvetica,sans-serif"> rather than the strict version.</font></font></div>

<div style="TEXT-ALIGN: left"><font face="courier new,monospace"><font face="arial,helvetica,sans-serif"></font></font> </div>
<div style="TEXT-ALIGN: left"><font face="courier new,monospace"><font face="arial,helvetica,sans-serif">As for migrating work, maybe I&#39;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&#39;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. </font></font></div>

<div style="TEXT-ALIGN: left"> </div>
<div style="TEXT-ALIGN: left"><font face="courier new,monospace"><font face="arial,helvetica,sans-serif">Could you elaborate?</font></font></div>
<div style="TEXT-ALIGN: left"> </div>
<div style="TEXT-ALIGN: left"><font face="courier new,monospace">-Edward</font></div>