haskell-prettyprinter / haskell-prettyprinter/prettyprinter
Exponential runtime for layoutSmart + fillSep + sep
- Dominant language
- Haskell
- Stars
- 309
- Forks
- 43
- Avg merge
- 21h 25m
- Merged PRs (30d)
- 1
Description
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.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.