<div dir="ltr">Hey Ben,<div><br></div><div>thanks for that. I didn’t realise I opened pretty much the Pandora’s box, hehe. I have now found (whilst reading Bartosz’s notes) the numerous tickets & discussions around the library, but what you say in this email neatly summarise the crux of the problem, as far as I could see. Rather than saying silly things, I would rather spend a bit of time reading everything that has been written by folks way smarter than me on the subject and get back to you folks later ;)</div><div><br></div><div>Alfredo</div></div><div class="gmail_extra"><br><div class="gmail_quote">On 18 April 2017 at 14:21, Ben Gamari <span dir="ltr"><<a href="mailto:ben@smart-cactus.org" target="_blank">ben@smart-cactus.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Alfredo Di Napoli <<a href="mailto:alfredo.dinapoli@gmail.com">alfredo.dinapoli@gmail.com</a>> writes:<br>
<br>
</span><div><div class="h5">> Hey Simon,<br>
><br>
> thanks for chiming in. I had the same suspect as well, and in fact my first<br>
> temptation was to use dlists to avoid costly concatenation (I guess a<br>
> Builder shares pretty much the same idea, which is avoid right-appends). I<br>
> eventually bailed out as that Pretty module had some functions like sepX or<br>
> fillNBE (I might be wrong, going by memory only here) which needed to<br>
> *inspect* the current [Doc] we were carrying around, and thus dlists<br>
> couldn’t accomplish this in O(1), but forcing it back to a list was<br>
> necessary. Am I right in thinking that using a Builder here will suffer the<br>
> same malady? Ideally I would like constant time for both appends, left<br>
> concat & inspection (as in pattern-matching inspection) but I don’t think<br>
> what I’m asking exists, at least not in its functional declination anyway ;)<br>
><br>
> That’s why I was thinking to give Deques (or more generally, Sequences) a<br>
> go: they don’t have O(1) appends but at least can be inspected in O(1).<br>
> Question has to be answered whether this will yield improvement or not,<br>
> which I guess depends upon the ratio of inspection / appending we do in the<br>
> pretty printing. In that case using dlists or builders might be better.<br>
> Last but not least, although the current implementation doesn’t backtrack<br>
> anyway, I’m wondering wether switching to a different representation for a<br>
> Doc (namely a huge function composition of Token(s), as described in the<br>
> paper) could be beneficial as well.<br>
><br>
> Do you guys have any opinions? Yesterday I extracted Pretty.hs from the<br>
> sourcetree and I’m now planning to produce a criterion benchmark and<br>
> compare different implementations, althought it’s a bit hard to predict the<br>
> real world usage as I don’t have access to a representative Doc document as<br>
> produced by GHC, so my benchs could be all ill-founded.<br>
><br>
</div></div>Note that GHC's `Pretty` module is just a slightly modified version of<br>
the `pretty` package. The differences are fairly minimal (although<br>
important for performance):<br>
<br>
 * It uses FastString in place of String, giving us fast `length` (in<br>
   <a href="https://ghc.haskell.org/trac/ghc/ticket/8809#comment:60" rel="noreferrer" target="_blank">https://ghc.haskell.org/trac/<wbr>ghc/ticket/8809#comment:60</a><br>
   I propose that we extend `pretty` with a typeclass for string types)<br>
<br>
 * GHC's variant still has a known stack overflow bug that was fixed<br>
   upstream. Unfortunately, compiler performance regressed when we<br>
   attempted to port upstream's patch (#10735)<br>
<br>
Ideally we would fix these and just use the `pretty` library itself.<br>
<br>
In addition to these issues, it would be quite helpful if `pretty`<br>
gained a special-case for the infinite band-width case (which is what we<br>
use in the code generator). The point here is that we should need to do<br>
no layout computation in the infinite band case: merely place line<br>
breaks precisely where the user asks. This should result in a noticeable<br>
improvement in code generation performance (IIRC Bartosz noted rather<br>
significant amounts of time spent pretty-printing assembler).<br>
<br>
Cheers,<br>
<br>
- Ben<br>
</blockquote></div><br></div>