This issue is based on GaloisInc/cryptol#1274. The story is that we recently ported our cryptol language interpreter to use prettyprinter, but later we noticed a severe slowdown that occurs when we print a list of tuples of any significant length. Below is a minimized example based on our pretty-printing code.

import Prettyprinter
import Prettyprinter.Render.String

main :: IO ()
main = putStrLn (renderString (layoutSmart defaultLayoutOptions d))
  where d = fillSep (replicate 30 (sep [pretty "abc", pretty "xyz"]))

The above program takes about 7 seconds to run on my machine. The run-time is exponential in the length of the list passed to fillSep: Incrementing from 30 to 31 doubles the run-time. 33 takes about a minute.

The exponential slowdown seems to occur only with layoutSmart; layoutPretty prints this example quickly at any size.

I did not expect layoutSmart to have exponential worst case behavior, as I assumed that this would have been mentioned in the documentation if it was known to be the case.